Friday, June 12, 2015

Self-balancing Binary Search Tree

Before we go any further lets see what will happen  if we insert sorted numbers into a regular Binary Search Tree (BST). Suppose we enter 10,20,30,40 and 50 in the same order. Then what we will get is a highly unbalanced BST:

Actually it has become a linked list now. You can read more about skewed BSTs here. As it hurts the performance badly there is always a need for balance Binary Search Tree.

A self balanced binary search tree is the one that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions. An example is AVL (Adelson-Velsky and Landis) Binary Search Tree which makes use of rotations to keep itself balanced.

As per wikipedia: "In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations."

The wi-ki page also demonstrates how rotation works:


AVL tree is generally compared with Red-Black tree as both have certain common properties and both support the concept of rotation. They also support same operations and take O(log n) time for basic operations (For purists they actually take O(lg n) time but base does not matter much in this case as they will show same pattern). For look up intensive applications AVL trees are supposed to be faster than Red-Black trees but both are height balanced.

We have already covered implementation of Binary Search Tree in previous article. Here I will create an abstract class that will have methods for rotation as well.
abstract public class RotatableBinarySearchTree<T extends Comparable<T>> extends BinarySearchTree<T> {
    protected enum Position {
       LEFT, RIGHT
    };
    public RotatableBinarySearchTree() { }
}

The methods that will perform rotation are: rotateLeft and rotateRight. These are shown below:
protected void rotateLeft(Node<T> node) {
 Position parentPosition = null;
 Node<T> parent = node.getParent();
 if (parent != null) {
  if (node.equals(parent.getLeft())) {
   // Lesser
   parentPosition = Position.LEFT;
  } else {
   // Greater
   parentPosition = Position.RIGHT;
  }
 }

 Node<T> greater = node.getRight();
 node.setRight(null);
 Node<T> lesser = greater.getLeft();

 greater.setLeft(node);
 node.setParent(greater);

 node.setRight(lesser);
 if (lesser != null)
  lesser.setParent(node);

 if (parentPosition != null) {
  if (parentPosition == Position.LEFT) {
   parent.setLeft(greater);
  } else {
   parent.setRight(greater);
  }
  greater.setParent(parent);
 } else {
  root = greater;
  greater.setParent(null);
 }
}

protected void rotateRight(Node<T> node) {
 Position parentPosition = null;
 Node<T> parent = node.getParent();
 if (parent != null) {
  if (node.equals(parent.getLeft())) {
   // Lesser
   parentPosition = Position.LEFT;
  } else {
   // Greater
   parentPosition = Position.RIGHT;
  }
 }

 Node<T> lesser = node.getLeft();
 node.setLeft(null);
 Node<T> greater = lesser.getRight();

 lesser.setRight(node);
 node.setParent(lesser);

 node.setLeft(greater);
 if (greater != null)
  greater.setParent(node);

 if (parentPosition != null) {
  if (parentPosition == Position.LEFT) {
   parent.setLeft(lesser);
  } else {
   parent.setRight(lesser);
  }
  lesser.setParent(parent);
 } else {
  root = lesser;
  lesser.setParent(null);
 }
}

This abstract class provides method for rotation and will be extended by the implementation of AVL and Red-Black Trees when we will discuss them.

No comments: