서론
Binary Search Tree(이진 탐색 트리) 에 관한 지식들을 공부하고, 정리했던 내용을 바탕으로 글을 작성해 보았습니다
혹시나 틀린 내용이 있다면 지적해 주시면, 바로 반영하도록 하겠습니다
Binary Search Tree 란?
Binary Search + Linked List
Binary Search
장점 : 검색에 특화되어 시간 복잡도 O(log n)
단점 : 삽입 삭제는 되지 않음
Linked List
장점 : 삽입 삭제 시간 복잡도 O(1)
단점 : 검색 시간 복잡도 O(n)
Binary Search Tree
Binary Search 의 검색 능력을 유지하면서, 빈번한 자료 삽입 및 삭제가 가능하도록 하는 자료 구조
Binary Search Tree 의 특징
A 노드를 기준으로, B를 포함하는 서브트리는 A보다 작음 (왼쪽 서브트리)
A 노드를 기준으로, C를 포함하는 서브트리는 A보다 큼 (오른쪽 서브트리)
조건
- 중복된 노드가 없어야 함 (위의 특징을 만족시킬 수 없기 때문)
- 왼쪽, 오른쪽 서브트리도 모두 Binary Search Tree 이다
정렬 방식
자신보다 왼쪽 노드들은 자신보다 작고, 오른쪽 노드들은 자신보다 크므로
왼쪽 노드(서브트리) → 자신 → 오른쪽 노드(서브트리) 로 순회하면 해당 BST 에서 정렬된 결과를 얻을 수 있다
BST 에서의 탐색 연산
위 트리가 BST 일 때,
- 루트 노드부터 시작하여, 찾고자 하는 수가 해당 노드보다 큰지, 작은지, 같은 지 판단한다
- 만약 작으면 왼쪽 서브트리의 루트 노드(왼쪽 자식)과 비교하고, 크면 오른쪽 서브트리의 루트 노드(오른쪽 자식)과 비교한다
- 위 과정에서 같은 경우(탐색하고자 하는 수를 찾은 경우)라면 탐색을 종료한다
- 만약 현재 노드가 리프 노드라면, 탐색이 실패한 것이다(찾고자 하는 수가 트리 내부에 존재하지 않음)
시간 복잡도
만약 현재 노드가 리프 노드라면, 탐색이 실패한 것이다(찾고자 하는 수가 트리 내부에 존재하지 않음)
마지막 경우에서 최악의 경우 리프 노드까지의 탐색이 이루어져야 하는데, 이 경우 해당 트리의 높이(h) 번 비교를 반복한다
따라서 탐색의 시간 복잡도는 O(h) 라고 할 수 있다
BST 에서의 삽입 연산
삽입 연산은 탐색 연산과 거의 비슷하다
- 루트 노드부터 시작하여 삽입하고자 하는 수가 해당 노드보다 큰지, 작은지 판단
- 만약 작으면 왼쪽 서브트리의 루트 노드(왼쪽 자식)과 비교하고, 크면 오른쪽 서브트리의 루트 노드(오른쪽 자식)과 비교한다
- 같은 경우는 BST 의 조건에 따라 존재하지 않으므로, 생각하지 않는다
- 리프 노드까지의 탐색을 마치고, 큰지 작은지를 비교하여 왼쪽 자식 혹은 오른쪽 자식에 해당 노드를 삽입한다
시간 복잡도
삽입 연산에서 트리의 리프 노드까지의 탐색 연산이 이루어져야 한다
이는 높이에 비례한 O(h) 의 시간 복잡도를 가진다
하지만 실제 노드를 삽입하는 연산은 연결 리스트와 동일하게 O(1) 의 시간 복잡도를 가진다
따라서 결과적으로 삽입 연산의 시간 복잡도는 O(h) 이라고 할 수 있다
BST 의 삭제 연산
삭제 연산은 3가지 경우로 나뉜다
자식 노드가 없는 경우, 하나 있는 경우, 두개 다 있는 경우이다
case 1) 자식 노드가 없는 경우 (리프 노드)
4를 가지는 노드를 삭제하고자 할 때, 단순히 4를 삭제하기만 하면 되고 후에 어떤 작업도 하지 않아도 된다
실제로 4가 삭제되는 과정은 3의 오른쪽 자식의 reference 를 null 로 만드는 과정으로 삭제가 이루어질 것이다
case 2) 자식 노드가 1개인 경우
자식 노드가 1개인 노드를 삭제하고자 할 때에는, 단순히 삭제된 노드의 자식 노드를 부모 노드로 연결하면 된다
이는 BST 의 특징 때문이며, 3과 1은 모두 5의 왼쪽 서브트리 내에 존재 하므로 3이 삭제되고 그 자리에 1이 들어가더라도 BST 의 조건을 만족시킬 수 있다
case 3) 자식 노드가 2개인 경우
알아야 할 내용
삭제할 노드의 왼쪽 서브트리 노드들 중 최대값 → predecessor
삭제할 노드의 오른쪽 서브트리 노드들 중 최소값 → successor
- 해당 BST 의 노드들을 정렬해 보았을 때, OO -> 13 -> 16 -> 20 -> OO 이 된다
- predecessor 은 삭제하고자 하는 노드 바로 직전의 값이며
- successor 은 삭제하고자 하는 노드 바로 직후의 값이다
3-1 ) successor 로 삭제할 노드를 대체
전체적인 흐름은 위 이미지와 같으며 단계 별로 설명하도록 하겠다
1. 삭제할 노드를 삭제하고, 빈 자리로 successor 노드가 이동
해당 과정에서 기존에 존재하던 노드 (16) 을 successor (20) 이 대체하였다
2. successor 가 존재하던 자리는 적절한 case (1 or 2) 에 맞게 그래프 재배치
해당 과정에서는 자식 노드가 1개 존재하는 case 2 에 해당하므로, 자식 노드를 빈 자리로 옮긴다
3. 완성된 그래프
완성된 그래프는 다음과 같으며, BST 의 조건을 모두 만족한다
3-2 ) predecessor 로 삭제할 노드를 대체
현재 상황에서는 predecessor 노드는 리프 노드이므로, case 1에 해당하며 기존 삭제한 자리를 대체 후에는 어떠한 작업도 일어나지 않는다
완성 후, 3-1 과는 모양은 다르지만 BST 의 조건을 모두 만족한다
위 연산이 가능한 이유
눈치 챘을지도 모르지만, predecessor 나 successor 노드는 반드시 자식 노드가 하나이거나 존재하지 않는다
Predecessor
predecessor 를 구할 때에는, 특정 노드의 왼쪽 서브트리의 오른쪽 자식을 계속 탐색한다
- Binary Search Tree 의 구조상 왼쪽 서브트리에는 자신보다 작은 노드들(만) 모두 존재한다
- 왼쪽 서브트리의 루트 노드에서 계속 오른쪽 자식들을 탐색해 나가는 과정은 특정 노드 보다 작지만, 가장 가까운(왼쪽 서브트리 중에서) 노드를 찾기 위한 연산이다
- 오른쪽 자식을 찾아 나가다 보면, 탐색을 멈추는 시점은 더이상 오른쪽 자식 노드가 존재하지 않는 경우이다
따라서, 오른쪽 자식이 더이상 존재하지 않는 경우라면? 왼쪽 자식만 있거나, 아니면 왼쪽 자식도 없거나 둘중 하나이다
그러므로, predecessor 노드는 자식 노드가 하나이거나, 없을 수밖에 없다
Successor
Successor 를 구할 때도 마찬가지이다. 특정 노드의 오른쪽 서브트리의 왼쪽 자식을 계속 탐색한다
따라서, 왼쪽 자식이 더이상 존재하지 않는 경우 오른쪽 자식만 있거나, 오른쪽 자식도 없는 두 경우가 존재한다
그러므로, successor 노드는 자식 노드가 하나이거나, 없을 수밖에 없다
시간 복잡도
먼저, 삭제 연산을 시도하려면 삭제할 노드를 찾아야 한다
삭제할 노드를 찾는 연산은 삭제할 노드의 높이 (d 라고 가정)에 따르므로, O(d) 가 될 것이다
두번째, successor (혹은 predecessor) 를 찾아가는 연산에서
successor 의 높이가 그래프의 높이와 같은 최악의 경우를 생각했을 때,
삭제할 노드에서부터 시작하여, successor 를 찾아가는 것 또한 높이에 비례한다
전체 높이(h) 에서 삭제할 노드의 높이(d) 를 뺀 O(h - d)
이 외에도 연결을 끊고, successor 를 삭제할 노드 위치로 옮기고 연결하는 일련의 과정들도 존재하지만 연결 리스트의 특성 상 O(1) 이므로 무시할 수 있다
따라서 삭제 연산의 시간 복잡도는 O(d + h - d) = O(h) 가 된다
한계점
Binary Search Tree 의 시간 복잡도는 그래프의 높이에 의해 결정된다
- 탐색, 삽입, 삭제 → O(h)
만약 이런 모양의 트리가 존재한다면 어떨까?
루트 노드를 기준으로 오른쪽 자식들만 존재하는 그래프라면?
이 경우, h = n(노드들의 개수) 이므로 시간 복잡도는 O(n) 이라고 할 수 있을 것이다
이렇게 되면 연산이 너무 비효율적이게 되므로 그래프의 균형을 맞춰가는 과정이 필요해질 것 같다
이러한 문제와 한계점을 해결하기 위하여, AVL 트리가 등장하였다
Reference
https://ratsgo.github.io/data%20structure&algorithm/2017/10/22/bst/
댓글