AVL Trees.ppt

1、AVL Trees,CSE 373 Data Structures Lecture 8,12/26/03,AVL Trees - Lecture 8,2,Readings,Reading Section 4.4,12/26/03,AVL Trees - Lecture 8,3,Binary Search Tree - Best Time,All BST operations are O(d), where d is tree depth minimum d is for a binary tree with N nodes What is the best case tree? What is

2、 the worst case tree? So, best case running time of BST operations is O(log N),12/26/03,AVL Trees - Lecture 8,4,Binary Search Tree - Worst Time,Worst case running time is O(N) What happens when you Insert elements in ascending order? Insert: 2, 4, 6, 8, 10, 12 into an empty BST Problem: Lack of “bal

3、ance”: compare depths of left and right subtree Unbalanced degenerate tree,12/26/03,AVL Trees - Lecture 8,5,Balanced and unbalanced BST,4,2,5,1,3,1,5,2,4,3,7,6,4,2,6,5,7,1,3,Is this “balanced”?,12/26/03,AVL Trees - Lecture 8,6,Approaches to balancing trees,Dont balance May end up with some nodes ver

4、y deep Strict balance The tree must always be balanced perfectly Pretty good balance Only allow a little out of balance Adjust on access Self-adjusting,12/26/03,AVL Trees - Lecture 8,7,Balancing Binary Search Trees,Many algorithms exist for keeping binary search trees balanced Adelson-Velskii and La

5、ndis (AVL) trees (height-balanced trees) Splay trees and other self-adjusting trees B-trees and other multiway search trees,12/26/03,AVL Trees - Lecture 8,8,Perfect Balance,Want a complete tree after every operation tree is full except possibly in the lower right This is expensive For example, inser

6、t 2 in the tree on the left and then rebuild as a complete tree,Insert 2 & complete tree,6,4,9,8,1,5,5,2,8,6,9,1,4,12/26/03,AVL Trees - Lecture 8,9,AVL - Good but not Perfect Balance,AVL trees are height-balanced binary search trees Balance factor of a node height(left subtree) - height(right subtre

7、e) An AVL tree has balance factor calculated at every node For every node, heights of left and right subtree can differ by no more than 1 Store current heights in each node,12/26/03,AVL Trees - Lecture 8,10,Height of an AVL Tree,N(h) = minimum number of nodes in an AVL tree of height h. Basis N(0) =

