红黑树

红黑树

定义：
红黑树是一颗平衡二叉搜索树，而且必须有以下规则：

1. 每个节点不是红色就是黑色；
2. 根结点为黑色；
3. 如果节点为红，其子节点必须为黑；
4. 任一节点至NULL的任何路径，所含黑节点数必须相同。

所以：

• 根据规则4，新增节点必须为红；
• 根据规则3，新增节点之父节点必须为黑。