二叉搜索树的规则: 非空二叉树的左子树的所有节点均小于根节点,若右子树不为空,右子树的所有节点均大于根节点
红黑树,除了符合二叉搜索树的基本规则外,还添加以下特性:
1:节点是红色或黑色
2:根节点是黑色的
3:每个叶子节点都是黑色的空节点(NIL节点)
4:每个红色节点的链各子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5:从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
原文:https://www.cnblogs.com/CoderZX/p/11699591.html