溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

什么是紅黑樹

發(fā)布時(shí)間：2022-05-18 14:48:11 來源：億速云 閱讀：146 作者：iii 欄目：大數(shù)據(jù)

這篇文章主要介紹“什么是紅黑樹”的相關(guān)知識(shí)，小編通過實(shí)際案例向大家展示操作過程，操作方法簡(jiǎn)單快捷，實(shí)用性強(qiáng)，希望這篇“什么是紅黑樹”文章能幫助大家解決問題。

為什么要有紅黑樹

想必大家對(duì)二叉樹搜索樹都不陌生，首先看一下二叉搜索樹的定義：
二叉搜索樹（Binary Search Tree），或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；若它的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；它的左、右子樹也分別為二叉排序樹。
從理論上來說，二叉搜索樹的查詢、插入和刪除一個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度均為O（log(n)）,已經(jīng)完全可以滿足我們的要求了，那么為什么還要有紅黑樹呢？
我們來看一個(gè)例子，向二叉搜索樹中依次插入（1，2，3，4，5，6），插入之后是這樣的

什么是紅黑樹  
退化成鏈表的二叉搜索樹
可以看到，在這種情況下，二叉搜索樹退化成了鏈表?。?！這時(shí)候查詢、插入和刪除一個(gè)元素的時(shí)候，時(shí)間復(fù)雜度變成了O（n），顯然這是不能接受的。出現(xiàn)這種情況情況的原因是二叉搜索樹沒有自平衡的機(jī)制，所以就有了平衡二叉樹的概念。  
 平衡二叉樹（Balanced Binary Tree）具有以下性質(zhì)：它是一棵空樹或它的左右兩個(gè)子樹的高度差的絕對(duì)值不超過1，并且左右兩個(gè)子樹都是一棵平衡二叉樹。  
還是剛剛的例子，假如我們用平衡二叉樹來實(shí)現(xiàn)的話，插入完元素后應(yīng)該是下面這樣的（不唯一）  
 
什么是紅黑樹  
自平衡的二叉樹
平衡二叉樹保證了在最差的情況下，二叉樹依然能夠保持絕對(duì)的平衡，即左右兩個(gè)子樹的高度差的絕對(duì)值不超過1。但是這又會(huì)帶來一個(gè)問題，那就是平衡二叉樹的定義過于嚴(yán)格，導(dǎo)致每次插入或者刪除一個(gè)元素之后，都要去維護(hù)二叉樹整體的平衡，這樣產(chǎn)生額外的代價(jià)又太大了。二叉搜索樹可能退化成鏈表，而平衡二叉樹維護(hù)平衡的代價(jià)開銷又太大了，那怎么辦呢？這就要談到“中庸之道”的智慧了。說白了就是把平衡的定義適當(dāng)放寬，不那么嚴(yán)格，這樣二叉樹既不會(huì)退化成鏈表，維護(hù)平衡的開銷也可以接受。沒錯(cuò)，這就是我們要談的紅黑樹了。首先看一下紅黑樹的定義：  
 紅黑樹是一種含有紅黑結(jié)點(diǎn)并能自平衡的二叉查找樹。它必須除了滿足二叉搜索樹的性質(zhì)外，還要滿足下面的性質(zhì)：  
性質(zhì)1：每個(gè)節(jié)點(diǎn)要么是黑色，要么是紅色。  
性質(zhì)2：根節(jié)點(diǎn)是黑色。  
性質(zhì)3：每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。  
性質(zhì)4：每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)一定都是黑色。  
性質(zhì)5：任意一結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)。  
這就是紅黑樹的五條性質(zhì)。我相信很多人都看到過，能背下來的也不在少數(shù)，但是真正理解為什么要這樣定義的恐怕就不多了。下面就從2-3樹的角度來談?wù)劶t黑樹的定義。    

從2-3樹來看紅黑樹

