建站
咨詢(xún)
售后
建站咨詢(xún)
新聞中心
本文主要講解下最近一直聽(tīng)到的紅黑樹(shù)，看看究竟是什么神仙鬼怪。
二叉樹(shù)
滿(mǎn)足以下兩個(gè)條件的樹(shù)就是二叉樹(shù)：
- 本身是有序樹(shù)(若將樹(shù)中每個(gè)結(jié)點(diǎn)的各子樹(shù)看成是從左到右有次序的(即不能互換)，則稱(chēng)該樹(shù)為有序樹(shù)(Ordered Tree))。
- 樹(shù)中包含的各個(gè)節(jié)點(diǎn)的度不能超過(guò) 2，即只能是 0、1 或者 2。
簡(jiǎn)單地理解，二叉樹(shù)(Binary tree)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支(即不存在分支度大于 2 的節(jié)點(diǎn))的樹(shù)結(jié)構(gòu)。通常分支被稱(chēng)作“左子樹(shù)”或“右子樹(shù)”。
二叉查找樹(shù)
要了解紅黑樹(shù)之前，免不了先看下二叉查找樹(shù)是什么。
維基百科上的定義：二叉查找樹(shù)(英語(yǔ)：Binary Search Tree)，也稱(chēng)為二叉搜索樹(shù)、有序二叉樹(shù)(ordered binary tree)或排序二叉樹(shù)(sorted binary tree)，是指一棵空樹(shù)或者具有下列性質(zhì)的二叉樹(shù)。
若任意節(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值;若任意節(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于或等于它的根節(jié)點(diǎn)的值;任意節(jié)點(diǎn)的左、右子樹(shù)也分別為二叉查找樹(shù)。
圖示理解：
上圖為查找值為29的節(jié)點(diǎn)，有以下步驟：
- 查看根節(jié)點(diǎn) 41。
- 因?yàn)?41>29，所以查看 41 的左孩子 20。
- 因?yàn)?20<29，所以查看 20 的右孩子 29，發(fā)現(xiàn)其正好是要查看的節(jié)點(diǎn)。
退化
二叉查找樹(shù)有個(gè)非常嚴(yán)重的問(wèn)題，如果數(shù)據(jù)的插入是從大到小插入的，或者是從小到大插入的話(huà)，會(huì)導(dǎo)致二叉查找樹(shù)退化成單鏈表的形式，俗稱(chēng)“瘸子“。
左瘸子：例如，插入數(shù)據(jù)依次為 {5,4,3,2,1}(從大到小)，則如下圖所示：
右瘸子：例如，插入數(shù)據(jù)依次為{1,2,3,4,5}(從小到大)，則如下圖所示：
為了解決該問(wèn)題，出現(xiàn)了一些解決方法，即平衡，能夠使得樹(shù)趨向平衡，這種自平衡的樹(shù)叫做平衡樹(shù)。
平衡樹(shù)
平衡樹(shù)(Balance Tree，BT)指的是，任意節(jié)點(diǎn)的子樹(shù)的高度差都小于等于 1。
常見(jiàn)的符合平衡樹(shù)的有 AVL 樹(shù)(二叉平衡搜索樹(shù))，B 樹(shù)(多路平衡搜索樹(shù)，2-3 樹(shù)，2-3-4 樹(shù)中的一種)，紅黑樹(shù)等。
AVL 樹(shù)
AVL 樹(shù)(由發(fā)明者 Adelson-Velsky 和 Landis 的首字母縮寫(xiě)命名)，是指任意節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度差不超過(guò) 1 的平衡樹(shù)。又稱(chēng)自平衡二叉搜索樹(shù)。
AVL 樹(shù)能解決上文二叉查找樹(shù)中的右瘸子問(wèn)題，例如，插入數(shù)據(jù)依次為 {1,2,3,4,5}(從小到大)，則如下圖所示：
AVL 樹(shù)會(huì)對(duì)不符合高度差的結(jié)構(gòu)進(jìn)行調(diào)整，從而使得二叉樹(shù)趨向平衡。
2-3 樹(shù)
2-3 樹(shù)，是指每個(gè)具有子節(jié)點(diǎn)的節(jié)點(diǎn)(內(nèi)部節(jié)點(diǎn)，internal node)要么有兩個(gè)子節(jié)點(diǎn)和一個(gè)數(shù)據(jù)元素，要么有三個(gè)子節(jié)點(diǎn)和兩個(gè)數(shù)據(jù)元素的自平衡的樹(shù)，它的所有葉子節(jié)點(diǎn)都具有相同的高度。
簡(jiǎn)單點(diǎn)講，2-3 樹(shù)的非葉子節(jié)點(diǎn)都具有兩個(gè)分叉或者三個(gè)分叉，所以，稱(chēng)作 2 叉-3 叉樹(shù)更容易理解。
另外一種說(shuō)法，具有兩個(gè)子節(jié)點(diǎn)和一個(gè)數(shù)據(jù)元素的節(jié)點(diǎn)又稱(chēng)作 2 節(jié)點(diǎn)，具有三個(gè)子節(jié)點(diǎn)和兩個(gè)數(shù)據(jù)元素的節(jié)點(diǎn)又稱(chēng)作 3 節(jié)點(diǎn)，所以，整顆樹(shù)叫做 2-3 樹(shù)。
所有葉子點(diǎn)都在樹(shù)的同一層，一樣高：
- 性質(zhì) 1：滿(mǎn)足二叉搜索樹(shù)的性質(zhì)。
- 性質(zhì) 2：節(jié)點(diǎn)可以存放一個(gè)或兩個(gè)元素。
- 性質(zhì) 3：每個(gè)節(jié)點(diǎn)有兩個(gè)或三個(gè)子節(jié)點(diǎn)。
創(chuàng)建 2-3 樹(shù)的規(guī)則
插入操作如下：
向 2-節(jié)點(diǎn)中插入元素：
向一顆只含有一個(gè) 3-節(jié)點(diǎn)的樹(shù)中插入元素：
2-3-4 樹(shù)
含義如下：
- 2 節(jié)點(diǎn)：包含兩個(gè)子節(jié)點(diǎn)和一個(gè)數(shù)據(jù)元素。
- 3 節(jié)點(diǎn)：包含三個(gè)子節(jié)點(diǎn)和一個(gè)數(shù)據(jù)元素。
- 4 節(jié)點(diǎn)：包含四個(gè)子節(jié)點(diǎn)和一個(gè)數(shù)據(jù)元素。
2-3-4 樹(shù)，它的每個(gè)非葉子節(jié)點(diǎn)，要么是 2 節(jié)點(diǎn)，要么是 3 節(jié)點(diǎn)，要么是 4 節(jié)點(diǎn)，且可以自平衡，所以稱(chēng)作 2-3-4 樹(shù)。
規(guī)則如下：
- 規(guī)則 1：加入新節(jié)點(diǎn)時(shí)，不會(huì)往空的位置添加節(jié)點(diǎn)，而是添加到最后一個(gè)葉子節(jié)點(diǎn)上。
- 規(guī)則 2：四節(jié)點(diǎn)可以被分解三個(gè) 2-節(jié)點(diǎn)組成的樹(shù)，并且分解后新樹(shù)的根節(jié)點(diǎn)需要向上和父節(jié)點(diǎn)融合。
插入操作
原本的 2-3-4 樹(shù)，如下圖：
對(duì)于上圖的 2-3-4 樹(shù)，插入一個(gè)節(jié)點(diǎn) 17，由于規(guī)則 1，節(jié)點(diǎn) 17 不會(huì)加入節(jié)點(diǎn) [16,18,20] 的子樹(shù)，而是與該節(jié)點(diǎn)融合。
由于規(guī)則 2，節(jié)點(diǎn) [16,17,18,20] 是一個(gè) 4 節(jié)點(diǎn)，將該節(jié)點(diǎn)進(jìn)行拆解成新的樹(shù)，將 18 作為子樹(shù)的根節(jié)點(diǎn)進(jìn)行拆分。
此時(shí)樹(shù)暫時(shí)失去了平衡，我們需要將拆分后的子樹(shù)的根節(jié)點(diǎn)向上進(jìn)行融合。
同理可得，由于規(guī)則 2，節(jié)點(diǎn) [6,10,14,18] 是一個(gè) 4 節(jié)點(diǎn)，將該節(jié)點(diǎn)進(jìn)行拆解成新的樹(shù)，將 14 作為子樹(shù)的根節(jié)點(diǎn)進(jìn)行拆分，完成了 2-3-4 樹(shù)的構(gòu)建。
總結(jié)了下插入節(jié)點(diǎn)的過(guò)程，無(wú)非也就為了符合兩條規(guī)則，那么，2-3 樹(shù)，2-3-4 樹(shù)都有了，那是不是也有 2-3-4-5 樹(shù)，2-3-4-5--...-n 樹(shù)的存在呢?
事實(shí)上是有的，世人把這一類(lèi)樹(shù)稱(chēng)為一個(gè)名字：B 樹(shù)。
B 樹(shù)
B 樹(shù)，表示的是一類(lèi)樹(shù)，它允許一個(gè)節(jié)點(diǎn)可以有多于兩個(gè)子節(jié)點(diǎn)，同時(shí)，也是自平衡的，葉子節(jié)點(diǎn)的高度都是相同的。
所以，為了更好地區(qū)分一顆 B 樹(shù)到底屬于哪一類(lèi)樹(shù)，我們給它一個(gè)新的屬性：度(Degree)：一個(gè)節(jié)點(diǎn)能有多少箭頭指向其他節(jié)點(diǎn)。
具有度為 3 的 B 樹(shù)，表示一個(gè)節(jié)點(diǎn)最多有三個(gè)子節(jié)點(diǎn)，也就是 2-3 樹(shù)的定義。具有度為 4 的 B 樹(shù)，表示一個(gè)節(jié)點(diǎn)最多有四個(gè)子節(jié)點(diǎn)，也就是 2-3-4 樹(shù)的定義。
圖為 4 的 B 樹(shù)的示例圖：
紅黑樹(shù)
R-B Tree，全稱(chēng)是 Red-Black Tree，又稱(chēng)為“紅黑樹(shù)”，它一種特殊的二叉查找樹(shù)。
紅黑樹(shù)的每個(gè)節(jié)點(diǎn)上都有存儲(chǔ)位表示節(jié)點(diǎn)的顏色，可以是紅(Red)或黑(Black)。
如何理解紅黑樹(shù)
一個(gè)經(jīng)典的紅黑樹(shù)，如下圖所示(省略了葉子節(jié)點(diǎn)都是黑色的 NIL 節(jié)點(diǎn))：
如第二張圖所示，將該紅黑樹(shù)與上文講到的 2-3-4 樹(shù)對(duì)比，是否發(fā)現(xiàn)，紅黑樹(shù)就是一個(gè) 2-3-4 樹(shù)：
- 每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。
- 根節(jié)點(diǎn)是黑色。
- 每個(gè)葉子節(jié)點(diǎn)(NIL)是黑色。注意：這里葉子節(jié)點(diǎn)，是指為空(NIL 或NULL)的葉子節(jié)點(diǎn)!
- 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。由于紅黑樹(shù)的每個(gè)節(jié)點(diǎn)都是由 2-3-4 樹(shù)轉(zhuǎn)化而來(lái)的，從而紅色節(jié)點(diǎn)不能連續(xù)兩個(gè)出現(xiàn)，不然會(huì)出現(xiàn) 4 節(jié)點(diǎn)的情況，導(dǎo)致違反了規(guī)則 2。
而且紅黑樹(shù)的每一個(gè)黑節(jié)點(diǎn)都是 3 節(jié)點(diǎn)中的最中間的那個(gè)值，或者是 2 節(jié)點(diǎn)中其中一個(gè)值。
- 從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。
原因：紅黑樹(shù)這些黑色節(jié)點(diǎn)在 2-3-4 樹(shù)中代表的是由 1 節(jié)點(diǎn)的一個(gè) 2-3-4 樹(shù)，而 2-3-4 樹(shù)是同一個(gè)子樹(shù)的深度是相同的，平衡的，所以從一個(gè)節(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)，確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍。因而，紅黑樹(shù)是相對(duì)是接近平衡的二叉樹(shù)。
- 紅黑樹(shù)雖然本質(zhì)上是一棵二叉查找樹(shù)，但它在二叉查找樹(shù)的基礎(chǔ)上增加了著色和相關(guān)的性質(zhì)使得紅黑樹(shù)相對(duì)平衡，從而保證了紅黑樹(shù)的查找、插入、刪除的時(shí)間復(fù)雜度最壞為 O(log n)。
由上面的例子所示，我們只要把紅黑樹(shù)當(dāng)做是 2-3-4 樹(shù)來(lái)處理，并且對(duì)應(yīng)的顏色進(jìn)行改變或者進(jìn)行左旋右旋的操作，即可達(dá)到使得紅黑樹(shù)平衡的目標(biāo)。
如何保持紅黑樹(shù)的結(jié)構(gòu)
當(dāng)我們插入一個(gè)新的節(jié)點(diǎn)的時(shí)候，如何保證紅黑樹(shù)的結(jié)構(gòu)依然能夠符合上面的五個(gè)特性呢?
樹(shù)的旋轉(zhuǎn)分為左旋和右旋，下面借助圖來(lái)介紹一下左旋和右旋這兩種操作。
①左旋
原本的狀態(tài)：
過(guò)程圖：
結(jié)束圖：
如上圖所示，當(dāng)在某個(gè)目標(biāo)結(jié)點(diǎn) E 上，做左旋操作時(shí)，我們假設(shè)它的右孩子 S 不是 NIL。
左旋以 S 到 E 之間的鏈為“支軸”進(jìn)行，它使 S 成為該子樹(shù)的新根，而 S 的左孩子則成為 E 的右孩子。
②右旋
原先狀態(tài)圖：
過(guò)程圖：
結(jié)束圖：
同左旋類(lèi)似，當(dāng)在某個(gè)目標(biāo)結(jié)點(diǎn) S 上，做右旋操作時(shí)，我們假設(shè)它的右孩子 S 不是 NIL。
左旋以 S 到 E 之間的鏈為“支軸”進(jìn)行，它使 S 成為該子樹(shù)的新根，而 S 的左孩子則成為 E 的右孩子。
應(yīng)用
紅黑樹(shù)的應(yīng)用比較廣泛，主要是用它來(lái)存儲(chǔ)有序的數(shù)據(jù)，它的時(shí)間復(fù)雜度是 O(logn)，效率非常之高。
例如，Java 集合中的 TreeSet 和 TreeMap，C++ STL 中的 set、map，以及 Linux 虛擬內(nèi)存的管理，都是通過(guò)紅黑樹(shù)去實(shí)現(xiàn)的。
作者：亥碼
編輯：陶家龍
出處：https://www.cnblogs.com/linzworld/p/13720477.html
當(dāng)前標(biāo)題：動(dòng)圖演示：如何徹底理解紅黑樹(shù)？
URL分享：http://www.dlmjj.cn/article/djcgshi.html
