-
二叉搜索樹
鎖定
二叉搜索樹原理
二叉搜索樹(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