關于紅黑樹(R-B tree)原理,看這篇如何

學過數據數據結構都知道二叉樹的概念,而又有多種比較常見的二叉樹類型,比如完全二叉樹、滿二叉樹、二叉搜索樹、均衡二叉樹、完美二叉樹等;今天我們要說的紅黑樹就是就是一顆非嚴格均衡的二叉樹,均衡二叉樹又是在二叉搜索樹的基礎上增加了自動維持平衡的性質,插入、搜索、刪除的效率都比較高。紅黑樹也是實現TreeMap存儲結構的基石。

一. 二叉搜索樹

二叉搜索樹又叫二叉查找樹、二叉排序樹,我們先看一下典型的二叉搜索樹,這樣的二叉樹有何規則特點呢?

  1. 節點的左子樹小于節點本身;
  2. 節點的右子樹大于節點本身;
  3. 左右子樹同樣為二叉搜索樹;

下圖就是一顆典型的二叉搜索樹

二叉搜索樹是均衡二叉樹的基礎,我們看一下它的搜索步驟如何

我們要從二叉樹中找到值為 58 的節點

第一步:首先查找到根節點,值為60的節點

第二步:比較我們要找的值58與該節點的大小

如果等于,那么恭喜,已經找到;

如果小于,繼續找左子樹;

如果大于,那么找右子樹;

很明顯58 < 60,因此我們找到左子樹的節點 56,此時我們已經定位到了節點56

第三步:按照第二步的規則繼續找

58 > 56 我們需要繼續找右子樹,定位到了右子樹節點58,恭喜,此時我們已經找到了。

我們經過三步就已經找到了,其實就是我們平時所說的二分查找,這種二叉搜索樹好像查找效率很高,但同樣它也有缺陷,如下面這樣的二叉搜索樹。

看到這樣的二叉搜索樹是否很別扭,典型的大長腿瘸子,但它也是二叉搜索樹,如果我們要找值為50的節點,基本上和單鏈表查詢沒多大區別了,性能將大打折扣。這個時候我們的均衡二叉樹就粉墨登場了,均衡二叉樹就是在二叉搜索樹的基礎上添加了自動維持平衡的性質。

上面的大長腿瘸子二叉搜索樹經過自動平衡后,可能就成為了下面這樣的二叉樹。

經過了自動平衡,再去找值為50的節點,查找性能將提升很多。紅黑樹就是非嚴格均衡的二叉搜索樹。

二. 紅黑樹規則特點

紅黑樹具體有哪些規則特點呢?

  1. 節點分為紅色或者黑色;
  2. 根節點必為黑色;
  3. 葉子節點都為黑色,且為null;
  4. 連接紅色節點的兩個子節點都為黑色(紅黑樹不會出現相鄰的紅色節點);
  5. 從任意節點出發,到其每個葉子節點的路徑中包含相同數量的黑色節點;
  6. 新加入到紅黑樹的節點為紅色節點;

規則看著好像挺多,沒錯,因為紅黑樹也是均衡二叉樹,需要具備自動維持平衡的性質,上面的6條就是紅黑樹給出的自動維持平衡所需要具備的規則

我們看一看一個典型的紅黑樹到底是什么樣兒?

首先解讀一下規則,除了字面上看到的意思,還隱藏了哪些意思呢?

第一. 從根節點到葉子節點的最長路徑不大于最短路徑的2倍

??怎么樣的路徑算最短路徑?

??從規則5中,我們知道從根節點到每個葉子節點的黑色節點數量是一樣的,那么純由黑色節點組成的路徑就是最短路徑;

??什么樣的路徑算是最長路徑?

??根據規則4和規則3,若有紅色節點,則必然有一個連接的黑色節點,當紅色節點和黑色節點數量相同時,就是最長路徑,也就是黑色節點(或紅色節點)* 2

第二. 為什么說新加入到紅黑樹中的節點為紅色節點

??從規則4中知道,當前紅黑樹中從根節點到每個葉子節點的黑色節點數量是一樣的,此時假如新的黑色節點的話,必然破壞規則,但加入紅色節點卻不一定,除非其父節點就是紅色節點,因此加入紅色節點,破壞規則的可能性小一些,下面我們也會舉例來說明。

什么情況下,紅黑樹的結構會被破壞呢?破壞后又怎么維持平衡,維持平衡主要通過兩種方式【變色】和【旋轉】,【旋轉】又分【左旋】和【右旋】,兩種方式可相互結合。

下面我們從插入和刪除兩種場景來舉例說明

