이진 검색 트리 정의와 조작

정의

N개의 원소 중에서 원하는 값을 찾는데 매번 절반으로 줄여나가기 때문에
시간 복잡도는 O(log*N)이다.

순회

이진 검색 트리를 중위 순회하면 정렬된 원소의 목록을 얻을 수 있다.

맨 왼쪽의 값은 최소 맨 오르쪽 값은 최대 값이다.

조작

이진 검색 트리가 유용할 때에는  원소의 추가 삭제 연산을 할 때이다.

만약 정렬된 배열에서 어떤 원소를 추가를 할 때 이 원소가 들어가야 하는 위치를 찾고

그 이후의 원소들은 다 한칸씩 옮겨야 하기 때문에 굉장히 오버헤드가 큰 반면에

이진트리에서는 새 원소가 들어갈 위치를 찾고 거기에 노드만 추가를 하면 되기 때문에

오버헤드가 굉장히 작다.

이진 검색 트리에서 원소의 삭제가 조금 까다로운데 어떤 원소를 삭제 할 때에는

해당노드의 왼쪽, 오른쪽 서브트리 즉, 두 서브트리를 합친 새로운 트리를 만들고

삭제가 되는 원소의 자리에 합친 트리를 붙여야 한다.

X보다 작은 원소의 수 찾기 / k번째 원소 찾기

이진 검색 트리에서 X보다 작은 원소가 몇 개 인지 크기순으로 정렬했을 때

앞에서부터 k번째 원소는 무엇인지 알아내는 것은 어렵지 않으나

표준라이브러리에서 제공하는 곳은 거의 없기 때문에 직접 구현을 해야 할 수밖에 없다.

요것은 트립(treap) 에서 살펴본다.