AVL Tree

The AVL Tree is one of Binary Search Tree with self balance mechanism. To prevent tree become out of balance, AVL Tree detect the depth of the node and decide whether to balance or not after adding new node.

Three ways to balance

Left rotation

Make the tree rotate to left. Typically happens when the amount of the right children are larger than left, so need to move the node to the left.

Right rotation

Make the tree rotate to right. Typically happens when the amount of the left children are larger than right, so need to move the node to the right.

Double rotation

Before doing the right rotation we need to check the amount of children of left right node is large than the left left node. We need to do left rotation first on the left node, and then do right rotation to self node after that.

In contrast, before doing the left rotation we need to check the amount of children of right left node is large than the right right node. If is larger, we need to do right rotation first at the right node and then do left rotation on self after.

Implementation

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

  add(value) {
    if (this.value > value) {
      // go left

      if (this.left) {
        this.left.add(value)
      } else {
        this.left = new Node(value)
      }

      if (!this.right || this.left.height > this.right.height){
        this.height = this.left.height + 1
      }


    } else {
      // go  right

      if (this.right) {
        this.right.add(value)
      } else {
        this.right = new Node(value)
      }

      if (!this.left || this.right.height > this.left.height){
        this.height = this.right.height + 1
      }

    }

    this._balance()
  }

  _balance() {
    const leftHeight = this.left ? this.left.height : 0
    const rightHeight = this.right ? this.right.height : 0

    if (leftHeight > rightHeight + 1) {
      // leftSide balance
      const leftLeftHeight = this.left.left ? this.left.left.height : 0
      const leftRightHeight = this.left.right ? this.left.right.height : 0

      if (leftRightHeight > leftLeftHeight) {
        // left rotate
        this.left._leftRotate()
      }

      // right rotate
      this._rightRotate()

    } else if (rightHeight > leftHeight + 1) {
      // rightSide balance
      const rightLeftHeight = this.right.left ? this.right.left.height : 0
      const rightRightHeight = this.right.right ? this.right.right.height : 0

      if (rightLeftHeight > rightRightHeight) {
        // right rotate
        this.right._rightRotate()
      }

      // left rotate
      this._leftRotate()
    }

  }


  _leftRotate() {
    const originRootValue = this.value
    const originLeft = this.left

    this.value = this.right.value
    this.left = this.right
    this.right = this.right.right
    this.left.value = originRootValue
    this.left.right = this.left.left
    this.left.left = originLeft

    this.left.updateHeight()
    this.updateHeight()

  }

  _rightRotate() {
    const origintRootValue = this.value
    const originRight = this.right
    this.value = this.left.value
    this.right = this.left
    this.left = this.left.left
    this.right.value = origintRootValue

    this.right.left = this.right.right
    this.right.right = originRight

    this.right.updateHeight()
    this.updateHeight()

  }

  updateHeight(){
    if (!this.left && !this.right){
      this.height = 1
    } else if (!this.right || this.left  && this.left.height > this.right.height){
      this.height = this.left.height + 1
    } else if (!this.left || this.right && this.right.height > this.left.height) {
      this.height = this.rigth.height + 1
    }

  }

}

class AVLTree {
  constructor() {
    this.root = null
    this.checkQueue = []
  }

  add(value) {
    const newNode = new Node(value)

    if (!this.root) {
      this.root = newNode
    } else {
      this.root.add(value)
    }
  }

}