知识卡片
红黑树用颜色约束保持近似平衡
红黑树维持二叉查找树次序,并约束节点红黑颜色、黑色根与空叶、红节点不得有红子节点,以及每个节点到后代空叶路径上的黑节点数相同。由此树高为 O(log n),正确维护后的查找、插入、删除可达到 O(log n)。
AVL树要求每个节点左右子树高度差的绝对值不超过1,并非书中所述任意不同节点的子树高度相差不超过1。遍历可用递归或显式栈,父指针有助于某些后继操作但不是必要条件。
138称根节点必须为空,这是错误表述:非空红黑树的根是实际节点且按常规定义为黑色;空孩子可用共享黑色哨兵表示。颜色和父指针具体存储依实现而定,父指针并非理论必需。
139概括 O(log n) 操作:前提是正确实现并维持红黑性质;普通不平衡二叉查找树的最坏复杂度仍是 O(n)。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 红黑树用颜色约束保持近似平衡
- · 结论
- · 分析
原书出处 · 3 处
- · 查看原书依据
红黑树。红黑树是一个近似平衡的。使用红黑树能够保证任何一个分支的长度都不会超过其他的分支长度的两倍。一个红黑树满足如下条件(Cormen等,2001): ·每一个节点被标记为红色或者黑色。 ·根节点是黑色的。 ·每一个叶子节点值为空,并且是黑色的。 ·所有的红色节点都有两个黑色子节点。 ·从一个节点
- · 查看原书依据
存储方面的需求。 ·每一个节点需要存储其颜色,至少需要一个bit,但是事实上大多数实现都使用了至少一个字节。 ·每一个节点都必须有一个父节点的链接,这个在二叉查找树中是不需要的。 红黑树的根节点必须是空值的。程序员能够让所有的叶子节点的指针都指向这个单个空值节点。
- · 查看原书依据
插入和删除操作也能够在O(log n)时间内完成。
参考来源
- 位置:《算法技术手册》第5章《驱动因素》(spine1555;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1518.html;u136-ch05-012)。
- 结论依据:136全文和03269红黑树示例实读。
- 原始内容:红黑树。红黑树是一个近似平衡的。使用红黑树能够保证任何一个分支的长度都不会超过其他的分支长度的两倍。一个红黑树满足如下条件(Cormen等,2001): ·每一个节点被标记为红色或者黑色。 ·根节点是黑色的。 ·每一个叶子节点值为空,并且是黑色的。 ·所有的红色节点都有两个黑色子节点。 ·从一个节点
- 位置:《算法技术手册》第5章《结论》(spine1557;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1520.html;u138-ch05-012)。
- 结论依据:138称根节点必须为空,这是错误表述:非空红黑树的根是实际节点且按常规定义为黑色;空孩子可用共享黑色哨兵表示。颜色和父指针具体存储依实现而定,父指针并非理论必需。
- 原始内容:存储方面的需求。 ·每一个节点需要存储其颜色,至少需要一个bit,但是事实上大多数实现都使用了至少一个字节。 ·每一个节点都必须有一个父节点的链接,这个在二叉查找树中是不需要的。 红黑树的根节点必须是空值的。程序员能够让所有的叶子节点的指针都指向这个单个空值节点。
- 位置:《算法技术手册》第5章《分析》(spine1558;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1521.html;u139-ch05-012)。
- 结论依据:139概括 O(log n) 操作:前提是正确实现并维持红黑性质;普通不平衡二叉查找树的最坏复杂度仍是 O(n)。
- 原始内容:插入和删除操作也能够在O(log n)时间内完成。