关于红黑二叉树的理解

最近看了些关于红黑二叉树的博客，有一些自己的见解。

红黑二叉树是一种特殊的平衡二叉树，拥有平衡二叉树的所有特征，这里就不再重复。

红黑二叉树的规则：

1、每个节点都必须有叶子节点（叶子节点没有任何数据）；

2、根节点和叶子节点必须是黑色；

3，红节点的父节点必须是黑色；

4、从根节点到任何叶子节点，他们的黑色节点的数目必须相同；

规则解释：

每个节点，不管有没有子节点，都必须有两个叶子节点，如果有子节点，则替换掉相应的叶子节点。

2/3/4点：由于任何分支到根节点的黑色节点数目必须相同，这就保证了各个分支之间长度相差<=1，这就是平衡二叉树的要求。

如果有插入操作，那么为了保证分支黑色节点数目相同，插入的数据一定是红节点，但是插入的节点的父节点却不一定是黑色节点，这个问题下面讨论。

红黑二叉树的操作：

左旋、右旋、重新着色。

左旋、右旋：当子二叉树不平衡时，如果左边的分支比右边的长，就进行右旋。顾名思义，向右旋转，具体操作是，让子根节点a的左子节点b成为子根节点，然后b的右子节点成为a的左子节点，这样就达到的右旋，左旋与右旋相似。

重新着色：左旋、右旋操作后要进行重新着色，从根节点开始着色，按照黑红黑的顺序着色，（如果存在末端节点一边有子节点，一边是叶子节点，则这个节点一定是黑色；如果所有末端节点都没有子节点，则这一级节点全都是黑色，不需要遵循红黑顺序）着色完成后，计算各个分支的黑色节点数目，如果数目相同，则二叉树平衡；否则对不平衡的子二叉树进行左旋、右旋操作，直到二叉树平衡。

增加：增加的节点一定是红色，以保持黑色节点数目相同。增加节点的父节点如果红色，代表这个子二叉树不平衡，按需要左旋或右旋，操作完成后重新着色，计算黑色节点数目，如不平衡，再调整。