참고자료
<C++로 쉽게 풀어쓴 자료구조> 천인국, 최영규 지음, 생능 출판사
공부 범위 : 챕터 9 이진 탐색 트리
이진 탐색 트리
탐색이란?
- 탐색 : 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업
- 레코드(record) : 하나 이상의 필드(field)로 구성된다
- 테이블(table) : 레코드의 집합
- 키(key) : 레코드를 식별할 수 있게 하는 필드
- 주요키(primary key) : 서로 중복되지 않는 고유한 값을 갖는 키
이진 탐색 트리란?
이진트리 기반, 효율적인 탐색을 위한 자료구조. 다음 조건을 만족해야 한다. 이 정의에 따라 이진 탐색 트리는 어느 정도 정렬된 상태를 유지하게 된다.
- 모든 노드는 유일한 키를 갖는다.
- 왼쪽 서브트리의 키들은 루트의 키보다 작다.
- 오른쪽 서브트리의 키들은 루트의 키보다 크다.
- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
이진 탐색 트리의 추상 자료형
이진 탐색 트리의 특성을 항상 만족하도록 하면서 삽입, 삭제, 탐색을 할 수 있어야 한다. 자세한 추상 자료형은 책으로 보자. 이진트리의 기본적인 모든 연산 또한 사용 가능하다.
이진 탐색 트리의 기본 틀 설계
이 책에서는 앞 챕터에서 만든 이진트리 클래스를 상속하고 삽입, 삭제, 탐색 함수를 추가했다.
이진 탐색 트리의 연산
탐색 연산
비교한 값이 루트보다 작으면 왼쪽으로, 크면 오른쪽으로, 같으면 탐색이 끝난다. 재귀를 기반으로 하나 반복으로 구현할 수 있다고 한다. 반복으로 구현한 함수에서는 while을 사용했다. 함수는 이진 탐색 트리에서 구현하는 방법도 있고, 노드 클래스에서 구현하는 방법도 있다. 자세한 코드는 생략한다.
삽입 연산
삽입하기에 앞서 적절한 자리를 찾기 위해 탐색을 해야 한다. 탐색해서 같은 값을 찾으면 키가 중복되므로 삽입할 수 없고, 탐색에 실패하면 같은 키가 없는 것이므로 실패한 자리에 삽입하면 된다. 마찬가지로 재귀와 반복 모두 구현 가능하다.
삭제 연산
삭제할 노드를 찾기 위해 탐색을 먼저 해야 하며, 세 가지 상황으로 나뉜다.
- 삭제하려는 노드가 단말 노드일 때 : 그냥 지우면 된다.
- 삭제하려는 노드가 양쪽 서브트리 중 하나만 가질 때 : 노드를 삭제한 후 서브트리를 이어붙이면 된다.
- 삭제하려는 노드가 양쪽 서브트리를 모두 가질 때 : 두 서브트리 중 하나를 루트로 만들어 이어붙여야 한다.
삭제하려는 노드가 단말 노드일 때
해당 노드의 부모 노드를 찾아서 링크를 null로 만들고 해당 노드는 메모리를 동적으로 해제하면 된다. 이때 삭제할 노드와 부모 노드를 함께 알아야만 삭제가 가능하다.
삭제하려는 노드가 서브트리를 하나 가질 때
해당 노드를 삭제한 후 자식으로 있던 서브트리를 붙이면 된다. 부모 노드와 자식 노드를 알아야 한다.
삭제하려는 노드가 서브트리를 두 개 가질 때
해당 노드를 삭제한 후 왼쪽이나 오른쪽 서브트리를 이어 붙이면 되는데, 붙이고 나서도 이진 탐색 트리의 조건을 만족해야 한다. 고로 삭제되는 노드와 가장 값이 비슷한 노드를 붙여야 한다.
삭제되는 노드와 가장 비슷한 노드는 왼쪽 서브트리의 가장 오른쪽 값과 오른쪽 서브트리의 가장 왼쪽 값이다. 책의 설명에 의하면 둘 중 어떤 것을 선택해도 상관 없으며 여기서는 오른쪽 서브트리의 값을 선택한다고 한다.
이어 붙일 노드를 정했다면 원래 있던 노드를 삭제한 자리로 옮기면 된다. 서브트리를 모두 옮기는 것이 아니고 단말 노드 하나만을 옮긴다.
이 과정을 수행하기 위해 삭제할 노드, 삭제 노드의 부모 노드, 후계자 노드, 후계자 노드의 부모 노드를 알아야 한다. 이중 후계 노드와 후계 노드의 부모 노드는 함수 내에서 탐색을 통해 찾을 수 있으므로 함수에는 삭제 노드와 삭제 노드의 부모 노드만 전달하면 된다.
세 가지 경우 모두 삭제 노드와 삭제 노드의 부모 노드만 알면 수행 가능하므로 하나의 함수로 구현하고 선택문을 두어 세 가지 경우를 구분하여 처리한다. 복수의 노드 정보를 필요로 하므로 노드 클래스에서 구현할 수는 없다.
이진 탐색 프로그램
위에서 설계한 이진 트리 클래스를 종합하고 인스턴스를 생성하여 테스트해본다.
이진 탐색 트리의 성능 분석
이진 탐색 트리의 시간 복잡도에 대해 설명하고 있다. 균형 트리에 대해 언급하였다.
이진 탐색 트리의 응용: 영어 사전
꼭 영어 사전일 필요는 없다. 트리에 저장되는 레코드는 단어와 의미를 갖고, 단어는 공백이 없는 하나의 문자열, 의미는 여러 개의 단어로 이루어진 문자열이다.
사전의 기능은 입력, 삭제, 단어 탐색, 의미 탐색, 사전 출력, 종료로 구성된다.