→ 딕셔너리, 세트를 구현할 때 쓸수있다. 그 이유는 뒤에서 살펴 보겠다.
이진탐색트리속성
- 부모 노드 왼쪽에는 무조건 부모노드보다 작은 자식노드가 들어가고 부모노드 오른쪽에는 부모노드보다 무조건 큰 자식 노드가 들어간다.
배열이나 파이썬리스트로 구현하지 않고 노드 인스턴스를 연결해서 구현
모든 자식노드가 부모의 레퍼런스를 저장하고 있다.
InOrder 순회를 하면 데이터의 값이 순서대로 출력된다.
⇒ ABCDEFGHI
삽입연산
- 새로운 노드 생성
- 루트 노드부터 비교하면서 저장할 위치 찾음
- 찾은 위치에 새롭게 만든 노드 연결
- 시간복잡도 : O(h) h=높이
탐색연산
- 주어진 노드의 데이터와 탐색하려는 데이터 비교
- 탐색하려는 데이터가 더 크면 노드의 오른쪽 자식으로간다.
- 탐색하려는 데이터가 더 작으면 노드의 왼쪽 자식으로 간다
- 찾을때까지 1~3과정을 반복한다.
- 탐색하려는 노드를 찾으면 리턴한다.
- 시간복잡도 : O(h) h=높이
삭제연산
초기 세팅 :삭제하려는 데이터를 갖는 노드를 먼저 찾아야 한다.
삭제하려는 데이터를 갖는 노드를 찾고 나면 총 세가지 경우로 나눌 수 있다.
- 삭제하려는 데이터가 leaf노드의 데이터일때
- 삭제하려는 데이터노드가 하나의 자식노드만 있을 때
- 삭제하려는 데이터의 노드가 두개의 자식이 있을 때
- 지우려는 노드의 successor를 받아옵니다. (find_min() 메소드 활용)
- successor는 지우려는 노드 오른쪽 부분트리에서 가장 작은 데이터이다.(즉, 지우려는 노드보다 바로 한단계 큰 노드라는 것이다.)
- 삭제하려는 노드 데이터에 successor의 데이터를 저장합니다.
- successor 노드를 삭제합니다.
- 지우려는 노드의 successor를 받아옵니다. (find_min() 메소드 활용)
이진 탐색트리 삭제 연산 시간 복잡도
초기 세팅 : 우선 공통적으로 삭제하려는 데이터를 갖는 노드를 탐색해야한다. → 탐색 시간 복잡도 → O(h) h=높이
- 삭제경우 : 지우려는 데이터노드가 leaf노드일때 → O(1)
- 삭제경우2 : 지우려는 데이터 노드가 하나의 자식이 있을때 → O(1)
- 삭제경우3 : 지우려는 데이터 노드가 두개의 자식이 있을때 → O(h) h=높이
| 탐색 | 탐색 후 단계들 | |
| 경우 1 | O(h) | O(1) |
| 경우 2 | O(h) | O(1) |
| 경우 3 | O(h) | O(h) |
탐색 적용... ⇒
| 탐색 + 탐색 후 단계들 | |
| 경우 1 | O(h) |
| 경우 2 | O(h) |
| 경우 3 | O(h) |
이진 탐색트리 높이
노드의 갯수가 n개 일때 높이가 항상 lg(n)은 아니다.
노드가 한쪽 방향으로 치우쳐져 있을때 즉, 편향되거나 치우쳐졌을때 최악의 경우 높이는 노드가 n일때 높이는 n이된다.
반면 트리가 균형을 이룰 수록 lg(n) 높이에 가까워 진다.
정리하자면...
- 편향된 트리 일수록 연산들은 비효율적
- 균형이 잡힌 트리일수록 연산이 효율적
이진 탐색 트리 평균 높이
평균적으로 이진 탐색 트리의 높이 h는 O(lg(n))
⇒ 하지만 삽입연산과 삭제연산들을 반복적으로 하면 높이가 O(lg(n)일 거라는 보장은 할수 없다.
| 이진 탐색 트리 연산 | 시간 복잡도 |
| 삽입 | O(h) (평균적 O(lg(n)), 최악 O(n)) |
| 탐색 | O(h) (평균적 O(lg(n)), 최악 O(n)) |
| 삭제 | O(h) (평균적 O(lg(n)), 최악 O(n)) |
노드들이 한쪽으로 편향되는 일은 흔하기 때문에 보통 높이 h를 써서 그대로 표현한다.
이진 탐색 트리를 통한 딕셔너리 구현
이진 탐색 트리 딕셔너리의 data 대신 Key-value로 구현 할수있으며 시간 복잡도는 동일하다.
추상자료형 세트나 딕셔너리를 코드로 구현할때 일반적인 경우에는 해시 테이블을 사용하는것이 이진 탐색트리를 사용하는 것보다 더 효율적이다.
하지만 세트의 데이터나 딕셔너리의 key를 정렬된 상태로 사용하고 싶을 때는 이진 탐색트리를 사용해야한다. 물론 이때 해시테이블때보다는 연산의 효율성은 조금 포기해야한다.
