A Binary Search Tree implementation in JavaScript (iterative)

BinaryTree.js

/**
 * @description Implementação de uma árvore binária de busca em JavaScript.
 * @author Gabriel Dewes at 13 oct, 2016
 */

/**
 * @constructor
 */
function BinaryTree() {
    /**
     * Ponteiro para a raiz da árvore.
     * @property _root
     * @type {Object}
     * @private
     */
    this._root = null;
}

BinaryTree.prototype = {
  /**
   * Initializes the tree.
   */
  constructor: BinaryTree,

  /**
   * @description Push de um nó na árvore, caso ela esteja vazia
   * este nó passará a ser a raiz (root), se não, inserido na sua
   * devida posição.
   * @param {int} key A chave para ordenar e buscar itens na árvore
   * @param {variant} value Um valor para armazenar no objeto.
   * @return {boolean} True se inseriu, False caso contrário
   * @method push
   */
  push: function (key, value) {
    var node = {
      key: key,
      value: value || {},
      left: null,
      right: null
    },
    // Usado para travessar sob a arvore
    current;

    // Sem itens na árvore ainda
    if (this._root === null) {
      this._root = node;
    }
    else {
      current = this._root;
      while (true) {
        // Se a chave é menor que a deste Nó, vai para esquerda.
        if (key < current.key) {
          // Se não existe nó esquerdo, então é aqui que ele vai ficar.
          if (current.left === null) {
            current.left = node;
            console.debug('_> Push ', node.key, ' at left of ', current.key);
            return true;
          }
          else {
            current = current.left;
          }
        }
        // Se a chave é maior que a deste Nó, vai para direita.
        else if (key > current.key) {
          // Se não existe nó direito, então o novo nó fica aqui.
          if (current.right === null) {
            current.right = node;
            console.debug('_> Push ', node.key, ' at right of ', current.key);
            return true;
          }
          else {
            current = current.right;
          }
        }
        // Se a chave for igual a uma chave existente, apenas ignora.
        else {
          console.debug("! The key ", node.key, " already exists in another node key ", current.key);
          return false;
        }
      }
    }
  },

  /**
   * Remove um nó através de sua chave. Esta ação requer que
   * todos outros nós da árvore sejam rebalanceados apropriadamente.
   * @param {int} key A chave para remover.
   * @return {void}
   * @method remove
   */
  remove: function(key) {
    var found = false,
        parent = null,
        current = this._root,
        childCount,
        replacement,
        replacementParent;

    while (!found && current) {
      if (key < current.key) {
        parent = current;
        current = current.left;
      }
      else if (key > current.key) {
        parent = current;
        current = current.right;
      }
      else {
        found = true;
      }
    }
    if (found) {
      childCount = (current.left !== null ? 1 : 0) + (current.right !== null ? 1 : 0);

      if (current === this._root) {
        switch(childCount) {
          case 0: {
            this._root = null;
            break;
          }
          // Um filho apenas, usa-o como raiz.
          case 1: {
            this._root = (current.right === null ? current.left : current.right);
            break;
          }

          case 2: {
            replacement = this._root.left;

            while (replacement.right !== null){
              replacementParent = replacement;
              replacement = replacement.right;
            }

            if (replacementParent !== null) {
              replacementParent.right = replacement.left;
              replacement.right = this._root.right;
              replacement.left = this._root.left;
            }
            else {
              replacement.right = this._root.right;
            }
            break;
          }
          this._root = replacement;
        }
      }
      else {
        switch (childCount) {
          // Sem filhos, apenas remove do pai.
          case 0: {
            if (current.key < parent.key){
              parent.left = null;
            }
            else {
              parent.right = null;
            }
            break;
          }

          // Um filho, apenas reatribui ao pai.
          case 1: {
            // Se a chave do nó atual for menor que a do pai,
            // apenas reseta o ponteiro do lado esquerdo.
            if (current.key < parent.key){
              parent.left = (current.left === null ? current.right : current.left);
            }
            // Reseta o ponteiro direito caso contrário.
            else {
              parent.right = (current.left === null ? current.right : current.left);
            }
            break;
          }
          // Dois filhos, um pouco mais complicado.
          case 2: {
            // Reseta os ponteiros para nova travessia.
            replacement = current.left;
            replacementParent = current;

            // Procura o máximo nó direito
            while(replacement.right !== null){
              replacementParent = replacement;
              replacement = replacement.right;
            }
            replacementParent.right = replacement.left;
            // Atribui o filho ao nó substituto
            replacement.right = current.right;
            replacement.left = current.left;
            // Posiciona o nó substituto à esquerda
            if (current.key < parent.key){
              parent.left = replacement;
            }
            else {
              parent.right = replacement;
            }
            break;
          }
        }
      }
    }
  },

  /**
   * Percorre a árvore e executa a função proccess para cada nó encontrado.
   * @param {Function} process A função a ser executada em cada nó
   * @return {void}
   * @method traverse
   */
  traverse: function(process) {
    // Tail Recursive function
    function inOrder(node){
      if (node){
        // Percorre a subárvore esquerda
        if (node.left !== null){
          inOrder(node.left);
        }
        // Chamada anônima a função
        process.call(this, node);
        // Percorre o lado direto da subarvore
        if (node.right !== null){
          inOrder(node.right);
        }
      }
    }
    // Começa na raiz
    inOrder(this._root);
  },

  /**
   * Verifica se uma chave existe na árvore
   * @param {int} key A chave para encontrar
   * @return {boolean} True se achar, False caso constrário.
   * @method contains
   */
  contains: function(key) {
    var found = false,
        current = this._root
    while (!found && current) {
      if (key < current.key){
        current = current.left;
      }
      else if (key > current.key){
        current = current.right;
      }
      else {
        found = true;
      }
    }
    return found;
  },

  /**
   * @description Retorna o numero de itens na árvore. Para isso é preciso
   * ser feita uma travessia em toda árvore.
   * @return {int} O número de itens na árvore
   * @method size
   */
  size: function(){
      var count = 0;
      this.traverse(function(node) {
          count++;
      });
      return count;
  },

  /**
   * Converte a árvore em um Array com todos os valores dos nós da árvore.
   * @return {Array} Array contento todos valores dos nós.
   * @method toArray
   */
  toArray: function() {
      var values = [];
      this.traverse(function(node) {
          values.push(node.value);
      });
      return values;
  },

  /**
   * Converte a árvore em um Array com todas as chaves dos nós da árvore.
   * @return {Array} Array contento a chave de cada nó.
   * @method toKeySet
   */
  toKeySet: function() {
      var values = [];
      this.traverse(function(node) {
          values.push(node.key);
      });
      return values;
  },
  toString: function(){
      return this.toArray().toString();
  }
};


var start = Date.now();
var bt = new BinaryTree();

for (let i=0; i<100; i++) {
  bt.push(Math.floor(Math.random()*100 +i));
}

var keySet = bt.toKeySet();
for (let i=0; i<keySet.length; i++) {
  bt.remove(keySet[i]);
}

console.log(bt.toArray());
console.log(bt.toKeySet());
console.log("Elapsed time: "+ (Date.now()-start) +" ms");