[Algorithm] 이진검색트리

검색트리

개체의 레코드를 저장하고 검색하기 위한 트리 형태의 자료구조

*레코드 : 개체에 대한 모든 정보를 포함한다. 어떤 사람이 레코드라면, 직장, 주민번호, 이름, 집 주소 등이 포함될 수 있다. 이들 각각의 정보를 나타내는 부분을 필드라고 한다.

 

검색트리는 최대 몇 개의 자식노드로 분기할 수 있느냐에 따라 이진검색트리와 다진검색트리로 나눈다.

이진 검색트리는 최대 2개의 자식 노드를 가질 수 있다.

 

이진검색트리

이진검색트리는 3가지 특성을 갖는다.

1) 이진검색트리의 각 노드는 키 값을 하나씩 갖는다. 키 값은 고유값이어야 한다.

2) 최상위에 루트 노드가 있고, 각 노드는 최대 2개의 자식 노드를 갖는다.

3) 임의의 노드 키 값은 왼쪽 자식노드보다 크고, 오른쪽 자식노드보다 작다. (left < parent < right)

 

이진검색트리의 예

이진검색트리에서의 검색

입력은 검색할 트리의 루트 노드 t, 검색하고자 하는 키 x가 주어진다.

1) t와 x를 비교하고 찾는 값이 t인 경우(x == t), t를 반환한다. 

2) x가 t보다 작다면(x < t) t의 왼쪽 자식 노드에 대해 재귀적으로 수행하고,

x가 t보다 크다면(x > t) t의 오른쪽 자식 노드에 대해 재귀적으로 수행한다.

 

이진검색트리에서의 삽입

입력은 검색과 동일하게 주어진다.

1) 이진검색트리 내에 삽입하고자 하는 키 x가 있는지 검색한다. 있을 경우 PASS

2) 검색 결과 없는 경우, 도달한 리프노드와 비교하고 작으면 왼쪽 자식 노드로, 크면 오른쪽 자식 노드로 삽입한다.

 

위에 주어진 이진검색트리에서 31을 삽입할 경우

이진검색트리 삽입

검색 단계에서 값이 있을 경우는 삽입하지 않고 끝난다. 없을 경우, 비교하면서 도달한 마지막 리프노드와 값을 비교하고 왼쪽, 오른쪽 중에 정해서 삽입한다.

 

이진검색트리에서의 삭제

삭제하려는 노드 r이 입력으로 주어질 때, 3가지 경우의 수가 존재한다.

1) r이 리프노드인 경우

2) r의 자식노드가 하나인 경우

3) r의 자식노드가 2개인 경우

 

Case 1의 경우, 자식이 없기 때문에 삭제되어도 파급효과가 없다. r을 가리키던 부모노드의 포인터를 NULL로 변경하면 된다.

 

Case 2의 경우, 자식이 하나이기 때문에, r을 가리키던 부모노드의 포인터를 r의 자식노드로 연결해주면 된다.

 

Case 3의 경우, 삭제하고 그 자리를 대체하더라도 이진검색트리의 성질을 전혀 깨지 않는 원소를 찾아야 한다.

이러한 원소는 2개가 존재한다.

 

1) r의 왼쪽 서브트리에서 가장 큰 원소 (r의 직전 원소)

2) r의 오른쪽 서브트리에서 가장 작은 원소 (r의 직후 원소)

 

r을 삭제하고, 대체할 값을 r의 자리에 넣어주면 된다.