設為首頁 - 加入收藏
廣告 1000x90
您的當前位置:主頁 > 資源代碼 > 技術文章 > 正文

從節點到葉子節點的路徑包含相同數目的黑色節點偉仔玲姐戀

來源: 伯樂在線 編輯:小編 時間:2019-05-27 14:02
從節點到葉子節點的路徑包含相同數目的黑色節點偉仔玲姐戀

            brother=parent.right

紅黑樹基礎知識 定義

紅黑樹是帶有 color 屬性的二叉搜索樹,color 的值為紅色或黑色,因此叫做紅黑樹。

23

        walk_node.left.parent=walk_node

            node=root

            walk_node.right.parent=walk_node

如果真的要問我紅黑樹有什麼用?為什麼要學它?我真的回答不上,但是我覺得,基礎的東西,多學一些也無妨。隻有學了,有個思路在腦海裡,以後才能用得上,不然等真正要用才來學的話,似乎會浪費了很多學習成本。

    whileIS_RED(node)

    elseif(node.key<walk.key)

        ifbrother.left.color==BLACK andbrother.right.color==BLACK

注意:該假設隻是加在 new_successor 的結點上,而不是該結點的顔色屬性。

5

18

     structRBNode *right;

15

6

        T.root=node

紅黑樹的性質

每個節點不是紅色就是黑色;

        elsewalk=walk.right

        ifIS_RED(brother)

對于 a,從上面可知,查找的算法複雜度是 O(lgn)。

22

        elseifbrother.right.color=BLACK

紅黑樹的插入操作分析

紅黑樹的插入操作,先找到要新節點插入的位置,将節點賦予紅色,然後插入新節點。最後做紅黑樹性質的修複。

7

6

    ifnode=parent.left

                uncle.color=BLACK

如果 uncle 是紅色,那麼直接将 uncle 變為黑色,同時 parent 也變黑。但是這樣一來,以 grandparent 為根所在的子樹的黑高就 +1,因此将 grandparent 變紅使其黑高減一,然後将 node 指向 grandparent,讓修複結點上升兩個 level,直到遇到根結點為止。

證明如下:

        grandparent=parent->parent

而前者,違反了性質 4 的,即紅黑樹出現了連續兩個紅結點的情況。修複的變化還要看父結點是祖父結點的左孩子還是右孩子,左右兩種情況是對稱的,此處看父結點是祖父結點的左孩子的情況。要恢複紅黑樹的性質,那麼就需要将 parent 的其中一個變黑,這樣的話,該結點所在的子樹的黑高 +1,這樣就會破壞了性質 5,違背了初衷。因此需要将 parent->parent(grandparent)的另一個結點(uncle 結點)的黑高也 +1 來維持紅黑樹的性質。

RB-DELETE(T,node)

删除過程中需要保存 successor 的顔色 color,因為删除操作可能會導緻紅黑樹的性質被破壞,而删除操作删除的是 successor。因此,每一次改變 successor 的時候,都要更新 color。

                node=grandparent

8

            brother.right.color=BLACK

每個葉子節點是黑色;

對每個節點來說,從節點到葉子節點的路徑包含相同數目的黑色節點。

    color=node.color

17

1

12

        walk_node.color=node.color

22

插入的算法複雜度分析

插入的步驟主要有兩步

=>  h<=2log(n+1)

        prev=walk

        walk_node.left=node.left

    while(walk!=NULL)

17

旋轉的算法複雜度:從圖示可知,旋轉的操作隻是做了修改指針的操作,因此算法複雜度是 O(1)。

        color=walk_node.color

可得 n + 1 >= 2^h/2。兩邊取對數得:

設根結點的 parent 指針指向 NULL,新結點的左右孩子 left 和 right 指向 NULL。葉子結點是 NULL。

25

設 h 是樹高,根據性質 4 可知道,每一條路徑至少有一半的節點是黑的,因此 bh(x) - 1 = h/2。

1

注:筆者參考的是算法導論的僞代碼,但是在實現的時候,因為用 NULL 表示空結點,如果需要修複的結點 need_fixup_node為空時無法拿到其父結點,因此保存了其父結點 need_fixup_node_parent 及其所在方向 direction,為删除修複時訪問其父結點及其方向時做調整。

4

9

7

        brother=parent.right

        transplant(T,node,walk_node)

如果直接将額外黑上移給父結點,那麼以 new_successor 的父結點為根的子樹就會失去平衡,因為左子樹的黑高 -1 了。因此需要根據 new_successor 的兄弟結點 brother 的顔色來考慮調整。

如果 successor 不是 node 的右孩子,而因為 node 的後繼是沒有左孩子的(這個可以查看相關證明),所以删除掉 node 的後繼 successor 之後,需要将 successor 的右孩子 successor.right 補上 successor 的位置。

13

紅黑樹的删除操作分析

紅黑樹的删除操作,先找到要删除的結點,然後找到要删除結點的後繼,用其後繼替換要删除的結點的位置,最後再做紅黑樹性質的修複。

21

2

node.color=BLACK

19


    本文網址:http://juhua666833.cn/a/ziyuan/jishuwenzhang/9276.html ,喜歡請注明來源。

網友評論:

發表評論
請自覺遵守互聯網相關的政策法規,嚴禁發布色情、暴力、反動的言論。
評價:
表情:
用戶名: 驗證碼:點擊我更換圖片
從節點到葉子節點的路徑包含相同數目的黑色節點偉仔玲姐戀

站長沙龍 juhua666833.cn 中國百萬站長的福音,一站式服務。網站地圖

Copyright © 2002-2019 站長沙龍 客服qq:

Top