탐색 트리란, 동적 집합 연산을 지원하는 자료구조이다. 딕셔너리와 우선순위 큐로 사용 가능하다.기본 연산은 트리의 높이에 비례하는 시간이 소요된다.노드가 n개인 완전 이진 트리인 경우: $O(\log n)$노드가 n개인 선형 체인의 경우: $O(n)$탐색 트리의 유형에는 이진 탐색 트리, 레드-블랙 트리, B-트리 등이 있다Binary Search Trees트리 높이를 h라 할 때, 많은 동적 집합 연산을 $O(h)$시간 안에 수행할 수 있다.이진 트리는 각 노드가 객체로 구성된 linked list 자료 구조로 표현된다.root[T]는 트리 T의 루트를 가리키며, 각 노드는 다음과 같은 필드를 포함한다.keyleft: 왼쪽 자식right: 오른쪽 자식p: 부모, p[root[T]] = NIL저장된 ke..