三. 紅黑樹節點插入

當我們插入值為66的節點時,紅黑樹變成了這樣

很明顯,這個時候結構依然遵循著上述6大規則,無需啟動自動平衡機制調整節點平衡狀態;

如果再向里面插入值為51的節點呢,這個時候紅黑樹變成了這樣

很明顯現在的結構不遵循規則 4 了,這個時候就需要啟動自動平衡機制調整節點平衡狀態

3.1 變色

我們可以通過變色的方式,使結構滿足紅黑樹的規則

  • 首先解決結構不遵循規則 4 這一點(紅色節點相連,節點49-51),需將節點49改為黑色;
  • 此時我們發現又違反了規則5(56-49-51-XX路徑中黑色節點超過了其他路徑),那么我們將節點45改為紅色節點;
  • 哈哈,妹的,又違反了規則4(紅色節點相連,節點56-45-43),那么我們將節點56和節點43改為黑色節點;
  • 但是我們發現此時又違反了規則5(60-56-XX路徑的黑色節點比60-68-XX的黑色節點多),因此我們需要調整節點68為黑色;
  • 完成!!

最終調整完成后的樹為:

但并不是什么時候都那么幸運,可以直接通過變色就達成目的,大多數時候還需要通過旋轉來解決。

如在下面這棵樹的基礎上,加入節點65.

插入節點65后進行以下步驟

這個時候,你會發現對于節點64無論是紅色節點還是黑色節點,都會違反規則5,路徑中的黑色節點始終無法達成一致,這個時候僅通過【變色】已經無法達成目的。我們需要通過旋轉操作,當然【旋轉】操作一般還需要搭配【變色】操作。

旋轉包括【左旋】和【右旋】,

左旋:

逆時針旋轉兩個節點,讓一個節點被其右子節點取代,而該節點成為右子節點的左子節點

左旋操作步驟如下:

首先斷開節點PL與右子節點G的關系,同時將其右子節點的引用指向節點C2;然后斷開節點G與左子節點C2的關系,同時將G的左子節點的應用指向節點PL

右旋:

順時針旋轉兩個節點,讓一個節點被其左子節點取代,而該節點成為左子節點的右子節點

右旋操作步驟如下:

首先斷開節點G與左子節點PL的關系,同時將其左子節點的引用指向節點C2;然后斷開節點PL與右子節點C2的關系,同時將PL的右子節點的應用指向節點G

無法通過變色而進行旋轉的場景分為以下四種:

3.2 左左節點旋轉

這種情況下,父節點和插入的節點都是左節點,如下圖(旋轉原始圖1)這種情況下,我們要插入節點65

規則如下:以祖父節點【右旋】,搭配【變色】

按照規則,步驟如下:

3.3 左右節點旋轉

這種情況下,父節點是左節點,插入的節點是右節點,在旋轉原始圖1中,我們要插入節點67

規則如下:先父節點【左旋】,然后祖父節點【右旋】,搭配【變色】

按照規則,步驟如下:

3.4 右左節點旋轉

這種情況下,父節點是右節點,插入的節點是左節點,如下圖(旋轉原始圖2)這種情況,我們要插入節點68

規則如下:先父節點【右旋】,然后祖父節點【左旋】,搭配【變色】

按照規則,步驟如下:

3.5 右右節點旋轉

這種情況下,父節點和插入的節點都是右節點,在旋轉原始圖2中,我們要插入節點70

規則如下:以祖父節點【左旋】,搭配【變色】

按照規則,步驟如下:

3.6 紅黑樹插入總結

無需調整 【變色】即可實現平衡 【旋轉+變色】才可實現平衡
情況1: 當父節點為黑色時插入子節點 空樹插入根節點,將根節點紅色變為黑色 父節點為紅色左節點,叔父節點為黑色,插入左子節點,那么通過【左左節點旋轉】
情況2: - 父節點和叔父節點都為紅色 父節點為紅色左節點,叔父節點為黑色,插入右子節點,那么通過【左右節點旋轉】
情況3: - - 父節點為紅色右節點,叔父節點為黑色,插入左子節點,那么通過【右左節點旋轉】
情況4: - - 父節點為紅色右節點,叔父節點為黑色,插入右子節點,那么通過【右右節點旋轉】

四. 紅黑樹節點刪除

相比較于紅黑樹的節點插入,刪除節點更為復雜,我們從子節點是否為null和紅色為思考維度來討論。

4.1 子節點至少有一個為null

