Binary Search Tree – Part 2 Rotations

Hi, in the second part of my tree series, I want to talk about rotations. In the first part, we learned what binary search trees are.

Trees offer us the possibility to execute the accesses with logarithmic runtime. But what if we are dealing with a degenerate tree? Exactly, we have in the worst case an overhead $O(n)$. This is bad, because we want to stay at $O(Log(n))$. This is where the rotations come into play, which help us to do this.

Rotations are used to rebalance trees. A tree can already be out of balance after an insertion / deletion operation. Here we have to intervene with rotations. We already know that the node we added or deleted last has brought the tree out of balance. Here we correct the problem with the help of rotations.

There are four types of rotations. The simple left rotation and right rotation. The two somewhat complex left-right rotation and right-left rotation.

Right rotation (RR rotation)

The right rotation, is a simple rotation, because here we take the grandparent node of the originator, and rotate with it once around the parent node of the originator. This then looks like in the picture. Here, node $6$ is rotated once to the right around node $4$. Thus, node $4$ becomes the new root node, which holds the grandparent on the right side. Simply said, the node around which is rotated, slides one level higher.

Left rotation (LL rotation)

Exactly the opposite of right rotation. A picture illustrates this once again.

Left-Right Rotation (LR Rotation)

The Left-Right Rotation, is for the cases where we cannot restore the balance with a simple rotation. This is the case when the parent is the left child of the grandparent. Also, when the child is the right child of the patent. Here we must first make a simple left rotation, so that the $2$ rotates left around the node $4$. Now we can, with a simple right rotation, rotate the node $6$ once to the right around the node $4$. We can see this again below

Right-Left Rotation (RL Rotation)

The right-left rotation, is also again only the exact counterpart, to the left-right rotation. A picture also clarifies this once again

These are now all kinds of rotations, which exist in the trees. But what if we want to rotate, but a node already exists at that point? Here we take out the said node first and execute the rotation. Afterwards we insert the node again. This then looks like this.

Extending the search tree

Let's program the nodes in Java. For this, we extend the class Tree by the rotations. The rotations will later return the rotated nodes in order to insert them at the right place in the tree.

public Node rotateLeft(Node node)
{
    if(node == null)
        return null;

    Node parent = node.getParent();
    node.setLeft(parent);
    node.setParent(parent.getParent());
    parent.setParent(node);
    return node;
}

If we look at the rotateLeft method, we see that the node is passed here around which the left side is to be rotated later. But first we have to check if this node is not a null. If it is, no rotation takes place, otherwise we get a NullPointerException. But if it is a valid node, its parent node (grandparent) is determined. This is assigned as left child to the node. After that, the parent node of the parent node is assigned to the node. And the left child is now assigned the current node as the parent node. At the end, the node, around which was rotated, is returned.

The same takes place analogously in the right rotation.

public Node rotateRight(Node node)
{
    if(node == null)
        return null;

    Node parent = node.getParent();
    parent.setLeft(null);
    node.setRight(parent);
    node.setParent(parent.getParent());
    parent.setParent(node);
    return node;
}

In the left-right rotation, the parent node of the right child is passed. The right one is our median after the rotations which is on top. Again, we first check that the passing node is not a zero. After that, we perform a left rotation on the right child. We simply store the node between and then perform a right rotation to get a balance at the end. We also return the result.

public Node rotateLeftRight(Node node)
{
    if(node == null)
        return null;

    node = rotateLeft(node.getRight());
    return rotateRight(node);
}

Analogous to the left-right rotation we have the matching counterpart in the right-left rotation

public Node rotateRightLeft(Node node)
{
    if(node == null)
         return null;

    node = rotateRight(node.getLeft());
    return rotateLeft(node);
}

I hope I could explain the topic rotations on trees, understandable 😄