Binary Search Tree 구현

이진탐색트리 시뮬레이션 연습 사이트

visualgo.net/en/bst

 

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

class BinarySearchTree {
  constructor(){
    this.root = null;
  }
  insert(value){
    const newNode = new Node(value);
    if (!this.root) this.root = newNode;
    else {
      let currentNode = this.root;
      while(1) {
       if (value < currentNode.value) {
         if (!currentNode.left) {
           currentNode.left = newNode;
           return this;
         }
         currentNode = currentNode.left;
       } else {
         if (!currentNode.right) {
           currentNode.right = newNode;
           return this;
         }
         currentNode = currentNode.right;
       }
      }
    }
  }
  
  lookup(value){
    if (!this.root) return false;
    let currentNode = this.root;
    while(currentNode) {
      if (value < currentNode.value) currentNode = currentNode.left;
      else if (value > currentNode.value) currentNode = currentNode.right;
      else if (value === currentNode.value) return currentNode;
    }
    return false;
  }
  
  remove(value) {
    if (!this.root) return false;
    let currentNode = this.root;
    let parentNode = null;
    while(currentNode) {
      if (value < currentNode.value) {
        parentNode = currentNode;
        currentNode = currentNode.left;
      } else if (value > currentNode.value) {
        parentNode = currentNode;
        currentNode = currentNode.right;
      } else if (currentNode.value === value) {
        if (!currentNode.right) {
          if (!parentNode) this.root = currentNode.left;
          else {
            if (currentNode.value < parentNode.value) parentNode.left = currentNode.left;
            else if (currentNode.value > parentNode.value) parentNode.right = currentNode.left;
          }
        } else if (!currentNode.right.left) {
          if (!parentNode) this.root = currentNode.left;
          else {
            currentNode.right.left = currentNode.left;
            if (currentNode.value < parentNode.value) parentNode.left = currentNode.right;
            else if (currentNode.value > parentNode.value) parentNode.right = currentNode.right;
          }
        } else {
          let leftmost = currentNode.right.left;
          let leftmostParent = currentNode.right;
          while (leftmost.left) {
            leftmostParent = leftmost;
            leftmost = leftmost.left;
          }
          leftmostParent.left = leftmost.right;
          leftmost.left = currentNode.left;
          leftmost.right = currentNode.right;
          
          if (!parentNode) this.root = leftmost;
          else {
            if (currentNode.value < parentNode.value) parentNode.left = leftmost;
            else if (currentNode.value > parentNode.value) parentNode.right = leftmost;
          }
        }
        return true;
      }
    }
  }
}