查找樹

sschrodinger

2019/08/16

二叉查找樹

二叉查找樹（BST）是一棵二叉樹，其中每一個(gè)節(jié)點(diǎn)都包含一個(gè) Comparable 的鍵（以及其相關(guān)的值）稳其，且每個(gè)節(jié)點(diǎn)的鍵都大于其左子樹中的任意節(jié)點(diǎn)的鍵而小于右子樹的任意節(jié)點(diǎn)的鍵（即不允許重復(fù)）窑多。

如下：

8ed5b0f1fbce498dc80646d75a76d7e.jpg

基本操作

get() 操作

使用 public Value get(Key key) 定義待错，獲得當(dāng)前 key 的值套菜。實(shí)現(xiàn)非常簡(jiǎn)單尔觉，直接遞歸就行。

put() 操作

使用 public void put(Key key, Value value) 定義傲宜，找打當(dāng)前的 key 并更新，沒有找到則者新建節(jié)點(diǎn)

min()/max() 操作

使用 public Node min(Node root) 和 public Node max(Node root) 定義夫啊，返回 root 中的最小鍵或者最大鍵函卒。

如下遞歸方式可以實(shí)現(xiàn)返回最小鍵：

• 如果根節(jié)點(diǎn)的左鏈接為空，那么這棵樹的最小鍵就是根節(jié)點(diǎn)撇眯。
• 否則报嵌，最小鍵就是左連接中的最小鍵

floor(Key key)/ceiling(Key key) 操作

使用 public Node floor(Key key) 和 public Node ceiling(Key key) 定義，返回 root 中該鍵的向下取整值或者向上取整值熊榛。

使用如下的遞歸方式可以實(shí)現(xiàn) floor(Key key)：

• 如果給定的 key 小于二叉樹的根節(jié)點(diǎn)的鍵锚国，那么 floor(key) 一定在左子樹中；
• 如果給定的 key 大于根節(jié)點(diǎn)玄坦，那么只有當(dāng)根節(jié)點(diǎn)右子樹中存在小于等于 key 的節(jié)點(diǎn)時(shí)血筑， floor(key) 才在右子樹中，否則根節(jié)點(diǎn)就是 floor(key)

如下：

[圖片上傳中...(1f66416af4b09e8800514d478942357.jpg-7d32d3-1566027254035-0)]

select()/rank() 操作

選擇操作使用 public Node select(int index)煎楣，選擇出排名為 k 的鍵（即樹中正好有 k 個(gè)小于他的鍵）豺总。

為了完成該功能，需要對(duì) Node 節(jié)點(diǎn)進(jìn)行擴(kuò)充择懂，增加屬性 N喻喳，代表以該節(jié)點(diǎn)為根的子樹中的節(jié)點(diǎn)總數(shù)。

可以使用如下的遞歸方式找到元素：

• 如果左子樹中的節(jié)點(diǎn)個(gè)數(shù) t > k困曙，繼續(xù)遞歸的在左子樹查找排名為 k 的鍵表伦，
• 如果等于 k谦去，返回根節(jié)點(diǎn)
• 如果 t < k，遞歸右子樹查找排名為 (k - t - 1) 的鍵

如下：

1f66416af4b09e8800514d478942357.jpg

排名操作使用 public int rank(Key key)蹦哼，判斷該 key 的排名是多少哪轿。

• rank(key) 返回該 key 對(duì)應(yīng)的排名 k
• 如果key 和根相等，返回左子樹節(jié)點(diǎn)總數(shù) t
• 如果 key 小于根翔怎，返回該 key 在左子樹的排名
• 如果 key 大于根窃诉，返回 t + 1 + 右子樹的排名

delete() 操作

首先考慮刪除最大鍵(deleteMax())/最小鍵(deleteMin())。

由 public Node deleteMax(Node root) 和 public Node deleteMin(Node root) 定義赤套，分別返回被刪除之后的樹的根節(jié)點(diǎn)

