欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

數(shù)據(jù)結(jié)構(gòu)之紅黑樹詳解

 更新時(shí)間:2014年08月28日 10:56:43   投稿:junjie  
這篇文章主要介紹了數(shù)據(jù)結(jié)構(gòu)之紅黑樹詳解,紅黑樹是一種自平衡二叉查找樹,它的統(tǒng)計(jì)性能要好于平衡二叉樹(AVL樹),因此,紅黑樹在很多地方都有應(yīng)用,需要的朋友可以參考下

1.簡(jiǎn)介

紅黑樹是一種自平衡二叉查找樹。它的統(tǒng)計(jì)性能要好于平衡二叉樹(AVL樹),因此,紅黑樹在很多地方都有應(yīng)用。在C++ STL中,很多部分(目前包括set, multiset, map, multimap)應(yīng)用了紅黑樹的變體(SGI STL中的紅黑樹有一些變化,這些修改提供了更好的性能,以及對(duì)set操作的支持)。它是復(fù)雜的,但它的操作有著良好的最壞情況運(yùn)行時(shí)間,并且在實(shí)踐中是高效的: 它可以在O(log n)時(shí)間內(nèi)做查找,插入和刪除等操作。

本文介紹了紅黑樹的基本性質(zhì)和基本操作。

2.紅黑樹的性質(zhì)

紅黑樹,顧名思義,通過紅黑兩種顏色域保證樹的高度近似平衡。它的每個(gè)節(jié)點(diǎn)是一個(gè)五元組:color(顏色),key(數(shù)據(jù)),left(左孩子),right(右孩子)和p(父節(jié)點(diǎn))。

紅黑樹的定義也是它的性質(zhì),有以下五條:

性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色

性質(zhì)2. 根是黑色

性質(zhì)3. 所有葉子都是黑色(葉子是NIL節(jié)點(diǎn))

性質(zhì)4. 如果一個(gè)節(jié)點(diǎn)是紅的,則它的兩個(gè)兒子都是黑的

性質(zhì)5. 從任一節(jié)點(diǎn)到其葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。

這五個(gè)性質(zhì)強(qiáng)制了紅黑樹的關(guān)鍵性質(zhì): 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。為什么呢?性質(zhì)4暗示著任何一個(gè)簡(jiǎn)單路徑上不能有兩個(gè)毗連的紅色節(jié)點(diǎn),這樣,最短的可能路徑全是黑色節(jié)點(diǎn),最長的可能路徑有交替的紅色和黑色節(jié)點(diǎn)。同時(shí)根據(jù)性質(zhì)5知道:所有最長的路徑都有相同數(shù)目的黑色節(jié)點(diǎn),這就表明了沒有路徑能多于任何其他路徑的兩倍長。

3.紅黑樹的基本操作

因?yàn)榧t黑樹也是二叉查找樹,因此紅黑樹上的查找操作與普通二叉查找樹上的查找操作相同。然而,紅黑樹上的插入操作和刪除操作會(huì)導(dǎo)致不再符合紅黑樹的性質(zhì)?;謴?fù)紅黑樹的性質(zhì)需要少量(O(log n))的顏色變更(實(shí)際是非??焖俚?和不超過三次樹旋轉(zhuǎn)(對(duì)于插入操作是兩次)。雖然插入和刪除很復(fù)雜,但操作時(shí)間仍可以保持為 O(log n) 次。

3.1插入操作

插入操作可以概括為以下幾個(gè)步驟:

(1)查找要插入的位置,時(shí)間復(fù)雜度為:O(N)

(2)將新節(jié)點(diǎn)的color賦為紅色

(3)自下而上重新調(diào)整該樹為紅黑樹

其中,第(1)步的查找方法跟普通二叉查找樹一樣,第(2)步之所以將新插入的節(jié)點(diǎn)的顏色賦為紅色,是因?yàn)椋喝绻O(shè)為黑色,就會(huì)導(dǎo)致根到葉子的路徑上有一條路上,多一個(gè)額外的黑節(jié)點(diǎn),這個(gè)是很難調(diào)整的。但是設(shè)為紅色節(jié)點(diǎn)后,可能會(huì)導(dǎo)致出現(xiàn)兩個(gè)連續(xù)紅色節(jié)點(diǎn)的沖突,那么可以通過顏色調(diào)換(color flips)和樹旋轉(zhuǎn)來調(diào)整,這樣簡(jiǎn)單多了。下面討論步驟(3)的一些細(xì)節(jié):

設(shè)要插入的節(jié)點(diǎn)為N,其父節(jié)點(diǎn)為P,其父親G的兄弟節(jié)點(diǎn)為U(即P和U是同一個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn))。

[1] 如果P是黑色的,則整棵樹不必調(diào)整便是紅黑樹。

[2] 如果P是紅色的(可知,其父節(jié)點(diǎn)G一定是黑色的),則插入z后,違背了性質(zhì)4,需要進(jìn)行調(diào)整。調(diào)整時(shí)分以下3種情況:

(a)N的叔叔U是紅色的

如上圖所示,我們將P和U重繪為黑色并重繪節(jié)點(diǎn)G為紅色(用來保持性質(zhì)5)。現(xiàn)在新節(jié)點(diǎn)N有了一個(gè)黑色的父節(jié)點(diǎn)P,因?yàn)橥ㄟ^父節(jié)點(diǎn)P或叔父節(jié)點(diǎn)U的任何路徑都必定通過祖父節(jié)點(diǎn)G,在這些路徑上的黑節(jié)點(diǎn)數(shù)目沒有改變。但是,紅色的祖父節(jié)點(diǎn)G的父節(jié)點(diǎn)也有可能是紅色的,這就違反了性質(zhì)4。為了解決這個(gè)問題,我們?cè)谧娓腹?jié)點(diǎn)G上遞歸調(diào)整顏色。

(b)N的叔叔U是黑色的,且N是右孩子

如上圖所示,我們對(duì)P進(jìn)行一次左旋轉(zhuǎn)調(diào)換新節(jié)點(diǎn)和其父節(jié)點(diǎn)的角色; 接著,按情形(c)處理以前的父節(jié)點(diǎn)P以解決仍然失效的性質(zhì)4。

(c)N的叔叔U是黑色的,且N是左孩子

如上圖所示,對(duì)祖父節(jié)點(diǎn)G 的一次右旋轉(zhuǎn); 在旋轉(zhuǎn)產(chǎn)生的樹中,以前的父節(jié)點(diǎn)P現(xiàn)在是新節(jié)點(diǎn)N和以前的祖父節(jié)點(diǎn)G 的父節(jié)點(diǎn), 然后交換以前的父節(jié)點(diǎn)P和祖父節(jié)點(diǎn)G的顏色,結(jié)果的樹滿足性質(zhì)4,同時(shí)性質(zhì)5[4]也仍然保持滿足。

3.2刪除操作

刪除操作可以概括為以下幾個(gè)步驟:

(1)查找要?jiǎng)h除位置,時(shí)間復(fù)雜度為:O(N)

(2)用刪除節(jié)點(diǎn)后繼或者節(jié)點(diǎn)替換該節(jié)點(diǎn)(只進(jìn)行數(shù)據(jù)替換即可,不必調(diào)整指針,后繼節(jié)點(diǎn)是中序遍歷中緊挨著該節(jié)點(diǎn)的節(jié)點(diǎn),即:右孩子的最左孩子節(jié)點(diǎn))

(3)如果刪除節(jié)點(diǎn)的替換節(jié)點(diǎn)為黑色,則需重新調(diào)整該樹為紅黑樹

其中,第(1)步的查找方法跟普通二叉查找樹一樣,第(2)步之所以用后繼節(jié)點(diǎn)替換刪除節(jié)點(diǎn),是因?yàn)檫@樣可以保證該后繼節(jié)點(diǎn)之上仍是一個(gè)紅黑樹,而后繼節(jié)點(diǎn)可能是一個(gè)葉節(jié)點(diǎn)或者只有右子樹的節(jié)點(diǎn),這樣只需用有節(jié)點(diǎn)替換后繼節(jié)點(diǎn)即可達(dá)到刪除的目的。如果需要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)兒子,那么問題可以被轉(zhuǎn)化成刪除另一個(gè)只有一個(gè)兒子的節(jié)點(diǎn)的問題。(沒看懂???可參考:http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91 )在第(3)步中,如果,如果刪除節(jié)點(diǎn)為紅色節(jié)點(diǎn),則他的父親和孩子全為黑節(jié)點(diǎn),這樣直接刪除該節(jié)點(diǎn)即可,不必進(jìn)行任何調(diào)整。如果刪除節(jié)點(diǎn)是黑節(jié)點(diǎn),分四種情況:

設(shè)要?jiǎng)h除的節(jié)點(diǎn)為N,其父節(jié)點(diǎn)為P,其兄弟節(jié)點(diǎn)為S。

由于N是黑色的,則P可能是黑色的,也可能是紅色的,S也可能是黑色的或者紅色的

(1)S是紅色的

此時(shí)P肯定是紅色的。我們對(duì)N的父節(jié)點(diǎn)進(jìn)行左旋轉(zhuǎn),然后把紅色兄弟轉(zhuǎn)換成N的祖父。我們接著對(duì)調(diào) N 的父親和祖父的顏色。盡管所有的路徑仍然有相同數(shù)目的黑色節(jié)點(diǎn),現(xiàn)在 N 有了一個(gè)黑色的兄弟和一個(gè)紅色的父親,所以我們可以接下去按 (2)、(3)或(4)情況來處理。

(2)S和S的孩子全是黑色的

