AVLTree.js

/**
 * Adelson-Velsky and Landis Tree
 * [Wikipedia](https://en.wikipedia.org/wiki/AVL_tree)
 * [A video lecture](http://www.youtube.com/watch?v=TbvhGcf6UJU)
 */
'use strict'

/**
 * A utility class for comparator
 * A comparator is expected to have following structure
 *
 * comp(a, b) RETURN < 0 if a < b
 * RETURN > 0 if a > b
 * MUST RETURN 0 if a == b
 */
let utils
;(function (_utils) {
  function comparator() {
    return function (v1, v2) {
      if (v1 < v2) return -1
      if (v2 < v1) return 1
      return 0
    }
  }
  _utils.comparator = comparator
})(utils || (utils = {}))

/**
 * @constructor
 * A class for AVL Tree
 * @argument comp - A function used by AVL Tree For Comparison
 * If no argument is sent it uses utils.comparator
 */
class AVLTree {
  constructor(comp) {
    /** @public comparator function */
    this._comp = undefined
    this._comp = comp !== undefined ? comp : utils.comparator()

    /** @public root of the AVL Tree */
    this.root = null
    /** @public number of elements in AVL Tree */
    this.size = 0
  }

  /* Public Functions */
  /**
   * For Adding Elements to AVL Tree
   * @param {any} _val
   * Since in AVL Tree an element can only occur once so
   * if a element exists it return false
   * @returns {Boolean} element added or not
   */
  add(_val) {
    const prevSize = this.size
    this.root = insert(this.root, _val, this)
    return this.size !== prevSize
  }

  /**
   * TO check is a particular element exists or not
   * @param {any} _val
   * @returns {Boolean} exists or not
   */
  find(_val) {
    const temp = searchAVLTree(this.root, _val, this)
    return temp != null
  }

  /**
   *
   * @param {any} _val
   * It is possible that element doesn't exists in tree
   * in that case it return false
   * @returns {Boolean} if element was found and deleted
   */
  remove(_val) {
    const prevSize = this.size
    this.root = deleteElement(this.root, _val, this)
    return prevSize !== this.size
  }
}

// creates new Node Object
class Node {
  constructor(val) {
    this._val = val
    this._left = null
    this._right = null
    this._height = 1
  }
}

// get height of a node
const getHeight = function (node) {
  if (node == null) {
    return 0
  }
  return node._height
}

// height difference or balance factor of a node
const getHeightDifference = function (node) {
  return node == null ? 0 : getHeight(node._left) - getHeight(node._right)
}

// update height of a node based on children's heights
const updateHeight = function (node) {
  if (node == null) {
    return
  }
  node._height = Math.max(getHeight(node._left), getHeight(node._right)) + 1
}

// Helper: To check if the balanceFactor is valid
const isValidBalanceFactor = (balanceFactor) =>
  [0, 1, -1].includes(balanceFactor)

// rotations of AVL Tree
const leftRotate = function (node) {
  const temp = node._right
  node._right = temp._left
  temp._left = node
  updateHeight(node)
  updateHeight(temp)
  return temp
}
const rightRotate = function (node) {
  const temp = node._left
  node._left = temp._right
  temp._right = node
  updateHeight(node)
  updateHeight(temp)
  return temp
}

// check if tree is balanced else balance it for insertion
const insertBalance = function (node, _val, balanceFactor, tree) {
  if (balanceFactor > 1 && tree._comp(_val, node._left._val) < 0) {
    return rightRotate(node) // Left Left Case
  }
  if (balanceFactor < 1 && tree._comp(_val, node._right._val) > 0) {
    return leftRotate(node) // Right Right Case
  }
  if (balanceFactor > 1 && tree._comp(_val, node._left._val) > 0) {
    node._left = leftRotate(node._left) // Left Right Case
    return rightRotate(node)
  }
  node._right = rightRotate(node._right)
  return leftRotate(node)
}

// check if tree is balanced after deletion
const delBalance = function (node) {
  const balanceFactor1 = getHeightDifference(node)
  if (isValidBalanceFactor(balanceFactor1)) {
    return node
  }
  if (balanceFactor1 > 1) {
    if (getHeightDifference(node._left) >= 0) {
      return rightRotate(node) // Left Left
    }
    node._left = leftRotate(node._left)
    return rightRotate(node) // Left Right
  }
  if (getHeightDifference(node._right) > 0) {
    node._right = rightRotate(node._right)
    return leftRotate(node) // Right Left
  }
  return leftRotate(node) // Right Right
}

// implement avl tree insertion
const insert = function (root, val, tree) {
  if (root == null) {
    tree.size++
    return new Node(val)
  }
  if (tree._comp(root._val, val) < 0) {
    root._right = insert(root._right, val, tree)
  } else if (tree._comp(root._val, val) > 0) {
    root._left = insert(root._left, val, tree)
  } else {
    return root
  }
  updateHeight(root)
  const balanceFactor = getHeightDifference(root)
  return isValidBalanceFactor(balanceFactor)
    ? root
    : insertBalance(root, val, balanceFactor, tree)
}

// delete am element
const deleteElement = function (root, _val, tree) {
  if (root == null) {
    return root
  }
  if (tree._comp(root._val, _val) === 0) {
    // key found case
    if (root._left === null && root._right === null) {
      root = null
      tree.size--
    } else if (root._left === null) {
      root = root._right
      tree.size--
    } else if (root._right === null) {
      root = root._left
      tree.size--
    } else {
      let temp = root._right
      while (temp._left != null) {
        temp = temp._left
      }
      root._val = temp._val
      root._right = deleteElement(root._right, temp._val, tree)
    }
  } else {
    if (tree._comp(root._val, _val) < 0) {
      root._right = deleteElement(root._right, _val, tree)
    } else {
      root._left = deleteElement(root._left, _val, tree)
    }
  }
  updateHeight(root)
  root = delBalance(root)
  return root
}
// search tree for a element
const searchAVLTree = function (root, val, tree) {
  if (root == null) {
    return null
  }
  if (tree._comp(root._val, val) === 0) {
    return root
  }
  if (tree._comp(root._val, val) < 0) {
    return searchAVLTree(root._right, val, tree)
  }
  return searchAVLTree(root._left, val, tree)
}

/**
 * A Code for Testing the AVLTree
 */
// (function test () {
//   const newAVL = new AVLTree()
//   const size = Math.floor(Math.random() * 1000000)
//   let uniques = 0
//   let i, temp, j
//   const array = []
//   for (i = 0; i < size; i++) {
//     temp = Math.floor(Math.random() * Number.MAX_VALUE)
//     if (newAVL.add(temp)) {
//       uniques++
//       array.push(temp)
//     }
//   }
//   if (newAVL.size !== uniques) {
//     throw new Error('elements not inserted properly')
//   }
//   const findTestSize = Math.floor(Math.random() * uniques)
//   for (i = 0; i < findTestSize; i++) {
//     j = Math.floor(Math.random() * uniques)
//     if (!newAVL.find(array[j])) {
//       throw new Error('inserted elements not found')
//     }
//   }
//   const deleteTestSize = Math.floor(uniques * Math.random())
//   for (i = 0; i < deleteTestSize; i++) {
//     j = Math.floor(Math.random() * uniques)
//     temp = array[j]
//     if (newAVL.find(temp)) {
//       if (!newAVL.remove(temp)) {
//         throw new Error('delete not working properly')
//       }
//     }
//   }
// })()

export { AVLTree }