AVL Tree in Javascript

In this tutorial, we will learn what is an AVL Tree and how to implement it in Javascript.

AVL tree is a self-balancing Binary Search Tree (BST) where the heights of the two child subtrees of any node cannot differ by more than one. If at any time they differ by more than one, rebalancing is done to restore this property.

Named after its inventors, Georgy Adelson-Velsky and Evgenii Landis, the two soviet inventors, who first published it in their 1962 paper “An algorithm for the organization of information”.

Why AVL Tree was invented?.

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. In the case of skewed binary tree the cost of these operations may become O(n).

In order to make sure that the upper bound of these operations to remain O(Logn), we will have to make sure that the height of the tree remains O(Logn) after every insertion and deletion.

Thus AVL tree is invented which make sure the height of tree is always O(Logn) where n is the number of nodes in the tree.

Balance factor

In AVL tree each node maintains extra information called a balance factor whose value is either -1, 0 or +1.

Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of the right subtree of that node.

Balance Factor = (Height of Left Subtree - Height of Right Subtree) or (Height of Right Subtree - Height of Left Subtree)

The self balancing property of an avl tree is maintained by the balance factor. The value of balance factor should always be -1, 0 or +1.

Following is the example of AVL Tree.

Operations on AVL Tree

There are various operations that are performed on the AVL tree.

Rotating the subtrees in an AVL Tree

There are two type of rotations using which we can interchange the positions of the nodes of a subtree.

Left Rotate

In left-rotation, the arrangement of the nodes on the right is transformed into the arrangements on the left node.

Steps

1. Initial tree

2. If y has a left subtree, assign x as the parent of the left subtree of y.

3.If the parent of x is NULL, make y as the root of the tree.
4.Else if x is the left child of p, make y as the left child of p.
5.Else assign y as the right child of p.

6. Make y as the parent of x.

---

Right Rotate

In left-rotation, the arrangement of the nodes on the left is transformed into the arrangements on the right node.

Steps:
1. Initial tree.

2.If x has a right subtree, assign y as the parent of the right subtree of x.

3.If the parent of y is NULL, make x as the root of the tree.
4.Else if y is the right child of its parent p, make x as the right child of p.
5.Else assign x as the left child of p.

6.Make x as the parent of y.

---

Left-Right and Right-Left Rotation

Left-Right Rotation

In left-right rotation, the arrangements are first shifted to the left and then to the right.

1. Do left rotation on x-y.

2. Do right rotation on y-z.

---

Right-Left Rotation

In right-left rotation, the arrangements are first shifted to the right and then to the left.

1. Do right rotation on x-y.

2. Do left rotation on z-y.

---

Inserting a node in AVL Tree.

A new Node is always inserted as a leaf node with balance factor equal to 0.

1. Initial tree with the new node that has to be inserted.

2. Go to the appropriate leaf node to insert a using the following recursive steps. Compare newKey with rootKey of the current tree.

• If newKey < rootKey, recur insertion algorithm on the left subtree of the current node until the leaf node is reached.
• Else if newKey > rootKey, recur insertion algorithm on the right subtree of current node until the leaf node is reached.
• Else, return leafNode.

3. Compare leafKey obtained from the above steps with newKey.

• If newKey < leafKey, make newNode as the leftChild of leafNode.
• Else, make newNode as rightChild of leafNode.

4. Update balanceFactor of the nodes.

5. If the nodes are unbalanced, then rebalance the node.

5.1. If balanceFactor > 1, it means the height of the left subtree is greater than that of the right subtree. So, do a right rotation or left-right rotation.

• If newNodeKey < leftChildKey do right rotation.
• Else, do left-right rotation.

5.2. If balanceFactor < -1, it means the height of the right subtree is greater than that of the left subtree. So, do right rotation or right-left rotation.

• If newNodeKey > rightChildKey do left rotation.
• Else, do right-left rotation.

---

Removing a node from AVL Tree.

A node is always deleted as a leaf node. After deleting a node, the balance factors of the nodes get changed. In order to rebalance the balance factor, suitable rotations are performed.

1. Locate nodeToBeDeleted recursively.

2. There are three cases for deleting a node:

• If nodeToBeDeleted is the leaf node, then remove nodeToBeDeleted directly.
• If nodeToBeDeleted has one child, then substitute the contents of nodeToBeDeleted with that of the child. Remove the child.
• If nodeToBeDeleted has two children, find the inorder successor of nodeToBeDeleted (ie. node with a minimum value of key in the right subtree).

3. Find the successor node

4. Remove the current node

5. Update the balanceFactor.

6. Rebalance the tree if the balance factor of any of the nodes is not equal to -1, 0 or 1.
6.1. If balanceFactor of currentNode > 1,

• If balanceFactor of leftChild >= 0, do right rotation.
• Else do left-right rotation.

5.2. If balanceFactor of currentNode < -1,

• If balanceFactor of rightChild <= 0, do left rotation.
• Else do right-left rotation.

---