在這種情況下,P可能是黑色的或者紅色的,我們簡(jiǎn)單的重繪S 為紅色。結(jié)果是通過S的所有路徑,它們就是以前不通過 N 的那些路徑,都少了一個(gè)黑色節(jié)點(diǎn)。因?yàn)閯h除 N 的初始的父親使通過 N 的所有路徑少了一個(gè)黑色節(jié)點(diǎn),這使事情都平衡了起來。但是,通過 P 的所有路徑現(xiàn)在比不通過 P 的路徑少了一個(gè)黑色節(jié)點(diǎn)。接下來,要調(diào)整以P作為N遞歸調(diào)整樹。

(3)S是黑色的,S的左孩子是紅色,右孩子是黑色

這種情況下我們?cè)?S 上做右旋轉(zhuǎn),這樣 S 的左兒子成為 S 的父親和 N 的新兄弟。我們接著交換 S 和它的新父親的顏色。所有路徑仍有同樣數(shù)目的黑色節(jié)點(diǎn),但是現(xiàn)在 N 有了一個(gè)右兒子是紅色的黑色兄弟,所以我們進(jìn)入了情況(4)。N 和它的父親都不受這個(gè)變換的影響。

(4)S是黑色的,S的右孩子是紅色

在這種情況下我們?cè)?N 的父親上做左旋轉(zhuǎn),這樣 S 成為 N 的父親和 S 的右兒子的父親。我們接著交換 N 的父親和 S 的顏色,并使 S 的右兒子為黑色。子樹在它的根上的仍是同樣的顏色,所以屬性 3 沒有被違反。但是,N 現(xiàn)在增加了一個(gè)黑色祖先: 要么 N 的父親變成黑色,要么它是黑色而 S 被增加為一個(gè)黑色祖父。所以,通過 N 的路徑都增加了一個(gè)黑色節(jié)點(diǎn)。

4.參考資料

(1)《算法導(dǎo)論》,第二版

(2) http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91

相關(guān)文章

  • C++ stack與queue模擬實(shí)現(xiàn)詳解

    C++ stack與queue模擬實(shí)現(xiàn)詳解

    這篇文章主要給大家介紹了關(guān)于c++stack與queue模擬實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面跟著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2021-08-08
  • 詳解c++優(yōu)先隊(duì)列priority_queue的用法

    詳解c++優(yōu)先隊(duì)列priority_queue的用法

    本文詳細(xì)講解了c++優(yōu)先隊(duì)列priority_queue的用法,文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-12-12
  • C++中的異常實(shí)例詳解

    C++中的異常實(shí)例詳解

    異常處理是C++的一項(xiàng)語言機(jī)制,用于在程序中處理異常事件,下面這篇文章主要給大家介紹了關(guān)于C++中異常的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2022-02-02
  • C語言實(shí)現(xiàn)簡(jiǎn)單學(xué)生成績管理系統(tǒng)項(xiàng)目

    C語言實(shí)現(xiàn)簡(jiǎn)單學(xué)生成績管理系統(tǒng)項(xiàng)目

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡(jiǎn)單學(xué)生成績管理系統(tǒng)項(xiàng)目,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-07-07
  • 深入分析C中不安全的sprintf與strcpy

    深入分析C中不安全的sprintf與strcpy

    本篇文章是對(duì)C中不安全的sprintf與strcpy函數(shù)的使用進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下
    2013-05-05
  • c語言文件讀寫示例(c語言文件操作)

    c語言文件讀寫示例(c語言文件操作)

    這篇文章主要介紹了c語言文件讀寫示例(c語言文件操作),需要的朋友可以參考下
    2014-02-02
  • C++實(shí)現(xiàn)打印兩個(gè)有序鏈表公共部分的方法

    C++實(shí)現(xiàn)打印兩個(gè)有序鏈表公共部分的方法

    這篇文章主要介紹了C++實(shí)現(xiàn)打印兩個(gè)有序鏈表公共部分的方法,涉及C++針對(duì)有序鏈表的簡(jiǎn)單遍歷、比較相關(guān)操作技巧,需要的朋友可以參考下
    2017-05-05
  • vsCode配置import@路徑提示的實(shí)現(xiàn)步驟

    vsCode配置import@路徑提示的實(shí)現(xiàn)步驟

    在導(dǎo)入文件設(shè)置路徑的時(shí)候方便了很多,本文主要介紹了vsCode配置import@路徑提示的實(shí)現(xiàn)步驟,具有一定的參考價(jià)值,感興趣的可以了解一下
    2023-08-08
  • C++解析wav文件方法介紹

    C++解析wav文件方法介紹

    最近將項(xiàng)目改為跨平臺(tái),于是音頻模塊從微軟的XAudio2改用OpenAL庫。之前使用MSDN的代碼,所以現(xiàn)在改為了C++標(biāo)準(zhǔn)的寫法,適用性更廣
    2022-09-09
  • 基于C語言實(shí)現(xiàn)簡(jiǎn)易的掃雷游戲

    基于C語言實(shí)現(xiàn)簡(jiǎn)易的掃雷游戲

    這篇文章主要為大家詳細(xì)介紹了基于C語言實(shí)現(xiàn)簡(jiǎn)易的掃雷游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-06-06

最新評(píng)論