紅黑樹(shù)

（1）每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。
（2）根節(jié)點(diǎn)是黑色。
（3）每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。?[注意：這里葉子節(jié)點(diǎn)，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)！]
（4）如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
（5）從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。

1、紅黑樹(shù)放棄了追求完全平衡，追求大致平衡，在與平衡二叉樹(shù)的時(shí)間復(fù)雜度相差不大的情況下，保證每次插入最多只需要三次旋轉(zhuǎn)就能達(dá)到平衡，實(shí)現(xiàn)起來(lái)也更為簡(jiǎn)單。
2、平衡二叉樹(shù)追求絕對(duì)平衡，條件比較苛刻，實(shí)現(xiàn)起來(lái)比較麻煩，每次插入新節(jié)點(diǎn)之后需要旋轉(zhuǎn)的次數(shù)不能預(yù)知

總結(jié)

以上是生活随笔為你收集整理的红黑树相关概念的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。