一般我們接觸最多的是二叉樹，也就是一個(gè)父節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。2-3樹與二叉樹的不同之處在于，一個(gè)父節(jié)點(diǎn)可以有兩個(gè)子節(jié)點(diǎn)，也可以有三個(gè)子節(jié)點(diǎn)，并且其也滿足類似二叉搜索樹的性質(zhì)。還有最重要的，2-3樹的所有葉子節(jié)點(diǎn)都在同一層，且最后一層不能有空節(jié)點(diǎn)，類似于滿二叉樹。
我們依次插入10，9，8，7，6，5，4，3，2，1來看一下2-3數(shù)是如何進(jìn)行自平衡的。
2-3樹在插入元素之前首先要進(jìn)行一次未命中的查找，然后將元素插入葉子節(jié)點(diǎn)中，之后再進(jìn)行平衡操作，下面具體說明。
首先插入10，如下圖

什么是紅黑樹  
2-3樹中插入10

然后插入9，9小于10，2-3樹在插入時(shí)要將9融入10這個(gè)葉子節(jié)點(diǎn)中（當(dāng)然也是根節(jié)點(diǎn)），融合完成后如下：  
 
什么是紅黑樹  
2-3樹中插入9

這是一個(gè)3節(jié)點(diǎn)，不用執(zhí)行平衡操作。2-3樹中把有兩個(gè)元素，三個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)稱為3節(jié)點(diǎn)，把有一個(gè)元素，兩個(gè)子節(jié)點(diǎn)的的節(jié)點(diǎn)稱為2節(jié)點(diǎn)。  
接著插入8，插入8的時(shí)候同樣要先融入葉子節(jié)點(diǎn)中，如下圖左側(cè)所示  
 
什么是紅黑樹  
2-3樹中插入8

8融入葉子節(jié)點(diǎn)后，該結(jié)點(diǎn)便擁有了3個(gè)元素，不滿足2-3樹的定義，這時(shí)就要把3節(jié)點(diǎn)進(jìn)行分裂，即把左側(cè)和右側(cè)的元素分裂為2節(jié)點(diǎn)，而中間的元素抽出，繼續(xù)融入其父節(jié)點(diǎn)，在這里便成為了一個(gè)根節(jié)點(diǎn)。  
繼續(xù)插入7，如下  
 
什么是紅黑樹  
2-3樹中插入7
插入后，各個(gè)節(jié)點(diǎn)都滿足2-3樹的定義，不需要進(jìn)行平衡操作。  
接著插入6，還是首先找到葉子節(jié)點(diǎn)，然后將其融入，如下圖左側(cè)所示  
 
什么是紅黑樹  
2-3樹中插入6
插入后6、7、8三個(gè)元素所在的葉子節(jié)點(diǎn)不再滿足2-3樹的定義，需要進(jìn)行分裂，即抽出元素7融入父節(jié)點(diǎn)，6和8分裂為7的左右子節(jié)點(diǎn)。  
接著插入5，如下圖所示，同樣不需要進(jìn)行平衡操作  
 
什么是紅黑樹  
2-3樹中插入5
接著插入4，還是首先找到葉子節(jié)點(diǎn)，然后將其融入，如下圖左側(cè)所示  
 
什么是紅黑樹  
2-3樹中插入4
插入后4、5、6三個(gè)元素所在的葉子節(jié)點(diǎn)不再滿足2-3樹的定義，需要進(jìn)行分裂，即抽出元素5融入父節(jié)點(diǎn)，4和6分裂為5的左右子節(jié)點(diǎn)。5融入父節(jié)點(diǎn)后，該結(jié)點(diǎn)便有了5、7、9三個(gè)元素，因而需要繼續(xù)分裂，元素7成為新的根節(jié)點(diǎn)，5和9成為7的左右子節(jié)點(diǎn)。  
接著插入3，3融入4所在的葉子節(jié)點(diǎn)中，不需要進(jìn)行平衡操作  
 
什么是紅黑樹  
2-3樹中插入3
接著插入2，還是首先找到葉子節(jié)點(diǎn)，然后將其融入，如下圖左側(cè)所示  
 
