数据结构-树-红黑树基本概念

红黑树是平衡二叉查找树的一种，所以在讲红黑树之前，我们要先了解下什么是平衡二叉查找树。首先我们知道什么是二叉查找树，二叉查找树在极端情况下，可能会变成链表，这个时候就需要平衡二叉查找树了。

什么是平衡二叉树

平衡二叉树的严格定义是任何一个节点，其左右子树的高度差不能大于1。从该定义上来说，满二叉树和完全二叉树都符合这个定义，所以满二叉树和完全二叉树都是平衡二叉树。非完全二叉树也有可能会是平衡二叉树如下图：

非完全二叉树的平衡二叉树

什么是平衡二叉查找树呢？

平衡二叉查找树就是同时满足平衡二叉树和二叉查找树的树。但是，很多平衡二叉查找树其实并没有严格满足上述条件，比如我们要说的红黑树，其左右子树的高度差就有可能大于1。很多人可能会说那还能叫平衡二叉查找树吗？平衡二叉查找树出来的初衷就是为了解决频繁插入、删除等更新行为导致的二叉查找树时间复杂度退化的情况，所以只要能满足左右子树相对平衡（树看起来相对对称），不会出现左边很高，右边很低（或相反）的情况就可以称为平衡了（换句话说只要满足频繁地插入或删除等更新动作不会导致复杂度退化即可）。
红黑树是平衡二叉查找树的一种，可能也是我们最常听到的一种，除了红黑树外，平衡二叉查找树还有诸如AVL树，Treap（树堆）等。

什么是红黑树？

红黑树简称R-B Tree（Red-Black Tree)，是一种不严格的平衡二叉树，其节点一部分会被标记为黑色，另一部分会被标记为红色，此外还需满足以下几点要求

1. 根节点为黑色
2. 叶子节点必须是黑色空节点，即叶子节点不存储数据
3. 父子节点之间不能同时为红色

4. 从任意节点出发，到达其可达的叶子节点的所有路径都包含相同的黑色节点数
   初次了解红黑树时，可能会对第二点产生疑惑，在了解红黑树概念的时候，不用太计较第二点，因为第二点是为了方便代码实现而设计的。可能单纯的文字还是会有疑惑，下面用图例来进行说明（为了理解方便，先抛开第二点）

   
   红黑树图例1
   红黑树图例2