-
二叉搜索樹
鎖定
二叉搜索樹原理
二叉搜索樹（BST）又稱二叉查找樹或二叉排序樹。一棵二叉搜索樹是以二叉樹來組織的，可以使用一個鏈表數據結構來表示，其中每一個結點就是一個對象。一般地，除了key和位置數據之外，每個結點還包含屬性lchild、rchild和parent，分別指向結點的左孩子、右孩子和雙親（父結點）。如果某個孩子結點或父結點不存在，則相應屬性的值為空（NULL）。根結點是樹中唯一父指針為NULL的結點，而葉子結點的孩子結點指針也為NULL。
[2]
二叉搜索樹結構
二叉搜索樹是能夠高效地進行如下操作的數據結構。
1.插入一個數值
2.查詢是否包含某個數值
二叉搜索樹性質
設x是二叉搜索樹中的一個結點。如果y是x左子樹中的一個結點，那麼y.key≤x.key。如果y是x右子樹中的一個結點，那麼y.key≥x.key。
在二叉搜索樹中：
1.若任意結點的左子樹不空，則左子樹上所有結點的值均不大於它的根結點的值。
2. 若任意結點的右子樹不空，則右子樹上所有結點的值均不小於它的根結點的值。
二叉搜索樹複雜度
二叉搜索樹算法實現
二叉排序樹的操作主要有：
1.查找：遞歸查找是否存在key。
2.插入：原樹中不存在key，插入key返回true，否則返回false。
3.構造：循環的插入操作。
4.刪除：（1）葉子節點：直接刪除，不影響原樹。
（2）僅僅有左或右子樹的節點：節點刪除後，將它的左子樹或右子樹整個移動到刪除節點的位置就可以，子承父業。
（3）既有左又有右子樹的節點：找到須要刪除的節點p的直接前驅或者直接後繼s，用s來替換節點p，然後再刪除節點s。
- 參考資料
-
- 1. 謝文韜. 基於無鎖結構的大容量數據高性能檢索系統研究[D].東南大學 ．中國知網．2017[引用日期2020-04-01]
- 2. Thomas H.Cormen、Charles E.Leiserson等．算法導論：機械工業出版社出版（第二版），2006-09-01
- 3. 秋葉拓哉 ，巖田陽一，北川宜稔．挑戰程序設計競賽：人民郵電出版社，2013-07
- 4. 大話數據結構．程傑：清華大學出版社，2011-06
