[자료구조] Tree 02

calendar_todayApril 15, 2021

local_offer#자료구조#algorithm#javascript

BST 삭제

매우 복잡하므로, 경우를 나누어서 이해하는 것이 좋다

Leaf Node 삭제

Leaf Node: Child Node가 없는 Node
삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.

Child Node가 하나인 Node 삭제

삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다.

Child Node가 두 개인 Node 삭제

삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.

1번이나 2번이나 결과적으론 비슷하므로 1번 위주로 설명

1번 방식을 이용한 삭제 시나리오

삭제할 Node의 오른쪽 자식 선택
오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 함
해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함
해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함
만약 해당 Node(가장 왼쪽 Node)가 오른쪽 Child Node를 가지고 있을 경우에는, 해당 Node의 본래 Parent Node(가장 왼쪽 Node의 Parent Node)의 왼쪽 Branch가 해당 Node의 오른쪽 Child Node를 가리키게 함

BST 삭제 코드 구현과 분석

삭제할 Node 탐색

삭제할 Node가 없는 경우도 처리해야 함
- 이를 위해 삭제할 Node가 없는 경우는 false를 리턴하고, 함수를 종료 시킴

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

class NodeManagement {
  head;
  constructor(head) {
    this.head = head;
  }
  insert(value) {
    let currentNode = this.head;

    while (true) {
      if (value < currentNode.value) {
        if (currentNode.left) {
          currentNode = currentNode.left;
        } else {
          currentNode.left = new Node(value);
          return;
        }
      } else {
        if (currentNode.right) {
          currentNode = currentNode.right;
        } else {
          currentNode.right = new Node(value);
          return;
        }
      }
    }
  }
  search(value) {
    let currentNode = this.head;
    while (currentNode) {
      if (currentNode.value === value) {
        return currentNode;
      } else {
        currentNode =
          currentNode.value > value ? currentNode.left : currentNode.right;
      }
    }

    return null;
  }
  delete(value) {
    let searched = false;
    let currentNode = this.head;
    let parentNode = this.head;
    while (currentNode) {
      if (currentNode.value === value) {
        searched = true;
        break;
      } else {
        parentNode = currentNode;
        currentNode =
          currentNode.value > value ? currentNode.left : currentNode.right;
      }
    }
    if (!searched) {
      return searched;
    }

    if (currentNode.left && currentNode.right) {
      // case 1: 삭제할 노드가 child Node가 두개 전부 있는 Node 일때

      let changeNode = currentNode.right;
      let changeNodeParent = currentNode.right;

      while (changeNode.left) {
        changeNodeParent = changeNode;
        changeNode = changeNode.left;
      }

      changeNodeParent.left = null;

      if (changeNode.right) {
        changeNodeParent.left = changeNode.right;
      }
      value < parentNode.value
        ? (parentNode.left = changeNode)
        : (parentNode.right = changeNode);
      changeNode.left = currentNode.left;
      changeNode.right = currentNode.right;
    } else if (currentNode.left || currentNode.right) {
      // case 2: 삭제할 노드가 child Node가 하나 뿐인 Node 일때
      const childNode = currentNode.left || currentNode.right;
      parentNode.value > value
        ? (parentNode.left = childNode)
        : (parentNode.right = childNode);
    } else {
      // case 3: 삭제할 노드가 leaf(terminal) Node 일때
      parentNode.value > value
        ? (parentNode.left = null)
        : (parentNode.right = null);
    }
  }
}

const head = new Node(30);
const BST = new NodeManagement(head);

BST.insert(15);
BST.insert(13);
BST.insert(11);
BST.insert(14);
BST.insert(18);
BST.insert(16);
BST.insert(19);
BST.insert(17);

BST.delete(15);

console.log(BST.search(16));

BST의 시간 복잡도와 단점

시간 복잡도(탐색시)

depth(트리의 높이)를 h라고 표기한다면, O(h)
n개의 노드를 가진다면, h = log2 n 에 가까움 -> 시간복잡도는 O(logn) 한번 실행시마다, 50%의 실행시간을 단축 시킬 수 있다는 것을 의미함

단점

평균 시간 복잡도는 O(logn) 이지만, 최악의 경우는 linked list 등과 동일한 성능을 보여줌(O(n))

이번에 시간 제일 많이 썼네.. 👀