最小鍵一定是沒有從根開始遍歷沒有左子樹的節(jié)點(diǎn)（左子樹的節(jié)點(diǎn)一定小于根節(jié)點(diǎn)）飘痛，那么我們就需要不斷深入根節(jié)點(diǎn)的左子樹直到遇到一個(gè)空連接，然后將指向該根節(jié)點(diǎn)的鏈接指向該節(jié)點(diǎn)的右子樹容握。

如下：

ed6634fb18276565ad2c53fe31dd9eb.jpg

最大鍵同理宣脉。

接下來是其他節(jié)點(diǎn)的刪除。我們可以使用刪除最大鍵/最小鍵的思路刪除任何只有一個(gè)子節(jié)點(diǎn)（或者沒有子節(jié)點(diǎn)）的節(jié)點(diǎn)剔氏。

但是如果刪除的節(jié)點(diǎn)有兩棵子樹塑猖，但是刪除之后只有一個(gè)空出來的鏈接。刪除節(jié)點(diǎn) x 后谈跛，可以用他的后繼節(jié)點(diǎn)填補(bǔ)他的位置羊苟。

因?yàn)?x 有一個(gè)右子節(jié)點(diǎn)，因此他的后繼節(jié)點(diǎn)就是右子樹的最小節(jié)點(diǎn)感憾。這樣的替換仍然能夠保證樹的有序性蜡励，因?yàn)?x.key 和他的后繼節(jié)點(diǎn)的鍵之間不存在其他的鍵，而且我們可以通過刪除最小鍵來刪除右子節(jié)點(diǎn)最小的鍵阻桅。

我們可以通過如下的四個(gè)步驟實(shí)現(xiàn)節(jié)點(diǎn)的刪除：

1. 將指向即將被刪除的節(jié)點(diǎn)鏈接保存為 t
2. 將 x 指向他的后繼節(jié)點(diǎn) min(t.right)
3. 將 x 的右鏈接（原本指向一棵所有節(jié)點(diǎn)都大于 x.key 的二叉查找樹）指向 deleteMin(t.right)凉倚，也就是在刪除節(jié)點(diǎn)之后所有的節(jié)點(diǎn)仍然大于 x.key 的子二叉查找樹
4. 將 x 的左鏈接（本為空）設(shè)為 t.left（其下所有的鍵都小于被刪除的節(jié)點(diǎn)和他的后繼節(jié)點(diǎn)）

如下：

754b0783e44b2bbcc764e4f2ff2426f.jpg

在實(shí)際工程中，也可以使用前驅(qū)節(jié)點(diǎn)嫂沉，隨機(jī)的選用前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)稽寒，以提高效率。

平衡查找樹

二插查找樹在極端情況下會(huì)導(dǎo)致樹的不平衡趟章，導(dǎo)致查找效率降為 O(n)杏糙，所以需要在創(chuàng)建樹的時(shí)候保證樹的平衡，使得平均查找效率接近 O(logn)尤揣。所以提出了 AVL 樹和 RB-Tree（紅黑樹）搔啊，保證樹的相對(duì)平衡。

AVL 樹

AVL 樹北戏，也稱平衡二叉搜索樹负芋，AVL 是其發(fā)明者姓名簡(jiǎn)寫。AVL 樹屬于樹的一種，而且它也是一棵二叉搜索樹旧蛾，不同的是他通過一定機(jī)制能保證二叉搜索樹的平衡莽龟，平衡的二叉搜索樹的查詢效率更高。

• AVL 樹是一棵二叉搜索樹锨天。
• AVL 樹的左右子節(jié)點(diǎn)也是 AVL 樹毯盈。
• AVL 樹擁有二叉搜索樹的所有基本特點(diǎn)。
• 每個(gè)節(jié)點(diǎn)的左右子節(jié)點(diǎn)的高度之差的絕對(duì)值最多為1病袄，即平衡因子為范圍為 [-1,1]搂赋。

在增加節(jié)點(diǎn)或者刪除節(jié)點(diǎn)的時(shí)候會(huì)導(dǎo)致樹高的變化，需要在這兩個(gè)地方保證樹高的平衡益缠。

AVL 樹的添加

