[Think Data Structures] 이진탐색트리(TreeMap) 구현 및 분석_1

이진 탐색 트리(binary search tree, BST)

---

요소가 정렬된 Map 인터페이스를 구현할 때 유용하게 쓰임

해싱의 문제점

• HashMap 클래스의 연산이 상수 시간이더라도 해싱이 느릴 수 있음(상수가 꽤 커질 수 있음)
• 해시 함수를 설계하는 것이 쉬운일이 아니며, 키가 특정하위 맵에 집중되면 성능이 나빠질 수 있음
• 키는 어떤 순서대로 저장되지 않음(테이블이 커지고 키가 재해시될 때 변하기도 함). 어떤 응용 프로그램에서는 키를 순서대로 유지하는 것이 필요하거나 유용할 때가 존재

Java에서는 TreeMap클래스를 제공

• TreeMap은 해시 함수를 사용하지 않음. 해싱 비용과 해시 함수를 고르는 어려움을 피할 수 있음
• 키는 이진탐색트리에 저장되는데, 선형시간으로 키를 순서대로 순회할 수 있음
• 핵심 메서드는 logN에 비례하며 상수시간만큼 우수하지 않지만 꽤 쓸만함

이진탐색트리

다음과 같은 속성이 있음

• 노드 왼쪽에 자식이 있다면 왼쪽 하위 트리의 모든 키는 노드에 있는 키보다 작음
• 노드 오른쪽에 자식이 있다면 오른쪽 하위트리의 모든 키는 노드에 있는 키보다 큼

일반적으로 비교 횟수는 트리에 있는 키의 개수가 아니라 트리의 높이에 비례합니다.

트리의 높이 h

노드의 개수 n

h=1 이면, n=1

h=2 이면, n=3

h=3 이면, n=7

h=4 이면, n=15

..

n = 2^h - 1

logn = h

O(logn)

containsValue 메서드는 트리 전체를 검색해야하기 때문에, 트리의 높이 h가 아니라 키의 개수인 n에 비례하게 된다.(트리를 전체 순회함)