红黑树

简单介绍

定义

红黑树是一种含有红黑结点并能自平衡的二叉查找树。它必须满足下面性质：

  • 性质1：每个节点要么是黑色，要么是红色。
  • 性质2：根节点是黑色。
  • 性质3：每个叶子节点是黑色。
  • 性质4：每个红色结点的两个子结点一定都是黑色。
  • 性质5：任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

自平衡

左旋

以某个结点作为支点(旋转结点)，其右子结点变为旋转结点的父结点，右子结点的左子结点变为旋转结点的右子结点，左子结点保持不变

image-20210501135230229

这个图 就非常的形象的表示了左旋的结果，其实我们理解左旋可以分为以下两点

  1. 旋转节点的右子节点变为它的父节点，左子节点不变，新的右子节点是原来右子节点的左子节点
  2. 旋转节点的右子节点 左子节点为 旋转节点；右子节点不变

套用到上图就是

  1. pivot是旋转节点，y变为pivot的父节点，左节点还是a，右节点变为b
  2. y的左节点是pivot，右节点不变，还是c

右旋

以某个结点作为支点(旋转结点)，其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左子结点，右子结点保持不变

image-20210501135810812

同左旋刚好相反，左和右的互换，两个点

  1. 旋转节点的左子节点变为它的父节点，右子节点不变，新的左子节点是原来左子节点的右子节点
  2. 旋转节点的左子节点 左子节点不变；右子节点为旋转节点

变色

结点的颜色由红变黑或由黑变红

插入

空树

当树是空的时候，插入的时候，直接将其作为根节点，并且是黑色的

插入的key已经存在了

  1. 当前节点的颜色不变
  2. 更改当前节点的值

插入节点的父节点为黑色节点

由于插入的节点颜色是红色的，所以直接插入即可，无需自平衡

插入节点的父节点为红色节点

  1. 叔叔节点存在并且为红色节点
  2. 叔叔节点为空，且祖父节点、父节点和新节点处于一条斜线上。
  3. 叔叔节点为空，且祖父节点、父节点和新节点不处于一条斜线上。
第一种情况

将父节点和叔叔节点与祖父节点的颜色互换

image-20210502073524655

第二种情况

将B节点进行右旋操作，并且和父节点A互换颜色

image-20210502073447008

第三种情况

将C节点进行左旋，这样就从第三种情况转换成第二种情况了，然后针对case 2进行操作处理就行

image-20210502073514982

删除

参考文章：