Nội dung

AVL Tree DEFINITION: AVL Tree is: • A Binary Search Tree, • in which the heights of the left and right subtrees of the root differ by at most 1, and • the left and right subtrees are again AVL trees. 1 AVL Tree The name comes from the discoverers of this method, G.M.Adel'son-Vel'skii and E.M.Landis. The method dates from 1962. 2 Balance factor Balance factor: • left_higher: HL = HR + 1 • equal_height: HL = HR • right_higher: HR = HL + 1 (HL , HR : the height of left and right subtree) In C++: enum Balance_factor {left_higher, equal_height, right_higher}; 3 AVL Trees and non-AVL Trees AVL trees non-AVL trees 4 Linked AVL Tree AVL_Node data left right balance End AVL_Node AVL_Tree root End AVL_Tree 5 Insertion into an AVL tree 6 Insertion into an AVL tree  Follow the usual BST insertion algorithm: insert the new node into the empty left or right subtree of a parent node as appropriate.  We use a reference parameter taller of the recursive_Insert function to show if the height of a subtree, for which the recursive function is called, has been increased.  At the stopping case of recursive, the empty subtree becomes a tree with one node for new data, taller is set to TRUE. 7 Insertion into an AVL tree Consider the subtree, for which the recursive function is called,  While taller is TRUE, for each node on the path from the subtree's parent to the root of the tree, do the following steps. a) If the subtree was the shorter: its parent's balance factor must be changed, but the height of parent tree is unchanged. taller becomes FALSE. b) If two subtree had the same height, its parent's balance factor must be changed, the height of parent tree increases by 1. taller remains TRUE. c) If the subtree was the higher subtree: only in this case, the definition of AVL is violated at the parent node, rebalancing must be done. taller becomes FALSE HL \ - - HL / HL / // 8 Insertion into an AVL tree  When taller becomes FALSE, the algorithm terminates.  When rebalancing must be done, the height of the subtree always returned to its original value, so taller always becomes FALSE! 9 Insertion into an AVL tree 10