이진 탐색 트리(Binary Search Tree)

<이진 탐색 트리(Binary Search Tree)>

이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조이다.
[이진 탐색 트리의 정의]

1. 모든 원소는 서로 다른 유일한 키를 갖는다.
2. 왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다.
3. 오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다.
4. 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리다.

[이진 탐색 트리의 탐색 연산]
1. 루트에서 시작한다.
2. 탐색할 킷값 x를 루트 노드의 킷값과 비교한다.
3. (킷값 = 루트노드의 킷값)인 경우 : 원하는 원소를 찾았으므로 탐색연산 성공
4. (킷값 < 루트노드의 킷값)인 경우 : 루트노드의 왼쪽 서브트리에 대해서 탐색연산 수행
5. (킷값 > 루트노드의 킷값)인 경우 : 루트노드의 오른쪽 서브트리에 대해서 탐색연산 수행
-> 서브트리에 대해서 순환적으로 탐색 연산을 반복한다.

 

[알고리즘]

예) 원소 11 탐색하기
① 찾는 킷값 11을 루트노드의 킷값 8과 비교
(찾는 킷값 11 > 노드의 킷값 8) 이므로 오른쪽 서브트리를 탐색
② (찾는 킷값 11 > 노드의 킷값 10) 이므로, 다시 오른쪽 서브트리를 탐색
③ (찾는 킷값 11 < 노드의 킷값 14) 이므로, 왼쪽 서브트리를 탐색
④ (찾는 킷값 11 = 노드의 킷값 11) 이므로, 탐색 성공! (연산 종료)

[이진 탐색 트리의 삽입 연산]
1. 먼저 탐색 연산을 수행
- 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인한다.
- 탐색에서 탐색 실패가 결정되는 위치가 삽입 위치가 된다.
2. 탐색 실패한 위치에 원소를 삽입한다.

예) 원소 4 삽입하기
① 찾는 킷값 4를 루트노드의 킷값 8과 비교하여, (찾는 킷값 4 < 노드의 킷값 8) 이므로, 왼쪽 서브트리를 탐색한다.
② (찾는 킷값 4 > 노드의 킷값 3) 이므로, 오른쪽 서브트리를 탐색한다.
③ (찾는 킷값 4 < 노드의 킷값 5) 이므로, 왼쪽 서브트리를 탐색해야하는데 왼쪽 자식노드가 없으므로 탐색 실패!
이때, 탐색 실패가 결정된 위치 즉, 왼쪽 자식노드의 위치가 삽입 위치가 된다.
④ 탐색작업으로 찾은 자리 즉, 노드 5의 왼쪽 자식노드 자리에 노드 4를 삽입한다.

[이진 탐색 트리의 삭제 연산]
1. 먼저 탐색 연산을 수행
2. 탐색하여 찾은 노드를 삭제한다.
3. 노드의 삭제 후에도 이진 탐색 트리를 유지해야 하므로 삭제 노드의 경우에 대한 후속 처리(이진 탐색 트리의 재구성 작업)가 필요하다. 

−삭제할 노드의 경우

 

① 삭제할 노드가 단말노드인 경우 : 차수가 0인 경우

② 삭제할 노드가 하나의 자식노드를 가진 경우 : 차수가 1인 경우

노드를 삭제하면, 자식 노드는 트리에서 연결이 끊어져서 고아가 된다.
- 후속 처리 : 이진 탐색 트리의 재구성. 삭제한 부모노드의 자리를 자식노드에게 물려준다.

③ 삭제할 노드가 두개의 자식노드를 가진 경우 : 차수가 2인 경우

Copyrightⓒ2014 By 한빛아카데미(주)