CS 146: Data Structures and Algorithms

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
 The AVL Tree Node
o With so many height calculations, it makes
sense to store each node's height in the node
itself.
public class BinaryNode
{
private int data; // data in this node
private int height; // height of this node
private BinaryNode left; // left child
private BinaryNode right; // right child

...
}

17
 AVL Tree Implementation, cont’d
o Class AVLTree overrides the insert() and
remove() methods of class BinarySearchTree.
n Each method calls the superclass's method and
wraps the result in a call to the balance() method.
protected BinaryNode insert(int data, BinaryNode node)
{
return balance(super.insert(data, node));
}

protected BinaryNode remove(int data, BinaryNode node)

{
return balance(super.remove(data, node));
}

18
 AVL Tree Implementation, cont’d
o The private AVLTree method balance()
checks whether the balance condition still
holds, and rebalances the tree with rotations
whenever necessary.

19
 AVL Tree Implementation, cont’d
private BinaryNode balance(BinaryNode node)
{
...
if (height(node.getLeft()) - height(node.getRight()) > 1) {
if (height(node.getLeft().getLeft())
>= height(node.getLeft().getRight())) {
node = singleRightRotation(node);
}
Case 1
else {
node = doubleLeftRightRotation(node);
} Case 2
}
else if (height(node.getRight()) - height(node.getLeft()) > 1) {
if (height(node.getRight().getRight())
>= height(node.getRight().getLeft())) {
node = singleLeftRotation(node);
}
Case 4
else {
node = doubleRightLeftRotation(node);
} Case 3
}
...
return node;
}
20
 AVL Tree Implementation, cont’d
private BinaryNode singleRightRotation(BinaryNode k2)
{ Case 1
BinaryNode k1 = k2.getLeft();
k2.setLeft(k1.getRight());
k1.setRight(k2);
k2.setHeight(Math.max(height(k2.getLeft()), height(k2.getRight())) + 1);
k1.setHeight(Math.max(height(k1.getLeft()), k2.getHeight()) + 1);

return k1;
}

private BinaryNode singleLeftRotation(BinaryNode k1)

{ Case 4
BinaryNode k2 = k1.getRight();
k1.setRight(k2.getLeft());
k2.setLeft(k1);
k1.setHeight(Math.max(height(k1.getLeft()), height(k1.getRight())) + 1);
k2.setHeight(Math.max(height(k2.getRight()), k1.getHeight()) + 1);

return k2;
}

21
 AVL Tree Implementation, cont’d
private BinaryNode doubleLeftRightRotation(BinaryNode k3)
{
k3.setLeft(singleLeftRotation(k3.getLeft()));
Case 2
return singleRightRotation(k3);
}

private BinaryNode doubleRightLeftRotation(BinaryNode k1)

{
k1.setRight(singleRightRotation(k1.getRight()));
return singleLeftRotation(k1); Case 3
}

22
Break

23
 Assignment #3
o This assignment will give you practice with
binary search trees (BST) and AVL trees.
o You are provided a TreePrinter class that
has a print() method that will print any
arbitrary binary tree.
n A template for how it prints a tree:
xx
/\
------------------------------ ------------------------------
/ \
xx xx
/\ /\
-------------- -------------- -------------- --------------
/ \ / \
xx xx xx xx
/\ /\ /\ /\
------ ------ ------ ------ ------ ------ ------ ------
/ \ / \ / \ / \
xx xx xx xx xx xx xx xx
/\ /\ /\ /\ /\ /\ /\ /\
-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
/ \ / \ / \ / \ / \ / \ / \ / \
xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx
/\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\
/ \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \
xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx xx24xx
xx
 Assignment #3, cont’d
o TreePrinter is able to print trees with height
up to 5, i.e., 32 node values on the bottom row.
n An example of an actual printed tree:
TreePrinter.ja
24
/\ va
-------------- --------------
/ \
18 73
/\ /\
------ ------ ------ ------
/ \ / \
12 19 38 87
/ /\ \
-- -- -- --
/ / \ \
10 37 41 90
\
\
64

25
 Assignment #3: First Part
o The first part of the assignment makes sure that
you can successfully insert nodes into, and
delete nodes from, a binary search tree (BST)
and an AVL tree.

26
 Assignment #3: First Part, cont’d
o First generate a random BST that has height 5
and contains random values from 10 through 99.
n You may have to generate dozens of trees
until you get one that's exactly height 5.
n Don't worry that the tree is unbalanced.
n Print the tree.

o Now repeatedly delete the root of the tree.

n Print the tree after each deletion to verify that
you did the deletion correctly.
n Stop when the tree becomes empty.

27
 Assignment #3: First Part, cont’d
o Second, create an AVL tree node by node.
n Generate 35 unique random integers 10-99
to insert into the tree.
n Print the tree after each insertion to verify that
you are keeping it balanced.
n Each time you do a rebalancing, print a message
indicating which rotation operation and which node.
o Example:
Double left-right rotation: 76
o As you did with the BST, repeatedly delete the
root of your AVL tree.
n Print the tree after each deletion to verify that
you are keeping it balanced.

28
 Assignment #3: First Part, cont’d
o A handy AVL tree balance checker:
private int checkBalance(BinaryNode node) throws Exception
{
if (node == null) return -1;

if (node != null) {
int leftHeight = checkBalance(node.getLeft());
int rightHeight = checkBalance(node.getRight());
if ( (Math.abs(height(node.getLeft()) - height(node.getRight())) > 1
)
|| (height(node.getLeft()) != leftHeight)
|| (height(node.getRight()) != rightHeight)) {
throw new Exception("Unbalanced trees.");
}
}

return height(node);
}

