1. 이진 탐색 트리
가. 이진 탐색 트리
탐색 트리의 기본
데이터의 삽입, 삭제, 탐색 등이 자주 발생하는 경우에 효율적인 구조
이진 트리이면서 같은 값을 갖는 노드가 없어야 함.
최상위 레벨에 루트 노드가 있고 각 노드는 최대 두 개의 자식을 가짐.
왼쪽 서브 트리에 있는 모든 데이터는 현재 노드의 값보다 작고, 오른쪽 서브 트리에 있는 모든 노드의 데이터는 현재 노드의 값보다 큼.
모든 서브 트리도 이진 탐색 트리의 성질을 만족해야함.
https://ko.wikipedia.org/wiki/이진_탐색_트리
이진 탐색 트리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전.
ko.wikipedia.org
나. 이진 탐색 트리에서의 탐색
데이터 탐색은 루트에서부터 시작됨.
루트 노드의 데이터와 찾으려는 데이터를 비교하여 루트 노드와 찾으려는 데이터가 같으면 탐색은 성공적으로 종료함.
그렇지 않고 루트 노드의 데이터가 찾으려는 데이터보다 작으면 루트 노드의 오른쪽 서브 트리를 탐색해가고, 루트 노드의 데이터가 찾으
는 데이터보다 크면 루트 노드의 왼쪽 서브 트리를 탐색해 감.
다. 이진 트리 탐색에서 재귀적 관점
이진 트리 탐색에서 루트 노드 t에서 왼쪽 자식 Left[t]로 분기하는 것은 Left[t]가 새로운 루트가 되었을 뿐 앞의 과정과 똑같은 작업
즉, 루트 노드와 찾으려는 데이터의 대소 비교를 하고 나면 자신과 성격은 똑같으면서 더 작은 문제를 만남(재귀적)
2. 이진 탐색 트리에서 삽입
가. 데이터 삽입
이진 탐색 트리에서의 삽입은 탐색 동작을 통해 이루어짐.
탐색에 성공하면 삽입은 실패함.(이는 삽입하려는 데이터가 이미 존재한다는 의미인데 이진 탐색 트리는 같은 데이터를 갖는 노드가 없어야 함.)
탐색에 실패하면 삽입을 할 수 있으며 탐색이 종료된 지점에 데이터를 값으로 하는 노드가 삽입됨.
삽입할 위치는 루트 노드에서부터 시작되며 삽입할 노드의 데이터가 비교하는 노드의 데이터보다 작으면 왼쪽 서브 트리로 진행하고 크면 오른쪽 서브 트리로 진행함.
나. 이진 탐색 트리의 특징
이진 탐색 트리는 좌우의 균형이 잘 잡힌 탐색 트리인데 균형이 잘 맞으면 탐색의 효율이 높음.
탐색 트리에서 효율은 트리의 깊이와 밀접한 관계가 있음.
트리의 모양이 극단적으로 왼쪽이나 오른쪽으로 치우쳐 있는 경우 탐색의 효율이 나쁨.(사향 이진 트리)
1) 사향 이진 트리(Skewed Binary Tree)
예) 데이터가 10, 20, 25, 30, 40, 45 의 순서로 원소 가 삽입될 경우에 만들어지는 트리의 모양은 극단적으로 오른쪽으로 치우쳐 있음(오른쪽 사향 이진 트리)
이 트리에서 45를 검색할 경우 10, 20, 25, 30, 40, 45 의 순서로 트리의 모든 원소와 비교해야 함.
40을 검색할 경우에는 10, 20, 25, 30, 40 의 순서 로 다섯번의 비교가 필요함.(검색 효율이 나쁨)
3. 이진 탐색 트리에서 삭제
가. 데이터 삭제
이진 탐색 트리에서 노드를 삭제하는 동작은 삭제할 노드의 위치에 따라 다음과 같이 세 가지로 구분됨.
t: 트리의 루트 노드, r: 삭제하고자 하는 노드
1) r이 리프 노드인 경우
바로 r을 삭제함.
2) r이 자식 노드가 하나인 경우
r의 자식(서브 트리)을 r의 자리에 놓고 r을 제거함.
3) r의 자식 노드가 두 개인 경우
조금 복잡함.
왼쪽 서브 트리에서 가장 큰 값(r 보다 한 단계 작은 값) 혹은 오른쪽 서브 트리에서 가장 작은 값(r 보다 한 단계 큰 값)을 가진 노드를 삭제 후 r의 값을 해당 값으로 바꿈.
이동시키려는 노드를 삭제할 때는 위 과정을 재귀적으로 반복함.
나. 삭제 작업의 수행시간
Case 1과 Case2는 상수 시간이 듦.
Case3는 노드 r의 직후 원소를 찾는데 최악의 경우 트리의 높이에 비례하는 시간이 듦.
삭제 작업을 위한 최악의 시간은 트리의 높이에 따라 O(log n)과 O(n) 사이에 결정됨.
이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을 때 O(h)가 됨.
따라서 n개의 노드를 가지는 이진 탐색 트리의 경우, 균형 잡힌 이진 트리의 높이는 log n 이므로 이진 탐색 트리 연산의 평균적인 경우의 시간 복잡도는 O(log n)임.
