数据结构-红黑树

红黑树

红黑树（Red Black Tree） 是一种自平衡二叉查找树

红黑树是一种特化的AVL树（平衡二叉树），都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能

红黑树，除了符合二叉搜索树的基本规则外，还添加了以下特性（规则）：

1. 节点是红色或黑色
2. 根节点是黑色
3. 每个叶子节点都是黑色的空节点(null)
4. 每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）

5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

   
   image.png

关键特性
从根到叶子的最长可能路径，不会超过最短可能路径的两倍长

• 在插入新的节点时， 通常都是红色节点

• 在插入新节点时，可能树不再平衡了。可以通过三种方式变换，让树保持平衡

  • 换色 - 左旋转 - 右旋转

换色
为了重新符合红黑树的规则，尝试把红色节点改为黑色节点，或者把黑色节点变为红色。
左旋转
逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子取代，而自己成为自己的左孩子

右旋转
顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己成为自己的右孩子

image.png

插入操作

假设插入的节点为N，其父节点为P， 其祖父节点为G, 其父节点的兄弟节点为U (P和U有相同的父节点G)

1. 情况一：

• 新节点N（默认为红色）位于树的根上，没有父节点

方案：这种情况，直接将红色变化为黑色即可 (规则2)

2. 情况二

• 新节点的父节点P为黑色 （直接符合规则）

3. 情况三

• 父节点P为红色，父节点的兄弟节点U也为红色

  
  image.png
  

  方案：

  • 将P和U变为黑色，把G变为红色
  • 现在新节点N有了一个黑色的父节点P,所有每条路径上的黑色节点数目没有改变
  • 而从更高的路径上，必然会经过G节点，所有那些路径的黑色节点数目也是不变的

可能出现的问题

• N的祖父节点G的父节点可能也是红色，这违反了规则3， 把G节点下面的所有当成一个整体新节点G。再递归判断符合哪种情况情况。
• 如果递归调整的颜色到了根节点，把根节点的颜色改为黑色即可。

4. 情况四

• 新节点N的叔叔节点U是黑色节点，且N是左节点

方案：

• 交换父节点P和祖父节点G的颜色

• 对祖父节点G进行右旋转

  
  image.png
  

  [图片上传中...(image.png-112472-1627113823203-0)]

5. 情况五（如果新节点N不是左节点，父节点左旋转之后，可以得到情况3或情况4的结果，再变化即可）

• 比如：新节点N的叔叔节点U是黑色， 且N是右节点

方案：

• 对P节点进行依次左旋转，形成情况四的结果
• 对祖父节点G进行右旋转，并且改变颜色即可

image.png

栗子： 依次插入10，9，8，7，6，5，4，3，2，1

黑色的空节点null 没有画出来

image.png image.png image.png image.png image.png image.png image.png image.png image.png image.png