AVL Tree

An AVL tree defined as a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees for any node cannot be more than one.

The difference between the heights of the left subtree and the right subtree for any node is known as the balance factor of the node.

The AVL tree is named after its inventors, Georgy Adelson-Velsky and Evgenii Landis, who published it in their 1962 paper “An algorithm for the organization of information”.

The above tree is AVL because the differences between the heights of left and right subtrees for every node are less than or equal to 1.

Rotating the subtrees in an AVL Tree:

An AVL tree may rotate in one of the following four ways to keep itself balanced:

Left Rotation:

When a node is added into the right subtree of the right subtree, if the tree gets out of balance, we do a single left rotation.

Right Rotation:

If a node is added to the left subtree of the left subtree, the AVL tree may get out of balance, we do a single right rotation.

Left-Right Rotation:

A left-right rotation is a combination in which first left rotation takes place after that right rotation executes.

Right-Left Rotation:

A right-left rotation is a combination in which first right rotation takes place after that left rotation executes.

Applications :

1. It is used to index huge records in a database and also to efficiently search in that.

2. For all types of in-memory collections, including sets and dictionaries, AVL Trees are used.

3. Database applications, where insertions and deletions are less common but frequent data lookups are necessary

4. Software that needs optimized search.

5. It is applied in corporate areas and storyline games.

Advantages :

1. AVL trees can self-balance themselves.

2. It is surely not skewed.

3. It provides faster lookups than Red-Black Trees

4. Better searching time complexity compared to other trees like binary tree.

5. Height cannot exceed log(N), where, N is the total number of nodes in the tree.

Disadvantages :

1. It is difficult to implement.

2. It has high constant factors for some of the operations.

3. Less used compared to Red-Black trees.

4. Due to its rather strict balance, AVL trees provide complicated insertion and removal operations as more rotations are performed.

5. Take more processing for balancing.

class AVLNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
    this.height = 1;
  }
}

class AVLTree {
  constructor() {
    this.root = null;
  }

  getHeight(node) {
    if (!node) return 0;
    return node.height;
  }

  getBalanceFactor(node) {
    if (!node) return 0;
    return this.getHeight(node.left) - this.getHeight(node.right);
  }

  rotateRight(y) {
    const x = y.left;
    const T2 = x.right;

    // Perform rotation
    x.right = y;
    y.left = T2;

    // Update heights
    y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1;
    x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1;

    return x;
  }

  rotateLeft(x) {
    const y = x.right;
    const T2 = y.left;

    // Perform rotation
    y.left = x;
    x.right = T2;

    // Update heights
    x.height = Math.max(this.getHeight(x.left), this.getHeight(x.right)) + 1;
    y.height = Math.max(this.getHeight(y.left), this.getHeight(y.right)) + 1;

    return y;
  }

  insert(value) {
    this.root = this._insertNode(this.root, value);
  }

  _insertNode(node, value) {
    if (!node) {
      return new AVLNode(value);
    }

    if (value < node.value) {
      node.left = this._insertNode(node.left, value);
    } else if (value > node.value) {
      node.right = this._insertNode(node.right, value);
    } else {
      // Duplicate values not allowed
      return node;
    }

    // Update height of current node
    node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));

    // Get the balance factor and balance the tree if necessary
    const balanceFactor = this.getBalanceFactor(node);

    // Left Left Case
    if (balanceFactor > 1 && value < node.left.value) {
      return this.rotateRight(node);
    }
    // Right Right Case
    if (balanceFactor < -1 && value > node.right.value) {
      return this.rotateLeft(node);
    }
    // Left Right Case
    if (balanceFactor > 1 && value > node.left.value) {
      node.left = this.rotateLeft(node.left);
      return this.rotateRight(node);
    }
    // Right Left Case
    if (balanceFactor < -1 && value < node.right.value) {
      node.right = this.rotateRight(node.right);
      return this.rotateLeft(node);
    }

    return node;
  }

  remove(value) {
    this.root = this._removeNode(this.root, value);
  }

  _removeNode(node, value) {
    if (!node) return null;

    if (value < node.value) {
      node.left = this._removeNode(node.left, value);
    } else if (value > node.value) {
      node.right = this._removeNode(node.right, value);
    } else {
      // Node with only one child or no child
      if (!node.left || !node.right) {
        const tempNode = node.left ? node.left : node.right;
        if (!tempNode) {
          node = null;
        } else {
          node = tempNode;
        }
      } else {
        // Node with two children
        const tempNode = this._findMinNode(node.right);
        node.value = tempNode.value;
        node.right = this._removeNode(node.right, tempNode.value);
      }
    }

    if (!node) return node;

    // Update height of current node
    node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));

    // Get the balance factor and balance the tree if necessary
    const balanceFactor = this.getBalanceFactor(node);

    // Left Left Case
    if (balanceFactor > 1 && this.getBalanceFactor(node.left) >= 0) {
      return this.rotateRight(node);
    }
    // Right Right Case
    if (balanceFactor < -1 && this.getBalanceFactor(node.right) <= 0) {
      return this.rotateLeft(node);
    }
    // Left Right Case
    if (balanceFactor > 1 && this.getBalanceFactor(node.left) < 0) {
      node.left = this.rotateLeft(node.left);
      return this.rotateRight(node);
    }
    // Right Left Case
    if (balanceFactor < -1 && this.getBalanceFactor(node.right) > 0) {
      node.right = this.rotateRight(node.right);
      return this.rotateLeft(node);
    }

    return node;
  }

  _findMinNode(node) {
    while (node && node.left !== null) {
      node = node.left;
    }
    return node;
  }

  search(value) {
    return this._searchNode(this.root, value);
  }

  _searchNode(node, value) {
    if (!node) return false;
    if (node.value === value) return true;
    if (value < node.value) {
      return this._searchNode(node.left, value);
    } else {
      return this._searchNode(node.right, value);
    }
  }

  reverse() {
    this.root = this._reverseNode(this.root);
  }

  _reverseNode(node) {
    if (!node) return null;

    const temp = node.left;
    node.left = this._reverseNode(node.right);
    node.right = this._reverseNode(temp);

    return node;
  }

  insertAt(value, index) {
    // Not supported in AVL tree
    console.log("Insertion at index not supported in AVL tree.");
  }

  removeAt(index) {
    // Not supported in AVL tree
    console.log("Removal at index not supported in AVL tree.");
  }

  printList() {
    this._inOrderTraversal(this.root);
  }

  _inOrderTraversal(node) {
    if (node !== null) {
      this._inOrderTraversal(node.left);
      console.log(node.value);
      this._inOrderTraversal(node.right);
    }
  }
}

// Example usage:
const avlTree = new AVLTree();
avlTree.insert(10);
avlTree.insert(5);
avlTree.insert(15);
avlTree.insert(3);
avlTree.insert(7);
avlTree.insert(12);
avlTree.insert(17);
avlTree.printList(); // Output: 3, 5, 7, 10, 12, 15, 17

console.log(avlTree.search(10)); // Output: true
console.log(avlTree.search(20)); // Output: false

avlTree.remove(12);
avlTree.printList(); // Output: 3, 5, 7, 10, 15, 17