Avl Trees
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Avl Trees as PDF for free.
More details
- Words: 1,742
- Pages: 47
Presentation on AVL TREES Submitted to Dr. V.K. Pathak Submitted by Anjali (220/07) III B.Tech IT
AVL Trees § An AVL tree is a binary search tree with a balance condition. § AVL is named for its inventors: Adel’son-Vel’skii and Landis § AVL tree approximates the ideal tree (completely balanced tree). § AVL Tree maintains a height close to the minimum. § Defenition :An AVL tree is a binary search tree such that for any node in the tree, the height of the left and right subtrees can differ by at most 1. •
Balance Factors § The balance factor (BF) of a node is the difference between the height of the node’s left sub-tree (HL) and the height of the node’s right sub-tree (HR). • § Balance Factor = Height of Left subtree – Height of Right subtree. • § By the AVL Tree Property, the balance factor of each node in an AVL tree must be -1, 0, or 1.
Example: AVL Tree with Balance Factor 50 BF = -1 BF = 0 17
67 BF = 1
61 BF = 0
Example
Two binary search trees: (a) an AVL tree; (b) not an AVL tree (unbalanced nodes are darkened)
Properties § The depth of a typical node in an AVL tree is very close to the optimal log N. § Consequently, all searching operations in an AVL tree takes O(log N) time. § An update (insert or remove) in an AVL tree could destroy the balance. It must then be rebalanced before the operation can be considered complete. § After an insertion, only nodes that are on the path from the insertion point to the root can have their balances altered.
Rebalancing § Suppose the node to be rebalanced is X. It is considered as pivot node. There are 4 cases that we might have to fix. § Balance is restored by tree rotations. There are four types of tree rotation: 1. LL rotation: An insertion in the left subtree of the left child of X. 2. LR rotation: An insertion in the right subtree of the left child of X. 3. RL rotation:An insertion in the left subtree of the right child of X, or 4. RR rotation: An insertion in the right subtree of the right child of X.
Balancing Operations: Rotations § LL and RR rotations are symmetric and requires the same operation for balance. – LL and RR rotations are handled by single rotation. § LR and RL rotations are symmetric and requires the same operation for balance. – LR and RL rotations are handled by double rotation.
•
Single Rotation § A single rotation switches the roles of the parent and child while maintaining the search order. § Single rotation handles the outside cases (i.e. LL and RR). § We rotate between a parent node and its child. – Child becomes parent. – Parent becomes right child in case 1 i.e. LL rotation – Parent become left child in case 4 i.e. RR rotation.
§ The result is a binary search tree that satisfies the AVL property.
Single rotation to fix case 1: LL Rotation 2
0
Symmetric single rotation to fix case 4 :RR Rotation 0
2
Example
Single LL rotation fixes an AVL tree after insertion of 1.
Analysis § One rotation is sufficient to fix cases 1 and 4. § Single rotation preserves the original height: – The new height of the entire subtree is exactly the same as the height of the original subtreebefore the insertion.
§ Therefore it is enough to do rotation only at the first node, where imbalance occurred, on the path from inserted node to root. § Thus the rotation takes O(1) time.
•
Double Rotation § Single rotation does not fix the inside cases (LR and RL). § These cases require a double rotation, involving three nodes and four subtrees.
Single rotation does not fix case 2. 2
2
Left–right double rotation to fix case 2 Lift this up: first rotate left between (k1, k2),
Left–right double rotation to fix case 2 Lift this up: first rotate left between (k1, k2), then rotate right between (k3,k2)
Left–right double rotation to fix case 2 Lift this up: first rotate left between (k1, k2), then rotate right between (k3,k2)
Left-Right Double Rotation § A left-right double rotation is equivalent to a sequence of two single rotations: – 1st rotation on the original tree: a left rotation between X’s left-child and grandchild – 2nd rotation on the new tree: a right rotation between X and its new left child.
•
Example
Example
Example
Double rotation fixes AVL tree after the insertion of 5.
Right–Left double rotation to fix case 3.
Right–Left double rotation to fix case 3.
Insertions in AVL Trees §Insertion in AVL trees is similar to the binary search tree. §To restore the property of AVL tree: 1.New converted tree should be balanced. 2.New converted tree should be a binary search tree with same inorder traversal. §There are 4 cases: § Outside Cases (require single rotation) : 1. Insertion into left subtree of left child of X. 2. Insertion into right subtree of right child of X. § Inside Cases (require double rotation) : 3. Insertion into right subtree of left child of X. 4. Insertion into left subtree of right child of X. §The rebalancing is performed through four separate rotation procedure.
AVL Insertion: Outside Case
j
Consider a valid AVL subtree
k
h h
h
X
Y
Z
AVL Insertion: Outside Case
j k
h
h+1
X
Inserting into X destroys the AVL property at node j
h
Y
Z
AVL Insertion: Outside Case
j k
h
h+1
X
Do a “right rotation”
h
Y
Z
Single right rotation
j k
h
h+1
X
Do a “right rotation”
h
Y
Z
Outside Case Completed “Right rotation” done!
k j
h+1
h
h
X
Y
Z
AVL property has been restored!
AVL Insertion: Inside Case
j
Consider a valid AVL subtree
k
h h
h
X
Y
Z
AVL Insertion: Inside Case
j
Y = node i and subtrees V and W
k X
h
i
h
h+1
h or h-1
V
W
Z
AVL Insertion: Inside Case
j
We will do a left-right “double rotation” . . .
k Z
i
X V
W
Double rotation : first rotation
j i k X
Z W
V
left rotation complete!
Double rotation : second rotation
j i k X
Z W
V
Now do a right rotation
Double rotation : second rotation right rotation complete! AVL property has been restored!
i
j
k h
h
h or h-1
X
V
W
Z
Example of Insertions in an AVL Tree
01 0
2-1 0 0 2 5
30 0
Insert 5, 40 0 3 5
Example of Insertions in an AVL Tree
0 5
11 0
20 0 0 2 5
30 0
0 3 5
0 5
11 0
Now Insert 45
2 -1 0 02 5
3 -1 0 3 -1 5 40 0
Single rotation (outside case)
0 5
11 0
2-2 0 0 2 5 Imbalance
3-2 0 -2 3 5 4 -1 0 40 5
0 5
11 0
2 -1 0 02 5
Now Insert 34
3 -1 0 4 0 0 03 0 4 5 5
Double rotation (inside case)
11 0
2 -2 0
0 0 5 Imbalance 2 5
Insertion of 34
3-2 0 1 4 0
1 3 5 0 3 4
4 0 5
There occurs RL rotation
Double rotation (inside case)
11 0
2 -2 0
0 0 5 Imbalance 2 5
3-2 0 1 3 5 1 3 4
Insertion of 34
0
4 0 0 3 4
There occurs RL rotation
0 5
11 0
2 -1 0
0 2 5
03 0
3 0 5 4 -1 0 0 0 3 4 4 5
Now it is an AVL tree
Node declaration for AVL trees template class AvlTree;
template class AvlNode { Comparable element; AvlNode *left; AvlNode *right; int height;
AvlNode( const Comparable & theElement, AvlNode *lt, AvlNode *rt, int h = 0 ) : element( theElement ), left( lt ), right( rt ), height( h ) { } friend class AvlTree;
};
Height template class int AvlTree::height( AvlNode *t) const { return t == NULL ? -1 : t->height; }
Single right rotation /** * Rotate binary tree node with left child. * For AVL trees, this is a single rotation for case 1. * Update heights, then set new root. */ template void AvlTree::rotateWithLeftChild( AvlNode * & k2 ) const { AvlNode *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; k2 = k1; }
Double Rotation /** * Double rotate binary tree node: first left child. * with its right child; then node k3 with new left child. * For AVL trees, this is a double rotation for case 2. * Update heights, then set new root. */ template void AvlTree::doubleWithLeftChild( AvlNode * & k3 ) const { rotateWithRightChild( k3->left ); rotateWithLeftChild( k3 ); }
/* Internal method to insert into a subtree. * x is the item to insert. * t is the node that roots the tree. */ template void AvlTree::insert( const Comparable & x, AvlNode * & t ) const { if( t == NULL ) t = new AvlNode( x, NULL, NULL ); else if( x < t->element ) { insert( x, t->left ); if( height( t->left ) - height( t->right ) == 2 ) if( x < t->left->element ) rotateWithLeftChild( t ); else doubleWithLeftChild( t ); } else if( t->element < x ) { insert( x, t->right ); if( height( t->right ) - height( t->left ) == 2 ) if( t->right->element < x ) rotateWithRightChild( t ); else doubleWithRightChild( t ); } else ; // Duplicate; do nothing t->height = max( height( t->left ), height( t->right ) ) + 1; }
Thank you!
AVL Trees § An AVL tree is a binary search tree with a balance condition. § AVL is named for its inventors: Adel’son-Vel’skii and Landis § AVL tree approximates the ideal tree (completely balanced tree). § AVL Tree maintains a height close to the minimum. § Defenition :An AVL tree is a binary search tree such that for any node in the tree, the height of the left and right subtrees can differ by at most 1. •
Balance Factors § The balance factor (BF) of a node is the difference between the height of the node’s left sub-tree (HL) and the height of the node’s right sub-tree (HR). • § Balance Factor = Height of Left subtree – Height of Right subtree. • § By the AVL Tree Property, the balance factor of each node in an AVL tree must be -1, 0, or 1.
Example: AVL Tree with Balance Factor 50 BF = -1 BF = 0 17
67 BF = 1
61 BF = 0
Example
Two binary search trees: (a) an AVL tree; (b) not an AVL tree (unbalanced nodes are darkened)
Properties § The depth of a typical node in an AVL tree is very close to the optimal log N. § Consequently, all searching operations in an AVL tree takes O(log N) time. § An update (insert or remove) in an AVL tree could destroy the balance. It must then be rebalanced before the operation can be considered complete. § After an insertion, only nodes that are on the path from the insertion point to the root can have their balances altered.
Rebalancing § Suppose the node to be rebalanced is X. It is considered as pivot node. There are 4 cases that we might have to fix. § Balance is restored by tree rotations. There are four types of tree rotation: 1. LL rotation: An insertion in the left subtree of the left child of X. 2. LR rotation: An insertion in the right subtree of the left child of X. 3. RL rotation:An insertion in the left subtree of the right child of X, or 4. RR rotation: An insertion in the right subtree of the right child of X.
Balancing Operations: Rotations § LL and RR rotations are symmetric and requires the same operation for balance. – LL and RR rotations are handled by single rotation. § LR and RL rotations are symmetric and requires the same operation for balance. – LR and RL rotations are handled by double rotation.
•
Single Rotation § A single rotation switches the roles of the parent and child while maintaining the search order. § Single rotation handles the outside cases (i.e. LL and RR). § We rotate between a parent node and its child. – Child becomes parent. – Parent becomes right child in case 1 i.e. LL rotation – Parent become left child in case 4 i.e. RR rotation.
§ The result is a binary search tree that satisfies the AVL property.
Single rotation to fix case 1: LL Rotation 2
0
Symmetric single rotation to fix case 4 :RR Rotation 0
2
Example
Single LL rotation fixes an AVL tree after insertion of 1.
Analysis § One rotation is sufficient to fix cases 1 and 4. § Single rotation preserves the original height: – The new height of the entire subtree is exactly the same as the height of the original subtreebefore the insertion.
§ Therefore it is enough to do rotation only at the first node, where imbalance occurred, on the path from inserted node to root. § Thus the rotation takes O(1) time.
•
Double Rotation § Single rotation does not fix the inside cases (LR and RL). § These cases require a double rotation, involving three nodes and four subtrees.
Single rotation does not fix case 2. 2
2
Left–right double rotation to fix case 2 Lift this up: first rotate left between (k1, k2),
Left–right double rotation to fix case 2 Lift this up: first rotate left between (k1, k2), then rotate right between (k3,k2)
Left–right double rotation to fix case 2 Lift this up: first rotate left between (k1, k2), then rotate right between (k3,k2)
Left-Right Double Rotation § A left-right double rotation is equivalent to a sequence of two single rotations: – 1st rotation on the original tree: a left rotation between X’s left-child and grandchild – 2nd rotation on the new tree: a right rotation between X and its new left child.
•
Example
Example
Example
Double rotation fixes AVL tree after the insertion of 5.
Right–Left double rotation to fix case 3.
Right–Left double rotation to fix case 3.
Insertions in AVL Trees §Insertion in AVL trees is similar to the binary search tree. §To restore the property of AVL tree: 1.New converted tree should be balanced. 2.New converted tree should be a binary search tree with same inorder traversal. §There are 4 cases: § Outside Cases (require single rotation) : 1. Insertion into left subtree of left child of X. 2. Insertion into right subtree of right child of X. § Inside Cases (require double rotation) : 3. Insertion into right subtree of left child of X. 4. Insertion into left subtree of right child of X. §The rebalancing is performed through four separate rotation procedure.
AVL Insertion: Outside Case
j
Consider a valid AVL subtree
k
h h
h
X
Y
Z
AVL Insertion: Outside Case
j k
h
h+1
X
Inserting into X destroys the AVL property at node j
h
Y
Z
AVL Insertion: Outside Case
j k
h
h+1
X
Do a “right rotation”
h
Y
Z
Single right rotation
j k
h
h+1
X
Do a “right rotation”
h
Y
Z
Outside Case Completed “Right rotation” done!
k j
h+1
h
h
X
Y
Z
AVL property has been restored!
AVL Insertion: Inside Case
j
Consider a valid AVL subtree
k
h h
h
X
Y
Z
AVL Insertion: Inside Case
j
Y = node i and subtrees V and W
k X
h
i
h
h+1
h or h-1
V
W
Z
AVL Insertion: Inside Case
j
We will do a left-right “double rotation” . . .
k Z
i
X V
W
Double rotation : first rotation
j i k X
Z W
V
left rotation complete!
Double rotation : second rotation
j i k X
Z W
V
Now do a right rotation
Double rotation : second rotation right rotation complete! AVL property has been restored!
i
j
k h
h
h or h-1
X
V
W
Z
Example of Insertions in an AVL Tree
01 0
2-1 0 0 2 5
30 0
Insert 5, 40 0 3 5
Example of Insertions in an AVL Tree
0 5
11 0
20 0 0 2 5
30 0
0 3 5
0 5
11 0
Now Insert 45
2 -1 0 02 5
3 -1 0 3 -1 5 40 0
Single rotation (outside case)
0 5
11 0
2-2 0 0 2 5 Imbalance
3-2 0 -2 3 5 4 -1 0 40 5
0 5
11 0
2 -1 0 02 5
Now Insert 34
3 -1 0 4 0 0 03 0 4 5 5
Double rotation (inside case)
11 0
2 -2 0
0 0 5 Imbalance 2 5
Insertion of 34
3-2 0 1 4 0
1 3 5 0 3 4
4 0 5
There occurs RL rotation
Double rotation (inside case)
11 0
2 -2 0
0 0 5 Imbalance 2 5
3-2 0 1 3 5 1 3 4
Insertion of 34
0
4 0 0 3 4
There occurs RL rotation
0 5
11 0
2 -1 0
0 2 5
03 0
3 0 5 4 -1 0 0 0 3 4 4 5
Now it is an AVL tree
Node declaration for AVL trees template
template
AvlNode( const Comparable & theElement, AvlNode *lt, AvlNode *rt, int h = 0 ) : element( theElement ), left( lt ), right( rt ), height( h ) { } friend class AvlTree
};
Height template class
Single right rotation /** * Rotate binary tree node with left child. * For AVL trees, this is a single rotation for case 1. * Update heights, then set new root. */ template
Double Rotation /** * Double rotate binary tree node: first left child. * with its right child; then node k3 with new left child. * For AVL trees, this is a double rotation for case 2. * Update heights, then set new root. */ template
/* Internal method to insert into a subtree. * x is the item to insert. * t is the node that roots the tree. */ template
Thank you!
