1.平衡二叉树

1.1平衡二叉树的定义

平衡二叉树，又叫平衡二叉搜索树，首先是一种特殊的二叉查找树，树的每个结点的左子树和右子树的高度差至多等于1

令F(n)表示n层平衡二叉树的最少节点，则F(n)=F(n-1)+F(n-2)+1
这是个类似斐波那契的递推数列

1.2为什么需要平衡二叉树

对一棵查找树进行增删查等动作，时间消耗与树的高度h成比例，并不与树的容量n成比例。为了便利我们的增删查工作，需要让树维持矮矮胖胖的好身材，也就是让h维持在O(lgn)左右。而平衡树，正是维持矮胖身材的优质树种

对于一棵普通的二叉查找树，插入新结点总可以在叶子结点进行，删除结点也可以使用被删除结点的逻辑后继结点直接替代被删除结点。因此，普通二叉查找树的增删非常容易，但需要承受的代价是操作后的二叉查找树结构不可控，不能总是维持矮胖的身材

因此，我们需要自平衡的二叉树，在插入和删除的时候，通过旋转操作将高度保持在logN
两款具有代表性的平衡树分别为AVL树和红黑树

2.红黑树（RBTree）

2.1红黑树定义 --- 头尾黑，不连红，路等黑

• 1.结点不是红色就是黑色
• 2.头尾黑。根是黑的，空结点也是黑的
• 3.不连红。不存在两个连续的红结点
• 4.路等黑。任一结点到每个叶子结点的路径含有的黑色结点数量相同。这是对树的高度进行约束，保证树能够满足平衡状态

不连红+路等黑 是红黑树在增删后调整树结构的2大准则

根据这两大准则，一棵红黑树不可能以下面的单支形式为枝末

红黑树不可能的树枝枝末
红黑树可能的树枝枝末只有2种，【单支黑-红】或者【拥有同色双孩子的倒V形结构】

红黑树的结点结构体如下：

# 红黑树结点结构体 
class  Node<T>{
   public  T value;  # 值
   public  Node<T> parent; # 父节点
   public  Node<T> left; # 左孩子
   public  Node<T> right; # 右孩子
   public  boolean isRed; # 颜色标记
}
相比普通的二叉树结点结构，红黑树的结点结构多了**父节点**和**颜色标记**

2.2二叉树的旋转

旋转包括左旋和右旋

左旋
左旋，指一棵树的根节点被其右孩子旋转取代，旋转后，原右孩子的左支将挂载到原根结点的右支，这通过大小关系很容易理解 右旋
右旋，指一棵树的根节点被其左孩子旋转取代，旋转后，原左孩子的右支将挂载到原根结点的左支

旋转可以改变二叉树的结构，使其由不平衡转为平衡

2.3红黑树的插入

• RBTree的插入与普通的平衡二叉树的插入方式一致，都在叶子结点进行插入
• 由于红黑树路等黑的特性，在对红黑树进行插入操作时，插入的结点必为红色
• 当且仅当插入结点的父结点为红色时，由于出现连红，需要对树进行旋转操作和颜色修复。显然，如果插入结点的父节点为黑色，那么不会对红黑树的任何性质造成破坏，无需修复

总结起来就是

【在合适的叶子插入红色结点，与父连红则进行插入修复。修复的目的是将父结点变成黑色，通过直接的颜色变换或者旋转后再颜色变换实现】

当插入结点的父结点是红色时，其叔叔结点要么是红色，要么为空，不可能是黑色，否则若为黑色，将违反路等黑规则；同时，其祖父结点必为红色，否则违反不连红规则

case1：插入结点的叔叔结点也是红色

这种情况下，插入结点的父结点和叔叔结点都是红色，根据不连红规则，其祖父结点必为黑色。那么将祖父结点涂红，父结点和叔叔结点涂黑即可（也就是交换颜色）。如果祖父结点涂红后产生连红，继续修正

case2：插入结点的叔叔结点为空，且祖父节点、父节点和新节点在一条直线上
旋转父结点 + 父结点与祖父结点交换颜色

红黑树插入case2

case3：插入结点的叔叔结点为空，且祖父节点、父节点和新节点不在一条直线上
先旋转新结点，将祖父节点、父节点和新节点调整在一条直线上，即转化为case2，然后按case2方法处理

红黑树插入case3

2.4红黑树的删除

红黑树的删除和上面提到的平衡二叉树的删除一样，叶子结点直接删除，中间结点使用其逻辑后继结点替代。如果删除的是红结点，无需调整；如果删除的是黑结点，则会影响路等黑的规则，需要调整

---

我认为，删除操作的思想这样比较好理解，也应该是这样的：

结点node被删除，实际上是【node的值变为其逻辑后继结点的值，然后逻辑后继结点被真正删除】。当后继结点被删除之后，势必破坏原来的“平衡”，真正被删除结点所在的一支会“变轻”，要重新实现平衡，就要向“轻的”这一支旋转，即向真正被删除结点一侧旋转。旋转后再调色满足要求即可

同理，插入操作的本质思想也是类似的：

插入一个结点，势必增重一侧，要向“轻的”一侧旋转。旋转后再调色

---

2.5红黑树的增删

红黑树只能增加红结点，并需要【避免连红】

红黑树可以删除任何结点，只在删除黑结点时，需要保持【路等黑】