AVL 樹有四種添加方式導(dǎo)致不平衡脑奠。

• LL 插入方式，插入的節(jié)點(diǎn)在 Z 節(jié)點(diǎn)的左子樹的左子樹上
• RR 插入方式幅慌，插入的節(jié)點(diǎn)在 Z 節(jié)點(diǎn)的右子樹的右子樹上
• LR 插入方式宋欺，插入的節(jié)點(diǎn)在 Z 節(jié)點(diǎn)的左子樹的右子樹上
• RL 插入方式，插入的節(jié)點(diǎn)在 Z 節(jié)點(diǎn)的右子樹的左子樹上

平衡二叉樹的失衡調(diào)整主要是通過旋轉(zhuǎn)最小失衡子樹來實(shí)現(xiàn)的胰伍。

最小失衡子樹：在新插入的結(jié)點(diǎn)向上查找齿诞，以第一個(gè)平衡因子的絕對(duì)值超過1的結(jié)點(diǎn)為根的子樹稱為最小不平衡子樹。也就是說骂租，一棵失衡的樹祷杈，是有可能有多棵子樹同時(shí)失衡的，如下菩咨。而這個(gè)時(shí)候吠式，我們只要調(diào)整最小的不平衡子樹，就能夠?qū)⒉黄胶獾臉湔{(diào)整為平衡的樹抽米。

LL 方式通過右旋轉(zhuǎn)的方式讓樹保持平衡，如下：

image.png

RR 方式通過左旋轉(zhuǎn)的方式讓樹保持平衡糙置，如下：

image.png

LR 方式通過左右雙旋讓樹保持平衡：

首先以根節(jié)點(diǎn)的左節(jié)點(diǎn)做左旋轉(zhuǎn)云茸，得到一個(gè) LL 樹，如下：

image.png

接著谤饭，對(duì) LL 樹做右旋轉(zhuǎn)标捺，讓樹保持平衡，如下：

image.png

RL 方式通過右左雙旋讓樹保持平衡揉抵，是 LR 方式的對(duì)稱亡容。

==綜上，對(duì)于 AVL 來說冤今，添加操作總能通過最多兩次旋轉(zhuǎn)來保證樹的平衡闺兢。==

AVL 樹的刪除

在 AVL 樹中，采用普通二叉樹的方式刪除節(jié)點(diǎn)戏罢，只是需要在不平衡時(shí)對(duì)二叉樹的平衡進(jìn)行調(diào)整屋谭。需要?jiǎng)h除的節(jié)點(diǎn)在較低子樹上時(shí)脚囊，會(huì)直接導(dǎo)致樹的不平衡。

當(dāng)調(diào)整了最小不平衡樹時(shí)桐磁，有可能會(huì)使得子樹變得更矮悔耘，那么需要再次調(diào)整，如下（刪除節(jié)點(diǎn) 6）：

刪除節(jié)點(diǎn) 6 之后變成我擂，如下：

1CD96D7859A692DB489FC229A0469244.png

這時(shí)衬以，最小不平衡樹為節(jié)點(diǎn) 5，調(diào)整節(jié)點(diǎn) 5校摩，如下：

6B9BE20E4DFFA27E54E99D2AD48BAC3D.png

這時(shí)看峻，節(jié)點(diǎn) 10 又變成了最小不平衡樹，需要繼續(xù)調(diào)整（左旋轉(zhuǎn)）秧耗，如下：

C2995A894CBB833D12C8145C2774D1C6.png

==綜上备籽，AVL 樹的刪除有可能導(dǎo)致整棵樹的級(jí)聯(lián)旋轉(zhuǎn)。==

RB-tree 紅黑樹

首先分井，我們引入一棵多叉樹车猬，2-3 樹，來解釋紅黑樹的實(shí)現(xiàn)原理尺锚。

2-3 查找樹

利用樹進(jìn)行查找時(shí)珠闰，希望樹盡量的平衡，這樣才能夠保證在每一次的查找保證 $O(logn)$ 的復(fù)雜度瘫辩。在動(dòng)態(tài)插入的過程種要維持平衡二叉樹的代價(jià)太高伏嗜，所以使用一種新型的平衡樹 - 2-3 查找樹。

