本篇內(nèi)容主要講解“怎么徹底理解紅黑樹”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“怎么徹底理解紅黑樹”吧!

創(chuàng)新互聯(lián)建站是一家專注于成都網(wǎng)站設(shè)計、網(wǎng)站制作、外貿(mào)營銷網(wǎng)站建設(shè)與策劃設(shè)計,掇刀網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)建站做網(wǎng)站,專注于網(wǎng)站建設(shè)十多年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:掇刀等地區(qū)。掇刀做網(wǎng)站價格咨詢:028-86922220

二叉樹

滿足以下兩個條件的樹就是二叉樹：

• 本身是有序樹(若將樹中每個結(jié)點(diǎn)的各子樹看成是從左到右有次序的(即不能互換)，則稱該樹為有序樹(Ordered Tree))。

• 樹中包含的各個節(jié)點(diǎn)的度不能超過 2，即只能是 0、1 或者 2。

簡單地理解，二叉樹(Binary tree)是每個節(jié)點(diǎn)最多只有兩個分支(即不存在分支度大于 2  的節(jié)點(diǎn))的樹結(jié)構(gòu)。通常分支被稱作“左子樹”或“右子樹”。

二叉查找樹

要了解紅黑樹之前，免不了先看下二叉查找樹是什么。

維基百科上的定義：二叉查找樹(英語：Binary Search Tree)，也稱為二叉搜索樹、有序二叉樹(ordered binary  tree)或排序二叉樹(sorted binary tree)，是指一棵空樹或者具有下列性質(zhì)的二叉樹。

若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值;若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有節(jié)點(diǎn)的值均大于或等于它的根節(jié)點(diǎn)的值;任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹。

圖示理解：

上圖為查找值為29的節(jié)點(diǎn)，有以下步驟：

• 查看根節(jié)點(diǎn) 41。

• 因為 41>29，所以查看 41 的左孩子 20。

• 因為 20<29，所以查看 20 的右孩子 29，發(fā)現(xiàn)其正好是要查看的節(jié)點(diǎn)。

退化

二叉查找樹有個非常嚴(yán)重的問題，如果數(shù)據(jù)的插入是從大到小插入的，或者是從小到大插入的話，會導(dǎo)致二叉查找樹退化成單鏈表的形式，俗稱“瘸子“。

左瘸子：例如，插入數(shù)據(jù)依次為 {5,4,3,2,1}(從大到小)，則如下圖所示：

右瘸子：例如，插入數(shù)據(jù)依次為{1,2,3,4,5}(從小到大)，則如下圖所示：

為了解決該問題，出現(xiàn)了一些解決方法，即平衡，能夠使得樹趨向平衡，這種自平衡的樹叫做平衡樹。

平衡樹

平衡樹(Balance Tree，BT)指的是，任意節(jié)點(diǎn)的子樹的高度差都小于等于 1。

常見的符合平衡樹的有 AVL 樹(二叉平衡搜索樹)，B 樹(多路平衡搜索樹，2-3 樹，2-3-4 樹中的一種)，紅黑樹等。

AVL 樹

AVL 樹(由發(fā)明者 Adelson-Velsky 和 Landis 的首字母縮寫命名)，是指任意節(jié)點(diǎn)的兩個子樹的高度差不超過 1  的平衡樹。又稱自平衡二叉搜索樹。

AVL 樹能解決上文二叉查找樹中的右瘸子問題，例如，插入數(shù)據(jù)依次為 {1,2,3,4,5}(從小到大)，則如下圖所示：

AVL 樹會對不符合高度差的結(jié)構(gòu)進(jìn)行調(diào)整，從而使得二叉樹趨向平衡。

2-3 樹

2-3 樹，是指每個具有子節(jié)點(diǎn)的節(jié)點(diǎn)(內(nèi)部節(jié)點(diǎn)，internal  node)要么有兩個子節(jié)點(diǎn)和一個數(shù)據(jù)元素，要么有三個子節(jié)點(diǎn)和兩個數(shù)據(jù)元素的自平衡的樹，它的所有葉子節(jié)點(diǎn)都具有相同的高度。

簡單點(diǎn)講，2-3 樹的非葉子節(jié)點(diǎn)都具有兩個分叉或者三個分叉，所以，稱作 2 叉-3 叉樹更容易理解。

