红黑树详解
查找算法有哪些？
暴力：遍历for
二分：能做二分查找的条件：有序
哈希：最高效O(1),hash冲突，JDK1.8里面HashMap：数组+链表+红黑树（处理Hash冲突的）
插值：
索引：
bfs&dfs：
平衡树：
B+树：
B-Tree:
红黑树：高效的查找算法数据结构
二叉搜索树：也叫二叉查找树，也叫二叉排序树
特点：右边的节点比左边的节点大，右子树节点大于根节点，左子树的节点小于根节点
二叉树
二叉查找树：
时间复杂度就是我们树的深度
时间复杂度分析：logn=> 2^x=n(树的高度) => x=log2 n（2是底） =>logn
时间复杂度与树高度(x)关系：
1. 时间复杂度:一般指代码运行的次数
2. 代码运行次数=树高度(x)
比如：假设该树高度为3， 从根节点下来，最坏情况要比较3次,相当于运行3次代码。
3. 所以，时间复杂度=树高度（x）
树高度（x）与树节点数（n）关系
1. 平衡二叉树理想情况需要做到左右高度相同
2. 那么，基于上述情况， x与n的关系就为 2^x=n
n=2^0+2^1+...+2^（x-1）=2^x-1。-1这种常数可以舍弃。
时间复杂度=x=log2n,2是底。
二叉查找树存在退化成链表的情况，如何解决？
不要让它变成一条链表
AVL树:平衡二叉树，它的左右子树高度之差不超过1，这样确实可以避免一条直线型的结构，
但还不是我们最理想的可以认为是理想状态
红黑树的底层数据结构是什么？（特殊的二叉树）二叉查找树
JDK1.7HashMap:数组+链表 --> 1.8推出了红黑树
数据结构的推算过程：
链表(暴力)->二叉树->二叉查找树->特殊的二叉查找树(自平衡的二叉树)
红黑树的性质(重点)
1.每个结点不是红色就是黑色
2.不可能有连在一起的红色结点
3.根节点都是黑色root(入度为0)
4.每个红色结点的两个子节点都是黑色，叶子结点都是黑色，
出度为0，满足了性质就可以近似的平衡了，不一定要变黑，可以为其他的。
红黑树的 3 种变换规则： 变色，左旋，右旋
1.改变颜色：最简单，红变黑，黑变红
变颜色条件：两个连续红色节点，并且叔叔节点是红色
变色规则： 把父节点变为黑色，把叔叔节点变为黑色，把爷爷节点变为红色
2.左旋 ：
左旋条件：两个连续红节点，并且叔叔节点是黑色，下面的红色节点在右子树
假设点旋节点为E，右子树根节点为S,
第一步: S 左旋作为点旋节点（也就是根节点）
第二步：E 左旋为左子树的根节点，E的左分支原节点不变
第三步：之前S的右子树的左子树(左半部分)挂到E的右分支上
其实还有变色，后边实例有详细描述
注意：挂载的不只是单独的一个节点，而是一个子树
动图如下：
(左旋条件：两个连续红节点，并且叔叔节点是黑色，下面的红色节点在右子树)
3.右旋：和左旋原理一样，自行推敲
右旋条件：两个连续红节点，并且叔叔节点是黑色，下边的红色节点在左子树
旋转和颜色变换规则：所有插入的点默认为红色
1.变色实例:
变颜色条件：两个连续红色节点，并且叔叔节点是红色
这里违反了性质4，有两个红节点相连
注意：78的父节点【89】是红色，78的爷爷节点的另一个子节点(叔叔节点)【45】也是红色
满足变颜色规则，更改规则如下
（1）把父结点设为黑色
（2）把叔叔结点也设为黑色
（3）把祖父结点，也就是父亲的父亲设置为红色（爷爷结点）
2.左旋实例：
左旋条件：两个连续红节点，并且叔叔节点是黑色，下面的红色节点在右子树
情况1： 如果当前节点是右子树，并且父节点是左子树
例如:(【900】是新插入的节点)
要根据父节点左旋【899】（根据谁左旋，谁就变成子节点）
【900】的左子树 挂到 【899】的右子树上 ， 【899】变为子节点 ， 【900】变为父节点
此时不变色
因为还需要右旋
情况2： 如果当前节点是右子树，并且父节点是右子树
例如：(【100】是当前节点)
根据祖父节点左旋【56】（根据谁左旋，谁就变成子节点）
【56】变为子节点，【89】变为父节点，【89】的左子树 挂到 【56】的右子树
同时： 父节点变黑（【89】变黑），祖父节点变红（【56】变红 )
3.右旋实例
右旋条件：两个连续红节点，并且叔叔节点是黑色 , 下面的红色节点在左子树
情况1：如果当前节点是左子树，并且父节点也是右子树
形如：(【8000】是当前节点)
根据父节点右旋【9000】（根据谁右旋，谁就变成子节点）
【9000】变为子节点，【8000】变为父节点，【8000】的右子树 挂到 【9000】的左子树
此时不变色
其实现在还是不满足性质，应该继续左旋，这里不多赘述，和上面左旋情况2 一样
情况2： 如果当前节点是左子树，并且父节点也是左子树
形如：(【899】是当前节点)
根据祖父节点右旋【1000】（根据谁右旋，谁就变成子节点）
【1000】变为子节点，【900】变为父节点，【900】的右子树 挂到 【1000】的左子树
同时： 父节点变黑（【900】变黑），祖父节点变红（【1000】变红）
平衡插入算法(插入的节点默认为红色)
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//新插入的节点默认为红色
x.red = true;
//循环
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//判断插入的父节点 是不是 null
if ((xp = x.parent) == null) {
//是null代表当前节点是根节点 ，根节点要置成黑色（根据性质）
x.red = false;
return x;
}
//现在 xp是父节点
//父节点不是红色 或者 xpp(祖父节点) 是 null
/** 父节点不是红色：满足性质 【!xp = red】如图: xpp(祖父节点) / \ xp【黑】 / x【红】 祖父节点是null: 当前是第二层的节点（根当作第一层，根节点一定黑色）满足性质 【(xpp = xp.parent) == null】如图： xp【黑】 / x【红】 */
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//父节点是左子树
/** xpp(祖父节点) / \ xppl(xp)【红色】 / x【红色】 */
if (xp == (xppl = xpp.left)) {
//存在右侧的叔叔节点 ，并且右侧叔叔节点 是红色
//满足红黑树变颜色的规则【插入节点红色，父亲节点红色，叔叔节点红色】
/** xpp(祖父节点)【黑】 / \ xppl(xp)【红色】 xppr(叔叔节点)【红】 / x【红色】 */
if ((xppr = xpp.right) != null && xppr.red) {
//右叔叔节点变黑色
xppr.red = false;
//父亲节点变黑色
xp.red = false;
//祖父节点变红色
xpp.red = true;
/** xpp(祖父节点)【红】 / \ xppl(xp)【黑】 xppr(叔叔节点)【黑】 / x【红色】 */
//祖父节点赋值给 x ， 继续循环，因为可能祖父节点的上一级也是红色
//所以要以祖父节点为基准，继续循环判断
x = xpp;
}
//不满足变色的规则
/** xpp(祖父节点)【黑】 / \ xppl(xp)【红色】 xppr(叔叔节点)【黑/Null】 / x【红色】 */
//那么就得进行旋转
else {
//插入的节点是右子节点
/** xpp(祖父节点)【黑】 / \ xppl(xp)【红色】 xppr(叔叔节点)【黑/Null】 \ x【红色】 */
if (x == xp.right) {
//因为xp的父节点可能又是红色，不满足性质，
//所以要以父节点为基准，继续循环判断
//左旋【以父节点为轴】将x设置为父节点
//（因为左旋后 子节点将会变成父节点）
root = rotateLeft(root, x = xp);
/** 左旋后 xpp(祖父节点)【黑】 / \ xp(原来的x)【红色】 xppr(叔叔节点)【黑/Null】 / x(原来的xp)【红色】 */
//xpp（插入节点的祖父节点）是null，说明父节点是根节点
//否则说明有祖父节点，设置xpp为（插入节点的）祖父节点
//旋转后 节点位置发生变化，须要重新判断xpp
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//父节点不是null
if (xp != null) {
//父节点 变黑
xp.red = false;
//祖父节点不是Null
if (xpp != null) {
//祖父节点变红
xpp.red = true;
//右旋 【以祖父节点为轴】
root = rotateRight(root, xpp);
/** 右旋后 xp【黑】 / \ x【红色】 xpp(原祖父节点)【红】 \ xppr等等..... */
}
}
}
}
/** else是指xp在右子树上，如图： xpp(祖父节点)【黑】 / \ xppr(叔叔节点)【黑/Null】 xppl(xp)【红色】 \ x【红色】 */
else {
//满足变色规则
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//x是左子节点
/** xpp(祖父节点)【黑】 / \ xppr(叔叔节点)【黑/Null】 xppl(xp)【红色】 / x【红色】 */
if (x == xp.left) {
//右旋，根据xp节点
root = rotateRight(root, x = xp);
//旋转之后 效果如下
/** xpp(祖父节点)【黑】 / \ xppr(叔叔节点)【黑/Null】 xp（原来的x）【红色】 \ x(原来的xp)【红色】 */
//赋值
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//xp不为空
if (xp != null) {
//设置xp为黑色
/** xpp(祖父节点)【黑】 / \ xppr(叔叔节点)【黑/Null】 xp（原来的x）【黑色】 \ x(原来的xp)【红色】 */
xp.red = false;
//xpp不为空
if (xpp != null) {
//设置xpp为红色
xpp.red = true;
//以祖父节点为轴，左旋
root = rotateLeft(root, xpp);
/** xp【黑】 / \ xpp(原来的祖父节点) 【红】 x【红色】 / xppr(叔叔节点)【黑/Null】 */
}
}
}
}
}
}
左旋算法
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
/** xpp(祖父节点)【黑】 / \ xppl(xp)【红色】 xppr(叔叔节点)【黑/Null】 \ x【红色】 */
//p就是上图的xp,也就是插入节点x的父节点
if (p != null && (r = p.right) != null) {
/** pp(祖父节点)【黑】 / \ p【红色】 xppr(叔叔节点)【黑/Null】 \ r【红色】 / rl（r的左子节点） */
//这句话的啥意思是 r.left(rl)也就是r的左子树 挂到 p.right也就是p的右子树上
//然后rl.parent(就是r) = p 意思是将rl(r的左子树) 的父节点设置为 p
//这样就完成了 r的左子树 挂到 p的右子树操作！！！！！！！！！！！
if ((rl = p.right = r.left) != null)
rl.parent = p;
//pp = r.parent = p.parent 意思是将r变成xpp的子节点（r取代了p原本的位置）
//pp == null 如果p的父节点是null
//执行下面if语句后 旋转后
/** pp(祖父节点)【黑】 / \ r【红色】 xppr(叔叔节点)【黑/Null】 / p【红色】 \ rl（r的左子节点） */
if ((pp = r.parent = p.parent) == null)
//如果if成立 ，说明r现在就是最顶级的节点
//让r变为根节点 因为现在r就是顶级的节点
//并且根节点设置为黑色【根据红黑树性质，根节点必须是黑色】
(root = r).red = false;
/** r(root)【黑色】 / p【红色】 \ rl（r的左子节点） */
//否则说明r还有父节点(pp)， 如果pp的左子节点是p
else if (pp.left == p)
//将r设置成pp的左子节点 之前只只设置了r.parent是pp，现在设置pp.left是r
//这样 r真正变成pp的左子节点
pp.left = r;
else
//如果p在右子树上，那么旋转都是一样的，只不过 设置为pp的右子节点为r
//【这里的图只是用作演示p在右子树情况，不和上边的图发生关联关系】
/** pp(祖父节点)【黑】 / \ xppr(叔叔节点)【黑/Null】 p【红色】【这里要设置为r】 \ r【红色】 / rl（r的左子节点） */
pp.right = r;
//将p设置成r的左子节点 之前只只设置了p.parent是r，现在设置r.left是p
//这样 p就真正变成了r的左子节点
r.left = p;
//r变成p的父亲
//这样r和p也完成了位置替换
p.parent = r;
/** pp(祖父节点)【黑】 / \ r【红色】 xppr(叔叔节点)【黑/Null】 / p【红色】 \ rl（r的左子节点） */
}
return root;
}
投递美团等公司10个岗位 >