9장 이진 탐색 트리

탐색을 위한 자료구조로 이진 트리를 사용하기 위해서 저장할 데이터의 크기에 따라 노드의 위치를 정의한 것이 이진 탐색 트리다.

 

(1) 모든 원소는 서로 다른 유일한 키를 갖는다.

(2) 왼쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 작다.

(3) 오른쪽 서브 트리에 있는 원소의 키는 그 루트의 키보다 크다.

(4) 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리다.

Select 예시 (11찾기)

Insert 예시 (4삽입)

Delete 예시 (8삭제)

왼쪽 서브 트리에서는 가장 오른쪽 링크필드가 후계자가 되고, 우측 서브 트리에서는 가장 왼쪽 링크필드가 후계자가 된다.