이진 탐색 트리_2

이진 탐색 트리와 해시 테이블

해시 테이블로 구현하는 딕셔너리와 세트 자료형을 이진 탐색 트리로 구현할 수 있다.

노드 인스턴스를 딕셔너리와 세트의 인스턴스로 지정하여 구현할 수 있다고 한다.

먼저 왜 이진 탐색 트리로 딕셔너리와 세트 자료형을 구현해서 사용하는 이유를 알아보자.

딕셔너리와 세트 자료형은 파이썬 내부적으로 해시 테이블로 구현되어 있다.(해시 테이블 포스팅 참고)

---

굳이 이진 탐색 트리로 구현하는 이유는 뭘까?

해시 테이블의 경우 데이터의 순서 관계를 저장하지 않는 자료구조이다. 

반면에, 이진 탐색 트리의 경우 데이터 사이에 순서를 저장하는 역할 하는 자료구조이며 in-order 방식으로 노드를 순회하면 트리 안에 있는 데이터를 순차적으로 출력할 수 있다.

결국, 세트의 데이터나 딕셔너리의 key를 정렬된 상태로 사용하고 싶을 때는 이진 탐색 트리를 사용한다.

일반적인 경우 당연히 해시 테이블로 구현된 자료형을 사용하는게 효율적이다. 물론 이진 탐색 트리로 구현을 해 사용해야하는 상황이라면 연산의 효율성은 포기해야 한다고 한다!

---

이진 탐색 트리의 한계점

이진 탐색 트리에서는 탐색/ 삽입/ 삭제 연산의 시간복잡도는 모두 O(H)이다.

트리의 높이가 낮을수록 연산을 하기 효율적이라는 것을 알 수 있다.

사실 이진 탐색 트리는 완전 이진 트리가 아닌 경우가 많다. 즉, 노드의 개수가 N개 일때 트리의 높이가 항상 H O(logH)이라고 단정지을 수는 없다는 뜻이다.

트리의 높이에 의해 수행 시간이 결정되는 구조인데 만약 이진 탐색트리가 아래와 같은 구조를 갖게 된다면 어떻게 될까

이진 탐색 트리가 완전 균형 트리가 아니라는 점에서 발생한다.

최악의 경우 이진 탐색 트리의 높이는 O(n)이 된다. 

위와 같이 트리 안에서 노드가 직선적인 모양으로 저장되는 것을 트리가 한쪽으로 편향됐다, 치우쳤다라 표현한다.

항상 이처럼 최악의 경우가 일어나는 것은 아니기에 평균적으로 라는 단어를 사용하여 

트리의 평균 높이를 O(logN)으로 볼 수 있다고 한다.

총 n개의 데이터를 이진 탐색 트리에 삽입하면, 삽입을 할 때 그 순서의 경우의 수는 n!입니다.
그러니까 1 ~ 6의 정수 데이터를 삽입하는 경우, 총 경우의 수는 6 * 5 * 4 * 3 * 2 * 1
6∗5∗4∗3∗2∗1입니다.
수학적으로 모든 순서의 확률이 동일하다고 가정하고 이 경우들의 평균 높이를 계산하면 O(lg(n))
이 됩니다.

평균적으로 이진 탐색 트리의 높이 H는 O(logN)이라 표현 할 수 있다.

---

이전 포스팅에서 이진 탐색 트리는 아래와 같은 트리 형태로 이루어져 있다는 가정하에 탐색/ 삽입/ 삭제를 알아보았다.

위와 같이 트리 루트 노드를 기준으로 왼쪽과 오른쪽이 균형을 이룬 모습으로 

트리의 높이가 작을수록, 높이가 log(N)에 가까울수록 트리가 균형이 잡혔다라 표현한다.

---

summary

아진 탐색 트리의 연산들의 시간은 모두 트리 높이 H에 비례한다.

편한된 트리일 수록 연산들인 비효율적이며

균형이 잡힌 트리 일 수록 연산들이 효율적이다.

평균적으로 이진 탐색 트리의 높이 H는 O(logH)이다. 하지만 이는 삽입 /삭제 연산들을 반복할때마다 노드가 재배치되며 높이가 항상! O(logN)이라는 보장은 할 수 없다. (트리가 균형을 잃기 때문이다.)

 

이진 탐색 트리에서 시간 복잡도를 O(H) 로 표기하는 이유

삽입과 삭제 연산들을 반복하다보면 이진 탐색 트리의 노드들이 한쪽으로 편향될 수 있기 때문에 이진 탐색 트리의 연산들의 시간 복잡도는 보통 높이 그대로 O(h)O(h)로 표기한다.

 

 

 

출처 : 코드 잇(자료구조)

자료 구조 | 코드잇 (codeit.kr)