多動(dòng)態(tài)圖詳細(xì)講解二叉搜索樹
點(diǎn)擊上方“程序員大白”，選擇“星標(biāo)”公眾號(hào)
重磅干貨，第一時(shí)間送達(dá)
來(lái)源：lufficc
https://lufficc.com/blog/binary-search-tree
在計(jì)算機(jī)科學(xué)中，二叉搜索樹（Binary Search Tree）（有時(shí)稱為有序或排序的二叉樹）是一種能存儲(chǔ)特定數(shù)據(jù)類型的容器。二叉搜索樹允許快速查找、添加或者刪除某一個(gè)節(jié)點(diǎn)，并且它是動(dòng)態(tài)的集合。
二叉搜索樹按照關(guān)鍵字順序地保存節(jié)點(diǎn)，因此查找和其他操作可以使用二叉搜索原理：當(dāng)在樹（或者尋找插入新節(jié)點(diǎn)的地方）中查找節(jié)點(diǎn)時(shí)，它從根節(jié)點(diǎn)遍歷到葉節(jié)點(diǎn)，與每個(gè)節(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較，然后基于比較結(jié)果，決定繼續(xù)在左子樹或者右子樹中進(jìn)行搜索。平均而言，每次比較將跳過(guò)樹的大約一半的元素，這使得每次查找，插入或刪除一個(gè)節(jié)點(diǎn)所花費(fèi)的時(shí)間與樹的節(jié)點(diǎn)個(gè)數(shù)的對(duì)數(shù)成（樹的高度）正比，比線性表的性能要好很多。
定義
二叉搜索樹是以一棵二叉樹來(lái)組織，每個(gè)節(jié)點(diǎn)就是一個(gè)對(duì)象，包括key、衛(wèi)星數(shù)據(jù)，除此之外還包括一些為了維持樹結(jié)構(gòu)所需要的信息：left、right、parent，分別指向左孩子、右孩子、父節(jié)點(diǎn)。其中如果孩子節(jié)點(diǎn)或者父節(jié)點(diǎn)不存在時(shí)，用NIL表示。根節(jié)點(diǎn)是樹中唯一一個(gè)父節(jié)點(diǎn)為NIL的節(jié)點(diǎn)。
二叉搜索樹具有以下性質(zhì)：
1、如果節(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于等于它的根結(jié)點(diǎn)的值；
2、如果節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于等于它的根結(jié)點(diǎn)的值；
3、任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹；
比如在上圖中根節(jié)點(diǎn)的關(guān)鍵字為6，左子樹有關(guān)鍵字2、4和5，均不大于6；右子樹有關(guān)鍵字7和8，均不小于6。這個(gè)性質(zhì)對(duì)樹中的每個(gè)節(jié)點(diǎn)都成立，也就是說(shuō)，二叉搜索樹的定義是遞歸的。
在討論二叉搜索樹的操作之前，先看看二叉搜索樹的遍歷。二叉搜索樹可以使用先序遍歷（preorder tree walk）、中序遍歷（inorder tree walk）和后序遍歷（postorder tree walk）。這樣命名的依據(jù)是根據(jù)輸出關(guān)鍵字相對(duì)于左右子樹的位置。以中序遍歷為例，偽代碼如下：
INORDER-TREE-WALK(x) ?
? ?if x != nil ?// 如果節(jié)點(diǎn)不為空 ?
? ? ? ?INORDER-TREE-WALK(x.left) ?// 首先遞歸地遍歷左孩子，直到左孩子為空 ?
? ? ? ?print x.key ? ? // 輸出當(dāng)前節(jié)點(diǎn)（顯然第一次運(yùn)行到這里時(shí)，它是最小值，因?yàn)樗钦脴涞淖钭蠊?jié)點(diǎn)） ? ?
? ? ? ?INORDER-TREE-WALK(x.right) ?// 遞歸地遍歷右孩子對(duì)于上圖中的二叉搜索樹，動(dòng)態(tài)過(guò)程如下，這樣輸出結(jié)果為：2，4，5，6，7，8，即按照從小到大的順序排列。因?yàn)檩敵鰰r(shí)一直遍歷左孩子，知道遇到第一個(gè)左孩子為空的節(jié)點(diǎn)，將它輸出，然后出棧返回繼續(xù)輸出。
查詢
二叉搜索樹還應(yīng)該可以完成MINIMUM，MAXIMUM，SUCCESSOR和PREDECESSOR操作，即求最小值，最大值，后繼和前驅(qū)，并且這些操作都可以在o(lgn)的時(shí)間內(nèi)完成。
查找指定關(guān)鍵字
TREE-SEARCH操作在二叉樹中查找一個(gè)具有指定的關(guān)鍵字的節(jié)點(diǎn)，輸入樹的根節(jié)點(diǎn)指針和關(guān)鍵字k，如果存在，返回節(jié)點(diǎn)指針，否則，返回nil。
TREE-SEARCH(x, k) ?
? ?if x == nil or k == x.key ?//如不存在或者找到，直接返回 ?
? ? ? ?return x ?
? ?if k < x.key ? ? ? ? ? ? ? ? ? ?//如果小于當(dāng)前節(jié)點(diǎn)，根據(jù)性質(zhì)，在左子樹中搜索 ?
? ? ? ?return TREE-SEARCH(x.left, k) ?
? ?else ? ? ? ? ? ? ? ? ? ? ? ? ?//如果大于等于當(dāng)前節(jié)點(diǎn)，根據(jù)性質(zhì)，在右子樹中搜索 ?
? ? ? ?return TREE-SEARCH(x.right, k)比如查找關(guān)鍵字為5的節(jié)點(diǎn)，首先從根節(jié)點(diǎn)6開始，與5進(jìn)行比較，因?yàn)?小于6，因此在節(jié)點(diǎn)6的左子樹繼續(xù)搜索。到達(dá)節(jié)點(diǎn)4時(shí)因?yàn)?大于4，所以在4節(jié)點(diǎn)的右子樹搜索，這樣就順利找到了節(jié)點(diǎn)5，此時(shí)函數(shù)將返回指向節(jié)點(diǎn)5的指針。如果找不到目標(biāo)節(jié)點(diǎn)，TREE-SEARCH函數(shù)將返回nil。整個(gè)搜索過(guò)程如下：
最小/最大關(guān)鍵字
通過(guò)從樹根開始，沿著left孩子向下搜索，直到遇到nil，那么根據(jù)二叉搜索樹的性質(zhì)，如果節(jié)點(diǎn)x沒(méi)有左子樹，而x的右子樹的關(guān)鍵字肯定都大于x.key，因此此時(shí)當(dāng)前節(jié)點(diǎn)一定是整個(gè)樹中的最小值。
TREE-MINIMUM(x) ?
? ?while x.left != nil ?// 沿著左子樹一直深入搜索下去，直到遇到左子樹為空的節(jié)點(diǎn)，此時(shí)當(dāng)前節(jié)點(diǎn)為最小值 ?
? ? ? ?x = x.left ?
? ?return x同理，最大關(guān)鍵字的偽代碼如下：
TREE-MAXIMUM(x) ?
? ?while x.right != nil ?// 沿著右子樹一直深入搜索下去，直到遇到右子樹為空的節(jié)點(diǎn)，此時(shí)當(dāng)前節(jié)點(diǎn)為最大值 ?
? ? ? ?x = x.right ?
? ?return x求取最大、最小關(guān)鍵字的時(shí)間復(fù)雜度僅為o(lgn)，即與樹的高度成正比，因?yàn)椴檎疫^(guò)程自上而下形成一條線，線的最大長(zhǎng)度為數(shù)的高度，如求取最小值的過(guò)程：
前驅(qū)/后繼
給定二叉搜索樹的一個(gè)節(jié)點(diǎn)，有事需要按照中序遍歷的次序查找它的后繼，如果所有的關(guān)鍵字互不相同，則一個(gè)節(jié)點(diǎn)x的后繼一定是大于x.key的最小關(guān)鍵字。
TREE-SUCCESSOR(x) ?
? ?if x.right != nil ? //case 1:如果右子樹不為空，則后繼一定是右子樹的最小值，即大于x的最小值（右子樹的值都大于x節(jié)點(diǎn)） ?
? ? ? ?return TREE-MINIMUM(x.right) ?
? ?y = x.p ? ?// case 2:右子樹為空時(shí) ?
? ?while y != nil and x == y.right ?
? ? ? ?x = y ? // 變量x代表節(jié)點(diǎn)原始x的祖先，如果找到x，它是父節(jié)點(diǎn)的左孩子，則循環(huán)終止 ?
? ? ? ?y = y.p ? // y 代表節(jié)點(diǎn)x的父節(jié)點(diǎn)，如果x是y的左孩子，循環(huán)終止，并且返回y ?
? ?return y1、對(duì)于第一種情況比較簡(jiǎn)單，如果x右子樹不為空，那它的后繼就是右子樹的最左節(jié)點(diǎn)，對(duì)應(yīng)偽代碼case 1，例如下圖尋找68的后繼，即尋找68的右子樹的最小節(jié)點(diǎn)72，同時(shí)它也是右子樹的最左節(jié)點(diǎn)。
2、第二種情況是x的右子樹為空，注意x的后繼始終是大于x的最小值（或者不存在），所以當(dāng)x的右子樹不存在時(shí)大于x的最小值在哪兒呢？我們只需要簡(jiǎn)單的從x開始沿樹而上，找到第一個(gè)這樣一個(gè)節(jié)點(diǎn)：它的父節(jié)點(diǎn)為空（即根節(jié)點(diǎn)）或者它的左孩子是x節(jié)點(diǎn)的祖先節(jié)點(diǎn)（不一定是直接祖先）。例如下圖中為了尋找17的后繼，沿著樹上升，首先以此遇到了節(jié)點(diǎn)13，11，它們均不符合條件，因?yàn)樗鼈儾皇歉腹?jié)點(diǎn)的左孩子。當(dāng)遇到節(jié)點(diǎn)10時(shí)，此時(shí)x指向節(jié)點(diǎn)10，y指向節(jié)點(diǎn)19，并且節(jié)點(diǎn)10是節(jié)點(diǎn)19的左孩子，符合條件，所以返回節(jié)點(diǎn)y，它是節(jié)點(diǎn)x的后繼。
再舉一個(gè)例子，下圖為了找15的后繼，仍然沿著樹上升，直到遇到節(jié)點(diǎn)10（此時(shí)偽代碼中的變量x指向節(jié)點(diǎn)10）：它是15的祖先，而且是左孩子。所以此時(shí)返回節(jié)點(diǎn)10的父節(jié)點(diǎn)19，即節(jié)點(diǎn)15的后繼。
一個(gè)二叉搜索樹中除了最大節(jié)點(diǎn)外，都有后繼。對(duì)于前驅(qū)節(jié)點(diǎn)，和后繼節(jié)點(diǎn)原理一樣，這里不再贅述。
插入
插入操作會(huì)引起二叉搜索樹集合的動(dòng)態(tài)變化，因此需要一定的修改來(lái)維持二叉搜索樹。由于二叉搜索樹的性質(zhì)，即左孩子小于等于父節(jié)點(diǎn)，右孩子大于等于父節(jié)點(diǎn)，因此插入操作相對(duì)簡(jiǎn)單。
將一個(gè)節(jié)點(diǎn)插入到二叉搜索樹中，需要調(diào)用TREE-INSERT，該過(guò)程以節(jié)點(diǎn)z作為輸入，其中z.left = nil, z.right = nil, z.key = 將要插入數(shù)據(jù)的關(guān)鍵字：
TREE-INSERT(T, z) ?
? ?y = nil ?
? ?x = T.root ?
? ?while x != nil //循環(huán)結(jié)束后，x一定為空，此時(shí)x即為節(jié)點(diǎn)z要插入的地方 ?
? ? ? ?y = x ? ?//在這里給y賦值，保證循環(huán)結(jié)束后y始終是x的父節(jié)點(diǎn) ?
? ? ? ?if z.key < x.key ?
? ? ? ? ? ?x = x.left ?
? ? ? ?else ?
? ? ? ? ? ?x = x.right ?
? ? ? ?z.p = y ?// ?y始終是x的父節(jié)點(diǎn)，為了插入z，需要讓z的父節(jié)點(diǎn)指向x的父節(jié)點(diǎn)，即指向y ?
? ? ? ?if y == nil ?// ?如果y為空，說(shuō)明插入時(shí)是一棵空的樹，需要將樹根指向z ?
? ? ? ? ? ?T.root = z ?
? ? ? ?elseif z.key < y.key ? // ?判斷節(jié)點(diǎn)z是y的左孩子還是右孩子 ?
? ? ? ? ? ?y.left = z ?
? ? ? ?else ?
? ? ? ? ? ?y.right = z上述偽代碼從樹根開始，指針x記錄了一條向下的簡(jiǎn)單路徑，通過(guò)while循環(huán)比較z.key和x.key的大小，使指針x和指針y向下移動(dòng)，循環(huán)結(jié)束時(shí)則找到一個(gè)空的x并作為一個(gè)槽，將節(jié)點(diǎn)z放到這里（插入），同時(shí)保持節(jié)點(diǎn)y為節(jié)點(diǎn)x的父節(jié)點(diǎn)，這樣可以很方便的決定插入之后將z作為它的左孩子還是右孩子。舉一個(gè)例子：
上圖為了在樹中插入節(jié)點(diǎn)46，首先x指向根節(jié)點(diǎn)，節(jié)點(diǎn)46與根節(jié)點(diǎn)68（x節(jié)點(diǎn)）比較，小于68，因此指針x指向根節(jié)點(diǎn)（x節(jié)點(diǎn)）的左孩子62，然后一直下移。注意當(dāng)x指向45的時(shí)候，節(jié)點(diǎn)46大于45，因此將x指向節(jié)點(diǎn)45的右孩子，此時(shí)x為nil了，循環(huán)結(jié)束，也就找到了節(jié)點(diǎn)46的位置：節(jié)點(diǎn)45的右孩子。然后進(jìn)行一些操作將節(jié)點(diǎn)46插入到樹中即可。
刪除
從二叉搜索樹中刪除一個(gè)節(jié)點(diǎn)z稍微有點(diǎn)棘手，但總的來(lái)說(shuō)可以分為三種情況：
1、如果z沒(méi)有孩子節(jié)點(diǎn)，那么簡(jiǎn)單的將它刪除，并修改它的父節(jié)點(diǎn)，用nil作為孩子節(jié)點(diǎn)代替z即可。
2、如果z只有一個(gè)孩子，那么將這個(gè)孩子提升到z的位置，并修改它的父點(diǎn)，用z的孩子代替z即可。
3、如果z有兩個(gè)孩子，那么用z的后繼y（此時(shí)z的后繼y一定在z的右子樹中，因?yàn)閦的右孩子不為空）來(lái)占據(jù)z的位置，此時(shí)z的原來(lái)的右子樹部分稱為y的新的右子樹，并且z的左子樹稱為y的新的左子樹。這種情況稍微麻煩，因?yàn)檫€與y是否為z的右孩子相關(guān)。
第一種情況：節(jié)點(diǎn)z沒(méi)有孩子
這種情況比較簡(jiǎn)單，我們直接刪除節(jié)點(diǎn)z即可，并不會(huì)影響到二叉搜索樹的性質(zhì)：
用動(dòng)圖來(lái)表示就是：
第二種情況：節(jié)點(diǎn)z只有一個(gè)孩子
這種情況也比較簡(jiǎn)單，直接用節(jié)點(diǎn)z的孩子代替節(jié)點(diǎn)z即可。其實(shí)第一種情況和第二種情況可以歸為一個(gè)：節(jié)點(diǎn)z的孩子個(gè)數(shù)小于2個(gè)，直接用節(jié)點(diǎn)z的孩子代替節(jié)點(diǎn)z即可，只是節(jié)點(diǎn)z沒(méi)有孩子時(shí)是用的nil代替節(jié)點(diǎn)z，這里為了更加清楚地說(shuō)明分了三種情況。
例如如下圖，當(dāng)節(jié)點(diǎn)42只有左孩子時(shí)，直接將42的父節(jié)點(diǎn)6的右孩子指向節(jié)點(diǎn)29，將節(jié)點(diǎn)29的父節(jié)點(diǎn)設(shè)置為節(jié)點(diǎn)6即可：
或者只有右孩子時(shí)也是如此，直接將94的左孩子指向78，78的父節(jié)點(diǎn)指向94即可：
第三種情況：節(jié)點(diǎn)z有兩個(gè)孩子
這種情況稍微復(fù)雜一點(diǎn)，因?yàn)榇藭r(shí)我們需要找到節(jié)點(diǎn)z的后繼y，而后繼節(jié)點(diǎn)y又分為y是節(jié)點(diǎn)z的直接右孩子或者不是。
1、z的后繼y是?z的右孩子
此時(shí)可以直接用后繼y代替z，而且y的左孩子此時(shí)一定為空（因?yàn)楹罄^的左孩子一定為空），再用z的左孩子代替y的原來(lái)為空的左孩子即可。
用動(dòng)圖表示刪除節(jié)點(diǎn)67就是：
2、z的后繼y不是?z的右孩子
在這種情況下我們先用y的右孩子x代替y，然后再用y代替z:
用動(dòng)圖表示刪除節(jié)點(diǎn)50就是用74代替73，即將73的父節(jié)點(diǎn)82的右孩子指向74,74的父節(jié)點(diǎn)設(shè)置為82，然后再用73代替50，即將50左孩子31設(shè)置為73的左孩子，50的右孩子82設(shè)置為73的右孩子：
為了實(shí)現(xiàn)刪除過(guò)程的偽代碼，我們需要定義一個(gè)子過(guò)程TRANSPLANT，它是用為了用以v為根的子樹替換以u(píng)為根的子樹，讓u的雙親節(jié)點(diǎn)變?yōu)関的雙親節(jié)點(diǎn)，即讓v稱為u的雙親節(jié)點(diǎn)的孩子：
TRANSPLANT(T, u, v) ?
? ?if u.p == nil ? // 當(dāng)u位樹的根節(jié)點(diǎn)時(shí)，直接將樹的根節(jié)點(diǎn)指向v ?
? ? ? ?T.root = v ?
? ?elseif u == u.p.left ? // 如果u是左孩子，則u的父節(jié)點(diǎn)的左孩子指向v ?
? ? ? ?u.p.left = v ?
? ?else ? ?// 如果u是右孩子，則u的父節(jié)點(diǎn)的右孩子指向v ?
? ? ? ?u.p.right = v ?
? ?if v != nil ? ? ?
? ? ? ?v.p = u.p ? ?// 將v的父節(jié)點(diǎn)設(shè)為u的父節(jié)點(diǎn)然后實(shí)現(xiàn)具體的刪除過(guò)程：
TREE-DELETE(T, z) ?
? ?if z.left == nil ?// 如果左孩子為空，則直接用右孩子代替z即可，而不管右孩子是否為空（右孩子為空時(shí)對(duì)應(yīng)情況一否則對(duì)應(yīng)情況二） ?
? ? ? ?TRANSPLANT(T, z, z.right) ?
? ?elseif z.right == nil ?// 右孩子為空，直接用做孩子代替z ?
? ? ? ?TRANSPLANT(T, z, z.left) ?
? ?else y = TREE-MINIMUM(z.right) ?// 左右孩子均不為空，找到z的后繼y，即z的右子樹的最小值，對(duì)應(yīng)第三種情況 ?
? ? ? ?if y.p != z ? // 如果z的后繼y不是z的右孩子，對(duì)應(yīng)第三種情況的2 ?
? ? ? ? ? ?TRANSPLANT(T, y, y.right) ?// 用y的右孩子代替y ?
? ? ? ? ? ?y.right = z.right ? ?// 將y的右孩子指向z的右孩子 ?
? ? ? ? ? ?y.right.p = y ? ? // 將y的右孩子(原來(lái)的z的右孩子)的父節(jié)點(diǎn)設(shè)為y ?
? ? ? ?TRANSPLANT(T, z, y) ?// 用y代替z ?
? ? ? ?y.left = z.left ?
? ? ? ?y.left.p = p因此總的來(lái)說(shuō)，刪除操作可以分為兩大類：
1、z的孩子總數(shù)小于2時(shí)，直接用z的孩子代替z即完成了對(duì)z的刪除。
2、z有兩個(gè)孩子時(shí)：
2.1. z的后繼y是z的右孩子：直接用y代替z即可（別忘了將z的左孩子的父節(jié)點(diǎn)設(shè)置為y）。
2.2. z的后繼y不是z的右孩子：先用y的右孩子x代替y，再用y代替z。
總結(jié)
因?yàn)槎嫠阉鳂涞男再|(zhì)，即可以在每個(gè)比較之后將數(shù)據(jù)規(guī)模變?yōu)樵瓉?lái)的一半，因此平均情況下每一個(gè)操作都可以在o(lgn)的時(shí)間內(nèi)完成，即花費(fèi)時(shí)間與樹的高度成正比。但在最壞的情況下，二叉搜索樹就退化為一個(gè)鏈表，此時(shí)的時(shí)間復(fù)雜度退化到了o(n)。但很多改進(jìn)版的二叉查找樹可以使樹高為o(lgn)，如SBT，AVL樹，紅黑樹等。
參考文獻(xiàn)
1、算法導(dǎo)論
2、維基百科
3、visualgo
推薦閱讀
關(guān)于程序員大白
程序員大白是一群哈工大，東北大學(xué)，西湖大學(xué)和上海交通大學(xué)的碩士博士運(yùn)營(yíng)維護(hù)的號(hào)，大家樂(lè)于分享高質(zhì)量文章，喜歡總結(jié)知識(shí)，歡迎關(guān)注[程序員大白]，大家一起學(xué)習(xí)進(jìn)步！