AVL Tree

5 Key excerpts on "AVL Tree"

• 

  eBook - ePub

  Data 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.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Data 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.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Data Structures and Algorithm Analysis in C++, Third Edition

  • 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

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Data Structures and Algorithm Analysis in Java, Third Edition

  • 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

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Swift Data Structure and Algorithms

  • 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

  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.

  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:

  Sign up to read

  Learn more about book