[TIL][Sun] 이진 탐색 트리, 균형 이진 탐색 트리

이진 탐색 트리 Binary Search Tree (BST)

노드 기반 이진 탐색 트리 데이터 구조로 다음 속성을 가진다.

1. 노드의 왼쪽 하위 트리에는 해당 노드의 key보다 적은 값을 가진 노드만 포함한다.(즉, 왼쪽 자식 노드부터는 본 노드보다는 작은 값을 가진다.)
2. 노드의 오른쪽 하위 트리에는 해당 노드의 key보다 큰 값을 가진 노드만 포함한다.
3. 왼쪽과 오른쪽 하위 트리 또한 반드시 이진 탐색 트리여야만 한다.

이러한 속성 덕분에 검색하기 유용하고, 덕분에 이진 ‘탐색’ 트리 라는 이름이 붙었다. 루트에서 시작되어 크고 작음을 비교하며 이동하면 되기에, 이 트리는 비교 횟수가 적은 요소를 검색하는 데 유용하다.

탐색 시간은 트리의 높이에 달렸다.

Nodes of BST

이진 탐색 트리의 각 노드는 서로 같은 값을 가질 수 없다. (Each node in a BST must have a unique key. In other words, no two nodes can have the same value.) 이 속성으로 말미암아 각각의 모든 노드에 대해서 왼쪽 하위 트리에 있는 건 현재 노드의 key(값)보다 작고, 오른편에 있는 것은 현재 노드의 key(값)보다 크다. 따라서 그 어떤 탐색 연산은 특정한 노드나 탐색해서 찾아내려는 값이 현재 이 트리에 없다는 결론으로 가는 unique 한 경로로 이어진다.

… 고 하는데, 중복 값을 다뤄야 할 때가 있다면 그땐 또 넣을 수 있다는 듯 하다. (비슷한 의문에 대한 스택오버플로우의 게시글) 그렇다면 이럴 때 BST는 중복 값을 어떻게 다룰까?

How to handle duplicates in Binary Search Tree?

노드의 값(key, value) 옆에 갯수(counter)를 적어 다룬다. 코드상으로는 node.count와 같은 하위속성을 추가한다.

         12(3)
       /        \\
     10(2)      20(1)
    /    \\
 9(1)   11(1)

Count of a key is shown in bracket

다른 트리들은?

중복 금지 규칙은 이진 탐색 메커니즘을 사용하는 BST에서만 특화된 것이라 볼 수 있다. 왜냐하면 (1) 트리가 순서대로 정렬되어 있고, (2) 각 요소가 고유해야 예측 가능한 O(logN)의 검색 시간을 유지할 수 있기 때문이다. 일반적인 이진 트리나 다원 탐색 트리는 duplicate value를 가질 수 있다. (다른 트리들은 중복 값을 허용한다.)

• 이진 트리 : 일반적인 이진 트리에서는 노드에 특정한 순서가 없고, 이로 인해 중복이 존재할 수 있다.
• B- / B+ 트리
• 트라이

operations

삽입

삽입 하기 위해서는 root에서 시작하고, root의 값을 삽입하고자 하는 값을 비교해야 한다. 만약 삽입하고자 하는 값이 적다면 왼쪽으로, 크다면 오른쪽으로 이동한다. 이 작업을 새로운 노드를 넣을 수 있는 빈 곳을 찾을 때까지 로직을 반복한다.

탐색

현재 노드의 값과 타겟 값을 비교하며 왼쪽 하위 트리로 갈지 오른쪽 하위 트리로 가 탐색할지, 혹은 현재의 노드가 키를 잡고 있는지를 확인한다. 검색은 root부터 시작한다.

삭제

어떤 노드를 삭제할 때, 세 가지의 주요 시나리오를 포함한다.

1. 자식이 없는 노드를 삭제할 때
2. 자식이 하나 있는 노드를 삭제할 때
3. 두 개의 자식이 있는 노드를 삭제할 때