8、 1, N(1) = 2 Induction N(h) = N(h-1) + N(h-2) + 1 Solution (recall Fibonacci analysis) N(h) h ( 1.62),h-1,h-2,h,12/26/03,AVL Trees - Lecture 8,11,Height of an AVL Tree,N(h) h ( 1.62) Suppose we have n nodes in an AVL tree of height h. n N(h) (because N(h) was the minimum) n h hence log n h (relative

9、ly well balanced tree!) h 1.44 log2n (i.e., Find takes O(logn),12/26/03,AVL Trees - Lecture 8,12,Node Heights,1,0,0,2,0,6,4,9,8,1,5,1,height of node = h balance factor = hleft-hright empty height = -1,0,0,height=2 BF=1-0=1,0,6,4,9,1,5,1,Tree A (AVL),Tree B (AVL),12/26/03,AVL Trees - Lecture 8,13,Nod

10、e Heights after Insert 7,2,1,0,3,0,6,4,9,8,1,5,1,height of node = h balance factor = hleft-hright empty height = -1,1,0,2,0,6,4,9,1,5,1,0,7,0,7,balance factor 1-(-1) = 2,-1,Tree A (AVL),Tree B (not AVL),12/26/03,AVL Trees - Lecture 8,14,Insert and Rotation in AVL Trees,Insert operation may cause bal

11、ance factor to become 2 or 2 for some node only nodes on the path from insertion point to root node have possibly changed in height So after the Insert, go back up to the root node by node, updating heights If a new balance factor (the difference hleft-hright) is 2 or 2, adjust tree by rotation arou

12、nd the node,12/26/03,AVL Trees - Lecture 8,15,Single Rotation in an AVL Tree,2,1,0,2,0,6,4,9,8,1,5,1,0,7,0,1,0,2,0,6,4,9,8,1,5,1,0,7,12/26/03,AVL Trees - Lecture 8,16,Let the node that needs rebalancing be .There are 4 cases:Outside Cases (require single rotation) :1. Insertion into left subtree of

13、left child of .2. Insertion into right subtree of right child of .Inside Cases (require double rotation) :3. Insertion into right subtree of left child of .4. Insertion into left subtree of right child of .,The rebalancing is performed through four separate rotation algorithms.,Insertions in AVL Tre

14、es,12/26/03,AVL Trees - Lecture 8,17,j,k,X,Y,Z,Consider a valid AVL subtree,AVL Insertion: Outside Case,h,h,h,12/26/03,AVL Trees - Lecture 8,18,j,k,X,Y,Z,Inserting into X destroys the AVL property at node j,AVL Insertion: Outside Case,h,h+1,h,12/26/03,AVL Trees - Lecture 8,19,j,k,X,Y,Z,Do a “right r

15、otation”,AVL Insertion: Outside Case,h,h+1,h,12/26/03,AVL Trees - Lecture 8,20,j,k,X,Y,Z,Do a “right rotation”,Single right rotation,h,h+1,h,12/26/03,AVL Trees - Lecture 8,21,j,k,X,Y,Z,“Right rotation” done! (“Left rotation” is mirrorsymmetric),Outside Case Completed,AVL property has been restored!,

16、h,h+1,h,12/26/03,AVL Trees - Lecture 8,22,j,k,X,Y,Z,AVL Insertion: Inside Case,Consider a valid AVL subtree,h,h,h,12/26/03,AVL Trees - Lecture 8,23,Inserting into Y destroys the AVL property at node j,j,k,X,Y,Z,AVL Insertion: Inside Case,Does “right rotation” restore balance?,h,h+1,h,12/26/03,AVL Tr

17、ees - Lecture 8,24,j,k,X,Y,Z,“Right rotation” does not restore balance now k is out of balance,AVL Insertion: Inside Case,h,h+1,h,12/26/03,AVL Trees - Lecture 8,25,Consider the structure of subtree Y,j,k,X,Y,Z,AVL Insertion: Inside Case,h,h+1,h,12/26/03,AVL Trees - Lecture 8,26,j,k,X,V,Z,W,i,Y = nod

18、e i and subtrees V and W,AVL Insertion: Inside Case,h,h+1,h,h or h-1,12/26/03,AVL Trees - Lecture 8,27,j,k,X,V,Z,W,i,AVL Insertion: Inside Case,We will do a left-right “double rotation” . . .,12/26/03,AVL Trees - Lecture 8,28,j,k,X,V,Z,W,i,Double rotation : first rotation,left rotation complete,12/2

19、6/03,AVL Trees - Lecture 8,29,j,k,X,V,Z,W,i,Double rotation : second rotation,Now do a right rotation,12/26/03,AVL Trees - Lecture 8,30,j,k,X,V,Z,W,i,Double rotation : second rotation,right rotation complete,Balance has been restored,h,h,h or h-1,12/26/03,AVL Trees - Lecture 8,31,Implementation,bala

20、nce (1,0,-1),key,right,left,No need to keep the height; just the difference in height, i.e. the balance factor; this has to be modified on the path of insertion even if you dont perform rotations Once you have performed a rotation (single or double) you wont need to go back up the tree,12/26/03,AVL

21、Trees - Lecture 8,32,Single Rotation,RotateFromRight(n : reference node pointer) p : node pointer; p := n.right; n.right := p.left; p.left := n; n := p ,X,Y,Z,n,You also need to modify the heights or balance factors of n and p,Insert,12/26/03,AVL Trees - Lecture 8,33,Double Rotation,Implement Double

22、 Rotation in two lines.,DoubleRotateFromRight(n : reference node pointer) ? ,X,n,V,W,Z,12/26/03,AVL Trees - Lecture 8,34,Insertion in AVL Trees,Insert at the leaf (as for all BST) only nodes on the path from insertion point to root node have possibly changed in height So after the Insert, go back up

23、 to the root node by node, updating heights If a new balance factor (the difference hleft-hright) is 2 or 2, adjust tree by rotation around the node,12/26/03,AVL Trees - Lecture 8,35,Insert in BST,Insert(T : reference tree pointer, x : element) : integer if T = null thenT := new tree; T.data := x; r

24、eturn 1;/the links to /children are null caseT.data = x : return 0; /Duplicate do nothingT.data x : return Insert(T.left, x);T.data x : return Insert(T.right, x); endcase ,12/26/03,AVL Trees - Lecture 8,36,Insert in AVL trees,Insert(T : reference tree pointer, x : element) : if T = null thenT := new

25、 tree; T.data := x; height := 0; return; caseT.data = x : return ; /Duplicate do nothingT.data x : Insert(T.left, x);if (height(T.left)- height(T.right) = 2)if (T.left.data x ) then /outside caseT = RotatefromLeft (T);else /inside caseT = DoubleRotatefromLeft (T);T.data x : Insert(T.right, x);code s

26、imilar to the left case EndcaseT.height := max(height(T.left),height(T.right) +1;return; ,12/26/03,AVL Trees - Lecture 8,37,Example of Insertions in an AVL Tree,1,0,2,20,10,30,25,0,35,0,Insert 5, 40,12/26/03,AVL Trees - Lecture 8,38,Example of Insertions in an AVL Tree,1,0,2,20,10,30,25,1,35,0,5,0,2

27、0,10,30,25,1,35,5,40,0,0,0,1,2,3,Now Insert 45,12/26/03,AVL Trees - Lecture 8,39,Single rotation (outside case),2,0,3,20,10,30,25,1,35,2,5,0,20,10,30,25,1,40,5,40,0,0,0,1,2,3,45,Imbalance,35,45,0,0,1,Now Insert 34,12/26/03,AVL Trees - Lecture 8,40,Double rotation (inside case),3,0,3,20,10,30,25,1,40

28、,2,5,0,20,10,35,30,1,40,5,45,0,1,2,3,Imbalance,45,0,1,Insertion of 34,35,34,0,0,1,25,34,0,12/26/03,AVL Trees - Lecture 8,41,AVL Tree Deletion,Similar but more complex than insertion Rotations and double rotations needed to rebalance Imbalance may propagate upward so that many rotations may be needed

29、.,12/26/03,AVL Trees - Lecture 8,42,Arguments for AVL trees:Search is O(log N) since AVL trees are always balanced. Insertion and deletions are also O(logn) The height balancing adds no more than a constant factor to the speed of insertion.Arguments against using AVL trees: Difficult to program more

30、 space for balance factor. Asymptotically faster but rebalancing costs time. Most large searches are done in database systems on disk and use other structures (e.g. B-trees). May be OK to have O(N) for a single operation if total run time for many consecutive operations is fast (e.g. Splay trees).,Pros and Cons of AVL Trees,12/26/03,AVL Trees - Lecture 8,43,Double Rotation Solution,DoubleRotateFromRight(n : reference node pointer) RotateFromLeft(n.right); RotateFromRight(n); ,X,n,V,W,Z,