国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質的職業教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 紅黑樹與普通的平衡二叉樹除了顏色到底有什么區別?

紅黑樹與普通的平衡二叉樹除了顏色到底有什么區別?

來源:千鋒教育
發布人:xqq
時間: 2023-10-11 03:56:58 1696967818

一、紅黑樹與普通的平衡二叉樹的區別

1、平衡二叉樹通過保持任一節點左、右子樹高度差的絕對值不超過1來維持二叉樹的平衡;而紅黑樹是根據查找路徑上黑色節點的個數以及紅、黑節點之間的聯系來維持二叉樹的平衡。

2、平衡二叉樹在插入或者刪除節點時為了保證左右子樹的高度差會進行旋轉,這一個旋轉根據數據的不同旋轉的復雜度也會不一樣,所以在插入或者刪除平衡二叉樹的節點時,旋轉的次數不可知,這也導致在頻繁的插入、修改中造成的效率問題;紅黑樹在執行插入修改的操作時會發生旋轉與變色(紅變黑,或者黑變紅)以確保沒有一條路徑會比其它路徑長出兩倍。

3、總體來說,在插入或者刪除節點時,紅黑樹旋轉的次數比平衡二叉樹少,因此在插入與刪除操作比較頻繁的情況下,選用紅黑樹。

什么樣的數據結構稱為紅黑樹

紅黑樹(Red Black Tree)是一種自平衡的二叉查找樹,它與平衡二叉樹相同的地方在于都是為了維護查找樹的平衡而構建的數據結構,它的主要特征是在二叉查找樹的每個節點上添加了一個屬性表示顏色,顏色有兩種,紅與黑。

性質:

每個節點是紅色或者黑色;

根節點是黑色;

所有葉子節點都是黑色(葉子是NIL節點,也稱為外節點);

每個紅色節點的子節點都是黑色(從每個葉子節點到根節點的所有路徑上不能有兩個連續的紅色節點);

從紅黑樹的任一節點到其每個葉子節點的所有路徑都包含相同數目的黑色節點(包含黑色節點的數目稱為該節點的黑高度)。

延伸閱讀:

二、什么是平衡二叉樹

平衡二叉樹(Balanced Binary Tree)的定義是這樣的——空樹,或者任一節點左、右子樹高度差的絕對值不超過1,稱為平衡二叉樹。

比如,我們將1,2,3,4,5,6,7,8這幾個節點以5,3,1,4,2,7,6,8的順序插入構造查找二叉樹,這棵樹就是一個平衡二叉樹,它的根節點高度為3,平均查找長度為(1*1+ 2*2 + 4*3 + 1*4)/8 = 2.625,,并且它的任一節點左、右子樹高度差的絕對值不超過1。而如果按照6,4,3,5,2,1,7,8的順序插入構造查找二叉樹,這棵樹也不能稱為平衡二叉樹,因為它的根節點的左子樹高度為4,而右子樹的高度為2,相差大于1;而對于4這一個節點,它的左子樹高度為3,右子樹的高度為1,相差也大于1。而這棵樹的平均查找長度為(1*1 + 2*2 + 3*3 + 4*1 + 5*1)/ 8 = 2.875(這里數據量較小,看不出與平衡二叉樹的明顯差別)。

聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT