이진 검색 트리란

image.png

이진 트리란 노드의 자식을 최대 두 개까지만 가질 수 있는 트리를 말한다. 이진 검색 트리는 이진 트리의 왼 쪽 자식을 부모 노드보다 작은 값, 오른 쪽 자식을 부모 노드 보다 큰 값으로 두어 만들어진 트리를 말한다.

이진 검색 트리는 효율적인 연산들을 제공한다. 이진 검색 트리는 어떤 값을 찾을 때 연결 리스트처럼 시작부터 끝 까지 일일이 확인할 필요 없이 루트부터 찾고자 하는 값을 따라 절반씩 양을 줄여 가면서 검색하므로 훨씬 효율적이다. 또 이진 검색트리를 중위 순회하게 되면 작은 값부터 앞에 오게 되므로 원소들을 정렬한 결과를 얻을 수 있다.

이진 검색트리의 또 다른 장점은 효율적인 연산을 제공하면서 원소의 추가 삭제와 같은 조작이 쉽다는 것이다. 배열의 경우 원소를 추가하거나 삭제해야 될 경우 다른 원소들의 위치를 모두 바꿔줘야 하기 때문에 매우 비효율적인 연산이 되지만 이진 검색트리는 추가의 경우 해당하는 자리의 부모 자식 노드의 포인터만 바꿔주면 되고 삭제의 경우 서브 트리를 재귀적으로 합쳐주는 과정만 거치면 된다.

이진 검색 트리의 시간 복잡도

이진 검색 트리의 모든 연산은 트리의 높이와 비례하는 시간이 걸린다. 한 단계씩 작업을 수행할 때 마다 트리의 루트에서 리프까지 한 칸 씩 내려가기 때문이다. 자료의 개수가 N개라고 할 때 이진 검색 트리가 대칭적으로 평평하게 짜여져 있다면 logN에 해당하는 시간 복잡도를 갖는다. 그러나 자료의 추가 순서에 따라 불균형하게 트리가 만들어 진다면 N의 시간 복잡도를 갖게 될 수 있다. 따라서 효율적인 이진 검색 트리의 구현을 위해 레드 블랙 트리와 같은 개선된 이진 검색 트리를 사용하는 것이 일반적이다.