紅黑樹

發(fā)布時(shí)間：2018-08-10 15:12,

瀏覽次數(shù)：415

一、在理解紅黑樹之前，先看一些二叉查找樹

二叉查找樹特性：左字?jǐn)?shù)上所有的節(jié)點(diǎn)的值都小于或等于他的根節(jié)點(diǎn)上的值

右子樹上所有節(jié)點(diǎn)的值均大于或等于他的根節(jié)點(diǎn)的值

左、右子樹也跟別為平衡二叉樹

舉個(gè)二叉樹的例子：

可以看到如果要查詢10的話，10>9

因此到他的右子樹，右子樹根節(jié)點(diǎn)為13，10<13

因此到其左子樹，左子樹根節(jié)點(diǎn)為11>10

到其左子樹，為10，找到相應(yīng)的節(jié)點(diǎn)

不過二叉查找樹有一些問題，可能會(huì)出現(xiàn)不平橫的情況，即如下圖所示的情況

從這種情況可以看出，明顯存在左子樹和右子樹深度相差過多，在使用平衡情況下的二叉查找樹是時(shí)間復(fù)雜度為logn，而出現(xiàn)這種極端情況的話，想要查9的位置就需要每一次都遍歷下一個(gè)右子樹，很有可能時(shí)間復(fù)雜度變?yōu)閚(與數(shù)組普通查詢的時(shí)間復(fù)雜度相同)

基于上述情況，引入了平衡二叉樹，紅黑樹即為平衡二叉樹的一種

二、紅黑樹

特性：節(jié)點(diǎn)是紅色或黑色

根節(jié)點(diǎn)一定是黑色

每個(gè)葉節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)(NIL節(jié)點(diǎn))

每個(gè)紅節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色的(從每個(gè)葉子到跟的所有路徑上不能有兩個(gè)連續(xù)的紅節(jié)點(diǎn))(即對于層來說除了NIL節(jié)點(diǎn)，紅黑節(jié)點(diǎn)是交替的，第一層是黑節(jié)點(diǎn)那么其下一層肯定都是紅節(jié)點(diǎn)，反之一樣)

從任一節(jié)點(diǎn)到其每個(gè)葉子節(jié)點(diǎn)的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)

正是由于這些原因使得紅黑樹是一個(gè)平衡二叉樹

紅黑樹的例子

向紅黑樹中插入節(jié)點(diǎn)14(一般默認(rèn)插入節(jié)點(diǎn)是紅色的)

在原樹上插入20

可以看到，插入以后樹已經(jīng)不是一個(gè)平衡的二叉樹，而且并不滿足紅黑樹的要求，因?yàn)?0和21均為紅色，這種情況下就需要對紅黑樹進(jìn)行變色，21需要變?yōu)楹谏?#xff0c;22就會(huì)變成紅色，如果22變成紅色，則需要17和25都變成黑色

而17變成黑色顯然是不成立的，因?yàn)槿绻?7變?yōu)楹谏?#xff0c;那么13就會(huì)變?yōu)榧t色，不滿足二叉樹的規(guī)則，因此此處需要進(jìn)行另一個(gè)操作---------左旋操作

左旋：下圖就是一個(gè)左旋的例子，一般情況下，如果左子樹深度過深，那么便需要進(jìn)行左旋操作以保證左右子樹深度差變小

對于上圖由于右子樹中17變?yōu)楹谏院笮枰?3變成紅色，因此進(jìn)行一次左旋，將17放在根節(jié)點(diǎn)，這樣既可保證13為紅色，左旋后結(jié)果

而后根據(jù)紅黑樹的要求進(jìn)行顏色的修改

進(jìn)行左旋后，發(fā)現(xiàn)從根節(jié)點(diǎn)17，到1左子樹的葉子節(jié)點(diǎn)經(jīng)過了兩個(gè)黑節(jié)點(diǎn)，而到6的左葉子節(jié)點(diǎn)或者右葉子節(jié)點(diǎn)要經(jīng)歷3個(gè)黑節(jié)點(diǎn)，很顯然也不滿足紅黑樹，因此還需要進(jìn)行下一步操作，需要進(jìn)行右旋操作

右旋：與左旋正好相反

由于是從13節(jié)點(diǎn)出現(xiàn)的不平衡，因此對13節(jié)點(diǎn)進(jìn)行右旋，得到結(jié)果

而后再對其節(jié)點(diǎn)進(jìn)行變色，得到結(jié)果

這便是紅黑樹的一個(gè)變換，它主要用途有很多，例如java中的TreeMap以及JDK1.8以后的HashMap在當(dāng)個(gè)節(jié)點(diǎn)中鏈表長度大于8時(shí)都會(huì)用到。

總結(jié)

以上是生活随笔為你收集整理的红黑树模拟软件_红黑树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。