前提：

在学习红黑树之前，先要理解一下平衡二叉树（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);
    }
}

红黑树调整规则：

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