红黑树介绍

java8之后，hashmap的桶链表引入了红黑树算法。大概先了解什么是红黑树

一种特殊的二叉树

学习于简书这篇

性质

• 每个节点都是红或者黑

• 根节点是黑色的

• 叶子节点是黑色的

• 节点是红色的，那么两个子节点就是黑色的

• 任意节点的两端子树，黑色节点树目相同

时间复杂度

O（lgn）

普通二叉树在最坏情况下可能达到O（n），但是红黑树的特性5，保证了没有一个子树的深度是另一个子树的两倍。这样保证了时间复杂度平均在O（lgn）

为什么节点两端的子树，在满足特性5的情况下，会保证深度不会相差两倍呢？

最短路径就是都是黑色，最长路径就是红黑交替

因为任意路径上的黑节点数量必须相同，而红节点的子节点必须是黑色的。致使树的形状接近平衡二叉树

平衡二叉树时间复杂度O(lgn)

左旋右旋

盗图–>

x左旋转，就是把x变成左节点，y代替原来位置，如果y有左子树，则挂在x的右子树。

盗图–>

y右旋，把y变成右节点，x代替原来位置，x要是有右子树，挂在y的左子树。

插入

• 正常二叉树插入
• 将插入节点标志为红色
• 旋转修正

插入时：

• 被插入的节点是根节点，直接标志为黑色

• 被插入的节点父节点是黑色，donothing

• 父节点是红色，叔叔节点是红色

  盗图->

  1. 将父节点，叔节点设置为黑色，祖父节点设置为红色。把祖父节点当成当前节点，继续操作，因为当前节点变成了根节点，所以直接又涂成黑色。

• 父节点是红色，叔节点是黑色，或者缺失，且当前节点是曲线边（父左当前右，父右当前左）

  1. 将父节点作为新的当前节点

  2. 以新的当前节点进行左旋

  3. 以新的当前节点再进行操作

     盗图–>

• 父节点是红色，叔叔节点是黑色，或者缺失，当前节点直线边（父左当前左，父右当前右）

  1. 将父节点色织为黑色

  2. 祖父设置为红色

  3. 以祖父节点为支点右旋

     盗图–>

删除

• 二叉树删除操作
• 旋转着色修正红黑树

删除时：

• 当前节点是黑色，父节点是黑色，兄弟节点红色
  1. 将兄弟节点设置为黑色
  2. 将父节点设置为红色
  3. 对以父节点为当前节点进行左旋
  4. 重设置删除节点的