关于红黑树最大高度 2logn

来源：1-1 平衡树和AVL

weixin_慕圣6334738

2021-09-01 15:58:25

老师你好，我不太能理解红黑树什么时候会出现2logn的情况，2logn您在课里讲的是，每个黑节点都带一个红色的节点。但是如果什么情况会出现一直都是连续的黑色节点配红色节点呢？如果往一个2节点不停插入一个新的node，那更上面的2节点不就会产生新的两个节点吗，那应该无法保持连续2节点吧

写回答

1回答

liuyubobobo

2021-09-02

比如这页 PPT 中的 2-3 树：

转化成红黑树是这样的：

        37(B)
       /    \
     12(R)   42(B)
    /    \
  11(B)  18(B)
  /
6(R)

请注意，他是黑平衡的，黑平衡的高度是 2。但是实际高度是 4。

他有 6 个节点，log(6) 大概是 2.58，是 2 这个级别的，其高度是 4。

继续加油！：）

算法与数据结构

波波老师5年集大成之作，算法与数据结构系统学习，考试、面试、竞赛通用

2636 学习 · 1090 问题

相似问题

回答 1

回答 1

回答 1

回答 1

B+树

回答 1