Red Black Tree

发表于 更新于 分类于
介绍红黑树的概念，及常用使用场景。

红黑树的定义

红黑树是一种自平衡二进制搜索树。每个节点存储一个代表颜色的标记位，用于在数的插入和删除期间保持数的近似平衡。红黑树是一个特殊的二叉树，用于组织可以进行比较的数据元素。

红黑树的特点

  1. 每个节点都必须是红色或者黑色；
  2. 跟节点是黑色。这条规则有时会被忽略，因为跟节点始终可以从红色变为黑色，但反过来就不一定成立。该规则对数据分析影响很小；
  3. 所有叶子节点（包括空节点）都是黑色；
  4. 红色节点的子节点都是黑色；
  5. 从给定节点到其任何后代NIL节点的每条路径都经过相同数量的黑色节点；

参考链接：