[자료구조] 이진 탐색트리

2022.01.14 - [2022/자료구조 + 알고리즘] - [자료구조] 이진 트리 참고하면 좋다!!!

[자료구조] 이진 트리

이진 탐색트리

이진 트리 T의 각 내부 노드 v가 엔트리 (k, x)를 저장하는 이진 트리이다.

• v의 왼쪽 서브트리에 있는 노드들에 저장된 키들은 k보다 작거나 같다.
• v의 오른쪽 서브트리에 있는 노드들에 저장된 키들은 k보다 크거나 같다.

정수 키들을 가진 맵을 나타내는 이진 탐색트리 T

T의 노드들에 저장된 키들은 일련의 내부 노드들에서 비교를 함으로써 탐색을 수행하는 방법을 제공하고 있다. 현재 노드 v에서 탐색이 중단되거나 왼쪽, 오른쪽 자식 노드에서 탐색이 계속될 수 있다. 따라서 여기서는 이진 탐색트리를 포화 이진트리(proper binary tree: 자식이 0 또는 2)로 생각한다. 이진 탐색 트리의 내부 노드에만 엔트리를 저장하고 외부 노드는 placeholder(자리 소유자)의 역할만 한다. 이렇게 하면 탐색과 갱신 알고리즘을 단순하게 한다. 비포화 이진 탐트리는 공간 사용율을 더 좋게 할 순 있지만 복잡한 탐색과 갱신함수를 사용하게 한다.
이진 탐색트리의 중요한 특성은 순서 맵(또는 딕셔너리)의 실현이다. 즉 이진 탐색트리는 계층적으로 부모와 자식 간의 관계를 이용하여 키들의 순서를 나타내어야 한다. 이진 탐색트리 T의 노드들에 대한 중위 순회는 감소하지 않는 순서로 키들을 방문해야 한다.

탐색

이진 탐색트리 T로 나타낸 맵 M에서 find(k) 연산을 수행하기 위해서 트리 T를 의사 결정 트리(decision tree)로 생각한다.
T의 각 내부 노드 v에서 탐색 키 k가 노드 v에 저장된 키(key(v)로 나타냄)보다 작은가, 같은가, 큰가에 대해 물어본다.
답이 "더 작다"이면 탐색을 왼쪽 서브트리에서 계속 한다. "같다"이면 탐색은 성공적으로 종료된다. "보다 크다"이면 탐색은 오른쪽 서브트리에서 계속 된다. 마지막으로 외부 노드에 도달하게 되면 탐색은 성공하지 못하고 종료된다.

(a) 정수 키들을 가진 맵을 나타내는 이진 탐색트리 T, (b) M에서 find(76) (성공)과 find(25) (실패) 연산을 실행했을 때 방문한 T의 노드들

이 방법을 알고리즘으로 나탄보자. 탐색 키 k와 T의 노드가 주어지면 이 함수(TreeSearch)는 v를 루트로 하는 T의 서브트리 T(v)의 노드(위치) w를 리턴하는데 다음 중 한 가지가 발생한다.

• w는 내부 노드이고 w의 엔트리는 k와 같은 키를 가진다.
• w는 T(v)의 중위 순회에서 k의 위치를 나타내는 외부노드이나 k는 T(v)에 포함되지 않는다.

따라서 find(k) 함수는 TreeSearch(k, T.root())를 호출하여 수행할 수 있다. 이 호출로 반환되는 T의 노드를 w라고 하자. 만약에 w가 내부 노드이면 w의 엔트리를 반환한다. 아니면 null을 반환한다.

Algorithm TreeSearch(k, v): if T.isExternal(v) then return null if k < key(v) then return TreeSearch(k, T.left(v)) else if k > key(v) then return TreeSearch(k, T.right(v)) return v {k = key(v)}

갱신 연산

1. 삽입

• insertAtExternal(v, e): 외부 노드 v에 요소 e를 삽입. v를 내부 노드로 확장하고 v는 새로운 (빈) 외부 자식 노드 가짐.

Algorithm TreeInsert(k, x, v): input: 탐색키 k, 연계값 x, T의 노드 v output: 엔트리(k, x)를 저장하고 있는 서브트리 T(v) 내의 새로운 노드(w) w <- TreeSearch(k,v) if T.isInternal(w) then return TreeInsert(k, x, T.left(w)) 오른쪽으로 진행해도 상관없음 T.insertAtExternal(w, (k,x)) return w

이 알고리즘은 T의 루트로부터 새로운 엔트리를 수용하는 새로운 내부 노드로 확장된 외부노드까지의 경로를 따라간다(아래 그림 참고).

이 앞의 그림의 탐색 트리에 키 78을 갖는 엔트리 삽입: (a) 삽입할 위치 찾기 (b) 결과 트리

2. 삭제

• removeAboveExternal(v): 외부 노드 v와 부모 노드를 제거하고 v의 부모 노드를 v의 형제 노드로 대체

이 연산이 주어지면, 키값이 k인 엔트리를 저장하고 있는 T의 한 노드를 찾기 위해 T에 대해서 TreeSearch(k, T.root())를 호출하여 맵 ADT의 erase(k) 연산 구현을 시작한다. TreeSearch가 외부 노드를 반환하면 맵 M에 키 k를 가진 엔트리가 없는 것이며 따라서 오류 신호를 보낸다. 대신에 TreeSearch가 내부 노드 w를 반환하면 w는 제거하고자 하는 엔트리를 저장하고 있는 것이며 다음과 같이 두 경우를 구분한다(아래 그림 참고).

• 노드 w의 자식 중 하나가 외부 노드이면(그림의 노드 z), Tㄴ에 대하여 removeAboveExternal(z) 연산을 수행하여 T로부터 간단히 w와 z를 제거한다. 이 연산은 w를 z의 형제 노드로 대체하고 w와 z를 T에서 제거함으로써 T를 재구성
• w의 두 자식 노드가 내부 노드이면 T로부터 노드 w를 간단히 제거할 수 없음. 다음과 같이 진행(아래 사진 참고)

• T의 중위 순회로 w다음에 오는 첫 번째 내부 노드 y를 찾는다. 노드 y는 w의 오른쪽 서브트리에서 가장 왼쪽에 있는 내부 노드이고 w의 오른쪽 자식 노드로 먼저 가고 거기서 T의 왼쪽 자식 노드를 따라 내려간다. 또한, y의 왼쪽 자식 x는 T의 중위 순회에서 노드 w 바로 다음에 오는 외부 노드이다.
• y의 엔트리를 w로 이동한다. 이러한 실행은 w에 저장되었던 엔트리를 삭제하는 효과를 갖는다
• T에 대한 removeAboveExternal(x)를 호출하여 T로부터 x와 y 노드를 삭제한다. 이러한 실행은 y를 x의 형제로 대체하고 T로 부터 x와 y를 삭제한다.

3. 이진 탐색트리의 성능

탐색, 삽입, 삭제 알고리즘의 분석은 유사하다. 방문한 각 노드에서 O(1) 시간을 소비하고 최악의 경우에 방문한 노드의 수는 T의 높이 h에 비례한다. 따라서 이진 탐색트리 T로 구현된 맵 M에서 find, insert, erase 함수는 h가 T의 높이일 때 O(h) 시간에 수행된다.

---

참고 문헌
[1] Michael T. Goodrich, Roberto Tamassia, Davaid M. Mount, C++로 구현하는 자료구조와 알고리즘, WILEY, 2013.