什么是紅黑樹  
2-3樹中插入2
插入后2、3、4三個(gè)元素所在的葉子節(jié)點(diǎn)不再滿足2-3樹的定義，需要進(jìn)行分裂，即抽出元素3融入父節(jié)點(diǎn)，2和4分裂為3的左右子節(jié)點(diǎn)，3融入5所在的父節(jié)點(diǎn)中。  
最后插入2，同樣先找到葉子節(jié)點(diǎn)，然后將其融入，如下圖所示  
 
什么是紅黑樹  
2-3樹中插入1
至此，我們便完成了在2-3樹中依次插入10，9，8，7，6，5，4，3，2，1，并且2-3樹始終維護(hù)著平衡。怎么樣，是不是很神奇。    

再看紅黑樹

那么紅黑樹與2-3樹有什么關(guān)系呢？現(xiàn)在我們對(duì)2-3樹進(jìn)行改造，改造成一個(gè)二叉樹。怎么改造呢？對(duì)于2節(jié)點(diǎn)，保持不變；對(duì)于3節(jié)點(diǎn)，我們首先將3節(jié)點(diǎn)中左側(cè)的元素標(biāo)記為紅色，如下圖2所示。

什么是紅黑樹  
2-3樹到紅黑樹的改造
然后我們將其改造成圖3的形式；再將3節(jié)點(diǎn)的位于中間的子節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置為父節(jié)點(diǎn)中那個(gè)紅色的節(jié)點(diǎn)，如圖4的所示；最后我們將圖4的形式改為二叉樹的樣子，如圖5所示。圖5是不是很熟悉，沒錯(cuò)，這就是我們常常提到的大名鼎鼎的紅黑樹了。  
下面我們回過頭再看下紅黑樹的五條性質(zhì)。  
 
什么是紅黑樹  
從2-3樹看紅黑樹
性質(zhì)1：每個(gè)節(jié)點(diǎn)要么是黑色，要么是紅色。  
2-3樹中存在2節(jié)點(diǎn)和3節(jié)點(diǎn)，3節(jié)點(diǎn)中左側(cè)的元素便是紅色節(jié)點(diǎn)，而其他的節(jié)點(diǎn)便是黑色節(jié)點(diǎn)。  
 性質(zhì)2：根節(jié)點(diǎn)是黑色。  
在2-3樹中，根節(jié)點(diǎn)只能是2節(jié)點(diǎn)或者3節(jié)點(diǎn)，2節(jié)點(diǎn)與3節(jié)點(diǎn)在紅黑樹中的等價(jià)形式，如下圖所示  
 
什么是紅黑樹  
2節(jié)點(diǎn)與3節(jié)點(diǎn)在紅黑樹中的等價(jià)形式
顯然，無論是哪種情況，根節(jié)點(diǎn)都是黑色的。  
 性質(zhì)3：每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。  
這里的葉子節(jié)點(diǎn)不是指左右子樹為空的那個(gè)葉子節(jié)點(diǎn)，而是指節(jié)點(diǎn)不存在子節(jié)點(diǎn)或者為空節(jié)點(diǎn)被稱作葉子節(jié)點(diǎn)。在性質(zhì)2中我們討論的根節(jié)點(diǎn)是黑色的都是討論根節(jié)點(diǎn)不為空的情況，若紅黑樹是一個(gè)空樹，那么根節(jié)點(diǎn)自然也是空的葉子節(jié)點(diǎn)，這時(shí)候葉子節(jié)點(diǎn)便必然是黑色的。  
 性質(zhì)4：每個(gè)紅色結(jié)點(diǎn)的兩個(gè)子結(jié)點(diǎn)一定都是黑色。  
還是從2-3樹的角度來理解，紅色節(jié)點(diǎn)對(duì)應(yīng)2-3樹中3節(jié)點(diǎn)左側(cè)的元素，那么它的子節(jié)點(diǎn)要么是2節(jié)點(diǎn)，要么是3節(jié)點(diǎn)。無論是2節(jié)點(diǎn)還是3節(jié)點(diǎn)對(duì)應(yīng)的節(jié)點(diǎn)顏色都是黑色的，這在性質(zhì)2時(shí)已經(jīng)討論了。  
 性質(zhì)5：任意一結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)。  
