在学习红黑树的时候我们需要知道一些关于树的基础知识，还有什么是二叉查找树。
在学习的时候我发现人的智慧真的是无穷的，能设计出这么优秀的算法，真的是超级厉害。
30张图带你彻底理解红黑树
java代码实现红黑树源码
二叉查找树
二叉查找树也叫做二叉搜索树，二叉排序树，二叉排序树主要是为了实现二分查找，让查找更加高效
二叉查找树特征
- 若它的左子树不为空，那么左子树所有节点的值都小于它的根节点的值
- 若它的右子树不为空，那么右子树上所有节点的值都大于它的根节点的值，相等的值左右子树均可
- 它的左右子树也分别是二叉查找树
平衡二叉查找树
别名AVL树，Balanced Binary Tree
要么它是一个空树，要么它的左子树和右子树都是平衡二叉树，并且左子树和右子树的深度之差的绝对值不超过1。
红黑树
红黑树也是二叉查找树，二叉查找树并不难，但是红黑树难的地方在于它是一个自平衡的二叉查找树，能够在破坏二叉树平衡的时候自己去找平衡通过左旋和右旋，这就是非常牛逼的，真的是非常牛逼。
红黑树是一个非完美平衡二叉树，是一个完美黑色平衡二叉树
红黑树的定义和性质
红黑树是一种含有红黑结点并能自平衡的二叉查找树,这里我插一嘴红黑只是为了区分的两个对立元素不是只能叫红黑，你叫黄黑也行。。
红黑树必须满足下面几个特性
- 每个节点要么是黑色要么是红色
- 根节点为黑色
- 每个叶子节点为黑色(null)是黑色的
- 每个红色节点的两个子节点都是黑色的。(就是说红色节点不能相互连接)
- 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。
红黑树不是完美平衡二叉树，可能出现左右子树的深度大于1的情况。但是从任意节点出发到叶子节点都有相同数量的黑色节点，称之为黑色完美平衡二叉树
红黑树各部分名称
为了后面的讲解不至于混淆，我们约定一下红黑树一些节点的叫法
我们把正在处理的节点叫做当前节点，把他的父亲叫做父节点，父亲的另一个孩子叫做兄弟节点，父亲的父亲叫做祖父节点
红黑树的基本操作
就是这些操作让红黑树能够变成一个自平衡的二叉查找树。
左旋
以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变。
右旋
以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变。
变色
结点的颜色由红变黑或由黑变红。
红黑树数据结构的定义
package RedBlackTree;
public class Node<T extends Comparable<T>, D> {
private RedBlackColor color;
private T key;
private D data;
private Node<T, D> parent;
private Node<T, D> leftChild;
private Node<T, D> rightChild;
public Node(RedBlackColor col, T key, D data, Node<T, D> parent, Node<T, D> leftChild, Node<T, D> rightChild) {
this.color = col;
this.key = key;
this.data = data;
this.parent = parent;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
public Node<T, D> GetParent() {
return this.parent;
}
public Node<T, D> GetLeftChild() {
return this.leftChild == null ? new Node<T, D>(RedBlackColor.BLACK,null,null,this,null,null) : this.leftChild;
}
public Node<T, D> GetRightChild() {
return this.rightChild == null ? new Node<T, D>(RedBlackColor.BLACK,null,null,this,null,null) : this.rightChild;
}
public T GetKey() {
return this.key;
}
public RedBlackColor GetColor() {
return this.color;
}
public D GetData()
{
return this.data;
}
public void setParent(Node<T,D> parent) {
this.parent = parent;
}
public void setColor(RedBlackColor color) {
this.color = color;
}
public void setLeftChild(Node<T, D> leftChild) {
this.leftChild = leftChild;
}
public void setRightChild(Node<T, D> rightChild) {
this.rightChild = rightChild;
}
public void setData(D data)
{
this.data = data;
}
}
|
这里的定义稍微有点复杂，大家想实现可以尽可能的少的去做，或者做成一个RedBlackTree类的内部类
红黑树的查询
红黑树的查询操作其实就是树的查找操作，只需要比较根节点大小递归或者非递归方式查询即可
public D GetData(T key)
{
Node<T,D> node = search(key,root);
return node == null ? null : node.GetData();
}
public Node<T,D> search(T key,Node<T,D> root)
{
if(root!=null)
{
int com = key.compareTo(root.GetKey());
if(com < 0) return search(key,root.GetLeftChild());
else if(com > 0) return search(key,root.GetRightChild());
else return root;
}
return null;
}
|
红黑树的左旋
红黑树左旋有这么几步
- 当前节点下移
- 当前节点的右孩子上移
- 当前节点的右孩子的左子树给当前节点
当前节点的父节点变成左孩子，右孩子取代当前节点的位置，当前节点的右子树变成右孩子的左子树。
public void leftRonate(Node<T,D> node)
{
Node<T,D> right = node.GetRightChild();
if(right.GetLeftChild() != null)
{
right.GetLeftChild().setParent(node);
}
node.setRightChild(right.GetLeftChild());
right.setLeftChild(node);
right.setParent(node.GetParent());
if(node.GetParent() !=null)
{
if(node.GetParent().GetLeftChild() == node) node.GetParent().setLeftChild(right);
else node.GetParent().setRightChild(right);
}
else
{
this.root = right;
}
node.setParent(right);
}
|
红黑树的右旋
右旋跟左旋类似，只不过是子树的切换和方向不同
- 当前节点下移，
- 当前节点的左孩子上移
- 当前节点的左孩子的右子树较给当前节点
public void Rightonate(Node<T,D> node)
{
Node<T,D> left = node.GetLeftChild();
if(left.GetRightChild()!=null)
{
left.GetRightChild().setParent(node);
}
node.setLeftChild(left.GetRightChild());
left.setRightChild(node);
left.setParent(node.GetParent());
if(node.GetParent()!=null)
{
if(node.GetParent().GetLeftChild() == node) node.GetParent().setLeftChild(left);
else node.GetParent().setRightChild(left);
}
else
{
this.root = left;
}
node.setParent(left);
}
|
红黑树的插入
红黑树的插入操作包括两部分：第一部分是查找插入的位置；第二部分是插入后的自平衡。查找插入的父节点很简单，跟查找操作区别不大
当插入的位置找好以后，把插入的节点放到正确的位置就可以了，插入的节点一律代表是红色，只有当插入的节点是红色才会触发自平衡保持红黑树的性质，其中插入的场景有很多，各自的场景有各自的一些处理方式
场景一：红黑树为空
把插入结点作为根结点，并把结点设置为黑色。
插入情景2：插入结点的Key已存在
插入结点的Key已存在，既然红黑树总保持平衡，在插入前红黑树已经是平衡的，那么把插入结点设置为将要替代结点的颜色，再把结点的值更新就完成插入。
- 把I设为当前结点的颜色
- 更新当前结点的值为插入结点的值
插入情景3：插入结点的父结点为黑结点
由于插入的结点是红色的，当插入结点的黑色时，并不会影响红黑树的平衡，直接插入即可，无需做自平衡。
插入情景4：插入结点的父结点为红结点
再次回想下红黑树的性质2：根结点是黑色。如果插入的父结点为红结点，那么该父结点不可能为根结点，所以插入结点总是存在祖父结点。这点很重要，因为后续的旋转操作肯定需要祖父结点的参与。
插入情景4.1：叔叔结点存在并且为红结点
从红黑树性质4可以，祖父结点肯定为黑结点，因为不可以同时存在两个相连的红结点。那么此时该插入子树的红黑层数的情况是：黑红红。显然最简单的处理方式是把其改为：红黑红。
- 将P和S设置为黑色
- 将PP设置为红色
- 把PP设置为当前插入结点
可以看到，我们把PP结点设为红色了，如果PP的父结点是黑色，那么无需再做任何处理；但如果PP的父结点是红色，根据性质4，此时红黑树已不平衡了，所以还需要把PP当作新的插入结点，继续做插入操作自平衡处理，直到平衡为止。
插入情景4.2：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的左子结点
单纯从插入前来看，也即不算情景4.1自底向上处理时的情况，叔叔结点非红即为叶子结点(Nil)。因为如果叔叔结点为黑结点，而父结点为红结点，那么叔叔结点所在的子树的黑色结点就比父结点所在子树的多了，这不满足红黑树的性质5。
插入情景4.2.1：插入结点是其父结点的左子结点
- 将P设为黑色
- 将PP设为红色
- 对PP进行右旋
插入情景4.2.2：插入结点是其父结点的右子结点
- 对P进行左旋
- 把P设置为插入结点，得到情景4.2.1
- 进行情景4.2.1的处理
插入情景4.3：叔叔结点不存在或为黑结点，并且插入结点的父亲结点是祖父结点的右子结点
情景对应情景4.2，只是方向反转.
插入情景4.3.1：插入结点是其父结点的右子结点
- 将P设为黑色
- 将PP设为红色
- 对PP进行左旋
插入情景4.3.2：插入结点是其父结点的右子结点
- 对P进行右旋
- 把P设置为插入结点，得到情景4.3.1
- 进行情景4.3.1的处理
好了，讲完插入的所有情景了。可能又同学会想：上面的情景举例的都是第一次插入而不包含自底向上处理的情况，那么上面所说的情景都适合自底向上的情况吗？答案是肯定的。理由很简单，但每棵子树都能自平衡，那么整棵树最终总是平衡的。
代码实现
public void balanceInsertion(Node<T,D> node)
{
Node<T,D> parent,gparent;
while (((parent = node.GetParent())!=null )&& parent.GetColor() == RedBlackColor.RED)
{
gparent = parent.GetParent();
if(gparent.GetLeftChild() == parent)
{
Node<T,D> uncle = gparent.GetRightChild();
if(uncle.GetColor() == RedBlackColor.RED)
{
gparent.setColor(RedBlackColor.RED);
uncle.setColor(RedBlackColor.BLACK);
parent.setColor(RedBlackColor.BLACK);
node = gparent;
continue;
}
else
{
if(parent.GetRightChild() == node)
{
leftRonate(parent);
Node<T,D> temp = node;
node = parent;
parent = temp;
}
parent.setColor(RedBlackColor.BLACK);
gparent.setColor(RedBlackColor.RED);
rightonate(gparent);
}
}
else
{
Node<T,D> uncle = gparent.GetLeftChild();
if(uncle.GetColor() == RedBlackColor.RED)
{
parent.setColor(RedBlackColor.BLACK);
uncle.setColor(RedBlackColor.BLACK);
gparent.setColor(RedBlackColor.RED);
node = gparent;
continue;
}
else
{
if(parent.GetLeftChild() == node)
{
rightonate(node);
Node<T,D> temp = node;
node = parent;
parent = temp;
}
parent.setColor(RedBlackColor.BLACK);
gparent.setColor(RedBlackColor.RED);
leftRonate(gparent);
}
}
}
if (root == node) {
node.setColor(RedBlackColor.BLACK);
}
}
public void insertNode(T key,D data)
{
int com;
Node<T,D> root = this.root;
Node<T,D> temp = null;
while (root!=null)
{
temp = root;
com = key.compareTo(root.GetKey());
if(com == 0)
{
root.setData(data);
return;
}
if(com < 0) root = root.GetLeftChild();
else root=root.GetRightChild();
}
Node<T,D> newNode = new Node<T, D>(RedBlackColor.BLACK,key,data,temp,null,null);
if(temp!=null)
{
com = newNode.GetKey().compareTo(temp.GetKey());
if(com<0) temp.setLeftChild(newNode);
else temp.setRightChild(newNode);
}
else
{
this.root = newNode;
return;
}
newNode.setColor(RedBlackColor.RED);
balanceInsertion(newNode);
}
|
红黑树的删除
红黑树插入已经够复杂了，但删除更复杂，也是红黑树最复杂的操作了。但稳住，胜利的曙光就在前面了！
红黑树的删除操作也包括两部分工作：一查找目标结点；而删除后自平衡。查找目标结点显然可以复用查找操作，当不存在目标结点时，忽略本次操作；当存在目标结点时，删除后就得做自平衡处理了。删除了结点后我们还需要找结点来替代删除结点的位置，不然子树跟父辈结点断开了，除非删除结点刚好没子结点，那么就不需要替代。
二叉树删除结点找替代结点有3种情情景：
- 情景1：若删除结点无子结点，直接删除
- 情景2：若删除结点只有一个子结点，用子结点替换删除结点
- 情景3：若删除结点有两个子结点，用后继结点（大于删除结点的最小结点）替换删除结点
补充说明下，情景3的后继结点是大于删除结点的最小结点，也是删除结点的右子树中最左结点。那么可以拿前继结点（删除结点的左子树最左结点）替代吗？可以的。但习惯上大多都是拿后继结点来替代，后文的讲解也是用后继结点来替代。另外告诉大家一种找前继和后继结点的直观的方法：把二叉树所有结点投射在X轴上，所有结点都是从左到右排好序的，所有目标结点的前后结点就是对应前继和后继结点。
讲一个重要的思路：删除结点被替代后，在不考虑结点的键值的情况下，对于树来说，可以认为删除的是替代结点！
基于此，上面所说的3种二叉树的删除情景可以相互转换并且最终都是转换为情景1！
- 情景2：删除结点用其唯一的子结点替换，子结点替换为删除结点后，可以认为删除的是子结点，若子结点又有两个子结点，那么相当于转换为情景3，一直自顶向下转换，总是能转换为情景1。（对于红黑树来说，根据性质5.1，只存在一个子结点的结点肯定在树末了）
- 情景3：删除结点用后继结点（肯定不存在左结点），如果后继结点有右子结点，那么相当于转换为情景2，否则转为为情景1。
- 综上所述，删除操作删除的结点可以看作删除替代结点，而替代结点最后总是在树末。有了这结论，我们讨论的删除红黑树的情景就少了很多，因为我们只考虑删除树末结点的情景了。
同样的，我们也是先来总体看下删除操作的所有情景
删除情景1：替换结点是红色结点
我们把替换结点换到了删除结点的位置时，由于替换结点时红色，删除也不会影响红黑树的平衡，只要把替换结点的颜色设为删除的结点的颜色即可重新平衡。
删除情景2：替换结点是黑结点
当替换结点是黑色时，我们就不得不进行自平衡处理了。我们必须还得考虑替换结点是其父结点的左子结点还是右子结点，来做不同的旋转操作，使树重新平衡。
删除情景2.1：替换结点是其父结点的左子结点
删除情景2.1.1：替换结点的兄弟结点是红结点
若兄弟结点是红结点，那么根据性质4，兄弟结点的父结点和子结点肯定为黑色，不会有其他子情景，我们按照以下进行处理，得到删除情景2.1.2.3（后续讲解，这里先记住，此时R仍然是替代结点，它的新的兄弟结点SL和兄弟结点的子结点都是黑色）。
- 将S设为黑色
- 将P设为红色
- 对P进行左旋，得到情景2.1.2.3
- 进行情景2.1.2.3的处理
删除情景2.1.2：替换结点的兄弟结点是黑结点
当兄弟结点为黑时，其父结点和子结点的具体颜色也无法确定（如果也不考虑自底向上的情况，子结点非红即为叶子结点Nil，Nil结点为黑结点），此时又得考虑多种子情景。
删除情景2.1.2.1：替换结点的兄弟结点的右子结点是红结点，左子结点任意颜色
即将删除的左子树的一个黑色结点，显然左子树的黑色结点少1了，然而右子树又又红色结点，那么我们直接向右子树“借”个红结点来补充黑结点就好啦，此时肯定需要用旋转处理了。
- 将S的颜色设为P的颜色
- 将P设为黑色
- 将SR设为黑色
- 对P进行左旋
替换结点的兄弟结点的右子结点为黑结点，左子结点为红结点
兄弟结点所在的子树有红结点，我们总是可以向兄弟子树借个红结点过来，显然该情景可以转换为情景2.1.2.1。
- 将S设为红色
- 将SL设为黑色
- 对S进行右旋，得到情景2.1.2.1
删除情景2.1.2.3：替换结点的兄弟结点的子结点都为黑结点
了，此次兄弟子树都没红结点“借”了，兄弟帮忙不了，找父母呗，这种情景我们把兄弟结点设为红色，再把父结点当作替代结点，自底向上处理，去找父结点的兄弟结点去“借”。但为什么需要把兄弟结点设为红色呢？显然是为了在P所在的子树中保证平衡（R即将删除，少了一个黑色结点，子树也需要少一个），后续的平衡工作交给父辈们考虑了，还是那句，当每棵子树都保持平衡时，最终整棵总是平衡的。
- 将S设为红色
- 把P作为新的替换结点
- 重新进行删除结点情景处理
删除情景2.2：替换结点是其父结点的右子结点
删除情景2.2.1：替换结点的兄弟结点是红结点
- 将S设为黑色
- 将P设为红色
- 对P进行右旋，得到情景2.2.2.3
- 进行情景2.2.2.3的处理
删除情景2.2.2：替换结点的兄弟结点是黑结点
删除情景2.2.2.1：替换结点的兄弟结点的左子结点是红结点，右子结点任意颜色
- 将S的颜色设为P的颜色
- 将P设为黑色
- 将SL设为黑色
- 对P进行右旋
删除情景2.2.2.2：替换结点的兄弟结点的左子结点为黑结点，右子结点为红结点
- 将S设为红色
- 将SR设为黑色
- 对S进行左旋，得到情景2.2.2.1
- 进行情景2.2.2.1的处理
删除情景2.2.2.3：替换结点的兄弟结点的子结点都为黑结点
- 将S设为红色
- 把P作为新的替换结点
- 重新进行删除结点情景处理
综上，红黑树删除后自平衡的处理可以总结为：
1、自己能搞定的自消化（情景1）
2、自己不能搞定的叫兄弟帮忙
3、兄弟都帮忙不了的，通过父母，找远方亲戚
代码实现
public Node<T,D> min(Node<T,D> node)
{
if(node.GetLeftChild()==null)
{
return node;
}
while (node.GetLeftChild()!=null)
{
node = node.GetLeftChild();
}
return node;
}
public Node<T,D> FindDeleteNodeReplace(Node<T,D> node)
{
if(node.GetRightChild()!=null)
{
return min(node.GetRightChild());
}
Node<T, D> y = node.GetParent();
while ((y != null) && (y.GetRightChild() == node)) {
node = y;
y = y.GetParent();
}
return y;
}
public void delete(Node<T,D> node)
{
Node<T,D> child,parent,replace;
RedBlackColor color = RedBlackColor.BLACK;
if(node.GetLeftChild()!=null && node.GetRightChild()!=null)
{
replace = FindDeleteNodeReplace(node);
parent = replace.GetParent();
child = replace.GetRightChild();
color = replace.GetColor();
if(node == replace.GetParent())
{
parent = replace;
}
else
{
if(child!=null)
{
child.setParent(replace.GetParent());
}
replace.GetParent().setLeftChild(child);
replace.setRightChild(node.GetRightChild());
node.GetRightChild().setParent(replace);
}
replace.setParent(node.GetParent());
replace.setLeftChild(node.GetLeftChild());
node.GetLeftChild().setParent(replace);
replace.setColor(node.GetColor());
if(node.GetParent()!=null)
{
if(node.GetParent().GetLeftChild()==node)
{
node.GetParent().setLeftChild(replace);
}
else node.GetParent().setRightChild(replace);
}
else {
this.root = replace;
}
if (color == RedBlackColor.BLACK) {
balanceDeletion(child, parent);
}
}
else
{
if(node.GetLeftChild() !=null)
{
replace = node.GetLeftChild();
}
else
{
replace = node.GetRightChild();
}
parent = node.GetParent();
if(parent!=null)
{
if(parent.GetLeftChild()==node)
{
parent.setLeftChild(replace);
}
else
{
parent.setRightChild(replace);
}
}
else
{
this.root = replace;
}
replace.setParent(parent);
color = node.GetColor();
if(color == RedBlackColor.BLACK)
{
balanceDeletion(replace,parent);
}
}
}
public void balanceDeletion(Node<T,D> node,Node<T,D> parent)
{
Node<T,D> other;
while (node.GetColor() == RedBlackColor.BLACK && node!=this.root)
{
if(parent.GetLeftChild() == node)
{
other = parent.GetRightChild();
if(other.GetColor()==RedBlackColor.RED)
{
parent.setColor(RedBlackColor.RED);
other.setColor(RedBlackColor.BLACK);
leftRonate(parent);
continue;
}
else
{
if(other.GetLeftChild().GetColor()==RedBlackColor.BLACK && other.GetRightChild().GetColor()==RedBlackColor.BLACK)
{
other.setColor(RedBlackColor.RED);
node = parent;
parent = node.GetParent();
}
else if(other.GetLeftChild().GetColor() == RedBlackColor.RED && other.GetRightChild().GetColor() ==RedBlackColor.BLACK)
{
other.setColor(RedBlackColor.RED);
other.GetLeftChild().setColor(RedBlackColor.BLACK);
rightonate(other);
}
else if(other.GetRightChild().GetColor() == RedBlackColor.RED)
{
other.setColor(parent.GetColor());
parent.setColor(RedBlackColor.BLACK);
other.GetRightChild().setColor(RedBlackColor.BLACK);
leftRonate(parent);
break;
}
}
}else
{
other = parent.GetLeftChild();
if(other.GetColor() == RedBlackColor.RED)
{
other.setColor(RedBlackColor.BLACK);
parent.setColor(RedBlackColor.RED);
rightonate(parent);
continue;
}
else
{
if(other.GetLeftChild().GetColor() == RedBlackColor.BLACK && other.GetRightChild().GetColor()==RedBlackColor.BLACK)
{
other.setColor(RedBlackColor.RED);
node = parent;
parent = node.GetParent();
}
else if(other.GetLeftChild().GetColor() == RedBlackColor.BLACK && other.GetRightChild().GetColor()==RedBlackColor.RED)
{
parent.setColor(RedBlackColor.RED);
other.GetRightChild().setColor(RedBlackColor.BLACK);
leftRonate(other);
}
else if(other.GetLeftChild().GetColor() == RedBlackColor.RED)
{
other.setColor(parent.GetColor());
parent.setColor(RedBlackColor.BLACK);
other.GetLeftChild().setColor(RedBlackColor.BLACK);
rightonate(parent);
break;
}
}
}
}
node.setColor(RedBlackColor.BLACK);
}
|
全部代码
java实现红黑树
