紅黑樹(shù)

為什么產(chǎn)生紅黑樹(shù)

  • 動(dòng)態(tài)規(guī)模比平衡二叉樹(shù)（AVL）??；（動(dòng)態(tài)規(guī)模指：對(duì)二叉樹(shù)進(jìn)行查找后進(jìn)行修改或刪除操作等）；
  • 因?yàn)锳VL對(duì)平衡度要求嚴(yán)格，導(dǎo)致動(dòng)態(tài)查找規(guī)模很大，而紅黑樹(shù)在動(dòng)態(tài)規(guī)模小的情況下也可以達(dá)到相對(duì)平衡；
  • 靜態(tài)查找（只查找不操作）相對(duì)比ACL要慢；
  • 一種特殊的二叉排序樹(shù)；

特性

  1. 每個(gè)結(jié)點(diǎn)要么紅色要么黑色；
  2. 根結(jié)點(diǎn)是黑色；
  3. 每個(gè)葉子結(jié)點(diǎn)都是 黑色；
  4. 紅色結(jié)點(diǎn)其孩子是黑色；
    4.1 不會(huì)出現(xiàn)連續(xù)紅色結(jié)點(diǎn)；
    4.2 紅色結(jié)點(diǎn)的父與子都是黑色；
  5. 從任意一個(gè)結(jié)點(diǎn)到葉子結(jié)點(diǎn)的簡(jiǎn)單路徑中黑色結(jié)點(diǎn)數(shù)量相同（黑高度）；
  6. 最長(zhǎng)簡(jiǎn)單路徑 / 最短簡(jiǎn)單路徑 < 2;

<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/red_black.png" width="558" />

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 數(shù)據(jù)結(jié)構(gòu)與算法--從平衡二叉樹(shù)(AVL)到紅黑樹(shù) 上節(jié)學(xué)習(xí)了二叉查找樹(shù)。算法的性能取決于樹(shù)的形狀，而樹(shù)的形狀取決于...
    sunhaiyu閱讀 7,801評(píng)論 4贊 32
  • 一. 算法之變，結(jié)構(gòu)為宗 計(jì)算機(jī)在很多情況下被應(yīng)用于檢索數(shù)據(jù)，比如航空和鐵路運(yùn)輸業(yè)的航班信息和列車(chē)時(shí)刻表的查詢，都...
    Leesper閱讀 7,370評(píng)論 13贊 42
  • 二叉搜索樹(shù)，平衡樹(shù)，B，b-，b+,b*,紅黑樹(shù) 二叉搜索樹(shù) ? 1.所有非葉子結(jié)點(diǎn)至多擁有兩個(gè)兒子（Le...
    raincoffee閱讀 4,114評(píng)論 3贊 18
  • 最近花了些時(shí)間重拾數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)知識(shí)，先嘗試了紅黑樹(shù)，花了大半個(gè)月的時(shí)間研究其原理和實(shí)現(xiàn)，下面是學(xué)習(xí)到的知識(shí)和一些...
    hoohack閱讀 1,588評(píng)論 8贊 30
  • 樹(shù)(tree)的基本知識(shí) 一.定義 樹(shù)是一種抽象數(shù)據(jù)類(lèi)型，或是實(shí)作這種抽象數(shù)據(jù)類(lèi)型的數(shù)據(jù)結(jié)構(gòu)，用來(lái)模擬具有樹(shù)狀結(jié)構(gòu)...
    337b94dc718f閱讀 7,563評(píng)論 3贊 42

友情鏈接更多精彩內(nèi)容