红黑树笔记

作者: 疯狂小兵 | 2017-04-01 | 阅读
「编辑」 「本文源码」

红黑树的特性:

  1. 每个节点或者是黑色,或者是红色。
  2. 根节点是黑色。
  3. 每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
  4. 如果一个节点是红色的,则它的子节点必须是黑色的。
  5. 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

注意:

  1. 特性(3)中的叶子节点,是只为空(NIL或null)的节点。
  2. 特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。

版权声明:本文由 在 2017年04月01日发表。本文采用CC BY-NC-SA 4.0许可协议,非商业转载请注明出处,不得用于商业目的。
文章题目及链接:《红黑树笔记》




  相关文章:

「游客及非Github用户留言」:

「Github登录用户留言」:

TOP