1-3. Delete

사실 이 메소드는 강의에는 없었지만 내가 직접 만들어보기로 했다. 그리고 해냈다!! 직인다 진짜.

그럼 로직을 살펴보자.

BST delete pesudocode

-- accepts the value

-- use find method to remove the value

• assign the found node to variable(found)
• if found is the leaf, simply remove it.
• otherwise, always go for the minimum child among the children on the right node.
• if there is no children on the right node, then chose the maximum child among the children on the left node.
• then swap found with chosen child.
• then cut leaf.

자르려는 node가 왼쪽 오른쪽 2개의 자식을 가지고 있을때 무조건 오른쪽 노드중에서 가장 작은 노드를 선택해서 swap한다음 자르면 됨.

delete(val) {
  if (!this.root) return undefined;
  if (this.root.left === null && this.root.right === null)
    return (this.root = null);

  // it is amazing!
  // unpacking trees Object into let current and parent.
  // and var name has to be the same with returned object's key
  // and if result of this.find(Val) is undefined then it will spit error as it can't put undefined into {var}
  let { current, parent } = this.find(val);

  function cutLeaf(parent, current) {
    if (parent.right === null) {
      parent.left = null;
    } else if (parent.left === null) {
      parent.right = null;
    } else if (parent.right !== null && parent.left !== null) {
      if (parent.right.val === current.val) {
        parent.right = null;
      } else {
        parent.left = null;
      }
    }
  }

  function swap(current, leaf) {
    var temp = current.val;
    current.val = leaf.val;
    leaf.val = temp;
  }

  // only leaf
  // (current.right && current.left) === null
  // it means if right is truthy then left is true or left is falsy
  // so if right is null it executes the code below.
  // because of operator precedence, &&(Logical And) is executed before '||'
  // so make it clear by explicitly expressing logic!
  if (current.right === null && current.left === null) {
    cutLeaf(parent, current);
  }

  function findInorderChildAndSwap(current, direction) {
    var chosen;
    direction ? (chosen = current.right) : (chosen = current.left);

    var chosenParent;

    while (direction ? chosen.left : chosen.right) {
      chosenParent = chosen;
      chosen = direction ? chosen.left : chosen.right; // 6
    }

    swap(current, chosen);

    // // if there is no children of inorder child
    if (!chosenParent) {
      chosenParent = current;
    }

    cutLeaf(chosenParent, chosen);
  }

  // if right child or both exists
  if (current.right) {
    findInorderChildAndSwap(current, true);

    // only left child exists
  } else if (current.left && !current.right) {
    findInorderChildAndSwap(current, false);
  }
  return this;
}

ECMA 6 에 추가된 문법을 배웠다. 바로 return 할 대상을 obj안에 넣어서 여러개를 package의 형태로 return가능하다는 점이다. 그리고 이걸 여러개의 변수에 분배가능하다는 것도 배웠다. 또한 이번기회에 ternary 문법 연습도 하고 이것저것 많이 배운것 같다.

그리고 마지막으로 operator precedence를 배웠다. AND이 OR보다 우선시 된다는 것!

항상 A와B가 NULL 일때 라는 조건문을 쓰고싶을때 if((A&B) === null) 이라고 하면 그 뜻이 아니다. 이건 a가 참일때 b가 되고 그게 null과 같을때 라는 뜻이다. && operator가 이런식으로 해석이 되는거라서 오해하면 안된다!

그럼 다음으로 tree Traverse 하는 방법을 알아보자