Ie
- 1. AVL Trees A tree is said to be balanced if for each node, the number of nodes in the left subtree and the number of nodes in the right subtree differ by at most one. A tree is said to be height-balanced or AVL if for each node, the height of the left subtree and height of the right subtree differ by at most one.
- 2. AVL Trees The height of the left subtree minus the height of the right subtree of a node is called the balance of the node. For an AVL tree, the balances of the nodes are always -1, 0 or 1. Given an AVL tree, if insertions or deletions are performed, the AVL tree may not remain height balanced.
- 3. AVL Trees Violation may occur when an insertion into 1. left subtree of left child (LL case) 2. right subtree of left child (RL case) 3. left subtree of right child (LR case) 4. right subtree of right child (RR case)
- 4. AVL Trees n+1 n+1 n+1 n+1 n n+1 n+1 n n+1 n+1 n+1 n+1 From: J Beidler, Data structures and algorithms, Springer1997
- 5. AVL Trees To maintain the height balanced property of the AVL tree after insertion or deletion, it is necessary to perform a transformation on the tree so that (1) the inorder traversal of the transformed tree is the same as for the original tree (i.e., the new tree remains a binary search tree). (2) the tree after transformation is height balanced.
- 6. AVL Trees Rotation - to restore the AVL tree after insertion - single rotation - double rotation
- 7. AVL Trees single rotation
- 8. AVL Trees Double rotation
- 9. AVL Trees: Single Rotation Fix LL and RR cases
- 10. AVL Trees: Single Rotation Example: 3 2 1 4 5 6 7 construct binary search tree without height balanced restriction depth of tree = 4 ii..ee.. LLLL ccaassee
- 11. AVL Trees: Single Rotation Construct AVL tree (height balanced)
- 12. AVL Trees: Single Rotation IInnsseerrtt 44,, 55 IInnsseerrtt 66
- 13. AVL Trees: Single Rotation IInnsseerrtt 77
- 14. AVL Trees: Double Rotation Single rotation fails to fix cases 2 and 3 (i.e. LR and RL cases) n n速 n+1 n
- 15. AVL Trees: Double Rotation Double rotation is used case 2 (LR case) n+1 n+1 n n n+1
- 16. AVL Trees: Double Rotation case 3 (RL case)
- 17. AVL Trees: Double Rotation Example: Double Rotation Double Rotation
- 18. AVL Trees: Double Rotation Insert 14 Double Rotation Double Rotation
- 19. AVL Trees: Double Rotation Insert 13 Single Rotation Single Rotation
- 20. AVL Trees: Double Rotation Insert 12, 11, 10 Single Rotation Single Rotation
- 21. AVL Trees: Double Rotation Insert 8 and 9
- 22. AVL Trees: Double Rotation Result
- 23. AVL Trees: Implementation After insertion, if the height of the node does not change => done Otherwise, if imbalance appears, then determine the appropriate action: single or double rotation
- 24. 4.5.3 AVL Trees: Implementation struct AvlNode; typedef struct AvlNode *Position; typedef struct AvlNode *AvlTree; AvlTree MakeEmpty( AvlTree T ); Position Find( ElementType X, AvlTree T ); Position FindMin( AvlTree T ); Position FindMax( AvlTree T ); AvlTree Insert( ElementType X, AvlTree T ); AvlTree Delete( ElementType X, AvlTree T ); ElementType Retrieve( Position P );
- 25. AVL Trees: Implementation struct AvlNode { ElementType Element; AvlTree Left; AvlTree Right; int Height; };
- 26. AVL Trees: Implementation AvlTree MakeEmpty( AvlTree T ) { if( T != NULL ) { MakeEmpty( T->Left ); MakeEmpty( T->Right ); free( T ); } return NULL; }
- 27. AVL Trees: Implementation static int Height( Position P ) { if( P == NULL ) return -1; else return P->Height; }
- 28. 4.5.3 AVL Trees: Implementation static Position SingleRotateWithLeft( Position K2 ) { Position K1; K1 = K2速Left; K2 速 Left = K1 速 Right; K1 速 Right = K2; K2 速 Height = Max( Height( K2 速 Left ), Height(K2 速 Right ) ) + 1; K1 速 Height = Max( Height( K1 速 Left ), K2 速 Height ) + 1; return K1; /* New root */ }
- 29. AVL Trees: Implementation static Position SingleRotateWithRight( Position K1 ) { Position K2; K2 = K1 速 Right; K1 速 Right = K2 速 Left; K2 速 Left = K1; K1 速 Height = Max( Height( K1 速 Left ), Height( K1 速 Right ) ) + 1; K2 速 Height = Max( Height( K2 速 Right ), K1 速 Height ) + 1; return K2; /* New root */ }
- 30. AVL Trees: Implementation static Position DoubleRotateWithLeft( Position K3 ) { /* Rotate between K1 and K2 */ K3 速 Left = SingleRotateWithRight( K3 速 Left ); /* Rotate between K3 and K2 */ return SingleRotateWithLeft( K3 ); }
- 31. AVL Trees: Implementation static Position DoubleRotateWithRight( Position K1) { /* Rotate between K3 and K2 */ K1 速 Right = SingleRotateWithLeft( K1 速 Right ); /* Rotate between K1 and K2 */ return SingleRotateWithRight( K1 ); }
- 32. AVL Trees: Implementation AvlTree Insert( ElementType X, AvlTree T ) { if ( T == NULL ) { /* Create and return a one-node tree */ T = malloc( sizeof( struct AvlNode ) ); if ( T == NULL ) FatalError( "Out of space!!!" ); else { T 速 Element = X; T 速 Height = 0; T 速 Left = T 速 Right = NULL; } } else
- 33. AVL Trees: Implementation if ( X < T 速 Element ) { T 速 Left = Insert( X, T 速 Left ) if ( Height( T 速 Left ) - Height( T 速 Right ) == 2 ) if ( X < T 速 Left 速 Element ) T = SingleRotateWithLeft( T ) else T = DoubleRotateWithLeft( T ); } else
- 34. AVL Trees: Implementation if ( X > T 速 Element ) { T 速 Right = Insert( X, T 速 Right ); if( Height( T 速 Right ) - Height( T 速 Left ) == 2 ) if( X > T 速 Right 速 Element ) T = SingleRotateWithRight( T ); else T = DoubleRotateWithRight( T ); } /* Else X is in the tree already; we'll do nothing */ T 速 Height = Max( Height( T 速 Left ), Height( T 速 Right ) ) + 1; return T; }
- 35. . .