查找樹

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 并更新，沒(méi)有找到則者新建節(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)

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

如下：

ed6634fb18276565ad2c53fe31dd9eb.jpg

最大鍵同理。

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

但是如果刪除的節(jié)點(diǎn)有兩棵子樹，但是刪除之后只有一個(gè)空出來(lái)的鏈接。刪除節(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)的鍵之間不存在其他的鍵，而且我們可以通過(guò)刪除最小鍵來(lái)刪除右子節(jié)點(diǎn)最小的鍵。

我們可以通過(guò)如下的四個(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 樹屬于樹的一種，而且它也是一棵二叉搜索樹，不同的是他通過(guò)一定機(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)整主要是通過(guò)旋轉(zhuǎn)最小失衡子樹來(lái)實(shí)現(xiàn)的。

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

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

image.png

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

image.png

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

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

image.png

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

image.png

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

==綜上，對(duì)于 AVL 來(lái)說(shuō)，添加操作總能通過(guò)最多兩次旋轉(zhuǎn)來(lái)保證樹的平衡。==

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 樹，來(lái)解釋紅黑樹的實(shí)現(xiàn)原理。

2-3 查找樹

利用樹進(jìn)行查找時(shí)，希望樹盡量的平衡，這樣才能夠保證在每一次的查找保證 $O(logn)$ 的復(fù)雜度。在動(dòng)態(tài)插入的過(guò)程種要維持平衡二叉樹的代價(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 樹查找過(guò)程和二叉樹相似，略。

添加

在一個(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-子

刪除

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

紅黑樹

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

• 紅連接均為左連接
• 沒(méi)有任何一個(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)插入到紅黑樹(除了在沒(méi)有節(jié)點(diǎn)時(shí)，會(huì)直接創(chuàng)建根為黑色的節(jié)點(diǎn))中，但是我們需要對(duì)顏色進(jìn)行調(diào)整。

可能會(huì)出現(xiàn)兩種情況，第一種情況是出現(xiàn)紅色右鏈接，第二種情況是出現(xiàn)兩個(gè)相連的紅連接。需要通過(guò)左旋轉(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 屬性為紅，并將他原來(lái)自身的 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è)路徑上可以允許沒(méi)有紅色節(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 來(lái)說(shuō)更為平衡，在插入和刪除 node 更容易引起 Tree 的 unbalance，因此在大量數(shù)據(jù)需要插入或者刪除時(shí)，AVL 需要 rebalance 的頻率會(huì)更高。因此，RB-Tree 在需要大量插入和刪除 node 的場(chǎng)景下，效率更高。自然，由于 AVL 高度平衡，因此 AVL 的 search 效率更高。

map 的實(shí)現(xiàn)只是折衷了兩者在 search、insert 以及 delete 下的效率?？傮w來(lái)說(shuō)，RB-tree 的統(tǒng)計(jì)性能是高于 AVL 的。

引用

mengzhisuoliu 博客

紅黑樹生成鏈接

Rick.lz 博客