B-self-balancing-binary-search-trees.asc

Appendix A: Self-balancing Binary Search Trees

Binary Search Trees (BST) are an excellent data structure to find elements very fast O(log n). However, when the BST branches have different branch sizes, then the performance suffers. In the worst case, all nodes can go to one side (e.g., right) and then the search time would be linear. At this point searching element won’t be any better on that tree than an array or linked list. Yikes!

Self-balanced trees will automatically rebalance the tree when an element is inserted to keep search performance. We balance a tree by making the height (distance from a node to the root) of any leaf on the tree as similar as possible.

From unbalanced BST to balanced BST

1                           2
  \                       /   \
   2        =>           1     3
    \
     3

In the example above: - Unbalanced BST: height node 3 is 2 and height node 2 is 1. - Balanced BST: height node 3 is 1 and height node 2 is 1. Much better!

As you might notice, we balanced the tree in the example by doing a rotation. To be more specific we rotated node 1 to the left to balance the tree. Let’s examine all the possible rotation we can do to balance a tree.

Tree Rotations

We can do single rotations left and right and also we can do double rotations. Let’s go one by one.

Single Right Rotation

Right rotation moves a node on the right as a child of another node.

Take a look at the examples in the code in the next section. As you will see we have an unbalanced tree 4-3-2-1. We want to balance the tree, for that we need to do a right rotation of node 3. So, we move node 3 as the right child of the previous child.

Single right rotation implementation

link:../src/data-structures/trees/tree-rotations.js[role=include]

In the rightRotation we identify 3 nodes:

• node this is the node we want to rotate to the right. E.g., node 3

• newParent this is the new parent after the rotation. E.g., node 2

• grandparent this the current’s node parent. E.g. node 4.

The swapParentChild as it name says, swap the children. For our example, it swaps node 4’s left children from `node 3 to node 2.

Take a look at the implementation.

Swap Parent and Child Implementation

link:../src/data-structures/trees/tree-rotations.js[role=include]

After swapParentChild, we have the following:

      4
     /
    2 - 3*
  /
 1

Still not quite what we want. So, newParent.setRightAndUpdateParent(node) will make node 3 the right child of node 2. Finally, we remove the left child of node 3 to be null.

      4
     /
    2
  /   \
 1     3*

Check out the rightRotation implementation again. It should make more sense to you now.

This rotation is also known as RR rotation.

Single Left Rotation

Left rotation is similar to the rightRotation we explained above.

Single left rotation implementation

link:../src/data-structures/trees/tree-rotations.js[role=include]

As you can see, this function is just the opposite of rightRotation. Where ever we used the right now we use the left here and vice versa. This rotation is also known as LL rotation.

If you are curious about the setRightAndUpdateParent and setLeftAndUpdateParent. Here’s the implementation:

Set and update parent implementation

link:../src/data-structures/trees/binary-tree-node.js[role=include]

You can also check out the full binary tree node implementation.

Left Right Rotation

This time are we going to do a double rotation.

Left-Right rotation implementation

link:../src/data-structures/trees/tree-rotations.js[role=include]

As you can see we do a left and then a right rotation. This rotation is also known as LR rotation

Right Left Rotation

Very similar to leftRightRotation. The difference is that we rotate right and then left.

Right-Left rotation implementation

link:../src/data-structures/trees/tree-rotations.js[role=include]

This rotation is also referred to as RL rotation.

Self-balancing trees implementations

So far, we have study how to make tree rotations which are the basis for self-balancing trees. There are different implementations of self-balancing trees such a Red-Black Tree and AVL Tree.