이중 3번의 경우가 가장 복잡한데, 왜냐하면 삭제된 노드를 교체하기 위해서 다음에 올 노드(inorder successor) 혹은 바로 앞에 온 전임자 노드를 찾아야 하기 때문이다.

[ ! ] inorder successor

오른쪽 하위 트리의 노드들 중 가장 작은 값을 가진 node를 특별히 칭하는 용어이다. 이것은 왼쪽 하위 트리의 모든 노드들보다 더 큰 값임을 보장한다. (당연한 말이다. 어떤 노드를 기준으로 그것보다 작으면 왼쪽, 그것보다 크면 오른쪽에 배치하니까. 여기서 오른쪽/왼쪽 하위 트리를 구분하는 기준은 root, 즉 최상단 노드를 기준으로 하는 것 같다.)

이 inorder successor는 왼쪽 자식을 소유하고 있지 않는데-왜냐하면 이 노드가 가장 작은 값이니까-이로 인해 그것의 현재 위치에서 이 노드를 제거하고 삭제한 노드의 위치로 옮겨 넣는 것이 용이하다. 어떤 면에서? BST 속성을 위배하지 않고 옮기는 측면에서.

• 왜 inorder successor?그 이유는 바로 postorder나 preorder는 이런 속성을 만족하지 않아서 그렇다고 한다. 예를 들어 postorder successor로는 현재 노드의 왼쪽 자식이 올 수도 있다. 이 경우 삭제된 노드를 이 왼쪽 자식이 대체한다면 BST의 규칙이 깨질 수 있다. (향후 예시 트리 그림 작성 예정) 따라서 트리 순회 타입과 inorder successor를 선택하는 건 연관이 적다.
• 이름을 보니 inorder라는 게 있다. 이거 어디서 많이 본 거다. 바로 세 가지 있는 tree traversal 목록에서 봤다. inorder, preorder, postorder. 그런데 왜 다른 것들은 언급이 없고 inorder의 successor를 다음에 올 노드로 쓰는 걸까? 다른 순회들은 왜 안 쓰는 걸까? 트리 순회 방법과 연관이 있을까?

---

균형 이진 트리 balanced binary search tree (BBST)

균형이진트리는 상위 포괄적인 용어로, 삽입, 삭제, 그리고 조회와 같은 연산이 O(logN) 시간복잡도 동안 효과적으로 이루어질 수 있도록 보장하는, 어떤 형태의 균형을 유지하는 이진 트리를 칭하는 말이다. 즉, 이진 탐색 트리에서 균형 속성이 더해져 추가적인 제약 조건을 가진 것이 BBST라고 보면 된다.

BBST 중 하나인 AVL트리와 비교하면, BBST는 ‘균형이 잡혀있다’에 대한 정의가 매우 다양하다. 회전 연산 또한 몇 BBST는 AVL과 다른 회전 방식을 취하기도 한다. 모든 BBST가 높이-균형하지 않다. 즉, 높이로 균형을 따지지만은 않는다.

이 트리는 프로그래밍 언어와 프레임워크에서 많은 고레벨 추상화의 기초를 이루기 때문에, 효율적인 데이터 구조와 알고리즘을 만들기 위해 BBST를 사용할 줄 알아야 한다

균형이진트리의 실제 사용 예시:

• 데이터베이스: 빠른 검색을 위한 인덱스 기록
• 파일시스템: 파일 정보 저장
• 효율적인 조회를 위한 라우팅 테이블 저장
• 메모리 관리: 빈 메모리 블록의 추적
• 게임 개발: AI와 연속 충돌 검사(collision detection)를 포함하는 다양한 알고리즘

key concept list:

• Height-Balanced Property: 트리마다 다양함
• Self-Balancing Trees: 스스로 균형을 잡는다.
• Complexity: 복잡도는 O(logN)