简单了解红黑树

简单了解红黑树

HashMap加入红黑树的原因

当我们的HashMap中存在大量数据时，加入我们某个bucket下对应的链表有n个元素，那么遍历时间复杂度就为O(n)，为了针对这个问题，JDK1.8在HashMap中新增了红黑树的数据结构，进一步使得遍历复杂度降低至O(logn)

红黑树的特点

性质1：每个节点要么是黑色，要么是红色
性质2：根节点是黑色
性质3：每个叶子节点（NIL）是黑色。注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！
性质4：每个红结点的两个子结点一定都是黑色
性质5：任意一结点到每个叶子结点的路径都包含相同数量的黑结点

红黑树时怎么保持平衡的？

三种 *** 作：左旋、右旋和变色。简单点说，旋转和变色的目的是让树保持红黑树的特性

• 左旋：以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变
• 右旋：以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变
• 变色：结点的颜色由红变黑或由黑变红

红黑树的插入 *** 作

以下图示的红黑树只是树的局部，不要纠结“根节点”的颜色

红黑树插入的节点默认都是红色，插入主要分为插入和修复过程
一 当插入第一个节点（根节点）时，直接变成黑节点即可

二 父节点为黑色，直接插入，不需要变色

三 如果父节点为红色，叔叔节点也是红色（此种情况爷爷节点一定是黑色），则父节点和叔叔节点变黑色，爷爷节点变红色（如果爷爷节点是根节点，则再变成黑色），然后爷爷节点此时需要递归（把爷爷节点当做新插入的节点再次进行比较）

四 如果父节点是红色，没有叔叔节点或者叔叔节点是黑色（此时只能是NIL节点），并且局部呈现直线，则以爷爷节点为支点旋转，旋转之后原来的爷爷节点变红色，原来的父节点变黑色，如果此时该节点和父节点朝右，则左旋，该节点和父节点朝左，右旋

五 如果父节点是红色，没有叔叔节点或者叔叔节点是黑色（此时只能是NIL节点）并且局部呈现三角形，首先旋转成直线，然后再按照情况四旋转即可

红黑树的删除 *** 作

二叉搜索树的性质保持：首先我们知道，对于二叉搜索树的任意一个节点，其子节点只有0个、1个或者2个。对于没有子节点的节点，我们直接删除就可以了，对于有一个子节点的节点，我们用其子节点及子节点子树补位替代就可以了，对于有两个子节点的节点，我们先将它和它的前驱节点或者后继节点交换，再删除即可，真正的过程是改变被删除节点的值，再删除前驱节点或者后继节点，如图

删除节点也是分为两部分：删除和修复

如果我们删除的是红色节点，我们不会破坏黑高，我们按照二叉搜索树的性质删除即可

如果删除的是黑色节点，情况就很复杂，因为它会破坏红黑树的性质。我们按照二叉搜索树删除后，还要进行修复 *** 作，我们把删除节点后取代原节点的那个节点记为X，称X为修复中心，我们开始修复，分为四种情况：

一 X的兄弟节点W为黑色，且W的子节点都是黑色

修复：由于X路径删除了黑色节点，使其黑高-1，所以首先将W变成红色节点来保持黑高，但改变后整体可能处于黑高不平衡，所以我们将X的父节点再当成修复中心来递归修复，直到修复对象变成根节点或者红色节点，最后再将修复对象变成黑色节点

二 X的兄弟节点W为黑色，且W的右子节点为红色

修复：W的颜色变成X放入父节点的颜色，X的父节点的颜色和W的右节点都变成黑色，左旋X的父节点

三 X的兄弟节点W为黑色，且W的子节点左红右黑

修复：交换W和W的左子节点的颜色，右旋W，变成了情况二，只不过这时候X的兄弟节点为C了

四 X的兄弟节点W为红色

修复：W和A的颜色互换，左旋A，此时将X的兄弟节点视为新的W，类型会是上述三种中的其中一种，再修复即可