另外一種說法，具有兩個子節(jié)點(diǎn)和一個數(shù)據(jù)元素的節(jié)點(diǎn)又稱作 2 節(jié)點(diǎn)，具有三個子節(jié)點(diǎn)和兩個數(shù)據(jù)元素的節(jié)點(diǎn)又稱作 3 節(jié)點(diǎn)，所以，整顆樹叫做 2-3  樹。

所有葉子點(diǎn)都在樹的同一層，一樣高：

• 性質(zhì) 1：滿足二叉搜索樹的性質(zhì)。

• 性質(zhì) 2：節(jié)點(diǎn)可以存放一個或兩個元素。

• 性質(zhì) 3：每個節(jié)點(diǎn)有兩個或三個子節(jié)點(diǎn)。

創(chuàng)建 2-3 樹的規(guī)則

插入操作如下：

向 2-節(jié)點(diǎn)中插入元素：

向一顆只含有一個 3-節(jié)點(diǎn)的樹中插入元素：

2-3-4 樹

含義如下：

• 2 節(jié)點(diǎn)：包含兩個子節(jié)點(diǎn)和一個數(shù)據(jù)元素。

• 3 節(jié)點(diǎn)：包含三個子節(jié)點(diǎn)和一個數(shù)據(jù)元素。

• 4 節(jié)點(diǎn)：包含四個子節(jié)點(diǎn)和一個數(shù)據(jù)元素。

  
  

2-3-4 樹，它的每個非葉子節(jié)點(diǎn)，要么是 2 節(jié)點(diǎn)，要么是 3 節(jié)點(diǎn)，要么是 4 節(jié)點(diǎn)，且可以自平衡，所以稱作 2-3-4 樹。

規(guī)則如下：

• 規(guī)則 1：加入新節(jié)點(diǎn)時，不會往空的位置添加節(jié)點(diǎn)，而是添加到最后一個葉子節(jié)點(diǎn)上。

• 規(guī)則 2：四節(jié)點(diǎn)可以被分解三個 2-節(jié)點(diǎn)組成的樹，并且分解后新樹的根節(jié)點(diǎn)需要向上和父節(jié)點(diǎn)融合。

插入操作

原本的 2-3-4 樹，如下圖：

對于上圖的 2-3-4 樹，插入一個節(jié)點(diǎn) 17，由于規(guī)則 1，節(jié)點(diǎn) 17 不會加入節(jié)點(diǎn)  [16,18,20] 的子樹，而是與該節(jié)點(diǎn)融合。

由于規(guī)則 2，節(jié)點(diǎn) [16,17,18,20] 是一個 4 節(jié)點(diǎn)，將該節(jié)點(diǎn)進(jìn)行拆解成新的樹，將 18 作為子樹的根節(jié)點(diǎn)進(jìn)行拆分。

此時樹暫時失去了平衡，我們需要將拆分后的子樹的根節(jié)點(diǎn)向上進(jìn)行融合。

同理可得，由于規(guī)則 2，節(jié)點(diǎn) [6,10,14,18] 是一個 4 節(jié)點(diǎn)，將該節(jié)點(diǎn)進(jìn)行拆解成新的樹，將 14 作為子樹的根節(jié)點(diǎn)進(jìn)行拆分，完成了 2-3-4  樹的構(gòu)建。

總結(jié)了下插入節(jié)點(diǎn)的過程，無非也就為了符合兩條規(guī)則，那么，2-3 樹，2-3-4 樹都有了，那是不是也有 2-3-4-5 樹，2-3-4-5--...-n  樹的存在呢?

事實(shí)上是有的，世人把這一類樹稱為一個名字：B 樹。

B 樹

B 樹，表示的是一類樹，它允許一個節(jié)點(diǎn)可以有多于兩個子節(jié)點(diǎn)，同時，也是自平衡的，葉子節(jié)點(diǎn)的高度都是相同的。

所以，為了更好地區(qū)分一顆 B 樹到底屬于哪一類樹，我們給它一個新的屬性：度(Degree)：一個節(jié)點(diǎn)能有多少箭頭指向其他節(jié)點(diǎn)。

具有度為 3 的 B 樹，表示一個節(jié)點(diǎn)最多有三個子節(jié)點(diǎn)，也就是 2-3 樹的定義。具有度為 4 的 B 樹，表示一個節(jié)點(diǎn)最多有四個子節(jié)點(diǎn)，也就是  2-3-4 樹的定義。

