[Data Structure] Binary Search Tree

 

📝 개요

(1) 자식 노드 갯수가 2개 이하로
(2) 왼쪽 자식은 모두 나보다 값이 작고
(3) 오른쪽 자식은 모두 나보다 값이 큰
그리고 모든 자식 노드 또한 위 3가지 성질을 갖는 자료구조.

 

from Wikipedia

When to use?

(1) Local Search

• getNextNode (next Largest key except myself)
• Range Search
  ex) 1~100 中 5~15

(2) Implements Data structure

Set, Binary Heap, Priority Queue

 

 

 

 

👨‍💻 Impelment (C++)

왼쪽, 오른쪽 자식뿐만 아니라 부모노드와 연결도 킵

BST.h

BST.cpp

main.cpp

---

Key Point (Delete Node)

 

가장 까다로운 부분이기 때문에 그림과 함께 정리한다.

void BST::deleteNode(data_t key) {

// (중략..)
    else if (targetNode->rightChild == nullptr) {
	// (중략..)
        // 부모 노드가 존재하는 경우 부모로부터 포인터를 직접 연결시켜줘야한다.
      Node* parentNode = targetNode->parent;
      
      // key point!!
      if (parentNode->data > targetNode->data) parentNode->leftChild = targetNode->leftChild;
      else parentNode->rightChild = targetNode->leftChild;
      if (targetNode->leftChild != nullptr) targetNode->leftChild->parent = parentNode;

// (중략..)

    } else {
        Node* nextNode = getNextNode(targetNode);
        targetNode->data = nextNode->data;
        // key point!!
        nextNode->parent->leftChild = nextNode->rightChild;

        if (nextNode->rightChild != nullptr) nextNode->rightChild->parent = nextNode->parent;
// (중략..)
    }

}

 

targetNode = targetNode->leftChild
// targetNode 대신 왼쪽 자식이 완벽하게 대치된것 처럼 보이지만
// targetNode의 부모노드는 여전히 targetNode의 주소를 가리키고 있기 때문에 완전히 삭제되지 않는다.
// 따라서 parentNode와 targetNode의 대소관계 (왼쪽위 부모? 오른쪽 위 부모?) 를 따져서 부모노드에서 targetNode의 자식노드로 포인터를 이어줘야한다.

Linked List 에서 특정 원소를 삭제할 때도 같은 방식으로 처리한다.

 

has no right child 3가지 케이스를 다음과 같이 표현할 수 있다.

본문 코드의 else if 절에 해당한다.

 

 

본문 코드의 else 절에 해당한다.