對(duì)于一個(gè)二叉查找樹伐厌，他的每一個(gè)節(jié)點(diǎn)有一個(gè)值和兩條連接承绸，左連接指向的二叉查找樹的值都小于該節(jié)點(diǎn)，右連接指向的二叉查找樹的值都大于該節(jié)點(diǎn)挣轨，對(duì)于一個(gè)整數(shù)類型的數(shù)組 int[] a = new int[] {1,2,3,4,5,6,7}军熏，他所構(gòu)成的平衡二叉查找樹如下所示：

平衡二叉查找樹

現(xiàn)引入 2-3 查找樹，定義如下：

定義

• 為一棵空樹或由以下節(jié)點(diǎn)組成
• 2-節(jié)點(diǎn)卷扮，含有一個(gè)值和兩條連接荡澎，左連接指向的 2-3 樹中的值都小于該節(jié)點(diǎn)，右連接指向的 2-3 樹的值都大于該節(jié)點(diǎn)（類似于查找二叉樹）
• 3-節(jié)點(diǎn)晤锹，含有兩個(gè)值和三條連接摩幔，左連接指向的 2-3 樹中的值都小于該節(jié)點(diǎn)，中連接指向的 2-3 樹的值位于該節(jié)點(diǎn)的兩個(gè)值之間鞭铆，右連接指向的 2-3 樹的值都大于該節(jié)點(diǎn)

對(duì)于一個(gè)字符數(shù)組 char[] chars = new char[] {A,C,H,L,P,S,X,E,J,R,M}或衡，他的平衡 2-3 樹如下所示：

平衡2-3樹

查找

2-3 樹查找過程和二叉樹相似，略。

添加

在一個(gè)只有根節(jié)點(diǎn)且是 2-節(jié)點(diǎn)的樹上添加元素薇宠。為了保證平衡偷办，我們需要將該節(jié)點(diǎn)替換成一個(gè) 3-節(jié)點(diǎn)，如下所示：

根-2節(jié)點(diǎn)添加

在一個(gè)只有根節(jié)點(diǎn)且是 3-節(jié)點(diǎn)的樹上添加元素澄港。為了保證平衡椒涯，我們需要將該節(jié)點(diǎn)做局部變化，操作如下：首先將該節(jié)點(diǎn)臨時(shí)增加一個(gè)值變成 4-節(jié)點(diǎn)回梧，然后對(duì)四節(jié)點(diǎn)進(jìn)行拆分废岂，變成 3 個(gè) 2-節(jié)點(diǎn)，如下所示：

根-3節(jié)點(diǎn)添加

在一個(gè)父節(jié)點(diǎn)且是 2-節(jié)點(diǎn)狱意，該節(jié)點(diǎn)是3-節(jié)點(diǎn)的樹上添加元素湖苞。為了保證平衡，我們需要將該節(jié)點(diǎn)做局部變化详囤，操作如下：首先將該節(jié)點(diǎn)臨時(shí)增加一個(gè)值變成 4-節(jié)點(diǎn)财骨，然后對(duì)四節(jié)點(diǎn)進(jìn)行拆分，變成 3 個(gè) 2-節(jié)點(diǎn)藏姐，最后將一個(gè) 2-節(jié)點(diǎn) 和 父節(jié)點(diǎn)合并隆箩，如下所示：

2-父 3-子

在一個(gè)父節(jié)點(diǎn)是 3-節(jié)點(diǎn)，該節(jié)點(diǎn)是3-節(jié)點(diǎn)的樹上添加元素羔杨。為了保證平衡捌臊，我們需要將該節(jié)點(diǎn)做局部變化，操作如下：首先將該節(jié)點(diǎn)臨時(shí)增加一個(gè)值變成 4-節(jié)點(diǎn)兜材，然后對(duì)四節(jié)點(diǎn)進(jìn)行拆分理澎，變成 3 個(gè) 2-節(jié)點(diǎn)，最后將一個(gè) 2-節(jié)點(diǎn) 和 父節(jié)點(diǎn)合并然后遞歸的對(duì)父節(jié)點(diǎn)進(jìn)行操作曙寡，直到根節(jié)點(diǎn)或者父節(jié)點(diǎn)是 2-節(jié)點(diǎn)停止糠爬，如下所示：

