红黑数R-B Tree
一. 知识储备
1.1 满二叉树、完全二叉树、平衡二叉树
满二叉树：除了叶子节点，每个节点都有左右子节点。如下：
**完全二叉树：最下面的两层节点数小于2。且最下一层的节点都集中在该层最左边的若干位置。**如下：
由上面可知，满二叉树从右边删去节点，可以得到完全二叉树。所以满二叉树是完全二叉树。反过来则不成立。
平衡二叉树：是一个二叉查找树，且左右子树的高度差不大于1。有一个平衡因子，用来衡量高度差（左子树的深度-右子树的深度），所以平衡因子只能有-1，0，1的值。
1.2 红黑树
特点：
(1) 每个节点或者是黑色，或者是红色。
(2) 根节点是黑色。
(3) 每个叶子节点是黑色。 [注意：这里叶子节点，是指为空的叶子节点！]
(4) 如果一个节点是红色的，则它的子节点必须是黑色的。
(5) 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。