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
:
public abstract class AbstractBalancedBinarySearchTree<T extends Comparable<T>, N extends AbstractBinaryNode<T, N>> extends AbstractBinarySearchTree<T, N> {
/**
* Rotates the specific node to the left.
* @param node the node to be rotated.
*/
protected void rotateLeft(N node) {
N child = node.getRightChild();
node.setRightChild(child.getLeftChild());
if (node.hasParent())
node.getParent().replaceChild(node, child);
else
setRoot(child);
child.setLeftChild(node);
}
/**
* Rotates the specific node to the right.
* @param node the node to be rotated.
*/
protected void rotateRight(N node) {
N child = node.getLeftChild();
node.setLeftChild(child.getRightChild());
if (node.hasParent())
node.getParent().replaceChild(node, child);
else
setRoot(child);
child.setRightChild(node);
}
}
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()
:
@Override
public N add(T key) {
N node = super.add(key);
balance(node);
return node;
}
@Override
public N remove(T key) {
N node = findNode(root, key);
if (node != null) {
N lowest = node.hasBothChildren() ? removeHibbard(node) : removeSelf(node);
if (lowest != null && lowest != node) balance(lowest);
}
return node;
}
/**
* Preserves the balance of the specific node and its ancestors.
* @param node the node to be balanced.
*/
protected abstract void balance(N node);
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
Was this helpful?