紅黑樹：創(chuàng)建平衡二叉樹的成本不小

紅黑樹的定義：

每個(gè)數(shù)的節(jié)點(diǎn)不是紅色就是黑色 根節(jié)點(diǎn)是黑色 每個(gè)葉子節(jié)點(diǎn)（空節(jié)點(diǎn)）是黑色的 如果一個(gè)節(jié)點(diǎn)是紅色的，那么它的子節(jié)點(diǎn)一定是黑色的 一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑色節(jié)點(diǎn) 確保沒有一條路徑會比其他路徑長兩倍，最相對接近平衡的二叉樹

---

紅黑樹的生成

2-3-4樹變化過來的（4階B樹）

下面一個(gè)2-3-4樹

?

?轉(zhuǎn)化成紅黑樹

?

?

總結(jié)

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

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