AVL TreesBinary Search TreeAVL Tree (Adelson-Velskii & Landis)Adding/deleteing node from AVL TreeSingle rotation (When the problem happens in “A”)Single rotation Single rotation (When the problem happens in “C”)Single RotationSingle rotationSingle Rotation Doesn’t Work in Some CasesSlide 10Double RotationSlide 121AVL Trees53 71 2 82Binary Search TreeBinary search tree, using simple insert and delete proceduresthe tree is nearly balance add - fast O(log n)delete a target - fast O(log n)search - fast O(log n)the tree is highly unbalance, it becomes a singly linked list (the worst case)add, delete and search - slow O(n) effectively using sequential search to find a location3AVL Tree (Adelson-Velskii & Landis)AVL Tree are BST with an additional balance condition to ensure the depth of the tree is O(log2N)Balance Condition: for any node in the tree, the height of the left and right subtrees can differ by at most 1.Must ensure that after insertion and deletion of a node, the balance condition is preserved4Adding/deleteing node from AVL Tree* Add a node connected to some node?* Delete some node?After an insertion, the nodes on the path from the insertionpoint to the root can have their balances altered.Rotation restores local balance5Single rotation (When the problem happens in “A”)k2k1ABCk1k2AB C6Single rotation Single rotation (When the problem happens in “C”)k2k1ABCk1k2A BC7Single RotationyB CxA354 76 9218xBAyC3547692188Single rotationPerform Single Rotation on K2Node *k1 = K2 -> left;K2 -> left = K1 -> RightK1 -> right = K2K2 = K1k2k1ABCk1k2AB C9Single Rotation Doesn’t Work in Some CasesHowever, when the problem happens in “B”…10Single Rotation Doesn’t Work in Some Cases354 86 921735486921711Double RotationyDxAzB CyDxAzB C354 86 921735468921712Double RotationPerform Double rotation on X=Perform Single Rotation on Y + Perform Single Rotation on X yDxAzB
View Full Document