性質(zhì)5應(yīng)該是紅黑樹最重要的一條性質(zhì)了。2-3樹是一顆絕對(duì)平衡的樹，即2-3樹中任意一個(gè)節(jié)點(diǎn)出發(fā)，到達(dá)葉子節(jié)點(diǎn)后所經(jīng)過的節(jié)點(diǎn)數(shù)都是一樣的。那么對(duì)應(yīng)到紅黑樹呢？2-3樹中2節(jié)點(diǎn)對(duì)應(yīng)到紅黑樹便是一個(gè)黑色的節(jié)點(diǎn)，而3節(jié)點(diǎn)對(duì)應(yīng)到紅黑樹是一個(gè)紅色節(jié)點(diǎn)和一個(gè)黑色節(jié)點(diǎn)。所以，無論是2節(jié)點(diǎn)還是3節(jié)點(diǎn)，在紅黑樹中都會(huì)對(duì)應(yīng)一個(gè)黑色節(jié)點(diǎn)。那么2-3樹中的絕對(duì)平衡，在紅黑樹中自然就是任意一結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑都包含數(shù)量相同的黑結(jié)點(diǎn)了。  
相信大家現(xiàn)在已經(jīng)對(duì)紅黑樹的五條性質(zhì)有了更加深刻的體會(huì)了。那么我們?cè)倏聪录t黑樹維持平衡的三種操作，即變色、左旋、右旋怎么理解呢？  
首先看一下  變色，以下圖為例，  
 
什么是紅黑樹  
紅黑樹的變色
在2-3樹中插入節(jié)點(diǎn)3后，便不再滿足2-3樹的定義，需要進(jìn)行分解，將元素2抽出作為1和3的父節(jié)點(diǎn)，然后2繼續(xù)向上融合。  
對(duì)應(yīng)到紅黑樹中就是，首先插入節(jié)點(diǎn)3，在紅黑樹中新插入的節(jié)點(diǎn)默認(rèn)為紅色，然后不滿足定義，所以需要進(jìn)行分解，分解后各個(gè)節(jié)點(diǎn)都為2節(jié)點(diǎn)，所以變?yōu)楹谏?。?節(jié)點(diǎn)需要繼續(xù)向上融合，故要變成紅色。  
接著看一下  右旋轉(zhuǎn)，以下圖為例，  
 
什么是紅黑樹  
紅黑樹的右旋轉(zhuǎn)
插入元素1后，進(jìn)行右旋轉(zhuǎn)操作，首先把2節(jié)點(diǎn)與3節(jié)點(diǎn)斷開連接，同時(shí)把2與2的右子樹斷開連接，然后把2的右子樹連接至3的左子樹位置，不會(huì)違背二分搜索樹的性質(zhì)，然后再把3連接至2的右子樹位置。最后還要改變對(duì)應(yīng)節(jié)點(diǎn)的顏色，即把2節(jié)點(diǎn)的顏色改為原來3節(jié)點(diǎn)的黑色，把3節(jié)點(diǎn)的顏色改為原來2節(jié)點(diǎn)的紅色。  
接著看一下  左旋轉(zhuǎn)，與右旋轉(zhuǎn)類似，以下圖為例，  
 
什么是紅黑樹  
紅黑樹的左旋轉(zhuǎn)
插入元素3后，進(jìn)行左旋轉(zhuǎn)操作，首先把2節(jié)點(diǎn)與3節(jié)點(diǎn)斷開連接，同時(shí)把3與3的左子樹斷開連接，然后把3的左子樹連接至2的右子樹位置，不會(huì)違背二分搜索樹的性質(zhì)，然后再把2連接至3的左子樹位置。最后還要改變對(duì)應(yīng)節(jié)點(diǎn)的顏色，即把2節(jié)點(diǎn)的顏色改為原來3節(jié)點(diǎn)的紅色，把3節(jié)點(diǎn)的顏色改為原來2節(jié)點(diǎn)的黑色。    

關(guān)于“什么是紅黑樹”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手