紅黑樹 01 紅黑樹和2-3樹的等價性

2-3樹

  • 2-3樹是一種絕對平衡的二分搜索樹;
  • 2-3樹中存在2種節(jié)點:2節(jié)點和3節(jié)點碘勉;
  • 2節(jié)點:每個節(jié)點存1個元素板辽,有2個孩子奇瘦;
  • 3節(jié)點:每個節(jié)點存2個元素,有3個孩子劲弦;
  • 新添加的元素都要融合進葉子節(jié)點耳标,或者融合成3節(jié)點,或者融合成臨時的4節(jié)點邑跪;
  • 融合成臨時的4節(jié)點后次坡,就要將4節(jié)點拆成3個2節(jié)點,然后將中間的節(jié)點向上融合到其父節(jié)點呀袱,融合后的結(jié)構(gòu)如果任然是4節(jié)點贸毕,則繼續(xù)拆;

紅黑樹

  • 紅黑樹和2-3樹是等價的夜赵;
  • 紅黑樹中的每個節(jié)點只存一個元素明棍,因而實現(xiàn)上更簡單;
  • 紅黑樹中的節(jié)點要么是紅色寇僧,要么是黑色摊腋;
  • 紅黑樹中紅節(jié)點表示其和其父節(jié)點一起表示2-3樹中的一個3節(jié)點;
  • 紅黑樹中紅節(jié)點都是向左傾斜的嘁傀,定義出來的兴蒸;
  • 紅黑樹中的節(jié)點有一個表示其顏色的屬性;
  • 紅黑樹中的紅節(jié)點對應(yīng)2-3樹中3節(jié)點中存儲的左邊的元素细办;
  • 紅黑樹中根節(jié)點是黑色的橙凳;
  • 紅黑樹中從任意節(jié)點到葉子節(jié)點(最后的空節(jié)點),經(jīng)過的黑色節(jié)點是一樣的笑撞; *
  • 紅黑樹中一個節(jié)點是紅色的岛啸,那么他的孩子節(jié)點都是黑色的;
  • 紅黑樹中一個節(jié)點是黑色的茴肥,那么他的右孩子是黑色的坚踩;
  • 紅黑樹中每個葉子節(jié)點(最后的空節(jié)點)是黑色的;
  • 紅黑樹是保持“黑平衡”的二叉樹瓤狐,嚴格意義上瞬铸,不是平衡二叉樹批幌;

紅黑樹時間復(fù)雜度分析

  • 紅黑樹的最大高度:2logn;
  • 紅黑樹的時間復(fù)雜度為O(logn)嗓节;
  • 紅黑樹添加刪除更快荧缘,AVL樹查詢更快;
  • 樹結(jié)構(gòu)不怎么變用AVL樹赦政,經(jīng)常添加刪除操作用紅黑樹胜宇;

紅黑樹基礎(chǔ)代碼

  • 紅黑樹中每個節(jié)點在初始化的時候都是紅節(jié)點;
  • 每個空節(jié)點(null)是黑節(jié)點恢着;
public class RBTree<K extends Comparable<K>, V> {

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node{
        public K key;
        public V value;
        public Node left, right;
        public boolean color;

        public Node(K key, V value){
            this.key = key;
            this.value = value;
            left = null;
            right = null;
            color = RED;
        }
    }

    private Node root;
    private int size;

