📌 이진 트리와 완전 이진 트리란?
- 이진 트리(binary tree): 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리. 즉, 자식 노드가 최대 두 개인 노드들로 구성된 트리를 말한다.
- 완전 이진 트리(complete binary tree): 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨에 한해서 가장 왼쪽부터 오른쪽으로 노드가 채워져 있는 트리를 말한다.
📌 이진 검색 트리란?
- 이진 검색 트리(binary search tree): 이진 검색 트리는 다음과 같은 조건을 갖는 이진 트리다.
- 왼쪽 서브트리 노드의 키 값은 노드의 키 값보다 작아야 한다.
- 오른쪽 서브트리 노드의 키 값은 노드의 키 값보다 커야 한다.
- 왼쪽 및 오른쪽 서브트리 노드도 각각 이진 검색 트리여야 한다.
다음과 같은 조건을 만족하기 때문에, 키 값이 같은 노드가 복수로 존재하지 않는다는 특징이 있다.
📌 이진 검색 트리의 특징
1. 구조가 단순하다.
2. 중위 순회의 깊이 우선 탐색(DFS)을 통해 노드의 키 값을 오름차순으로 구할 수 있다.
- [그림 2]의 예시를 통해 이진 검색 트리를 중위 순회할 경우, 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 - > 11 -> 12 라는 결과를 얻을 수 있다.
3. 이진 검색과 유사한 방식으로 빠르게 검색할 수 있다.
- 이진 검색의 시간복잡도는 O(logn)이고, 이진 검색 트리의 시간복잡도는 트리의 높이(h)의 영향을 받기 때문에 시간복잡도가 O(h)다. [그림 2]의 예시를 보았을 때, 높이 h에 따른 노드의 개수가 2^(k+1) - 1 개 이므로 이진 검색 트리의 높이는 logn이라 볼 수 있으며, 따라서 시간복잡도는 이진 검색의 시간복잡도와 같이 O(logn)이 된다.
- 하지만 이진 검색과 같은 시간복잡도를 갖는 것은 아니다. 이유는 아래의 그림을 통해 볼 수 있다.
[그림 3]과 같은 이진 검색 트리가 있을 경우, 시간복잡도가 O(logn)이 아닌 O(n)이 된다. 이렇게 트리의 균형이 한 쪽으로 치우쳐진 경우는 worst case이며, 앞에서 말했다싶이 O(n)의 시간복잡도를 가지게 된다.
4. 검색 뿐만 아니라 삽입, 삭제 또한 쉽다는 장점을 지니고 있다.
- 앞에서 말했듯 이진 검색 트리에서의 검색은 평균적으로 O(logn)이 나오고, 최악의 경우 O(n)의 시간복잡도를 가지게 된다. 이는 검색 뿐만 아니라 삽입, 삭제 또한 마찬가지이다. 이를 정리하자면 다음과 같다.
| 이진 검색 트리 연산 | 시간복잡도 |
| 검색 | 평균: O(logn), 최악: O(n) |
| 삽입 | 평균: O(logn), 최악: O(n) |
| 삭제 | 평균: O(logn), 최악: O(n) |
출처:
1. https://www.geeksforgeeks.org/binary-search-tree-data-structure/
Binary Search Tree - GeeksforGeeks
A page for Binary Search Tree Data structure with detailed definition of binary search tree, its representation and standard problems on binary search tree.
www.geeksforgeeks.org
2. https://steadily-worked.tistory.com/389
[자료구조] 이진 탐색 트리(2) (삭제, 시간 복잡도)
이진 탐색 트리 삭제 II 삭제하려는 데이터의 노드가 두 개의 자식이 있을 때 우선 지우려는 노드의 오른쪽 자식(16)으로 간다. 여기서, find_min 메소드의 파라미터에 root 대신 이 16을 넣어주면 된
steadily-worked.tistory.com
3. https://product.kyobobook.co.kr/detail/S000001817975
Do it! 자료구조와 함께 배우는 알고리즘 입문: 파이썬 편 | 시바타 보요 - 교보문고
Do it! 자료구조와 함께 배우는 알고리즘 입문: 파이썬 편 | 기업 코딩 테스트와 모든 시험의 기초가 되는 ‘자료구조와 알고리즘’! 213개의 그림과 136개의 파이썬 실전 예제로 빠르고! 쉽게! 배운
product.kyobobook.co.kr
'Computer Science > Data Structure' 카테고리의 다른 글
| Queue와 Priority Queue란? (0) | 2023.01.24 |
|---|---|
| 해시 테이블(Hash Table)이란? (0) | 2023.01.13 |
| 📖 연결 리스트(Linked list) (0) | 2022.04.26 |
