AVL Tree

Question 1

What is an AVL Tree

Answer 1

An AVL is a balanced BST. The height of immediate subtrees of any node differs by at most one (also called balance factor)

height of AVL tree is always O(log(n))

If at any time height differ by more than one, rebalancing is done to restore this property(called rotation)

Question 2

Why AVL Tree?

Answer 2

Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that the height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations.

Question 3

Insert in AVL tree

Answer 3

Insert is the same as BST where all the smaller value goes to the left and larger value goes to the right subtree. In addition, there is a check if the height of any node is greater than 1 then it needs rebalancing.

• case 1: if rotation is required (LL, LR, RL, RR)
• case 2: if rotation is not required (same as a BST)

Question 4

Type of rotations in AVL Tree

Answer 4

If at any time height differ by more than one, rebalancing is done to restore this property(called rotation)

• Left Left:
• Left Right
• Right Left
• Right Right

Question 5

Left-Left Rotation Algorithm

Answer 5

Find the grandchild that created the disbalance
If the left child of the left node is creating a disbalance, then need to do a right rotation on the disbalanced node

Algo:
function rightRotate(currentDisbalancedNode) {
	const newRoot = currentDisbalancedNode.left;
	currentDisbalancedNode.left = currentDisbalancedNode.left.right;
	newRoot.right = currentDisbalancedNode;

	// need to update the height of the updated nodes
	currentDisbalancedNode.height = calculateHeight(currentDisbalancedNode);
	newRoot.height = calculateHeight(newRoot);
	return newRoot;
}

Question 6

Insert in AVL Tree Code

Answer 6

insert(node, data) {
    // Same as BST insert method
    const newNode = new Node(data);
    if (this.head === null) {
      this.head = newNode;
      return newNode;
    } 

if (!node) {
  return newNode;
} else if(data <= node.data) {
  node.left = this.insert(node.left, data);
} else if(data > node.data){
  node.right = this.insert(node.right, data);
}

node.height = this.calculateHeight(node);

    // AVL implementation
    const balance = this.getBalance(node);

    // To check the balance four cases are possible 
    // Left subtree is not balanced with insert, resulting in LL, LR rotation
    // right subtree is not balanced with insert resulting in RR, RL rotations
    if (balance > 1) {
      // Left subtree is larger than right subtree
      // disbalanced_node.left.left >  disbalanced_node.left.right then LL otherwise LR
      if (data < node.left.data) {
        // LL rotation
        return this.rotateRight(node);
      } else {
        // LR rotation
        node.left = this.rotateLeft(node.left);
        return this.rotateRight(node);
      }
    } else if(balance < -1) {
      // right subtree is larger than left subtree
      // disbalanced_node.right.right > disbalanced_node.right.left
      if (data > node.right.data) {
        // RR rotation
        return this.rotateLeft(node);
      } else {
        //RL rotation
        node.right = this.rotateRight(node.right);
        return this.rotateLeft(node);
      }
    }

return node;

}

Question 7

Delete in AVL Tree code

Answer 7

delete(node, data) {
    // same as BST delete
    if (!node) return null;

    if (data < node.data){
      // left subtree
      node.left = this.delete(node.left, data);
    } else if (data > node.data) {
      // right subtree
      node.right = this.delete(node.right, data);
    } else {
      // found the node to delete
      // 3 cases: 
      if (!node.left &amp;&amp; !node.right) {
        // case1: node with no child
        return null;
      } else if (!node.left &amp;&amp; node.right){
        // case2: only right child
        // update current node with child node
        node = node.right; 
      } else if (node.left &amp;&amp; !node.right) {
        // case2: only left child
        // update the current node with node.left
        node = node.left;
      } else {
        // case3: node has both left and right child 

        // step1: find the successor(node with minimum value on the right subtree
        const successorNode = this.getSuccessor(node.right);

        // step2: update the node.data with successor node.data
        node.data = successorNode.data;

        // step3: delete the successor node
        node.right = this.delete(node.right, node.data);
      }
    }

    // Update the height of current Node
    node.height = this.calculateHeight(node);

    // check balance of current node
    const balance = this.getBalance(node);

    // balance of tree based on the height of left-subtree - height of right-subtree
    if (balance > 1) {
      // height of Left subtree > height of right subtree
      if (this.getBalance(node.left) >= 0) {
        // LL condition: rotateRight
        return this.rotateRight(node);
      } else {
        //LR condition: rotateLeft(node.left) and rotateRight(node);
        node.left = this.rotateLeft(node.left);
        return this.rotateRight(node);
      }
    } else if (balance < -1) {
      // height of right subtree > height of left subtree
      if (this.getBalance(node.right) <= 0) {
        //RR condition: rotateLeft
        return this.rotateLeft(node);
      } else {
        // RL condition: rotateRight(node.right) and rotateLeft(node)
        node.right = this.rotateRight(node.right);
        return this.rotateLeft(node);
      }
    }

return node;   }