Complete code of AVL Tree in Javascript.

// Create node
const Node = function(item){
  this.item = item;
  this.height = 1;
  this.left = null;
  this.right = null;
}

//AVL Tree
const AVLTree = function(){
  let root = null;
  
  //return height of the node
  this.height = (N) => {
    if (N === null){
      return 0;
    }
    
    return N.height;
  }
  
  //right rotate
  this.rightRotate = (y) => {
    let x = y.left;
    let T2 = x.right;
    x.right = y;
    y.left = T2;
    y.height = Math.max(this.height(y.left), this.height(y.right)) + 1;
    x.height = Math.max(this.height(x.left), this.height(x.right)) + 1;
    return x;
  }
  
  //left rotate
  this.leftRotate = (x) => {
    let y = x.right;
    let T2 = y.left;
    y.left = x;
    x.right = T2;
    x.height = Math.max(this.height(x.left), this.height(x.right)) + 1;
    y.height = Math.max(this.height(y.left), this.height(y.right)) + 1;
    return y;
  }
  
  // get balance factor of a node
  this.getBalanceFactor = (N) => {
    if (N == null){
      return 0;
    }
    
    return this.height(N.left) - this.height(N.right);
  }
  
  
  // helper function to insert a node
  const insertNodeHelper = (node, item) => {

    // find the position and insert the node
    if (node === null){
      return (new Node(item));
    }
    
    if (item < node.item){
      node.left = insertNodeHelper(node.left, item);
    }else if (item > node.item){
      node.right = insertNodeHelper(node.right, item);
    }else{
      return node;
    }
    
    // update the balance factor of each node
    // and, balance the tree
    node.height = 1 + Math.max(this.height(node.left), this.height(node.right));
    
    let balanceFactor = this.getBalanceFactor(node);
    
    if (balanceFactor > 1) {
      if (item < node.left.item) {
        return this.rightRotate(node);
      } else if (item > node.left.item) {
        node.left = this.leftRotate(node.left);
        return this.rightRotate(node);
      }
    }
    
    if (balanceFactor < -1) {
      if (item > node.right.item) {
        return this.leftRotate(node);
      } else if (item < node.right.item) {
        node.right = this.rightRotate(node.right);
        return this.leftRotate(node);
      }
    }
    
    return node;
  }
  
  // insert a node
  this.insertNode = (item) => {
    // console.log(root);
    root = insertNodeHelper(root, item);
  }
  
  //get node with minimum value
  this.nodeWithMimumValue = (node) => {
    let current = node;
    while (current.left !== null){
      current = current.left;
    }
    return current;
  }
  
  // delete helper
  const deleteNodeHelper = (root, item) => {

    // find the node to be deleted and remove it
    if (root == null){
      return root;
    }
    if (item < root.item){
      root.left = deleteNodeHelper(root.left, item);
    }else if (item > root.item){
      root.right = deleteNodeHelper(root.right, item);
    }else {
      if ((root.left === null) || (root.right === null)) {
        let temp = null;
        if (temp == root.left){
          temp = root.right;
        }else{
          temp = root.left;
        }
        
        if (temp == null) {
          temp = root;
          root = null;
        } else{
          root = temp;
        }
      } else {
        let temp = this.nodeWithMimumValue(root.right);
        root.item = temp.item;
        root.right = deleteNodeHelper(root.right, temp.item);
      }
    }
    if (root == null){
      return root;
    }

    // Update the balance factor of each node and balance the tree
    root.height = Math.max(this.height(root.left), this.height(root.right)) + 1;
    
    let balanceFactor = this.getBalanceFactor(root);
    if (balanceFactor > 1) {
      if (this.getBalanceFactor(root.left) >= 0) {
        return this.rightRotate(root);
      } else {
        root.left = this.leftRotate(root.left);
        return this.rightRotate(root);
      }
    }
    if (balanceFactor < -1) {
      if (this.getBalanceFactor(root.right) <= 0) {
        return this.leftRotate(root);
      } else {
        root.right = this.rightRotate(root.right);
        return this.leftRotate(root);
      }
    }
    return root;
  }
  
  //delete a node
  this.deleteNode = (item) => {
    root = deleteNodeHelper(root, item);
  }
  
  // print the tree in pre - order
  this.preOrder = () => {
    preOrderHelper(root);
  }
  
  const preOrderHelper = (node) => {
    if (node) {
      console.log(node.item);
      preOrderHelper(node.left);
      preOrderHelper(node.right);
    }
  }
}

Insert:
w AVLTree();
tree.insertNode(33);
tree.insertNode(13);
tree.insertNode(53);
tree.insertNode(9);
tree.insertNode(21);
tree.insertNode(61);
tree.insertNode(8);
tree.insertNode(11);
tree.preOrder();
tree.deleteNode(13);
console.log("After Deletion: ");
tree.preOrder();

Output:
33
13
9
8
11
21
53
61
"After Deletion: "
33
9
8
21
11
53
61

---

Time complexity of AVL Tree