Algorithms #5: AVL Tree using JavaScript

Wednesday, May 1st, 2019

Motivation

When a binary tree is created it has an edge case where the search for a node can take up to O(n). If all the nodes are in ascending/descending order, then the program needs to traverse the depth of the tree before finding the desired node this is not efficient. To prevent this issue the binary search tree can be balanced each time any deletion or insertion is made so the worst-case search complexity will be O(logn).

Approach

For the AVL tree to be always balanced it needs to have auto-balancing mechanism. This auto-balancing mechanism consists of a set of rotations that rotate the nodes to achieve a balanced tree after each node insertion or deletion. Apart from rotations the insertion and deletion work same as binary search tree.

Left-Left Heavy(Right Rotation)

Right rotation is basically used if the node's left subtree is left heavy

Right-Right Heavy(Left Rotation)

Left rotation is basically used if the node's right subtree is right heavy

Left-Right Heavy(Left-Right Rotation)

The right-left rotation is used if the node is left heavy and the left sub-tree is right heavy.

Right-Left Heavy(Right-Left Rotation)

The left-right rotation is used if the node is right heavy and the right sub-tree is left heavy.

Implementation

class Node{
height;
value;
left;
right;

constructor(value, height){
  this.value = value;
  this.height = height;
}
}


class AVLTree{
  constructor(){
      this.queue = [];
      this.rootNode = undefined;
  }

  getHeight = (node) =>{
    if(node === undefined){
      return -1;
    }

    return node.height;
  }

  insertNode = (node, value) =>{
      if(node === undefined){
          node = new Node(value, 0);
          return node;
      }else if(value<node.value){
          node.left = this.insertNode(node.left, value);
          this.queue.push(node);
          return node;
      }else{
          node.right = this.insertNode(node.right, value);
          this.queue.push(node);
          return node;
      }
  }

  rotateRight = (node) =>{

    let node_left_subtree = node.left;
    let node_left_subtree_right = node.left.right;

    node_left_subtree.right = node;
    node.left = node_left_subtree_right;

    node.height = Math.max(this.getHeight(node.right),this.getHeight(node.left))+1;
    node_left_subtree.height = Math.max(this.getHeight(node_left_subtree.right), this.getHeight(node_left_subtree.left))+1;

    if(this.queue.length === 0){
      root = node_left_subtree;
    }else{
      let parentNode = this.queue[0];
      if(parentNode.right === node){
          parentNode.right = node_left_subtree;
      }else if(parentNode.left === node){
          parentNode.left = node_left_subtree;
      }
    }
  }

  clearQueue(){
      this.queue = [];
  }

  rotateLeft  = (node, parentNode) => {

    let node_right_subtree = node.right;
    let node_right_subtree_left = node.right.left;

    node_right_subtree.left = node;
    node.right = node_right_subtree_left;

    node.height = Math.max(this.getHeight(node.right),this.getHeight(node.left))+1;
    node_right_subtree.height = Math.max(this.getHeight(node_right_subtree.right), this.getHeight(node_right_subtree.left))+1;

    if(this.queue.length === 0){
        root = node_right_subtree;
    }else{
      let parentNode = this.queue[0];
      if(parentNode.right === node){
          parentNode.right = node_right_subtree;
      }else if(parentNode.left === node){
          parentNode.left = node_right_subtree;
      }
    }
  }

  printTree = (node) => {
    if (node === undefined)
      return;
    this.printTree(node.left);
    console.log(node.value + " " + node.height);
    this.printTree(node.right);
  }

  balanceHeight = () => {
    while(this.queue.length>0){

        let node = this.queue.shift();
        let leftHeight = this.getHeight(node.left);
        let rightHeight = this.getHeight(node.right);

        if(Math.abs(leftHeight-rightHeight)<=1){//balanced
            node.height = Math.max(leftHeight, rightHeight)+1;
        }else{

             if(rightHeight>leftHeight)//node is right heavy
             {
                 let leftRightHeight =this.getHeight(node.right.left);
                 let rightRightHeight =this.getHeight(node.right.right);
                 if(rightRightHeight>=leftRightHeight)//node is right heavy and its right child right heavy or balanced
                  this.rotateLeft(node);
                 else//node is right heavy and its right child is left heavy
                 {
                     this.rotateRight(node.right);
                     this.rotateLeft(node);
                 }
             }
             else
             {
                 let leftLeftHeight=this.getHeight(node.left.left);
                 let leftRightHeight=this.getHeight(node.left.right);
                 if(leftLeftHeight>=leftRightHeight)//node is left heavy and its left child is left heavy or balanced
                  this.rotateRight(node);
                 else//node is left heavy and its left child is right heavy
                 {
                     this.rotateLeft(node.left);
                     this.rotateRight(node);
                 }
             }
        }

    }

  }
}


///usage
let avlTree = new AVLTree();

console.log(avlTree)

let root=avlTree.insertNode(undefined,2);
avlTree.balanceHeight();
avlTree.clearQueue();
root= avlTree.insertNode(root,4);
avlTree.balanceHeight();
avlTree.clearQueue();
root= avlTree.insertNode(root,6);
avlTree.balanceHeight();
avlTree.clearQueue();
root= avlTree.insertNode(root,8);
avlTree.balanceHeight();
avlTree.clearQueue();
root= avlTree.insertNode(root,10);
avlTree.balanceHeight();
avlTree.clearQueue();
avlTree.printTree(root);

In the above implementation if a node does not have a child then its height is 0 if it has only 1 generation of children then height is 1 but if the node is a grand parent on either left of right side then its height is 2. So the height of a node depends on the maximum depth of its children/descendants. After a node is inserted the code balances the whole tree. When the code is run it inserts 2, 4, 6, 8, 10 in that order. If this were a simple binary search tree then there would be nodes only on the right. In this case AVL tree will balance the tree as nodes are inserted so the final structure of the tree will be balanced like:

In the output the heights of nodes are 4(height=2), 2(height=0), 8(height=1), 6(height=0), 10(height=0).

💡 Practice Coding

Practice coding questions from top companies like Google, Amazon, Apple, and others. Signup today at Softnami's daily coding.