二元搜尋樹有什麼用

二元搜尋樹主要用於搜尋和動態排序，二元樹進行“插入/查詢/刪除”的時間複雜度為“O(log(n))”，但是實際使用的時候通常不會有這麼快，因為插入順序所用的「middle」通常不是那麼準。

二元搜尋樹的作用

我知道的主要作用是搜尋和動態排序，二元樹進行插入/查詢/刪除的時間複雜度為O(log(n))。但是實際使用的時候通常不會有這麼快，因為你插入順序所用的middle通常不是那麼準，尤其是在插入資料的順序是有序或基本有序的時候，這顆二元樹會嚴重的不平衡，最糟糕的情況下會下降到和鍊錶一樣。

二元排序樹的操作主要有：

1.查找：遞迴尋找是否存在key。

2.插入：原樹中不存在key，插入key回傳true，否則回傳false。

3.建構：循環的插入操作。

4.刪除：（1）葉子節點：直接刪除，不影響原樹。

（2）僅有左或右子樹的節點：節點刪除後，將它的左子樹或右子樹整個移動到刪除節點的位置就可以，子承父業。

（3）既有左又有右子樹的節點：找到須要刪除的節點p的直接前驅或直接後繼s，用s來替換節點p，然後再刪除節點s。

以上是二元搜尋樹有什麼用的詳細內容。更多資訊請關注PHP中文網其他相關文章！