Javascriptデータ構造06:ツリーの削除

Treeの削除は削除するノードのChildによって行われる.

ツリーの削除

1. No Child

Parent Nodeへのリンクを解除します.

2. One Child

ノードとChildノードの間にリンクを接続します.

このノードとChildノードの間のリンクを切断...?

3. Two Children

のノード

を削除するには

削除するノードの右側のChildノードで、最も左側のノードを検索し、

を削除します.

// 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);

げんかい

本削除中にエラーが発生しました.

同じ値

を入力した場合の更新問題.

ポスト

これは私が

年に書いたコードの中で一番汚いです.再包装が必要です.

200.04.13初回作成

댓글 환영 by.protect-me