前提：

在学习红黑树之前，先要理解一下平衡二叉树（AVL）和二叉搜索树（BST）。因为这三个存在一定的关系。学习AVL和BST可以更好地理解红黑树（BRT）.

BST（二叉搜索树）

规定：

1、它或者是一棵空树，
2、或者是具有下列性质的
  - 若它的左子树不空，则左子树上所有结点的值均小于它的的值；
  - 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  - 它的左、右子树也分别为二叉搜索树
总结一句话：左边的比该节点小，右边的比该节点大。不具有调节的能力，按插入顺序挨个插入。但是可能导致二叉搜索树变成链表，成为线型关系。
如下图：

BST.png

AVL（平衡二叉树）

规定：

1、可以认为是BST改良版，增加了自动调节能力
2、一个节点的左右子节点高度差绝对值不能大于1
3、如果绝对值高度差大于1，将会进行左旋或者右旋进行调节
总结：虽然解决了BST存在的问题，但是高度绝对值不大于1，这就导致AVL在插入或者删除的过程中，导致频繁的调整二叉树。

演示:

演示左旋

GIF 2020-12-30 16-31-39.gif

演示右旋

GIF 2020-12-30 16-34-41.gif

说明：有的也会有说单旋，双旋的。单旋或者双旋指的是经过几次旋转达到平衡二叉树要求，没啥新鲜的，了解就可以了。

BRT（红黑树）

规定：

1、根节点为黑色
2、叶子null节点为黑色
3、红节点的子节点为黑色
4、新入的节点默认为红色（可能后期调整就变成黑色了）
5、某个节点到叶子节点所有路径上的黑色节点一样多。

总结（很重要，请认真看）：
  1、规定中，很多要求节点为黑色，这就给红色节点很多限制
  2、规定2中，叶子节点为黑色，那么就表明至少一半以上为黑色节点
  3、规定5中，规定路径中黑色节点一样多，就可以为，红黑树是平衡二叉树（完美平衡二叉树）变化而来，原来平衡二叉树的所有节点都为黑色节点，然后在所有为黑色节点的平衡二叉树中插入红色节点（按规定插），并且二叉树不用调整。这样的话就解决了AVL频繁调整的问题。
有了红黑树是怎么由AVL转变而来的，那么接下来就开始讲解红黑树的调整了。

红黑树的结构：

//hashMap中的红黑树，将k 和V放到一个Node中，然后通过TreeNode，表示红黑树。
//这里只是做个大致展示。不同实现，结构不同
class Node{
    public K key;
    public V value;
    public Node left, right, parent;
    public boolean color;
}

//hashMap中的红黑树结构
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
}

//super中的结构是：
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

红黑树调整规则：

父节点	叔节点	类型 看爷爷节点	操作
黑色	-	-	无需操作
红色	红色	-	父叔都变黑，祖父变红，祖父变成当前节点，递归规则
红色	黑色	左左	右旋+变色
红色	黑色	右右	左旋+变色
红色	黑色	左右	先左旋，再右旋+ 变色
红色	黑色	右左	先右旋，再左旋+变色

配图.png

分步演示：

前提：每个gif图并不是很长时间，耐心看看。也可以在线面连接中自己去尝试 数据结构可视化

1、叔父都为红：

GIF 2020-12-30 16-40-58.gif

• （1）添加0005为根节点
• （2）添加0004
• （3）添加0006
• （4）添加0008，叔父节点为红色，叔父变黑，祖父变红，但是祖父为根节点，仍为黑。
  注意：有个看不见的null叶子节点，为黑色，这里没办法展示，特此说明

父黑叔红

左左：

GIF 2020-12-30 17-02-30.gif

• （1）插入0005
• （2）插入0004
• （3）插入0003，此时父节点0004为红，叔节点（null节点）为黑，右旋+变色

右右

和左左类似，只是旋转方向不一样，直接看图，不再解释

GIF 2020-12-30 16-53-12.gif

右左

GIF 2020-12-30 17-06-19.gif

• （1）插入0002，根节点

• （2）插入0001

• （3）插入0003

• （4）插入0005，父节点0003为红，叔节点0001也为红,父叔都变黑色，祖父变红，祖父为根节点，仍变为黑色。

• （5.1）插入0004，放到0005左边，父0005为红色，叔节点为null（黑色）。

  
  插入0004.png

• （5.1）先右旋，0004变为0005父节点，

  
  右旋.png

• （5.2）再左旋

  
  左.png

左右

和右左同理，不再详细解释过程，看一下图就可以

GIF 2020-12-30 17-20-13.gif

总结：

  这里讲解的是插入时候，简单的变化规则，实际中会出现多级旋转、变色这种情况。大家可以在上面的网站中，自己动手创建，看看他的变化，会有更好地体会。
  关于删除，我还没很好的理解，个人感觉删除比插入难点，理解完后，我在这个文章后继续追加。
  感谢各位阅读，希望给点个赞，谢谢！