Computer Science
AVL Tree
AVL tree is a self-balancing binary search tree that maintains a balance factor for each node. The balance factor is the difference between the heights of the left and right subtrees. AVL trees are named after their inventors, Adelson-Velsky and Landis.
Written by Perlego with AI-assistance
Related key terms
8 Key excerpts on "AVL Tree"
eBook - ePubQuick Reference to Data Structures and Computer Algorithms, A
An Insight on the Beauty of Blockchain
- Divya Joseph(Author)
- 2019(Publication Date)
- BPB Publications(Publisher)
Now suppose we want to search the key 30 then first it will be compared with 100 then it will go to the left subtree, then it will compare with 30 and it will go to the left subtree. Now it’s in leaf node and it will find 30 and will get the record pointed by the key 30. Now it can traverse sequentially in another leaf node also. So, it is getting property to traverse sequentially all the keys.4.15 AVL Tree (Height Balanced Binary Trees)
Adelson-Velskii and Landis in 1962 introduced a binary tree structure that is balanced with respect to the height of sub trees. Because of this balance nature, dynamic retrievals can be performed in 0(log n) time. Also, a new identifier can be entered or deleted from such a tree in time 0(log n). The resulting tree remains height balanced. The tree introduced by them is given the name AVL-Tree.Definition: An empty tree is height balanced. If T is a not an empty binary tree with TL and TR as its left and right sub trees, then T is height balanced if:
In an AVL Tree, height of left and right sub tree of any node will be with maximum difference of one and it is basically a binary search tree.1. TL and TR are height balanced and 2. |hL -hR | ≤ 1, where hL and hR are the heights of TL and TR respectively In an AVL Tree, each node has a balance factor (B.F). The difference found between the height of left subtree of a particular node and right subtree of a node,Balance factor of a node = Height of left subtree – Height of right subtreeis known as the balance factor of a node.For a particular node, when the height of its right subtree is one more than height of its left subtree, then such node is called as right heavy or right high. A node is called left heavy or left high if its left subtree is one more than height of its right subtree.A node is called balanced if the height of right and left subtree is equal. The balance factor will be 1 for left height, -1 for right high and 0 for balanced node. So in an AVL Tree, each node can have only 3 values of balance factor which are -1, 0, 1. Example. of AVL Trees.Example of BST but not AVL Tree.4.15.1 Insertion in AVL Tree
Insertion in AVL Tree is same as insertion in B.S.T. Here also we will search for the position where the new node is to be inserted and then insert the node. But AVL Tree has a property that the height of left and right subtree will be with maximum difference of 1. Suppose after inserting new node, this difference becomes more than one. In this condition, we have to restore the property of AVL Tree again. To restore the property of AVL Tree, we should convert the tree in such a way that:
eBook - ePubData Structures Through C++
Experience Data Structures C++ through animations
- Yashavant Kanetkar(Author)
- 2020(Publication Date)
- BPB Publications(Publisher)
right is a thread. When we reach a link we go to the right child and again follow the same procedure by checking its left sub-tree.As we follow these steps we are sometimes likely to reach the head node, and that is the time to stop the procedure.AVL Trees
We know that height of a BST is the maximum number of edges from leaf node to root node. Note that if we change the order of insertion of nodes in a BST, we may get BSTs of different heights. As a confirmation, you may try creating two BSTs using the insertion order as 30, 40, 10, 50, 20, 5, 35 and 50, 40, 35, 30, 20, 10, 5. In the first case you would get a BST of height 2 and in the second case a BST of height 6.Also, search time in a BST depends upon its height. Searching is efficient if the heights of both left and right sub-trees of any node are equal. However, frequent insertions and deletions in a BST are likely to make it unbalanced. The efficiency of searching is ideal if the difference between the heights of left and right sub-trees of all the nodes in a BST is at the most one. Such a binary search tree is called a Balanced BST . It was invented in the year 1962 by two Russian mathematicians—G. M. Adelson-Velskii and E. M. Landis. Hence such trees are also known as AVL Trees. Figure 7-15 shows some examples of AVL Trees.Figure 7-15. AVL Trees.The balance factor of a node is calculated as height of the left sub-tree minus height of the right sub-tree of the node. The balance factor of any node in an AVL BST should be -1, 0 or 1. If it is other than these three values then the tree is not balanced.To re-balance and make it an AVL Tree the nodes need to be properly adjusted. This is done by doing one of the 4 types of rotations—Left rotation, Right rotation, Left Right rotation and Right Left rotation. Of these, first two involve a 1 step process, whereas the next two involve a 2 step process.
eBook - ePubData Structures using C
A Practical Approach for Beginners
- Amol M. Jagtap, Ajit S. Mali(Authors)
- 2021(Publication Date)
- Chapman and Hall/CRC(Publisher)
balance factor. The AVL Tree was initiated in the year 1962 by G.M. Ade’son-Ve’skii and E.M. Landis in their honor’s height balanced BST is termed as AVL Tree. In the complete balanced tree, left and right sub-trees of any node would have the same height. Every AVL Tree is a BST, but all the BSTs need not to be AVL Trees.5.9.2 Definition
An empty tree is height-balanced, if T is a non-empty BST with TL and TR as its left and right sub-tree, then T is height-balanced if,- TL and TR are height-balanced and
- | hL - hR | <= 1.
where hL and hR are the heights of TL and TR , respectively.An AVL Tree is a balanced BST. In an AVL Tree, the balance factor of every node is either −1, 0 or +1.The balance factor of a node is the difference between the heights of the left and right sub-trees of that node. The height of the left sub-tree – height of the right sub-tree or height of the right sub-tree – height of the left sub-tree is used to compute the balancing factor of a node. In the following explanation, we calculate as follows:Balance factor (T) = height of left sub-tree – height of right sub-tree where T is a binary tree. BF (T) = −1, 0, 1.If AVL Tree’s balance factor is exceeding the value 1 for any of the nodes, then rebalancing has to be taken place. After each insertion and deletion of items, if the balance factor of any node exceeds value 1, then rebalancing of the tree is carried out by using different rotations. These rotations are characterized by the nearest ancestor of the newly inserted node whose balance factor becomes +2 or −2.5.9.3 AVL Tree Rotations
In the AVL Tree, after each operation such as inserting and deleting, we have to check the balance factor of each node in the tree. If each node fulfills the balance factor condition, then we conclude the operation; otherwise, we must make it balanced. We use rotation operations to balance the tree every time the tree becomes unbalanced because of any operation.
eBook - ePubData Structures Through C
Learn the fundamentals of Data Structures through C
- Yashavant Kanetkar(Author)
- 2020(Publication Date)
- BPB Publications(Publisher)
rightflag is a thread. When we reach a link we go to the right child and again follow the same procedure by checking its left sub-tree.As we follow these steps we are sometimes likely to reach the head node, and that is the time to stop the procedure.AVL Trees
We know that height of a BST is the maximum number of edges from leaf node to root node. Note that if we change the order of insertion of nodes in a BST, we may get BSTs of different heights. As a confirmation, you may try creating two BSTs using the insertion order as 30, 40, 10, 50, 20, 5, 35 and 50, 40, 35, 30, 20, 10, 5. In the first case you would get a BST of height 2 and in the second case a BST of height 6.Also, search time in a BST depends upon its height. Searching is efficient if the heights of both left and right sub-trees of any node are equal. However, frequent insertions and deletions in a BST are likely to make it unbalanced. The efficiency of searching is ideal if the difference between the heights of left and right sub-trees of all the nodes in a BST is at the most one. Such a binary search tree is called a Balanced BST . It was invented in the year 1962 by two Russian mathematicians—G. M. Adelson-Velskii and E. M. Landis. Hence such trees are also known as AVL Trees. Figure 7-15 shows some examples of AVL Trees.Figure 7-15. AVL Trees.The balance factor of a node is calculated as height of the left sub-tree minus height of the right sub-tree of the node. The balance factor of any node in an AVL BST should be -1, 0 or 1. If it is other than these three values then the tree is not balanced.To re-balance and make it an AVL Tree the nodes need to be properly adjusted. This is done by doing one of the 4 types of rotations—Left rotation, Right rotation, Left Right rotation and Right Left rotation. Of these, first two involve a 1 step process, whereas the next two involve a 2 step process.
- Clifford A. Shaffer(Author)
- 2012(Publication Date)
- Dover Publications(Publisher)
A different approach to improving the performance of the BST is to not require that the tree always be balanced, but rather to expend some effort toward making the BST more balanced every time it is accessed. This is a little like the idea of path compression used by the UNION/FIND algorithm presented in Section 6.2. One example of such a compromise is called the splay tree. The splay tree is described in Section 13.2.2.Figure 13.4 Example of an insert operation that violates the AVL Tree balance property. Prior to the insert operation, all nodes of the tree are balanced (i.e., the depths of the left and right subtrees for every node differ by at most one). After inserting the node with value 5, the nodes with values 7 and 24 are no longer balanced.13.2.1 The AVL Tree
The AVL Tree (named for its inventors Adelson-Velskii and Landis) should be viewed as a BST with the following additional property: For every node, the heights of its left and right subtrees differ by at most 1. As long as the tree maintains this property, if the tree contains n nodes, then it has a depth of at most O(log n ). As a result, search for any node will cost O(log n ), and if the updates can be done in time proportional to the depth of the node inserted or deleted, then updates will also cost O(log n ), even in the worst case.The key to making the AVL Tree work is to alter the insert and delete routines so as to maintain the balance property. Of course, to be practical, we must be able to implement the revised update routines in Θ(log n ) time.Consider what happens when we insert a node with key value 5, as shown in Figure 13.4 . The tree on the left meets the AVL Tree balance requirements. After the insertion, two nodes no longer meet the requirements. Because the original tree met the balance requirement, nodes in the new tree can only be unbalanced by a difference of at most 2 in the subtrees. For the bottommost unbalanced node, call it S
- Clifford A. Shaffer(Author)
- 2012(Publication Date)
- Dover Publications(Publisher)
A different approach to improving the performance of the BST is to not require that the tree always be balanced, but rather to expend some effort toward making the BST more balanced every time it is accessed. This is a little like the idea of path compression used by the UNION/FIND algorithm presented in Section 6.2. One example of such a compromise is called the splay tree. The splay tree is described in Section 13.2.2.Figure 13.4 Example of an insert operation that violates the AVL Tree balance property. Prior to the insert operation, all nodes of the tree are balanced (i.e., the depths of the left and right subtrees for every node differ by at most one). After inserting the node with value 5, the nodes with values 7 and 24 are no longer balanced.13.2.1 The AVL Tree
The AVL Tree (named for its inventors Adelson-Velskii and Landis) should be viewed as a BST with the following additional property: For every node, the heights of its left and right subtrees differ by at most 1. As long as the tree maintains this property, if the tree contains n nodes, then it has a depth of at most O(log n ). As a result, search for any node will cost O(log n ), and if the updates can be done in time proportional to the depth of the node inserted or deleted, then updates will also cost O(log n ), even in the worst case.The key to making the AVL Tree work is to alter the insert and delete routines so as to maintain the balance property. Of course, to be practical, we must be able to implement the revised update routines in Θ (log n ) time.Consider what happens when we insert a node with key value 5, as shown in Figure 13.4 . The tree on the left meets the AVL Tree balance requirements. After the insertion, two nodes no longer meet the requirements. Because the original tree met the balance requirement, nodes in the new tree can only be unbalanced by a difference of at most 2 in the subtrees. For the bottommost unbalanced node, call it S
eBook - ePub- Erik Azar, Mario Eguiluz Alebicto(Authors)
- 2016(Publication Date)
- Packt Publishing(Publisher)
-1,1 ], as expected.Now that we now how to rebalance the AVL Tree with these for techniques (two simple rotations and two double rotations), let's finish the content of AVL Trees explaining the search and insertion process.Search in the AVL Trees is the same as in a binary search tree. There is no difference when trying to search for a specific node in terms of methodology.Search
Insertion
However, the insertion process is more complicated. AVL Trees are strictly balanced trees, and inserting a new node can break that balance. Once we put the new node in the correct subtree, we need to ensure that the balance factors of its ancestors are correct. This process is called retracing . If there is any balance factor with wrong values (not in the range [-1 , 1 ]), we will use rotations to fix it.Let's see what the process looks like at a high level:- We insert the new node Z , in a valid AVL Tree, so all the balance factors are in the range [-1, 1 ].
- We are going to add node Z into a subtree of node X .
- We go from the bottom of the tree to the subtree, checking the balance factors. If some of them are incorrect, we are going to perform rotations to fix them. Then, we go up again until the balance factors are equal to 0 or until reaching the root.
Passage contains an image Trie tree
Until now, we have seen different types of trees, such as binary trees, binary search trees, red-black trees, and AVL Trees. In all these types of tree, the content of a node (a value or a key) is not related to the content of a previous node. A single node has a complete meaning, such as a value or number by itself.But in some scenarios in real life, we need to store a series of data in which those values have common parts; think of it as the suffixes or prefixes in related words, in the alphabet, in a telephone directory.Here is where a trie tree shines. They are ordered data structures where edges contain part of a key and its descendant nodes have common share part of the previous values. Check this example out:
eBook - ePubData Structures and Algorithms Implementation Through C
Let's Learn and Apply
- Brijesh Bakariya(Author)
- 2018(Publication Date)
- BPB Publications(Publisher)
The drawback of Binary search Tree (BST) is that if our BST is skewed then the worst case searching time is O(n) rather than Log(n). In this example we take two types of skewed tree.Fig. 10.20: Left skewed binary search treeFig. 10.21: Right skewed binary search treeIn the above left and right skewed binary search tree, the searching element 50 or 10 will take O(n) time because it will have to scan n number of time. Both the trees are unbalanced that is why it will take linear time rather than logarithmic time. The AVL Tree overcomes these types of problems.There are following properties about AVL Tree.- Searching BST is efficient when height of both left and right subtree is equal.
- If height of both left and right subtree is not equal then it takes more time to insert and delete element.
- Searching of element is fast when our left subtree and right subtree are balanced.
- That tree is called balance binary tree.
10.14 Balance Factor
Balance Factor (BF) is the difference between height of Left Subtree (LST) and height of Right Subtree (RST). Balance Factor = Mod [Height (LST) - Height (RST)] Moreover a Binary Search Tree is said to be AVL Tree if and only if every node has the balance factor 0 or 1. Let's take an example for calculating a balance factorFig. 10.22: Balance FactorMoreover a Binary Search Tree is said to be AVL Tree if and only if every node of the tree has balance factor 0 or 1. Let's take an example for calculating a balance factorFig. 10.23: Example of binary search treeIn the above tree the Balance Factor (BF) of 1. Balance Factor (1) = Mod [Height (LST of 1) - Height (RST of 1)] then Balance Factor (1) = Mod [0 - 2] = 2 that means the above tree is not balance. Similarly BF (2) = Mod [Height (LST of 2) - Height (RST of 2)] = Mod [0-1] =1. BF (3) = = Mod [Height (LST of 3) - Height (RST of 3)] = Mod [0-0] =0. Finally, the above tree is not balance because the balance factor of 1 is 2. There are following trees with balance factors.Tree 1
Fig. 10.24: Tree with Balance FactorTree 2
Fig. 10.25: Tree with Balance FactorTree 3
Fig. 10.26: Tree with Balance FactorTree 4
Fig. 10.27:
Learn about this page
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