3-父 3-子

刪除

由此可見， 2-3 樹是由下向上生長(zhǎng)的举庶，但是刪除操作需要對(duì)樹進(jìn)行從上和從下兩方面的判斷秩铆，相對(duì)來說，刪除非常費(fèi)時(shí)灯变。

紅黑樹

紅黑樹是 2-3 樹的一種特殊實(shí)現(xiàn)，使用標(biāo)準(zhǔn)的查找二叉樹代替和一些額外的信息來表示 2-3 樹捅膘。我們將樹中的鏈接分為兩種類型：紅連接將兩個(gè) 2 節(jié)點(diǎn)鏈接起來構(gòu)成三節(jié)點(diǎn)添祸，黑連接代表普通連接。標(biāo)準(zhǔn)定義及性質(zhì)如下：

• 紅連接均為左連接
• 沒有任何一個(gè)節(jié)點(diǎn)同時(shí)和兩條紅連接相連
• 該樹是黑色完美平衡的寻仗，及任意空連接到根節(jié)點(diǎn)的路徑上的黑連接數(shù)量相同
• 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)（黑節(jié)點(diǎn)的數(shù)目稱為黑高black-height）

因?yàn)榧t連接總為左鏈接刃泌，并且不會(huì)有兩個(gè)節(jié)點(diǎn)同時(shí)和紅連接相連，所以根節(jié)點(diǎn)一定是黑連接。

在每一個(gè)節(jié)點(diǎn)的內(nèi)部耙替，維護(hù)了一個(gè)顏色信息亚侠，用于存儲(chǔ)該節(jié)點(diǎn)到他的父節(jié)點(diǎn)的節(jié)點(diǎn)的鏈接顏色，如果該節(jié)點(diǎn)是紅色俗扇，則代表他和父節(jié)點(diǎn)組成一個(gè) 3 節(jié)點(diǎn)硝烂，為了方便理解，我們可以把紅色鏈接畫平铜幽，如下：

2BB9B6028D7B5E7804E3A188C7BE8931.png

紅黑樹的插入

每次將一個(gè)節(jié)點(diǎn)插入到紅黑樹時(shí)滞谢，總會(huì)構(gòu)造一個(gè)紅色節(jié)點(diǎn)插入到紅黑樹(除了在沒有節(jié)點(diǎn)時(shí)，會(huì)直接創(chuàng)建根為黑色的節(jié)點(diǎn))中除抛，但是我們需要對(duì)顏色進(jìn)行調(diào)整狮杨。

可能會(huì)出現(xiàn)兩種情況，第一種情況是出現(xiàn)紅色右鏈接到忽，第二種情況是出現(xiàn)兩個(gè)相連的紅連接橄教。需要通過左旋轉(zhuǎn)或者右旋轉(zhuǎn)修復(fù)。

我們定義左旋轉(zhuǎn)是將一條紅色的右連接旋轉(zhuǎn)得到一條左連接喘漏。右連接相反护蝶，如下圖所示：

左旋轉(zhuǎn)

左旋轉(zhuǎn)的偽代碼如下所示：

Node rotateLset(Node h) {
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = h.color;
    h.color = red;
}

只需更改他的 color 屬性為紅，并將他原來自身的 color 屬性賦值給右連接節(jié)點(diǎn)就行陷遮。

同理滓走，右連接示意圖如下：

右旋轉(zhuǎn)

NOde rotateRight(Node h) {
    node x= h.left;
    h.left = x.right;
    x.right = h;
    x.color = h.color;
    h.color = read;
}

對(duì)于每一個(gè)插入，都插入一個(gè)紅連接帽馋。

