여기에서 일부 검색 트리와 차이점을 살펴보겠습니다. 다양한 검색 트리가 있습니다. 그들은 본질적으로 다릅니다. 기본 검색 트리는 이진 검색 트리(BST)입니다. 다른 검색 트리로는 AVL 트리, B 트리, Red-Black 트리, 스플레이 트리 등이 있습니다.
이 트리는 작업을 기반으로 비교할 수 있습니다. 이 트리의 시간 복잡도를 확인할 수 있습니다.
| 검색 트리 | 평균 사례 | ||
|---|---|---|---|
| | 삽입 | 삭제 | 검색 |
| 이진 검색 트리 | O(로그 n) | O(로그 n) | O(로그 n) |
| AVL 트리 | O(로그2 n) | O(로그2 n) | O(로그2 n) |
| B 트리 | O(로그 n) | O(로그 n) | O(로그 n) |
| 적-검정 나무 | O(로그 n) | O(로그 n) | O(로그 n) |
| 스프레이 트리 | O(로그2 n) | O(로그2 n) | O(로그2 n) |
| 검색 트리 | 최악의 경우 | ||
|---|---|---|---|
| | 삽입 | 삭제 | 검색 |
| 이진 검색 트리 | O(n) | O(n) | O(n) |
| AVL 트리 | O(로그2 n) | O(로그2 n) | O(로그2 n) |
| B 트리 | O(로그 n) | O(로그 n) | O(로그 n) |
| 적-검정 나무 | O(로그 n) | O(로그 n) | O(로그 n) |
| 스프레이 트리 | O(로그2 n) | O(로그2 n) | O(로그2 n) |