[TIL] 이진 탐색 트리 BST, Binary Search Tree

이진 탐색 트리 BST, Binary Search Tree 

이진 트리와 B-Tree 는 정리했었는데 이진 탐색 트리는 정리를 안 해놔서 복습 겸 정리한다 

이진 트리 Binary Tree 정리 내용

B-Tree 정리 내용

이진 탐색 트리의 속성 

1. 각 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가 있는 노드만 포함된다

2. 각 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가 있는 노드만 포함된다

3. 모든 서브 트리 또한 이진 검색 트리이다 

4. 중복된 키를 허용하지 않는다 

https://yoongrammer.tistory.com/71

 

이진 탐색 트리 생성 예시

60, 15, 62, 80, 54, 11

 

1. 50을 트리의 루트로 트리에 삽입

2. 다음 요소의 키가 루트 노드 키보다 작으면 왼쪽 하위 트리의 루트로 삽입 

3. 루트 노드 키보다 크면 하위 트리의 오른쪽 루트로 삽입 

이진 트리의 검색 

1. 루트 노드부터 탐색 시작

2. 검색 값을 루트와 비교하여 루트보다 작으면 왼쪽으로, 루트보다 크다면 오른쪽으로 이동한다

3. 일치하는 값을 찾을 때까지 탐색을 반복한다

4. 찾고자 하는 값이 없다면 NULL 을 반환한다 

 

이진 트리의 검색 코드 구현 (RBTree 검색으로 대체)

node_t *rbtree_find(const rbtree *t, const key_t key)
{
  // TODO: implement find
  // root node 부터 탐색 시작
  node_t *current = t->root;

  // nil->node 도달까지 (Key 를 못 찾을 때까지) 탐색 진행
  // 찾는 값 key 과 현재 값 current->key 를 비교
  // Current 와 비교했을 때 Key 가 작다면 왼쪽으로 이동
  // Current 와 비교했을 때 Key 가 크다면 오른쪽으로 이동
  while (current->key != t->nil)
  {
    // 현재 값보다 찾는 값이 클 때 왼쪽으로 이동
    if (current->key > key)
      current = current->left;
    // 현재 값보다 찾는 값이 작을 때 오른쪽으로 이동
    else if (current->key < key)
      current = current->right;
    // Key 를 찾았을 때 해당 노드 current 반환
    else
      return current;
  }

  // nil node 까지 도달했지만 Key 가 없는 경우,
  // node_t * 반환 타입에 맞게 NULL return
  return NULL;
}

 

 

이진 탐색 트리의 시간 복잡도

균형 상태일 때 O(logN), 불균형 상태일 때 최대 O(N) 

이진 탐색 트리는 Inorder Traversal (left -> root -> right 순서로 순회) 로 정렬할 수 있고

이진 트리에서 노드가 N개 있을 때 트리의 높이 h는 최소 log(N+1) 이다

트리에서 탐색의 시간 복잡도는 O(h)이며,

트리가 균형 상태일 때는 최소 높이를 가지기 때문에 시간 복잡도가 O(logN)이 되고

Skewed Tree 의 경우 h = N 이 되어 시간 복잡도가 O(N) 으로 최대가 된다 

 

이진 탐색 트리의 삽입 

1. 루트 노드의 값 root->key 과 삽입할 노드의 값 key 을 비교한다

key 가 root->key 보다 작으면 왼쪽 서브 트리, 크면 오른쪽 서브 트리로 이동한다

2. 리프 노드에 도달할 때까지 반복하며, 리프 노드에 도달한 후

해당 노드의 값보다 작으면 왼쪽 자식 노드에, 크면 오른쪽 자식 노드에 삽입한다 

 

이진 탐색 트리의 높이가 h 일 때, 삽입의 시간 복잡도는 O(h)이다 

 

이진 탐색 트리의 삭제 

트리의 균형이 깨지지 않도록 아래 세 가지 상황으로 분류하여 각각 다른 과정으로 삭제를 진행한다

Case 1. 삭제할 노드가 리프 노드인 경우 

해당 노드를 그냥 삭제한다

Case 2. 삭제할 노드에 자식이 하나 있는 경우 

해당 노드를 삭제하고 그 노드의 부모 노드와 자식 노드를 연결한다

Case 3. 삭제할 노드에 자식이 둘 있는 경우

1. 삭제할 노드와 그 노드의 오른쪽 서브 트리를 찾는다 

2. Successor 노드를 찾는다 (Inorder Traversal 에서 삭제할 노드 바로 다음 노드)

3. 삭제할 노드와 Successor 노드의 자리를 바꾼다 

4. 기존 Successor 자리에 있는 노드를 삭제한다 

 

이진 탐색 트리의 높이가 h 일 때, 삭제의 시간 복잡도는 O(h)이다 

 

* Successor 용어는 B-Tree 정리 내용 참고 

Inorder Predecessor - 노드의 왼쪽 자식에서 가장 큰 Key 

pre-(앞의) decessor(가다, 나가다), 앞서가는 것 - 특정 노드의 "앞서" 있는 (더 작은 값인) 노드 

Inorder Successor - 노드의 오른쪽 자식에서 가장 작은 Key 

suc-(아래로) cessor(가다, 나아가다), 다음에 오는 것 - 특정 노드의 "다음" 에 있는 (더 큰 값인) 노드