當待刪除的節點的子節點至少有一個為null節點時,刪除了該節點后,將其有值的節點取代當前節點即可,若都為null,則將當前節點設置為null,當然如果違反規則了,則按需調整,如【變色】以及【旋轉】。

4.2 子節點都是非null節點

這種情況下,

第一步:找到該節點的前驅或者后繼

前驅:左子樹中值最大的節點(可得出其最多只有一個非null子節點,可能都為null);

后繼:右子樹中值最小的節點(可得出其最多只有一個非null子節點,可能都為null);

前驅和后繼都是值最接近該節點值的節點,類似于該節點.prev = 前驅,該節點.next = 后繼。

第二步:將前驅或者后繼的值復制到該節點中,然后刪掉前驅或者后繼

如果刪除的是左節點,則將前驅的值復制到該節點中,然后刪除前驅;如果刪除的是右節點,則將后繼的值復制到該節點中,然后刪除后繼;

這相當于是一種“取巧”的方法,我們刪除節點的目的是使該節點的值在紅黑樹上不存在,因此專注于該目的,我們并不關注刪除節點時是否真是我們想刪除的那個節點,同時我們也不需考慮樹結構的變化,因為樹的結構本身就會因為自動平衡機制而經常進行調整。

前面我們已經說了,我們要刪除的實際上是前驅或者后繼,因此我們就以前驅為主線來講解,后繼的學習可參考前驅,包括幾種情況

4.2.1 前驅為黑色節點,并且有一個非null子節點

分析:

因為要刪除的是左節點64,找到該節點的前驅63;

然后用前驅的值63替換待刪除節點的值64,此時兩個節點(待刪除節點和前驅)的值都為63;

刪除前驅63,此時成為上圖過程中間環節,但我們發現其不符合紅黑樹規則4,因此需要進行自動平衡調整;

這里直接通過【變色】即可完成。

4.2.2 前驅為黑色節點,同時子節點都為null

分析:

因為要刪除的是左節點64,找到該節點的前驅63;

然后用前驅的值63替換待刪除節點的值64,此時兩個節點(待刪除節點和前驅)的值都為63;

刪除前驅63,此時成為上圖過程中間環節,但我們發現其不符合紅黑樹規則5,因此需要進行自動平衡調整;

這里直接通過【變色】即可完成。

4.2.3 前驅為紅色節點,同時子節點都為null

分析:

因為要刪除的是左節點64,找到該節點的前驅63;

然后用前驅的值63替換待刪除節點的值64,此時兩個節點(待刪除節點和前驅)的值都為63;

刪除前驅63,樹的結構并沒有打破規則。

4.3 紅黑樹刪除總結

紅黑樹刪除的情況比較多,但也就存在以下情況:

刪除的是根節點,則直接將根節點置為null;

待刪除節點的左右子節點都為null,刪除時將該節點置為null;

待刪除節點的左右子節點有一個有值,則用有值的節點替換該節點即可;

待刪除節點的左右子節點都不為null,則找前驅或者后繼,將前驅或者后繼的值復制到該節點中,然后刪除前驅或者后繼;

節點刪除后可能會造成紅黑樹的不平衡,這時我們需通過【變色】+【旋轉】的方式來調整,使之平衡,上面也給出了例子,建議大家多多練習,而不必背下來。

五. 總結

本文主要介紹了紅黑樹的相關原理,首先紅黑樹的基礎二叉搜索樹,我們先簡單說了一下二叉搜索樹,并且講了一下搜索的流程,然后就針對紅黑樹的6大規則特點,紅黑樹的插入操作,刪除操作,都使用了大量的圖形來加以說明,技術都是練出來的,有時候很多似是而非的地方,當動筆去寫的時候,其實很好理解。紅黑樹的使用非常廣泛,如TreeMap和TreeSet都是基于紅黑樹實現的,而Jdk8中HashMap當鏈表長度大于8時也會轉化為紅黑樹,紅黑樹比較復雜,本人也是還在學習過程中,如果有不對的地方請批評指正,望共同進步謝謝。

posted @ 2019-07-17 19:43  工匠初心  閱讀(...)  評論(...編輯  收藏
内蒙古快3开奖结果 重庆快乐十分一定牛 5月22日股票推荐 江苏快三遗漏 微豪配资 新开棋牌游戏平台 *pk10qq群 棋牌游戏交易平台 模拟炒股支付宝 快乐10分钟开奖结 股票配资平台全国招商 3d开奖号试机号 义乌期货配资 北京11选5走势一 融可赢配资 中国足球吧 快乐10分钟一