概念~
二叉查找樹(英語:Binary Search Tree),也稱二叉搜尋樹、有序二叉樹(英語:ordered binary tree),排序二叉樹(英語:sorted binary tree),是指一棵空樹或者具有下列性質的二叉樹:
若任意節點的左子樹不空,則左子樹上所有結點的值均小于它的根結點的值;
若任意節點的右子樹不空,則右子樹上所有結點的值均大于它的根結點的值;
任意節點的左、右子樹也分别為二叉查找樹;
沒有鍵值相等的節點。
二叉查找樹相比于其他資料結構的優勢在于查找、插入的時間複雜度較低——為O(log n)。
二叉查找樹是基礎性資料結構,用于建構更為抽象的資料結構,如集合、multiset、關聯數組等。
二叉查找樹的查找過程和次優二叉樹類似,通常采取二叉連結清單作為二叉查找樹的存儲結構。中序周遊二叉查找樹可得到一個關鍵字的有序序列,一個無序序列可以通過構造一棵二叉查找樹變成一個有序序列,構造樹的過程即為對無序序列進行查找的過程。每次插入的新的結點都是二叉查找樹上新的葉子結點,在進行插入操作時,不必移動其它結點,隻需改動某個結點的指針,由空變為非空即可。
搜尋、插入、删除的複雜度等于樹高,期望
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5iYkVDN5EzYwIjNhBTMyEDZxczMmFWM4QTY5Q2N0E2Yw8CXh9CXj9CXw8CXoRXYt9CXnJ3buEWakVWbptWa35CZh9GbwV3Lc9CX6MHc0RHaiojIsJye.png)
,最壞
(數列有序,樹退化成線性表)。
雖然二叉查找樹的最壞效率是O(n),但它支援動态查詢,且有很多改進版的二叉查找樹可以使樹高為
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5iYkVDN5EzYwIjNhBTMyEDZxczMmFWM4QTY5Q2N0E2Yw8CXh9CXj9CXw8CXoRXYt9CXnJ3buEWakVWbptWa35CZh9GbwV3Lc9CX6MHc0RHaiojIsJye.png)
故不失為一種好的動态查找方法。
其中C++的STL中的set就是使用的紅黑樹作為存儲結構的(ps:hash_set使用的是hash_table作為存儲結構)
在二叉搜尋樹b中查找x的過程為:
若b是空樹,則搜尋失敗,否則:
若x等于b的根節點的資料域之值,則查找成功;否則:
若x小于b的根節點的資料域之值,則搜尋左子樹;否則:
查找右子樹。
向一個二叉搜尋樹b中插入一個節點s的算法,過程為:
若b是空樹,則将s所指結點作為根節點插入,否則:
若s->data等于b的根節點的資料域之值,則傳回,否則:
若s->data小于b的根節點的資料域之值,則把s所指節點插入到左子樹中,否則:
把s所指節點插入到右子樹中。(新插入節點總是葉子節點)
DeleteBST
在二叉查找樹删去一個結點,分三種情況讨論:
若*p結點為葉子結點,即PL(左子樹)和PR(右子樹)均為空樹。由于删去葉子結點不破壞整棵樹的結構,則隻需修改其雙親結點的指針即可。
若*p結點隻有左子樹PL或右子樹PR,此時隻要令PL或PR直接成為其雙親結點*f的左子樹(當*p是左子樹)或右子樹(當*p是右子樹)即可,作此修改也不破壞二叉查找樹的特性。
若*p結點的左子樹和右子樹均不空。在删去*p之後,為保持其它元素之間的相對位置不變,可按中序周遊保持有序進行調整,可以有兩種做法:其一是令*p的左子樹為*f的左/右(依*p是*f的左子樹還是右子樹而定)子樹,*s為*p左子樹的最右下的結點,而*p的右子樹為*s的右子樹;其二是令*p的直接前驅(in-order predecessor)或直接後繼(in-order successor)替代*p,然後再從二叉查找樹中删去它的直接前驅(或直接後繼)。
在二叉查找樹上删除一個結點的算法如下:
Python版
binary_tree_delete
in-order-traversal
構造一顆二叉排序樹()
每個結點的
為該結點的層次數。最壞情況下,當先後插入的關鍵字有序時,構成的二叉查找樹蛻變為單支樹,樹的深度為
,其平均查找長度為
(和順序查找相同),最好的情況是二叉查找樹的形态和折半查找的判定樹相同,其平均查找長度和
成正比(
)。
本文轉自ZH奶酪部落格園部落格,原文連結:http://www.cnblogs.com/CheeseZH/p/5283510.html,如需轉載請自行聯系原作者