Binary Search Trees
o A binary search tree has these properties
for each of its nodes:
n All the values in the node's left subtree is
less than the value of the node itself.
n All the values in the node's right subtree is
greater than the value of the node itself.
2
AVL Trees
o An AVL tree is a binary search tree (BST)
with a balance condition.
n Named after its inventors,
Adelson-Velskii and Landis.
o For each node of the BST, the heights of its
left and right subtrees can differ by at most 1.
n Remember that the height of a tree is the
length of the longest path from the root to a leaf.
n The height of the root = the height of the tree.
n The height of an empty tree is -1.
3
AVL Trees, cont’d
Data Structures and Algorithms in Java, 3rd ed. 4
by Mark Allen Weiss
Pearson Education, Inc., 2012
Balancing AVL Trees
o We need to rebalance the tree whenever the
balance condition is violated.
n We need to check after every insertion and deletion.
Data Structures and Algorithms in Java, 3rd ed. 5
by Mark Allen Weiss
Pearson Education, Inc., 2012
Balancing AVL Trees, cont’d
o Assume the tree was balanced before
an insertion.
o If it became unbalanced due to the insertion,
then the inserted node must have caused
some nodes between itself and the root
to be unbalanced.
o An unbalanced node must have the height of
one of its subtrees exactly 2 greater than the
height its other subtree.
6
Balancing AVL Trees, cont’d
o Let the deepest unbalanced node be α.
o Any node has at most two children.
o A new height imbalance means that the
heights of α’s two subtrees now differ by 2.
α α
1 2 3 4
7
Balancing AVL Trees, cont’d
o Therefore, one of the following α
had to occur:
n Case 1 (outside left-left):
The insertion was into the
left subtree of the left child of α. 1 2 3 4
n Case 2 (inside left-right): The insertion was into the
right subtree of the left child of α.
n Case 3 (inside right-left): The insertion was into the
left subtree of the right child of α.
n Case 4 (outside right-right): The insertion was into
the right subtree of the right child of α.
Cases 1 and 4 are mirrors of each other,
and cases 2 and 3 are mirrors of each other.
8
Balancing AVL Trees: Case 1
o Case 1 (outside left-left):
Rebalance with a single right rotation.
Data Structures and Algorithms in Java, 3rd ed. 9
by Mark Allen Weiss
Pearson Education, Inc., 2012
Balancing AVL Trees: Case 1, cont’d
o Case 1 (outside left-left):
Rebalance with a single right rotation.
Node A is unbalanced.
Single right rotation: A's left
child B becomes the new
root of the subtree.
Node A becomes the right
child and adopts B's right child
as its new left child.
Node 8 is unbalanced.
Single right rotation: 8's left
child 7 becomes the new
root of the subtree.
Node 8 is the right child.
http://www.cs.uah.edu/~rcoleman/CS221/Trees/AVLTree.htm
l
Data Structures and Algorithms in Java, 3rd ed. 10
by Mark Allen Weiss
Pearson Education, Inc., 2012
Balancing AVL Trees: Case 4
o Case 4 (outside right-right):
Rebalance with a single left rotation.
Data Structures and Algorithms in Java, 3rd ed.
by Mark Allen Weiss
Pearson Education, Inc., 2012
Node A is unbalanced.
Single left rotation: A's right
child C becomes the new
root of the subtree.
Node A becomes the left
child and adopts C's left child
as its new right child. 11
http://www.cs.uah.edu/~rcoleman/CS221/Trees/AVLTree.htm
Balancing AVL Trees: Case 2
o Case 2 (inside left-right):
Rebalance with a double left-right rotation.
Data Structures and Algorithms in Java, 3rd ed. 12
by Mark Allen Weiss
Pearson Education, Inc., 2012
Balancing AVL Trees: Case 2, cont’d
o Case 2 (inside left-right):
Rebalance with a double left-right rotation.
http://www.cs.uah.edu/~rcoleman/CS221/Trees/AVLTree.htm
l
Node A is unbalanced.
Double left-right rotation: E becomes the new root of the subtree after two
rotations. Step 1 is a single left rotation between B and E. E replaces B as the
subtree root. B becomes E's left child and B adopts E's left child F as its new
right child. Step 2 is a single right rotation between E and A. E replaces A is
the subtree root. A becomes E's right child and A adopts E's right child G as its
new left child. 13
Balancing AVL Trees: Case 3
o Case 3 (inside right-left):
Rebalance with a double right-left rotation.
Data Structures and Algorithms in Java, 3rd ed. 14
by Mark Allen Weiss
Pearson Education, Inc., 2012
Balancing AVL Trees: Case 3, cont’d
http://www.cs.uah.edu/~rcoleman/CS221/Trees/AVLTree.htm
o Case 3 (inside right-left): l
Rebalance with a double right-left rotation.
Node A is unbalanced.
Double right-left rotation: D becomes the new root of the subtree after two
rotations. Step 1 is a single right rotation between C and C. D replaces C as
the subtree root. C becomes D's right child and C adopts D's right child G as
its new left child. Step 2 is a single left rotation between D and A. D replaces A
is the subtree root. A becomes D's left child and A adopts D's left child F as its
new right child. 15
AVL Tree Implementation
o Since an AVL tree is just a BST with a balance
condition, it makes sense to make the AVL tree
class a subclass of the BST class.
public class AvlTree extends BinarySearchTree
o Both classes can share the same
BinaryNode class.
16
