資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
Microsoft Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學資料結構中搜索樹的比較
在這裡，我們將看到一些搜尋樹及其區別。存在許多不同的搜尋樹，它們本質上有所不同。基本的搜尋樹是二叉搜尋樹 (BST)。其他一些搜尋樹包括 AVL 樹、B 樹、紅黑樹、伸展樹等。
這些樹可以根據它們的運算進行比較。我們將看到這些樹的時間複雜度。
| 搜尋樹 | 平均情況 | ||
|---|---|---|---|
| 插入 | 刪除 | 查詢 | |
| 二叉搜尋樹 | O(log n) | O(log n) | O(log n) |
| AVL樹 | O(log2 n) | O(log2 n) | O(log2 n) |
| B樹 | O(log n) | O(log n) | O(log n) |
| 紅黑樹 | O(log n) | O(log n) | O(log n) |
| 伸展樹 | O(log2 n) | O(log2 n) | O(log2 n) |
| 搜尋樹 | 最壞情況 | ||
|---|---|---|---|
| 插入 | 刪除 | 查詢 | |
| 二叉搜尋樹 | O(n) | O(n) | O(n) |
| AVL樹 | O(log2 n) | O(log2 n) | O(log2 n) |
| B樹 | O(log n) | O(log n) | O(log n) |
| 紅黑樹 | O(log n) | O(log n) | O(log n) |
| 伸展樹 | O(log2 n) | O(log2 n) | O(log2 n) |
更新於：2019年8月27日
2K+ 次瀏覽
廣告