CODEWITHSUNDEEP
typescriptdata-structurestreeavl-tree
M. Nicol
M. Nicol

Reputation: 123

How to identify double rotations in a AVL Tree when each node stores the deepest subtree beneath it?

I am working on an AVL tree such that each Node holds the deepest sub-tree beneath it. Here is an example of the tree, where the representation is value: height.

0: 2
 \
  1: 1
   \
    2: 0

To check the balance, I used the following function given an AVL Tree node or undefined. Following code snippet is written in TypeScript. The formula used is left - right depth, with undefined child nodes returning -1.

private balanceFactor(currentNode: AVLTreeNode<E> | undefined): number {
    if (currentNode === undefined) {
      return -1;
    }
    let leftHeight = currentNode.hasLeft() ? currentNode.getLeft().getHeight() : -1;
    let rightHeight = currentNode.getRight() ? currentNode.getRight().getHeight() : -1;
    return leftHeight - rightHeight
}

To implement the logic code of the rotations, I found a previous stack post: https://stackoverflow.com/a/19281663/10448256

The post deals the following logic for the double rotations:

balance(N) = Depth(Nleft) - Depth(Nright)

if (balance(P) > 1) {
    if (balance(L) < 0) {
        rotate_left(L);
    }
    rotate_right(P);
}
else if (balance(P) < -1) {
    if (balance(R) > 0) {
        rotate_right(R); 
    }
    rotate_left(P);      
}

Consider the following double rotation scenario:


    2: 2
   /
  1: 1
   \
    0: 0

When the balance factor is called on node 2, it creates a BF of two (2 - 0), and since the right is undefined, the balance factor of the right is -1. This results in a double rotation, correctly creating the following tree:

         1: 1
      /       \
    0: 0     2: 0

While the double rotation works, it does not allow for single rotations. If the first example is tried again:

2: 2
 \
  1: 1
   \
    0: 0

It creates a balance factor of 2 at value 2, where the left node is a -1 because it is undefined, incorrectly resulting in a double rotation detection.

What logic should I use to identify the difference between double and single rotations?

Upvotes: 0

Views: 316

Answers (1)

trincot
trincot

Reputation: 350270

The logic that is implemented in the code you found in a related question is correct.

While the double rotation works, it does not allow for single rotations.

The inner if condition in the referenced code determines whether a double or single rotation should occur.

If the first example is tried again:

2: 2
 \
  1: 1
   \
    0: 0

It creates a balance factor of 2 at value 2, where the left node is a -1 because it is undefined, incorrectly resulting in a double rotation detection.

This is due to an error in your balanceFactor function. When a node is absent, you have there an empty tree. Such a tree is balanced. There is no good reason to return -1 in that case as if that empty tree is out of balance. You should return 0:

private balanceFactor(currentNode: AVLTreeNode<E> | undefined): number {
    if (currentNode === undefined) {
      return 0; // Correction
    }
    let leftHeight = currentNode.hasLeft() ? currentNode.getLeft().getHeight() : -1;
    let rightHeight = currentNode.getRight() ? currentNode.getRight().getHeight() : -1;
    return leftHeight - rightHeight
}

Remark: it is not efficient to call getHeight in the process of determining the balance factor. This can be done incrementally without the need to know a node's height. See for instance this implementation which uses a lookup table (matrix) for the balance factors found in the two nodes that participate in a rotation, giving the new balance factors for those nodes.

Upvotes: 0

Related Questions