圖為 4 的 B 樹的示例圖：

紅黑樹

R-B Tree，全稱是 Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查找樹。

紅黑樹的每個節(jié)點(diǎn)上都有存儲位表示節(jié)點(diǎn)的顏色，可以是紅(Red)或黑(Black)。

如何理解紅黑樹

一個經(jīng)典的紅黑樹，如下圖所示(省略了葉子節(jié)點(diǎn)都是黑色的 NIL 節(jié)點(diǎn))：

如第二張圖所示，將該紅黑樹與上文講到的 2-3-4 樹對比，是否發(fā)現(xiàn)，紅黑樹就是一個 2-3-4 樹：

• 每個節(jié)點(diǎn)或者是黑色，或者是紅色。

• 根節(jié)點(diǎn)是黑色。

• 每個葉子節(jié)點(diǎn)(NIL)是黑色。注意：這里葉子節(jié)點(diǎn)，是指為空(NIL 或NULL)的葉子節(jié)點(diǎn)!

• 如果一個節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。由于紅黑樹的每個節(jié)點(diǎn)都是由 2-3-4 樹轉(zhuǎn)化而來的，從而紅色節(jié)點(diǎn)不能連續(xù)兩個出現(xiàn)，不然會出現(xiàn) 4  節(jié)點(diǎn)的情況，導(dǎo)致違反了規(guī)則 2。

而且紅黑樹的每一個黑節(jié)點(diǎn)都是 3 節(jié)點(diǎn)中的最中間的那個值，或者是 2 節(jié)點(diǎn)中其中一個值。

• 從一個節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

原因：紅黑樹這些黑色節(jié)點(diǎn)在 2-3-4 樹中代表的是由 1 節(jié)點(diǎn)的一個 2-3-4 樹，而 2-3-4  樹是同一個子樹的深度是相同的，平衡的，所以從一個節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

如下圖所示，藍(lán)色代表是黑色節(jié)點(diǎn)：

注意如下幾點(diǎn)：

• 特性(3)中的葉子節(jié)點(diǎn)，是只為空(NIL 或 null)的節(jié)點(diǎn)。

• 特性(5)，確保沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。

• 紅黑樹雖然本質(zhì)上是一棵二叉查找樹，但它在二叉查找樹的基礎(chǔ)上增加了著色和相關(guān)的性質(zhì)使得紅黑樹相對平衡，從而保證了紅黑樹的查找、插入、刪除的時間復(fù)雜度最壞為  O(log n)。

由上面的例子所示，我們只要把紅黑樹當(dāng)做是 2-3-4 樹來處理，并且對應(yīng)的顏色進(jìn)行改變或者進(jìn)行左旋右旋的操作，即可達(dá)到使得紅黑樹平衡的目標(biāo)。

如何保持紅黑樹的結(jié)構(gòu)

當(dāng)我們插入一個新的節(jié)點(diǎn)的時候，如何保證紅黑樹的結(jié)構(gòu)依然能夠符合上面的五個特性呢?

樹的旋轉(zhuǎn)分為左旋和右旋，下面借助圖來介紹一下左旋和右旋這兩種操作。

①左旋

原本的狀態(tài)：

過程圖：

結(jié)束圖：

如上圖所示，當(dāng)在某個目標(biāo)結(jié)點(diǎn) E 上，做左旋操作時，我們假設(shè)它的右孩子 S 不是 NIL。

左旋以 S 到 E 之間的鏈為“支軸”進(jìn)行，它使 S 成為該子樹的新根，而 S 的左孩子則成為 E 的右孩子。

②右旋

原先狀態(tài)圖：

過程圖：

結(jié)束圖：

同左旋類似，當(dāng)在某個目標(biāo)結(jié)點(diǎn) S 上，做右旋操作時，我們假設(shè)它的右孩子 S 不是 NIL。

左旋以 S 到 E 之間的鏈為“支軸”進(jìn)行，它使 S 成為該子樹的新根，而 S 的左孩子則成為 E 的右孩子。

到此，相信大家對“怎么徹底理解紅黑樹”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

當(dāng)前題目：怎么徹底理解紅黑樹
URL鏈接：http://jinyejixie.com/article18/iissgp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供用戶體驗、商城網(wǎng)站、動態(tài)網(wǎng)站、軟件開發(fā)、企業(yè)網(wǎng)站制作、網(wǎng)站制作

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)