红黑树的定义
之所以这么久才新开红黑树, 是因为我觉得红黑树是真的太难了, 要说清楚与实现都不是容易的事情, 我主要参考了一些博客, 传送门.
实际上我的大部分理解都是来自这一篇博客, 我添加了一些自己的理解以及实现方式.
红黑树是在二叉搜索树的基础上, 添加了对二叉搜索的限制, 每次新增或者删除节点时需要维护树的结构, 红黑树有以下性质:
- 节点为红色或黑色
- NIL 节点(空叶子节点)为黑色, 所有的叶子节点均为空叶子节点.
- 红色节点的子节点为黑色
- 从根节点到 NIL 节点的每条路径上的黑色节点数量相同
下图是一颗合法的红黑树:
