이진탐색트리는 단어에서 알 수 있듯이 이진트리에서 탐색을 하는 자료구조 입니다. 이진트리를 기반으로 하지만 약간의 차이점이 있는데 어떤 차이점이 존재하는지 알아보겠습니다.
왼쪽 서브 트리는 루트 노드보다 값이 작습니다.오른쪽 서브 트리는 루트 노드보다 값이 큽니다.서브 트리도 이진 탐색트리의 구성을 갖고 있습니다.
위의 그림이 이진탐색트리의 예시입니다. 왼쪽 서브트리를 보면 루트 노드의 값인 8보다 작은 것을 볼 수 있습니다. 그리고 오른쪽 서브트리는 루트노드 8보다 값이 크다는 것도 확인할 수 있습니다.
그리고 이진탐색트리는 중위 순회 방법으로 탐색하면 2-3-5-8-10-11-14-16 같이 정렬이 된다는 특징을 가지고 있습니다.
11을 탐색한다고 가정해보겠습니다.
- 찾으려는 값 11과 루트노드 8을 비교합니다. 11 > 8 이기 때문에
오른쪽 서브트리로 이동합니다. - 오른쪽 서브트리도 이진탐색트리의 구조를 갖추고 있습니다. 서브트리의 루트노드인 10과 11을 비교합니다. 11 > 10 이기 때문에
오른쪽 서브트리로 이동합니다. - 그리고 오른쪽 서브트리의 루트노드인 14와 11을 비교합니다. 14 > 11 이기 때문에 이번에는
왼쪽 서브트리로 이동합니다. - 이 때 14의 왼쪽 노드는 11이기 때문에 탐색 성공을 하게 됩니다.
이러한 과정을 반복해서 탐색을 하게 되는데 위와 같이 이진트리가 경사지지 않다면 탐색을 할 때 비교해야 할 노드들이 절반씩 사라지기 때문에 효과적입니다.
탐색 시간복잡도는 트리의 높이에 비례한다는 것을 알 수 있습니다. 즉, 높이가 높을 수록 탐색연산에 오래걸리게 됩니다. 아래에서 다시 살펴보겠지만, 트리의 높이가 n이라면 O(n)이 걸리게 되고 logN이라면 O(logN)이 걸리게 됩니다.
이진탐색트리에서 노드를 삽입연산을 할 때 노드가 들어갈 위치를 먼저 탐색하는 과정이 필요합니다. 이유는 이진 탐색트리에서는 같은 키 값을 갖는 노드가 없어야 하기 때문이고 또한 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치이기 때문입니다.
삽입연산의 시간복잡도 역시 트리의 높이게 비례하게 됩니다. 높이가 n이라면 O(n), logN이라면 O(logN)이 걸리게 됩니다.
삭제 연산은 삽입 연산과는 다르게 많이 복잡합니다. 삭제 연산도 삽입 연산과 마찬가지로 삭제할 노드를 찾기 위한 탐색의 과정이 필요합니다.
삭제 연산에서의 경우는 3가지가 있습니다.
삭제하려는 노드가 단말 노드일 경우삭제하려는 노드가 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우삭제하려는 노드가 두개의 서브 트리 모두 가지고 있을 경우
단말 노드란 가장 마지막에 존재하는 노드를 말합니다.(즉, 자식 노드가 존재하지 않습니다.) 이번 삭제 연산이 그나마 제일 쉽습니다.
과정은 위와 같이 삭제할 노드가 존재하는 위치를 탐색한 후에 부모노드에서 삭제할 노드의 연결을 끊어주면 됩니다.
위의 그림을 보면 알 수 있듯이 삭제하려는 노드가 서브트리를 가지는 경우입니다. 이 경우도 그렇게 어렵지는 않습니다. 삭제하려는 서브트리를 삭제하려는 노드 부모와 연결시키면 됩니다.
삭제하려는 노드가 왼쪽 서브트리, 오른쪽 서브트리를 모두 가지고 있으면 서브트리 중에서 어떤 것을 삭제된 노드 자리에 채워야 할까요?
삭제할 노드와 가장 가까운 값은 왼쪽 서브트리의 가장 큰 값 또는 오른쪽 서브트리의 가장 작은 값이라는 것을 생각할 수 있습니다.
루트노드 보다 작으면 왼쪽 서브트리, 루트노드 보다 크면 오른쪽 서브트리로 구성됩니다. 그렇기 때문에 위와 같이 생각할 수 있는 것입니다.
따라서 위와 같이 왼쪽 서브트리의 가장 큰 값을 삭제된 노드에 채울지, 오른쪽 서브트리의 가장 작은 값을 삭제된 노드에 채울지를 결정하면 됩니다.(코드로 구현하려고 하니 쉽지 않습니다..)
이진탐색트리의 삽입, 삭제, 탐색 연산은 높이에 비례합니다. 만약 트리의 높이가 h라면 시간복잡도는 O(h)가 됩니다.
트리의 높이가 h가 되려면 위와 같이 경사트리가 되어야 합니다. 이러면 일반 리스트에서 탐색을 하는 것과 동일해지기 때문에 트리의 이점을 가지지 못합니다.
하지만 일반적으로 트리의 높이는 logN 이기 때문에 이 때 탐색, 삽입, 삭제의 시간복잡도는 O(logN)이 됩니다.