向單個(gè) 2-節(jié)點(diǎn)中插入新鍵搅方。如果新鍵小于老鍵，則增加一個(gè)紅色左連接绽族，否則增加一個(gè)紅色右連接并進(jìn)行左旋轉(zhuǎn)姨涡，兩種情況都能產(chǎn)生一個(gè)等效的3-連接，如下所示：

單個(gè)2-節(jié)點(diǎn)中插入新鍵

向樹底部的 2-節(jié)點(diǎn)中插入新鍵吧慢√纹總是增加一個(gè)新的紅色連接，如果他的父節(jié)點(diǎn)是 2-節(jié)點(diǎn)检诗，那么按照如上兩種方式調(diào)整節(jié)點(diǎn)就行匈仗。

向一棵雙鍵樹（3-節(jié)點(diǎn)）中插入新建，分為了三種子情況逢慌，第一種情況是新鍵最大悠轩，第二種情況是新鍵在中間，第三種情況是新鍵最小攻泼。

如下如所示：

3-節(jié)點(diǎn)

對(duì)于一個(gè)節(jié)點(diǎn)和兩個(gè)紅色連接直接相聯(lián)火架，這種情況等效于一個(gè) 4-節(jié)點(diǎn)鉴象，當(dāng)將這兩個(gè)紅色連接變黑時(shí)，需要將父節(jié)點(diǎn)由黑變紅何鸡，因?yàn)檫@樣的變換會(huì)在父節(jié)點(diǎn)產(chǎn)生一個(gè) 3-節(jié)點(diǎn)纺弊，理由如下：

顏色變換

每產(chǎn)生一個(gè)紅色連接都會(huì)向上傳遞直到根節(jié)點(diǎn)。

==綜上骡男，在插入一個(gè)節(jié)點(diǎn)時(shí)淆游，紅黑樹最多做兩次旋轉(zhuǎn)，但是洞翩，可能會(huì)遞歸的改變顏色直到根節(jié)點(diǎn)==

==從 2-3 樹稽犁，我們可以看出，在一個(gè)路徑上骚亿，紅色節(jié)點(diǎn)一定小于等于黑色節(jié)點(diǎn)已亥，并且一個(gè)路徑上可以允許沒有紅色節(jié)點(diǎn)，設(shè) 紅色節(jié)點(diǎn)為 red-num, 黑色節(jié)點(diǎn)為 black-num来屠，路徑長(zhǎng)為 path虑椎，則有 0 <= (black-num - rednum) <= path==

紅黑樹/AVL 樹對(duì)比

1. 如果插入一個(gè) node 引起了樹的不平衡，AVL最多只需要 2 次旋轉(zhuǎn)操作俱笛，復(fù)雜度O(1), RB-Tree 最壞需要 O(logn) 復(fù)雜度捆姜；在刪除 node 引起樹的不平衡時(shí)，最壞情況下迎膜，AVL 需要維護(hù)從被刪 node 到 root 這條路徑上所有 node 的平衡性泥技，因此需要旋轉(zhuǎn)的量級(jí) O(logN)，而 RB-Tree 最多只需 3 次旋轉(zhuǎn)磕仅，只需要 O(1) 的復(fù)雜度珊豹。
2. 其次，AVL 的結(jié)構(gòu)相較 RB-Tree 來說更為平衡榕订，在插入和刪除 node 更容易引起 Tree 的 unbalance店茶，因此在大量數(shù)據(jù)需要插入或者刪除時(shí)，AVL 需要 rebalance 的頻率會(huì)更高劫恒。因此贩幻，RB-Tree 在需要大量插入和刪除 node 的場(chǎng)景下，效率更高两嘴。自然丛楚，由于 AVL 高度平衡，因此 AVL 的 search 效率更高憔辫。

map 的實(shí)現(xiàn)只是折衷了兩者在 search鸯檬、insert 以及 delete 下的效率÷莨福總體來說喧务，RB-tree 的統(tǒng)計(jì)性能是高于 AVL 的。

引用

mengzhisuoliu 博客

紅黑樹生成鏈接

Rick.lz 博客