Javascript 자료구조 06 : Tree 삭제

Tree의 삭제는 삭제하고자 하는 Node의 Child가 몇개인지에 따라 경우를 나누어 진행한다.

Tree 삭제

1. No Child

• Parent Node와의 link를 끊어준다.

2. One Child

• Parent Node와 Child Node 사이에 link를 연결한다.
• 해당 Node와 Child Node 사이의 link를 끊어준다...?

3. Two Children

• 삭제할 Node
• 삭제할 Node의 오른쪽 Child Node에서 가장 왼쪽에 있는 Node를 찾아서 삭제할

// remove
function remove(data) {
  let searched = false;
  let parent = null;
  let current = this.root;
  while (current) {
    if (current.data === data) {
      searched = true;
      break;
    } else {
      if (data < current.data) {
        parent = current;
        current = current.left;
      } else {
        parent = current;
        current = current.right;
      }
    }
  }
  // tree 내에 data가 없는 경우 return
  if (!searched) return false;
  //
  // parent의 왼쪽에 current가 있는 경우
  let leftFlag = true;
  // parent의 오른쪽에 current가 있는 경우
  if (parent.data < current.data) {
    leftFlag = false;
  }
  //
  // 1. No Child
  if (!current.left && !current.right) {
    if (leftFlag) {
      parent.left = null;
    } else {
      parent.right = null;
    }
    return;
  }
  // 2. One Child
  else if (current.left && !current.right) {
    // current의 왼쪽은 있고, 오른쪽은 없는 경우
    if (current.data < parent.data) {
      // parent의 왼쪽에 current가 있는 경우
      parent.left = current.left;
    } else {
      // parent의 오른쪽에 current가 있는 경우
      parent.right = current.left;
    }
  } else if (!current.left && current.right) {
    // current의 왼쪽은 없고, 오른쪽은 있는 경우
    if (current.data < parent.data) {
      // parent의 왼쪽에 current가 있는 경우
      parent.left = current.right;
    } else {
      // parent의 오른쪽에 current가 있는 경우
      parent.right = current.right;
    }
  }
  // 3. Two Children
  // 삭제할 Node(current)의 오른쪽 node에서 가장 작은 수
  // = 삭제할 Node(current)의 오른쪽 node에서 왼쪽 끝 node
  // 위 node를 target이라 지칭.
  // 그 최하위 왼쪽 노드는 더 이상의 왼쪽 node는 없고,
  // 오른쪽 노드가 있는 경우 + 오른쪽 노드가 없는 경우로 다시 나누어 생각
  else {
    if (current.data < parent.data) {
      // parent의 왼쪽에 current가 있는 경우
      let target = current.right;
      let targetParent = current.right;
      // target과 targetParent를 찾음.
      while (target.left) {
        targetParent = target;
        target = target.left;
      }
      // current의 오른쪽으로 넘어와서 target에 left가 없을 경우
      // targetParent와 target가 같아짐
      if (targetParent === target) {
        parent.left = target;
        target.left = current.left;
        current.right = null;
      } else {
        // target에 left가 있는 경우
        if (target.right) {
          // target의 오른쪽이 있으면
          targetParent.left = target.right;
        } else {
          // target의 오른쪽이 없으면
          targetParent.left = null;
        }
        parent.left = target;
        target.right = current.right;
        target.left = current.left;
      }
    } else {
      // parent의 오른쪽에 current가 있는 경우
      let target = current.right;
      let targetParent = current.right;
      // target과 targetParent를 찾음.
      while (target.left) {
        targetParent = target;
        target = target.left;
      }
      // current의 오른쪽으로 넘어와서 target에 left가 없을 경우
      // targetParent와 target가 같아짐
      if (targetParent === target) {
        parent.right = target;
        target.left = current.left;
        current.right = null;
      } else {
        if (target.right) {
          // target의 오른쪽이 있으면
          targetParent.left = target.right;
        } else {
          // target의 오른쪽이 없으면
          targetParent.left = null;
        }
        parent.right = target;
        target.right = current.right;
        target.left = current.left;
      }
    }
  }
}

테스트코드 - 이전 글(javascript 자료구조04 : Tree)의 Node, LinkedList 코드 추가 필요

let tree = new Tree();
tree.insert(50);
tree.insert(25);
tree.insert(75);
tree.insert(15);
tree.insert(40);
tree.insert(60);
tree.insert(100);
tree.insert(5);
tree.insert(20);
tree.insert(30);
tree.insert(45);
tree.insert(29);
tree.insert(27);
tree.remove(25);
console.log(tree);

한계

1. root를 삭제할 경우 에러.
2. 같은 값을 넣었을 때 업데이트 문제.

후기

• 살면서 짠 코드 중에 가장 더러웠다. 리팩토링이 시급하다.

• 2020.04.13 최초 작성

댓글 환영 by.protect-me