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 rotationSlide 9Slide 10Slide 11Single Rotation Doesn’t Work in Some CasesSlide 13Slide 14Slide 15Double RotationTrySlide 181AVL 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 (the length of the path form the node to the deepest leaf) 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 Rotation354 76 92183547692188Single rotationPerform Single Rotation on K2Node *k1 = K2 -> left; //identify k1K2 -> left = K1 -> RightK1 -> right = K2K2 = K1k2k1ABCk1k2AB C9Single rotationExample: in BST, if we insert 1, 2, 3, 4, 5, 6 in order, we get a BST tree like:10Single rotationIn AVL tree, it would be:11Single rotationIn AVL tree, it would be:12Single Rotation Doesn’t Work in Some CasesHowever, when the problem happens in “B”…13Single Rotation Doesn’t Work in Some Cases k2k1ABCk2k1BAC14Single Rotation Doesn’t Work in Some Cases k2k1ABCk2k1ACB15Single Rotation Doesn’t Work in Some Cases354 86 921735486921716Double RotationyDxAzB CyDxAzB C354 86 921735468921717TryInsert 1, 2, 3, 4, 5, 3.518Double RotationPerform Double rotation on X=Perform Single Rotation on Y + Perform Single Rotation on X yDxAzB
View Full Document