详细描述红黑树如何左旋、右旋(图文结合)

详细描述红黑树如何左旋、右旋(图文结合)

引用

CSDN

1.

https://blog.csdn.net/renshen4322/article/details/137087946

红黑树是一种自平衡的二叉查找树，在计算机科学中被广泛应用于实现关联数组、数据库和编译器中的符号表等数据结构。本文将详细介绍红黑树的左右旋转操作，帮助读者理解这种数据结构的平衡机制。

首先要理解二叉查找树
二叉查找树（BST）具备什么特性呢？

1. 左子树上所有结点的值均小于或等于它的根结点的值。
2. 右子树上所有结点的值均大于或等于它的根结点的值。
3. 左、右子树也分别为二叉排序树。

• 二叉查找树是二分查找的思想，查找所需的最大次数等同于二叉树的高度。
• 在插入节点的时候也是利用类似的方法，一层一层比较大小，找到合适的插入位置。
• 如右图，这样虽然满足了二叉查找树的条件，但是这个是瘸腿的二叉查找树，就和链表没有区别了。这是二叉查找树的缺点
• 解决二叉查找树多次插入新节点而导致的不平衡的方法，就是使用红黑树。
• 红黑树是一种自平衡的二叉查找树。除了符合二叉查找树的基本特性外，还具有下列的附加特性：

1. 节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶子节点都是黑色的空节点（NIL节点）。
4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
   

• 上面一系列的规则，保证了红黑树的自平衡。红黑树从根到叶子的最长路径不会超过最短路径的2倍
• 当插入或删除节点的时候，红黑树的规则有可能被打破，这个时候需要进行调整来维持红黑树的规则。
  如下图，如果向原红黑树插入值为21的新节点，由于父节点22是红色节点，因此这种情况打破了红黑树的规则4（每个红色节点的两个子节点都是黑色），必须进行调整，使之重新符合红黑树的规则。
  
• 调整的方法有两种：

1. 变色：红变黑，黑变红
2. 旋转：左旋转和右旋转
   变换规则

• 旋转和颜色变换规则：所有插入的点默认为红色

1. 变颜色的情况：当前结点的父亲是红色，且它的祖父结点的另一个子结点也是红色（叔叔结点）：
   （1）把父节点设为黑色
   （2）把叔叔也设为黑色
   （3）把祖父也就是父亲的父亲设为红色（爷爷）
   （4）把指针定义到祖父结点设为当前要操作的（爷爷）分析的点变换的规则
2. 左旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是右子树。左旋以父节点作为左旋
3. 右旋：当前父结点是红色，叔叔是黑色的时候，且当前的结点是左子树。右旋
   （1）把父节点变为黑色
   （2）把祖父结点变为红色（爷爷）
   （3）把祖父结点旋转（爷爷）
   变色
   为了重新符合红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。

• 下图所表示的是红黑树的一部分，需要注意节点25并非根节点。因为节点21和节点22连续出现了红色，不符合规则4，所以把节点22从红色变成黑色：
  
• 但这样并不算完，因为凭空多出的黑色节点打破了规则5，所以发生连锁反应，需要继续把节点25从黑色变成红色：
  
• 此时仍然没有结束，因为节点25和节点27又形成了两个连续的红色节点，需要继续把节点27从红色变成黑色：
  
  左旋转
• 左旋转，就是将S点旋转到根节点，S节点的左边都挂到E节点的右边
• 就是将要旋转的子结点的左边挂到之前节点E的右边
  右旋转
  将要旋转的子结点的右边移到之前结点E的左边
  举例说明

1. 首先我们要插入结点6，按照二叉查找树放在如下位置。
   
2. 我们发现结点6和结点7是红色的，不满足规则，下一步要判断是变色还是旋转
   当前结点的父亲是红色，且它的祖父结点的另一个子结点也是红色，我们要进行的是变色。把父节点和叔叔设为黑色，把祖父也就是父亲的父亲设为红色（爷爷）
   
3. 我们发现结点5和结点12还是不满足规则。变色是说父亲结点和叔叔结点都是红色。不满足，我们用旋转。结点12位于结点5的右子树上。用左旋。
   [图片上传失败...(image-b433f8-1585661664741)]
4. 对结点5还要进行右旋。
   （1）把父节点变为黑色
   （2）把祖父结点变为红色（爷爷）
   （3）以爷爷结点旋转
   
5. 以上。上面的红黑树就没有问题了