红黑树的插入

王守钰 2020-03-11 13:03:57

红黑树演示地址

https://note.img.wangshouyu.com/apps/tree/RedBlack.html

红黑树的定义与性质

image
红黑树是一种含有红黑结点并能自平衡的查找二叉树。共有5个特性。

  1. 每个结点要么是黑色,要么是红色。
  2. 根结点是黑色。
  3. 每个叶子结点(NIL)是黑色。
  4. 每个红色结点的俩个子结点一定都是黑色。
  5. 任意一结点到叶子结点的路径都包含数量相同的黑结点。

查找二叉树

查找二叉树,又称为二叉排序树(Binary Sort Tree)。一棵查找二叉树,或者是一棵空树,或者满足以下递归条件:

  1. 查找树的左、右子树各是一棵查找树。
  2. 若查找树的左子树非空,则其左子树上的各结点值均小于根结点的值。
  3. 若查找树的右子树非空,则其右子树上的各结点值均大于根结点的值。

红黑树平衡的最小单元

image
红黑树插入结点时候,默认添加红色结点。最小单元只需要关注CPGU结点。

红黑树自平衡的原子操作

红黑树的自平衡操作包括:变色、旋转。其中旋转又可以分为左旋和右旋。旋转要有圆心,有方向。旋转结点围绕子结点进行旋转。

右旋

image

以旋转结点的子结点为圆心,进行旋转。旋转结点作为圆心结点的子结点。圆心结点的子结点作为旋转结点的子结点。

左旋

image

以旋转结点的子结点为圆心结点逆时针方向,基于最短路径来确定方向旋转。

无父结点

新增红色结点,变成黑色Root结点。
image

三点一线

image
如上图所示,以200结点为圆心100结点进行左旋,100结点变红色、200结点变黑色。
image
如上图所示,以90结点为圆心,100结点进行右旋。90结点变黑色,100结点变红色。

三角关系

image
如上图所示,插入150结点,先进行以150结点为圆心,200结点的右旋;再进行以150为圆心100结点进行左旋。100结点变红色,150结点变黑色。
image
如上图所示,插入95结点,先进行以95为圆心,90结点的左旋;再进行以95为圆心100结点进行右旋。100结点变红色,95结点变黑色。

父结点和叔叔结点都是红色,仅变色

image
插入200结点后,发现父结点100的颜色和叔叔90结点的颜色都为红色,那么这时候就需要将90结点和100结点的颜色都变为黑色,95结点变为红色。95结点又是root结点,那么95结点就需要变成黑色。

复杂的转换案例

image
插入888结点后,首先父结800点和叔叔700结点变为黑色,祖父结777点变为红色。这时候777结点和父结点666祖父结点500进行旋转变色,666结点变成祖结点,500结点变成子结点,666的子结点600变为500的子结点。666结点变为黑色,500结点变为红色。