[자료구조] BST(Binary Search Tree, 이진 탐색 트리)

1. BST란?

BST(Binary Search Tree, 이진 탐색 트리)는 root 노드의 값보다 작은 값은 왼쪽 자식에, 큰 값은 오른쪽 자식에 저장되어 있는 서브 트리들로 구성되어 있는 트리이다. 모든 노드가 최대 2개의 자식 노드를 가지며, 중복된 값은 허용되지 않는다.
BST는 이렇게 정해진 규칙으로 값을 저장한다는 특징 덕분에 노드의 탐색, 삽입, 삭제가 편리한 트리이다.

위 사진은 BST의 예시이다. 위 사진처럼 root 노드의 값보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 저장한다. 또, 가장 왼쪽에 있는 노드는 최솟값, 가장 오른쪽에 있는 노드는 최댓값을 가진다.

2. 시간복잡도

• 생성
  • 정렬된 배열 이용: $O(n)$
  • 정렬되지 않은 배열 이용: 평균 $O(n\log n)$, 최악의 경우 $O(n^2)$
• 탐색, 삽입, 삭제
  • 불균형한 BST의 경우: 평균 $O(\log n)$, 최악의 경우 $O(n)$
  • 균형한 BST의 경우: 평균 $O(\log n)$, 최악의 경우 $O(\log n)$
• 순회: $O(n)$

3. 탐색, 삽입, 삭제

탐색

1. 찾고자 하는 값을 root 노드에서부터 탐색
2. 찾고자 하는 값이 root 노드보다 작으면 왼쪽으로 이동, 크면 오른쪽 노드로 이동
3. 자식 노드를 root 노드로 하여 반복 탐색

삽입

1. 삽입하고자 하는 값이 root 노드보다 작으면 왼쪽으로 이동, 크면 오른쪽 노드로 이동
2. 리프 노드에 도달할 때까지 이동한 후, 올바른 위치에 삽입

삭제

1) 삭제할 노드가 리프 노드

1. 삭제할 노드 삭제

2) 삭제할 노드의 자식 노드가 1개

1. 삭제할 노드의 자식 노드를 삭제할 노드의 부모 노드와 연결
2. 삭제할 노드 삭제

3) 삭제할 노드의 자식 노드가 2개

1. 삭제할 노드의 left 서브 트리의 최댓값 또는 right 서브 트리의 최솟값 찾기
2. 삭제할 노드를 찾은 노드로 대체
3. 삭제할 노드 삭제

4. Indexed BST

Index가 추가된 BST이다. 이는 BST를 더 효과적으로 탐색할 수 있게 도와준다. 여기서는 leftsize를 index로 사용하였다. Leftsize는 자신의 왼쪽 자식 노드의 개수이다.

5. BST의 rank

BST의 rank는 해당 BST를 inorder로 탐색했을 때의 순서를 의미한다. 예를 들어, 위의 BST를 inorder로 탐색했을 때의 순서는 [2, 5, 8, 9, 10, 11, 12, 13, 14, 15, 16]인데, 이때 rank(2) = 0, rank(9) = 3, rank(15) = 9이다.