Balanced Search Trees

BALANCED SEARCH TREES
Avoiding the Limitations Imposed by Binary Search

Trees
Read Weiss, Section 4.4 (page 123-136)
Today’s Lecture
Limitation of BSTs
Balanced BSTs
AVL Trees
Worst Case Performance
Try inserting {10,20,30,40} into a BST
How Can We Enforce Balance?
To ensure the tree remains balanced, we introduce a “balance”
requirement
For every node in the tree, the height of the left and right
sub trees can differ by at most 1.
AVL Tree (Adelson-Velskii and Landis)
(Note: There are also other ways of enforcing balance)
AVL vs Non-AVL
Which of the following is AVL?

AVL vs Non-AVL
Which of the following is AVL?

How Height Imbalance Occurs?
How Imbalance in Binary Search Trees Occurs?
Case 1- The “outside” case
Two Symmetrical Cases
A. An insertion into the left sub-tree of the left child of α.
B. An insertion into the right sub-tree of the right child of α.
Case 2 – The “inside” case
Also has Two Symmetrical Cases
An insertion into the right sub-tree of the left child of α.
An insertion into the left sub-tree of the right child of α.
Enforcing Balance
Mechanisms We can use to create Balanced Tree (AVL) from
Imbalanced Trees
Solution for Case 1
Let’s rebalance the trees shown below
An example of case 1
Note that imbalance occurs at node ‘3’
1a 1b
5
Solution for Case 1a
We can rotate the left sub-tree to the right with respect to ‘3’
Solution for Case 1
Case 1a – fixed using right rotation
Case 1b – fixed using left rotation

Example
Insert and balance {5,4,3,2,1}

Solution for Case 2
Attempt to balance the following tree using a single rotation

(Case 2)
Cannot be rebalanced with a single rotation

