4.2. Balanced BST
This section discusses abstraction of binary search trees.
A binary search tree gives the worst-case complexity of for searching a key when it is not balanced, where is the number of nodes in the tree:
Search | Insert | Delete | |
Unbalanced |
|
| |
Balanced |
|
|
To ensure the complexity, it needs to be balanced at all time (or at most time).
Rotation
There are 4 cases of unbalanced trees to be considered:
Left linear
[3, 2, 1]
Right linear
[1, 2, 3]
Left zig-zag
[3, 1, 2]
Right zig-zag
[1, 3, 2]
These cases can be balanced by performing rotations as follows:
What should happen to the subtrees (red/orange/green/blue triangles) after the rotations?
Abstract Balanced Binary Search Tree
Let us create an abstract class AbstractBalancedBinarySearchTree
that inherits the abstract class AbstractBinarySearchTree
:
Where does
node
end up being after the rotations?
The followings demonstrate how the rotateLeft()
method works:
Let us override the add()
and remove()
methods that call the abstract method balance()
:
L3
: calls theadd()
method in the super class,AbstractBinarySearchTree
.L4
: performs balancing onnode
that is just added.L14
: performs balancing onnode
that is the lowest node in the tree affected by this removal.L24
: defines a balancing algorithm for a specific type of balanced binary search trees.
What are the worst-case complexities of the
add()
andremove()
methods above?
Last updated