********* AVL Trees ********* The classic binary search tree can be unbalanced, reducing the efficiency of the operations on it. .. figure:: ./img/unbalanced_tree.drawio.png :align: center | An AVL (Adelson-Velskii and Landis) tree is a binary search tree with a **balance condition**. We want to maintain a depth of :math:`O(\log N)`. We can enforce some conditions: 1. Requiring that the left subtree has the same depth as the right subtree. 2. Or requiring that every node must have the left and right subtree of the same height. With the first condition it is not enough, because we can obtain the following tree: .. figure:: ./img/FG_04_031.* :align: center | The second condition would work only for trees of :math:`2^k -1`, otherwise some nodes would be unbalanced. So this condition is too restrictive. **So what are the conditions of the AVL trees?** AVL tree In AVL trees, for every node in the tree, the height of the left and right subtrees can differ by at most 1. .. note:: The height of an empty tree is defined to be -1. The following figure illustrates the difference between an AVL tree and a binary search tree: .. figure:: ./img/FG_04_032.* :align: center The tree on left is an AVL tree, not the other one. How does it work? ================= The height information is kept for each node (in the node structure). All the operations can be performed in :math:`O(\log N)`, with the exception of insertion and deletion. If we take the AVL tree in the previous figure and we try to insert 6, it would destroy the balance condition. .. figure:: ./img/avl_insert_6.drawio.png :align: center | In this case, the property has to be restored before the insertion step is considered over. To restore the property, we just need to do a **rotation**. After an insertion, only nodes that are on the path from the insertion point to the root might have their balance altered because only those nodes have their subtrees altered. .. figure:: ./img/avl_path_insert.drawio.png :align: center | Let us call the node that must be rebalanced :math:`\alpha`. Since any node has at most two children, and a height imbalance requires that :math:`\alpha`'s two subtrees' height differs by two, a violation might occur in four cases: 1. An insertion into the left subtree of the left child of :math:`\alpha`. 2. An insertion into the right subtree of the left child of :math:`\alpha`. 3. An insertion into the left subtree of the right child of :math:`\alpha`. 4. An insertion into the right subtree of the right child of :math:`\alpha`. .. admonition:: Activity :class: activity Which node is :math:`\alpha` in the previous example? And in which case, are we? Cases 1 and 4 are identical in theory, as are cases 2 and 3. For cases 1 and 4, the insertion occurs on the *"outside"* (left-left, right-right) and can be fixed by a **single rotation**. For cases 2 and 3, the insertion occurs on the *"inside"* (left-right, right-left) and need to be fixed using a **double rotation**. .. important:: These are fundamental operations! They will be used regularly, so they need to be efficient. Single Rotation =============== To illustrate the idea of a single rotation we will consider the following figure. .. figure:: ./img/FG_04_034.* :align: center | On the left we have an unbalanced tree after an insertion, and on the right we have the tree after the single rotation. In detail we have :math:`k_2`, for which the left subtree is two levels deeper than its right subtree. The node on the path of the unbalance is :math:`k_1`. The idea behind the rotation: * Imagine that the tree is flexible. * Grab the node on the path (:math:`k_1` in the example). * Shake it, and let the gravity take hold. The result will be that :math:`k_1` is the new root. The binary search tree property tells us that in the original tree :math:`k_2 > k_1`, so :math:`k_2` becomes the right child of :math:`k_1`. You can also see that :math:`X, Y` and :math:`Z` are still on the same side respectively to :math:`k_1` and :math:`k_2`. .. note:: We could have the symmetric case and it would not change the idea. .. figure:: ./img/FG_04_036.* :align: center .. admonition:: Example :class: example Taking back the example of inserting 6 into the AVL tree. .. figure:: ./img/avl_insert_6_rotation.drawio.png :align: center * The node containing 8 is unbalanced. * The node on the path is 7. * We rotate 7 and 8. * We obtain the new subtree with 7 as the root. .. admonition:: Activity :class: activity * Consider an empty AVL tree. * Now, consider the following insertion order: 3,2,1,4,5,6,7. * Draw the tree after each insertion with the corresponding rotations when necessary. .. admonition:: Solution :class: dropdown, example * Nothing happens until we try to insert 1. * When 1 is inserted, the tree becomes unbalanced, so we apply one rotation. .. figure:: ./img/rotation-activity-01.png :align: center * Then we insert 4. * When we insert 5, the tree becomes unbalanced. * We fix it with a rotation. .. figure:: ./img/rotation-activity-02.png :align: center * Then we insert 6. * The unbalance is at the node 2, so we take the first node on the path between 2 and 6. .. figure:: ./img/rotation-activity-03.png :align: center * Finally, we insert 7. * The node containing 5 becomes unbalanced. 6 is the node on the path, so we rotate 5 and 6. .. figure:: ./img/rotation-activity-04.png :align: center Double rotation =============== Using a simple rotation fix cases 1 and 4. However, it doesn't work for cases 2 and 3, as shown in the following figure. .. figure:: ./img/FG_04_037.* :align: center | The problem is that :math:`Y` is too deep and a single rotation does not make it any less deep. This is why we use a **double rotation**. Before using it, we need to consider one more node. We just inserted a new node in :math:`Y`, so it's not empty. We can consider it has a root and two subtrees. Consequently, the entire tree may be viewed as four subtrees connected by three nodes. On which we can apply the double rotation, as illustrated below. .. figure:: ./img/FG_04_038.* :align: center | One of the subtree (:math:`B` or :math:`C`) is deeper than :math:`D`, but we cannot be sure which one. In the end, it doesn't matter, both subtrees are drawn at :math:`1.5` levels below :math:`D`. **Ok, how do balance the tree?** Remember that a rotation between :math:`k_1` and :math:`k_3` doesn't work. So the only root possible is :math:`k_2`. It means that :math:`k_1` must be the left child of :math:`k_2`, and :math:`k_3` the right child. Then, we adjust the subtrees: * :math:`B` must be on the left of :math:`k_2`, so a child of :math:`k_1`. * :math:`C` must be on the right of :math:`k_2`, so a child of :math:`k_3`. Is is called a double rotation, because it is the same effect of rotating between :math:`\alpha`'s child and grandchild, and then between :math:`\alpha` and its new child. .. admonition:: Activity :class: activity * Take the tree the previous activity (the state after all the insertion). * Insert the following nodes: 16, 15, 14, 13, 12, 11, 10, 8, 9. * Draw each step with the corresponding single and double rotations. .. admonition:: Solution :class: dropdown, example * Adding 16 doesn't break the balancing. * However adding 15 does. You can see that 15 is in the interior, so we need to do a double rotation. * We rotate 16 and 15, then 15 and 7. .. figure:: ./img/rotation-activity-05.png :align: center * Next we insert 14, creating a balance issue at node 6. * We rotate first 7 and 15, then 7 and 6. .. figure:: ./img/rotation-activity-06.png :align: center * Now, we insert 13. * 13 is in the right subtree of the right subtree, so a single rotation is needed. .. figure:: ./img/rotation-activity-07.png :align: center * After inserting 12, we need to balance the tree. * If you look at it, 12 is in a left-left subtree, so only one rotation is needed. .. figure:: ./img/rotation-activity-08.png :align: center * Inserting 11, and 10 ask for a single rotation each time. * Inserting 8 doesn't require any rotation. .. figure:: ./img/rotation-activity-09.png :align: center * However inserting 9 makes the tree unbalanced again, since 9 is between 10 and 8. * We perform a double rotation. * We roatate 8 and 9, then between 9 and 10. .. figure:: ./img/rotation-activity-10.png :align: center The theory should be clear by now, so we can move to the implementation details. Implementation of the AVL ADT ============================= The implementation details are straightforward except that there are several cases. Classes ------- **AVL node** The class representing a node is similar to the one for the binary search tree, but we had the balancing in it. .. literalinclude:: ./AVLTree.java :language: java :linenos: :lines: 10-45 As you can see, we inherit from :code:`Node`, so we don't need to redefine everything. One more thing, we optimize the type of height and just maintain if one subtree is unbalanced with -1, +1 or 0 if it's balanced. However, it complicates the code. **AVL Tree** For the tree the public interface is the same. In the end what changes is the balancing of the binary tree search. Something that the user will not need to use directly, so it will be in the private part of the class. .. literalinclude:: ./AVLTree.java :language: java :linenos: :lines: 3-8, 47-49, 205 Insertion --------- To insert a new node containing :math:`X` into the tree :math:`T`: .. figure:: ./img/insertion_algorithm.png :align: center | Insert ****** We will optimize the code of the AVl tree, but we will try to make it readable. We will consider the following functions: * The :code:`add` function * The :code:`rebalanceLeft` function * The :code:`rebalanceRight` function The :code:`add` one is identical to the one in the binary tree search, except for the private one in which we need to launch the :code:`rebalanceLeft` or :code:`rebalanceRight` after the insertion. .. literalinclude:: ./AVLTree.java :language: java :linenos: :lines: 66-105 :emphasize-lines: 22, 25, 32, 35 This way the balancing will be done at each level, if necessary. Note that we are using two functions :code:`decrementBalance(localRoot);` and :code:`incrementBalance(localRoot);`. Indeed we need to update the balance of each node on the path to the root or until a rebalance is done. .. literalinclude:: ./AVLTree.java :language: java :linenos: :lines: 180-203 Balance ******* We need to consider different cases: * The difference between the left subtree and the right subtree is greater than 1. * Check if the depth is greater on the exterior (left-left) * Simple rotation on the left. * Otherwise, double rotation on the left. * Otherwise, check the difference between the right subtree and the left subtree is greater than 1. * Check if the depth is greater on the exterior (right-right). * Simple rotation on the right. * Otherwise double rotation on the right. We will use 2 private methods for the rotations: .. literalinclude:: ./AVLTree.java :language: java :linenos: :lines: 107-112, 141, 143-148, 178 The first one :code:`rebalanceLeft` can be written as: .. literalinclude:: ./AVLTree.java :language: java :linenos: :lines: 107-141, 143-148, 178 .. admonition:: Activity :class: activity * Implement the :code:`rebalanceRight` method. .. literalinclude:: ./AVLTree.java :language: java :linenos: :lines: 143-148, 178 **Rotations** As you can see we need to define the two rotation functions: * :code:`rotateLeft` * :code:`rotateRight` Starting with :code:`rotateLeft`. The following figure illustrates the idea. .. figure:: ./img/implementation_rotate_left.drawio.png :align: center Which is very simple to implement: .. literalinclude:: ./BinarySearchTreeWithRotate.java :language: java :linenos: :lines: 28-43 .. admonition:: Activity :class: activity * Implement :code:`rotateRight` * It's the symmetric function: .. figure:: ./img/implementation_rotate_right.drawio.png :align: center Deletion -------- We didn't talk about removing a node. Again it is the same as for the binary tree search, but we need to balance the tree after each deletion. .. .. literalinclude:: ../code/topic4/AvlTree.cpp .. :language: cpp .. :linenos: .. :lines: 160-188 .. :emphasize-lines: 28 Other operations ---------------- Everything else is exactly the same as in the binary tree search ADT. And it should not surprise you. The AVL Tree is just a self-balancing BST, nothing more, nothing less.