Solution for Case 2
Step 1: Rotate left the sub-tree 1-2 (This takes us back to case 1a
Step 2: Rotate right (same as previous example)

Example
Insert and balance {12, 8, 7, 14, 18, 10, 20, 2, 15}

Implementation
Search, findMin, findMax, traversal
Exactly the same as BSTs
Insertion and Deletion

Fundamentally similar
Rotations must be done after insertion and deletion
Extra code needed to keep track of height of the tree
Some AVL Implementation Details
Additional Concepts and Implementation Details of AVL
Theorem: Let T be an AVL tree and x be a node in T. Then
xr − xl ≤ 1,
where xr − xl denotes the absolute value of xr − xl.
Let x be a node in the AVL tree T.

1. If xl > xr, we say that x is left high. In this case, xl = xr + 1.
2. If xl = xr, we say that x is equal high.
3. If xr > xl, we say that x is right high. In this case, xr = xl + 1.
Definition: The balance factor of x, written bf(x), is defined by bf(x) = xr − xl.
Let x be a node in the AVL tree T. Then:

1. If x is left high, then bf(x) = −1.
2. If x is equal high, then bf(x) = 0.
3. If x is right high, then bf(x) = 1.
Definition: Let x be a node in a binary tree. We say that the node x violates the
balance criteria if xr − xl > 1, that is, if the height of the left and right subtrees
of x differ by more than 1.
The following defines the node of an AVL tree:

• To insert an item in an AVL tree, first we search the tree and find the place
where the new item is to be inserted.
• Because an AVL tree is a binary search tree, to find the place for the new item
we can search the AVL tree using a search algorithm similar to the one
designed for binary search trees.
• If the item to be inserted is already in the tree, then the search ends at a
nonempty subtree.
• Because duplicates are not allowed, in this case we can output an appropriate
error message.
• Suppose that the item to be inserted is not in the AVL tree. Then the search
ends at an empty subtree and we insert the item in that subtree.
• After inserting the new item in the tree, the resulting tree might not be an
AVL tree.
• Thus, we must restore the tree’s balance criteria.
• This is accomplished by traveling the same path (back to the root node) that
was followed when the new item was inserted in the AVL tree.
• The nodes on this path (back to the root node) are visited and either their
balance factors are changed, or we might have to reconstruct part of the tree.
• The reconstruction procedure is called rotating the tree.
• There are two types of rotations, left rotation and right rotation.
• Suppose that the rotation occurs at node x.
• If it is a left rotation, then certain nodes from the right subtree of x move to its
left subtree; the root of the right subtree of x becomes the new root of the
reconstructed subtree.
• If it is a right rotation at x, certain nodes from the left subtree of x move to its
right subtree; the root of the left subtree of x becomes the new root of the
reconstructed subtree.
• In Figure AVL-16, subtrees T1, T2, and T3 are of equal height, say h. The dotted
rectangle shows an item insertion in T1, causing the height of the subtree T1 to
increase by 1.
• The subtree at node a is still an AVL tree, but the balance criteria is violated at
the root node. We note the following in this tree.
Because the tree is a binary search tree:

• Every key in T1 is smaller than the key in node a.
• Every key in T2 is larger than the key in node a.
• Every key in T2 is smaller than the key in node b.
Therefore:
1. We make T2 (the right subtree of node a) the left subtree of node b.
2. We make node b the right child of node a.
3. Node a becomes the root node of the reconstructed tree, as shown in Figure
AVL-16.
• In Figure AVL-18, the dotted rectangle shows that a new item is inserted in the
subtree, T2 or T3, causing the subtree to grow in height.
• All keys in T3 are smaller than the key in node c.
• All keys in T3 are larger than the key in node b.
• All keys in T2 are smaller than the key in node b.
• All keys in T2 are larger than the key in node a.
• After insertion, the subtrees with root nodes a and b are still AVL trees.
• The balance criteria is violated at the root node, c, of the tree.
• The balance factors of node c, bf(c) = −1, and node a, bf(a) = 1, are opposite.
• This is an example of double rotation.
• One rotation is required at node a and another rotation is required at node c.
• If the balance factor of the node where the tree is to be reconstructed and the
balance factor of the higher subtree are opposite, that node requires a double
rotation.
• First we rotate the tree at node a and then at node c.
• Now the tree at node a is right high, so we make a left rotation at a. Next,
because the tree at node c is left high, we make a right rotation at c.
• Figure AVL-18 shows the resulting tree (which is to the right of the tree after
insertion). Figure AVL-19, however, shows both rotations in sequence.
• Suppose that the tree is to be reconstructed, by rotation, at node x. Then the subtree
with the root node x requires either a single or a double rotation.
1. Suppose that the balance factor of the node x and the balance factor of the root
node of the higher subtree of x have the same sign, that is, both positive or both
negative.
a. If these balance factors are positive, make a single left rotation at x.
b. If these balance factors are negative, make a single right rotation at x.
2. Suppose that the balance factor of the node x and the balance factor of the higher
subtree of x are opposite in sign. To be specific, suppose that the balance factor
of the node x prior to insertion was −1 and suppose that y is the root node of
the left subtree of x. After insertion, the balance factor of the node y is 1. That is,
after insertion, the right subtree of node y grew in height. In this case, we
require a double rotation at x. First we make a left rotation at y (because y is right
high). Then we make a right rotation at x.
• The following steps describe the function insertIntoAVL:
1. Create a node and assign the item to be inserted to the info field of this
node.
2. Search the tree and find the place for the new node in the tree.
3. Insert the new node in the tree.
4. Backtrack the path, which was constructed to find the place for the new
node in the tree, to the root node. If necessary, adjust the balance factors
of the nodes, or reconstruct the tree at a node on the path.
• The function insertIntoAVL also uses a bool member variable,
isTaller, to indicate to the parent whether the subtree grew in height
or not.
To delete an item from an AVL tree, first we find the node containing the item to
be deleted. The following four cases arise:
Case 1: The node to be deleted is a leaf.
Case 2: The node to be deleted has no right child, that is, its right subtree is
empty.
Case 3: The node to be deleted has no left child, that is, its left subtree is empty.
Case 4: The node to be deleted has a left child and a right child.

Balanced Search Trees

Uploaded by

Copyright:

Available Formats

Balanced Search Trees

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Balanced Search Trees

Uploaded by

Copyright:

Available Formats

BALANCED SEARCH TREES

Avoiding the Limitations Imposed by Binary Search

Which of the following is AVL?

Which of the following is AVL?

Case 1a – fixed using right rotation

Case 1b – fixed using left rotation

Insert and balance {5,4,3,2,1}

Attempt to balance the following tree using a single rotation

Cannot be rebalanced with a single rotation

Step 2: Rotate right (same as previous example)

Insert and balance {12, 8, 7, 14, 18, 10, 20, 2, 15}

Insertion and Deletion

where xr − xl denotes the absolute value of xr − xl.

Let x be a node in the AVL tree T.

Definition: The balance factor of x, written bf(x), is defined by bf(x) = xr − xl.

Let x be a node in the AVL tree T. Then:

The following defines the node of an AVL tree:

Because the tree is a binary search tree:

You might also like