AVL (Adelson-Velskii and Landis scientists who found this tree) trees are balanced Binary search trees. All the operations like addition, deletion and searching in the worst case of O(log(n)).
What are AVL Trees: AVL trees are balanced binary search trees. A tree said to be balanced if the height of the left sub tree and right sub tree difference should be at most one at each node. i.e left sub tree and right sub tree difference should either 0, 1, -1.
Why AVL Trees: The problem with Binary Search Tree (BST) is that, if the given input values are in any sorted order(ascending or descending) the BST will be completely left or right as shown below. So Search will take worst case of O(n) where n is the no. of nodes in the BST.
From the above images it is very clear that , BST is not advisable to construct for sorted input values.
How to construct AVL Tree: Construction of AVL tree is same as Binary search tree, but the difference is after inserting the new node into the tree or deleting a node from the tree, again need to check each node for the balance. if the tree is not balanced, we need to re-structure or rebuild the tree for balancing using rotation.
Algorithm for AVL Tree:
Step1: Get the element to insert into the tree.
Step2: if the tree is empty, make the node as root node.
Step3: If the tree is not empty, traverse the tree until it reaches NULL in such a way that
if(element > node->element)
move node to node->right
else if(element < node->element)
move node to node->left
Step4: After inserting check for the height of the node in Tree
Step5: If any node is not balanced, find the rotation type.
Step6: After doing the rotation, adjust the new heights of the rotated nodes
Example of the AVL Tree: Below is the AVL tree which satisfies Binary search tree property at each node and the difference between left sub tree height and right sub tree height is at most 1.
Here is C Program for AVL trees.
What are AVL Trees: AVL trees are balanced binary search trees. A tree said to be balanced if the height of the left sub tree and right sub tree difference should be at most one at each node. i.e left sub tree and right sub tree difference should either 0, 1, -1.
Why AVL Trees: The problem with Binary Search Tree (BST) is that, if the given input values are in any sorted order(ascending or descending) the BST will be completely left or right as shown below. So Search will take worst case of O(n) where n is the no. of nodes in the BST.
 |
| Left skewed BST |
 |
| Right skewed BST |
From the above images it is very clear that , BST is not advisable to construct for sorted input values.
How to construct AVL Tree: Construction of AVL tree is same as Binary search tree, but the difference is after inserting the new node into the tree or deleting a node from the tree, again need to check each node for the balance. if the tree is not balanced, we need to re-structure or rebuild the tree for balancing using rotation.
Algorithm for AVL Tree:
Step1: Get the element to insert into the tree.
Step2: if the tree is empty, make the node as root node.
Step3: If the tree is not empty, traverse the tree until it reaches NULL in such a way that
if(element > node->element)
move node to node->right
else if(element < node->element)
move node to node->left
Step4: After inserting check for the height of the node in Tree
Step5: If any node is not balanced, find the rotation type.
Step6: After doing the rotation, adjust the new heights of the rotated nodes
Example of the AVL Tree: Below is the AVL tree which satisfies Binary search tree property at each node and the difference between left sub tree height and right sub tree height is at most 1.
 |
| AVL Tree |
No comments:
Post a Comment