이진 탐색 트리 (Binary Search Tree)

얼핏보면 분할통치법을 쓸것 같지만 아닙니다!

분할 통치법은 양쪽으로 나눈 후, 모두 다루고 다시 합치지만

이진 탐색 트리는 양쪽으로 나눈 후 한쪽은 안씁니다!! ㅎㅎ

합치지도 않구요 !! ㅎㅎ

이진 탐색 트리의 핵심

key (left child) < key (parent) <= key (right child)

- 물론 반대도 성립합니다 -

의 성질을 이용하는 것

과정

1. 키 k가 주어짐

2. 현재 노드보다 작으면 왼쪽 부트리에서, 크다면 오른쪽 부트리에서 작업

3. 현재 노드와 k가 같아진다면 원소 반환하고 종료

4. 외부노드에 도달한다면, 탐색의 실패를 의미 --> 탐색 실패 원소 반환하고 종료 ("No Such Key")

성능

최악의 경우 - 편향 트리인 경우 --> O(n)

최선의 경우 - 좌우 대칭인 경우 --> O(log n)

코드는 코드 게시판에 올릴게요~