Demo 29
 Assignment #3: Second Part
o The second part of the assignment compares
the performance of a BST vs. an AVL tree.

30
 Assignment #3: Second Part
o First, generate n random integers.
n n is some large number, explained on the next slide.

o Time and print how long it takes to insert the

random integers one at a time into an initially
empty BST.
n Do not print the tree after each insertion.

o Time and print how long it takes to insert the

same random integers one at a time into an
initially empty AVL tree.
n Do not print the tree after each insertion.

31
 Assignment #3: Second Part, cont’d
o Choose a value of n large enough to give you
consistent timings that you can compare.
n Try values of n = 1,000 10,000 100,000 1,000,000

o If T(n) is the time function, how does the growth

of TBST(n) compare with the growth of TAVL(n
)?

32
 Assignment #3: Second Part, cont’d
o Second, generate k random integers.
n k is some large value.

o Time how long it takes to search your

n-node BST for all k random integers.
n It doesn’t matter whether or not the search succeeds.

o Time how long it takes to search your n-node

AVL tree for the same k random integers.
o Compare the grow rates of these two time
functions.

33
 Assignment #3: Second Part, cont’d
o Third, perform a random mixture of m insertions
and searches on your BST and then on your
n-node AVL tree.
n m is some large number.
n Perform the same sequence of insertions and
searches on both trees.

o Try different ratios of insertions vs. searches.

o Empirically estimate the ratio where an AVL tree
has better performance than a BST for a
mixture of insertions and searches.
34
 Assignment #3, cont’d
o You can use any code from the lectures
or from the textbook.
o You do not have to use
parameterized generic types.
n You can use raw (nongeneric) types,
or <Integer>.

35
 Assignment #3, cont’d
o You may choose a partner to work with you
on this assignment.
n Both of you will receive the same score.

o Create a zip file containing:

n Your Java source files.
n Any instructions on how to build and run your code.
n Text files containing your outputs.
n A 1- or 2-page that briefly describes your
conclusions from doing this assignment.

36
 Assignment #3, cont’d
o Email the zip file to me
n Subject line:
CS 146 Assignment #3: Your Name(s)

o If you work with a partner, both of you turn in

one assignment.
n CC your partner's email address so I can “reply all”
to you both.

o Due Friday, July 3.

37
 Splay Trees
o Not a new type of tree, but a reimplementation
of the BST insert, delete, and search methods.
n The goal is to improve their performance.

o No single operation on a splay tree is

guaranteed to have better performance.
n But a series of m operations will take O(m log n) time
for a tree of n nodes, whenever m > n.

o Not highly balanced like an AVL tree.

n Lowering the cost of an entire series of operations is
more important then keeping the tree balanced.

38
 Splay Trees, cont’d
o Whenever a splay tree node is accessed,
the tree performs splaying operations that
moves the accessed node to the root of the tree.
o Splaying a node consists of a series of rotations.
n Similar to AVL tree rotations.

o The goal is to move the accessed node

to the root.
o A side benefit is to make the tree
more balanced.

39
 Splay Trees, cont’d
o The theory is that once a node has been
accessed, it will soon be accessed again.
o Future accesses are fast if the node is the root.

40
 Splay Trees, cont’d
o How is a worst-case BST created ?
n When all the nodes are entered in sorted order.
n Suppose the bottom node is accessed in such a tree:

Data Structures and Algorithms in Java, 3rd ed. 41

by Mark Allen Weiss
Pearson Education, Inc., 2012
 Splay Trees, cont’d
o If a node hasn’t been accessed in a while,
then the next time it’s accessed, you pay the
performance penalty of splaying.
o But accesses of that node in the near future
will be very fast.
o And so we amortize the cost of splaying
over future operations.

42
Splay Trees, cont’d

Data Structures and Algorithms in Java, 3rd ed. 43

by Mark Allen Weiss
Pearson Education, Inc., 2012
Splay Trees, cont’d

Data Structures and Algorithms in Java, 3rd ed. 44

by Mark Allen Weiss
Pearson Education, Inc., 2012
Splay Trees, cont’d

Data Structures and Algorithms in Java, 3rd ed. 45

by Mark Allen Weiss
Pearson Education, Inc., 2012
Splay Trees, cont’d

Data Structures and Algorithms in Java, 3rd ed. 46

by Mark Allen Weiss
Pearson Education, Inc., 2012
Splay Trees, cont’d

Data Structures and Algorithms in Java, 3rd ed. 47

by Mark Allen Weiss
Pearson Education, Inc., 2012
Splay Trees, cont’d

Data Structures and Algorithms in Java, 3rd ed. 48

by Mark Allen Weiss
Pearson Education, Inc., 2012
Splay Trees, cont’d

Data Structures and Algorithms in Java, 3rd ed. 49

by Mark Allen Weiss
Pearson Education, Inc., 2012
Splay Trees, cont’d

Data Structures and Algorithms in Java, 3rd ed. 50

by Mark Allen Weiss
Pearson Education, Inc., 2012
Splay Trees, cont’d

Data Structures and Algorithms in Java, 3rd ed. 51

by Mark Allen Weiss
Pearson Education, Inc., 2012