    public RBTree(){
        root = null;
        size = 0;
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    // 判斷節(jié)點node的顏色
    private boolean isRed(Node node){
        if(node == null)
            return BLACK;
        return node.color;
    }

}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市财破,隨后出現(xiàn)的幾起案子掰派,更是在濱河造成了極大的恐慌,老刑警劉巖左痢,帶你破解...
    沈念sama閱讀 219,427評論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件靡羡,死亡現(xiàn)場離奇詭異,居然都是意外死亡俊性,警方通過查閱死者的電腦和手機略步,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,551評論 3 395
  • 文/潘曉璐 我一進店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來定页,“玉大人趟薄,你說我怎么就攤上這事〉浠玻” “怎么了杭煎?”我有些...
    開封第一講書人閱讀 165,747評論 0 356
  • 文/不壞的土叔 我叫張陵,是天一觀的道長卒落。 經(jīng)常有香客問我羡铲,道長,這世上最難降的妖魔是什么儡毕? 我笑而不...
    開封第一講書人閱讀 58,939評論 1 295
  • 正文 為了忘掉前任也切,我火速辦了婚禮,結(jié)果婚禮上腰湾,老公的妹妹穿的比我還像新娘雷恃。我一直安慰自己,他們只是感情好檐盟,可當我...
    茶點故事閱讀 67,955評論 6 392
  • 文/花漫 我一把揭開白布褂萧。 她就那樣靜靜地躺著,像睡著了一般葵萎。 火紅的嫁衣襯著肌膚如雪导犹。 梳的紋絲不亂的頭發(fā)上唱凯,一...
    開封第一講書人閱讀 51,737評論 1 305
  • 那天,我揣著相機與錄音谎痢,去河邊找鬼磕昼。 笑死,一個胖子當著我的面吹牛节猿,可吹牛的內(nèi)容都是我干的票从。 我是一名探鬼主播,決...
    沈念sama閱讀 40,448評論 3 420
  • 文/蒼蘭香墨 我猛地睜開眼滨嘱,長吁一口氣:“原來是場噩夢啊……” “哼峰鄙!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起太雨,我...
    開封第一講書人閱讀 39,352評論 0 276
  • 序言:老撾萬榮一對情侶失蹤吟榴,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后囊扳,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體吩翻,經(jīng)...
    沈念sama閱讀 45,834評論 1 317
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,992評論 3 338
  • 正文 我和宋清朗相戀三年锥咸,在試婚紗的時候發(fā)現(xiàn)自己被綠了狭瞎。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,133評論 1 351
  • 序言:一個原本活蹦亂跳的男人離奇死亡搏予,死狀恐怖熊锭,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情缔刹,我是刑警寧澤球涛,帶...
    沈念sama閱讀 35,815評論 5 346
  • 正文 年R本政府宣布,位于F島的核電站校镐,受9級特大地震影響亿扁,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜鸟廓,卻給世界環(huán)境...
    茶點故事閱讀 41,477評論 3 331
  • 文/蒙蒙 一从祝、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧引谜,春花似錦牍陌、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,022評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至贝室,卻和暖如春契讲,著一層夾襖步出監(jiān)牢的瞬間仿吞,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,147評論 1 272
  • 我被黑心中介騙來泰國打工捡偏, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留唤冈,地道東北人。 一個月前我還...
    沈念sama閱讀 48,398評論 3 373
  • 正文 我出身青樓银伟,卻偏偏與公主長得像你虹,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子彤避,可洞房花燭夜當晚...
    茶點故事閱讀 45,077評論 2 355

推薦閱讀更多精彩內(nèi)容

  • 如果不先提出最佳問題忠藤,你怎么會去找最佳答案呢挟伙? 看完《改變提問,改變?nèi)松返那皟烧潞竽:ⅲ∠笞钌畹木褪沁@句話。 你會...
    小凡_閱讀 309評論 0 0
  • 哈嘍贮缅,哈嘍榨咐! 胖友們,你們好鴨谴供!我是剛來到簡書的小白小編阿嘟~ 我呀块茁,落地在蘇州,開花在南京 所以主推這兩個地方的...
    吃土少女嘟閱讀 665評論 0 7
  • 張愛玲曾說:“出名要趁早”桂肌。我覺得這句話在任何時候都是適用的数焊。 寒假過去大半了...
    陪伴是最好的安慰劑閱讀 288評論 2 2
  • 這時學(xué)校是地上的一顆星,這時我是學(xué)校里的一個人崎场。夕陽西下佩耳,放學(xué)了,我又是一個人了谭跨。我磨蹭著出了教室門干厚,外面竟是漆黑...
    騎著蝸牛賽跑閱讀 299評論 0 1