개념
이진 탐색 트리 (Binary Search Tree)
- 모든 노드의 왼쪽 서브 트리는 해당 노드의 값보다 작은 값들만 가진다
and 모든 노드의 오른쪽 서브 트리는 해당 노드의 값보다 큰 값들만 가진다
이진 탐색 트리 의 특징
-각각의 노드들을 맨 아래의 수평선에 사영시키면, 사영된 노드는 왼쪽부터 작은순임
동작
이진 탐색 트리의 최소값
- 트리의 가장 왼쪽에 존재
이진 탐색 트리의 최대값
- 트리의 가장 오른쪽에 존재
트리를 순회하는 방식 (3가지)
순회
: 트리의 모든 노드들을 1번씩 방문하는 것
1. inorder traversal (중위 순회)
0) 루트 노드에서 출발
1) 재귀적으로 왼쪽 서브 트리 순회 [전위]
2) 현재 노드 방문 (ex.값 출력) -> [중위]
3) 재귀적으로 오른쪽 서브 트리 순회 [후위]
(이진탐색트리에 한해서) 중위 순회의 특징
-각각의 노드들을 맨 아래의 수평선에 사영시키면, 사영된 노드 순서대로 방문됌(출력됌) 즉, 정렬된 형태로 접근이 가능함
-일반적인 트리에서도 쓰임 (binary search tree 에서만 쓰이는 게 아님)
2. preorder traversal (전위 순회)
0) 루트 노드에서 출발
1) 현재 노드 방문 (ex. 값 출력) -> [전위]
2)재귀적으로 왼쪽 서브 트리 순회 [중위]
3)재귀적으로 오른쪽 서브 트리 순회 [후위]
3. postorder traversal (후위 순회)
0) 루트 노드에서 출발
1) 재귀적으로 왼쪽 서브 트리 순회 [전위]
2) 재귀적으로 오른쪽 서브 트리 순회 [중위]
3) 현재 노드 방문 (ex. 값 출력) -> [후위]
노드의 predecessor(선임자)
해당 노드보다 값이 작은 노드들 중에서, 가장 값이 큰 노드
(구현의 관점)
임의의 노드의 predecessor를 구하는 방법
1) 그 노드의 왼쪽 서브트리가 있는 경우
왼쪽 서브트리에서 최대값을 가지는 노드를 찾기2) 그 노드의 왼쪽 서브트리가 없는 경우
그 노드의 조상들을 거꾸로 찾아올라가면서 (우측 상단이 아니라)
좌측 상단으로 거슬러 올라가서 처음 만나는 조상 노드를 찾기
노드의 successor(후임자)
해당 노드보다 값이 큰 노드들 중에서, 가장 값이 작은 노드
(구현의 관점)
임의의 노드의 successor를 구하는 방법
1) 그 노드의 오른쪽 서브트리가 있는 경우
오른쪽 서브트리에서 최소값을 가지는 노드를 찾기2) 그 노드의 오른쪽 서브트리가 없는 경우
그 노드의 조상들을 거꾸로 찾아올라가면서 (좌측 상단이 아니라)
우측 상단으로 거슬러 올라가서 처음 만나는 조상 노드를 찾기
이집 탐색 트리의 (삽입/삭제/검색) 방식
삽입(insert)
- 루트 노드에서 시작
삭제(delete)
- 루트 노드에서 시작
- 삭제하려는 노드가 있는지 "검색"해서 있으면 "삭제"
- 1) 자녀가 0개인 노드 삭제:
삭제될 노드를 가리키던 레퍼런스를, 가리키는 게 없도록 처리 - 2) 자녀가 1개인 노드 삭제:
삭제될 노드를 가리키던 레퍼런스를, 삭제될 노드의 자녀를 가리키게 변경 - 3) 자녀가 2개인 노드 삭제:
삭제될 노드의 오른쪽 서브 트리에서, [값이 가장 작은 노드]가 삭제될 노드를 대체
- 1) 자녀가 0개인 노드 삭제:
삭제(delete) 후에도, 이진 트리의 속성을 유지하기 위해 레퍼런스를 잘 조정해야함
검색(search)
- 루트 노드에서 시작
이진 탐색 트리의 시간 복잡도
시간 복잡도는 점근적 방식을 통해 분석함.
N이 무한대로 갔을 때 어떤 형태를 띄게 될까? 를 분석하는 것임.
*N = 트리의 노드 수
순서: best / avg / worst
- insert: Θ(1) / O(logN) / Θ(N)
- delete: Θ(1) / O(logN) / Θ(N)
- search: Θ(1) / O(logN) / Θ(N)
일부 문서에서는 best case를 O(logN)으로 표기하기도 한다.
왜냐면 트리의 구조에 따라서 case를 구분하여 시간복잡도를 구할 수도 있기 때문이다.예를 들면, 아래와 같다.
- best case
중간에 하나도 노드가 비어있지 않은 꽉찬(perfect) 이진 탐색 트리- average case
적당히 밸런스가 있는(혹은 밸런스가 랜덤성을 띄는) 이진 탐색 트리- worst case
편향된 이진 탐색 트리
avg (= 평균적, 일반적)
- 트리에 있는 노드들이 어느정도 균형을 맞춰서 퍼져 있는 형태를 의미함
- 즉, 임의의 [좌/우] 서브 트리의 높이 차이가 크게 나지 않는 것
worst (= 최악, 극단적)
모든 노드에 접근하는 경우
(삽입/삭제/검색) 은 루트 노드에서 시작한다.
[좌/우] 어떤 서브 트리를 선택하든,
선택한 쪽을 집중하고, 선택하지 않은 쪽은 신경쓰지 않는다.
따라서 점근적 방식에서 생각해보면 size를 1/2로 줄여나가는 것으로 생각할 수 있다.
이진탐색트리의 장점
삽입/삭제 가 유연하다
- 레퍼런스 조정만 잘해주면 되기 때문임
값의 크기에 따라, [좌/우] 서브트리가 나눠지기에, 삽입/삭제/검색이 보통은 빠르다
값의 순서대로 순회 가능하다
- inorder traversal (중위 순회)를 하면, 값이 정렬된 형태로 접근이 가능함
이진탐색트리의 단점
트리가 구조적으로 한쪽으로 편향될수록, 삽입/삭제/검색 등등의 동작 수행 시간이 악화된다
"단점"을 해결하기 위해 사용되는 트리
스스로 균형을 잡는 이진탐색트리
worst의 경우에도 (삽입/삭제/검색)의 시간복잡도가 모두 O(logN)임
- 1) AVL 트리
- 2) Red-Black 트리
