【算法】红黑树原理和算法介绍

红黑树介绍

二叉查找树

　　学红黑树，首先理解二叉查找树

　　

　　二叉查找树（BST）具备特性

1. 左子树上所有结点的值均小于或等于它的根结点的值。

2. 右子树上所有结点的值均大于或等于它的根结点的值。

3. 左、右子树也分别为二叉排序树。

• 二叉查找树是二分查找的思想，查找所需的最大次数等同于二叉树的高度。
• 在插入节点的时候也是利用类似的方法，一层一层比较大小，找到合适的插入位置。
• 如下图，这样虽然满足了二叉查找树的条件，但是这个是瘸腿的二叉查找树，就和链表没有区别了。这是二叉查找树的缺点

　　

• 解决二叉查找树多次插入新节点而导致的不平衡的方法，就是使用红黑树。
• 红黑树是一种自平衡的二叉查找树。

红黑树

　　R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

　　红黑树的特性:
　　（1）每个节点或者是黑色，或者是红色。
　　（2）根节点是黑色。
　　（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
　　（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点旋转到根节点，E节点的左边都挂到S节点的左边，将要旋转的子结点的左边移到之前结点S的右边

　　

举例说明

1. 首先我们要插入结点6，按照二叉查找树放在如下位置。

　　　　

　　2、我们发现结点6和结点7是红色的，不满足规则，下一步要判断是变色还是旋转

　　　　当前结点的父亲是红色，且它的祖父结点的另一个子结点也是红色，我们要进行的是变色。

　　　　把父节点和叔叔设为黑色，把祖父也就是父亲的父亲设为红色（爷爷）

　　　　

　　3、我们发现结点5和结点12还是不满足规则。

　　　　变色是说父亲结点和叔叔结点都是红色。不满足，我们用旋转。结点12位于结点5的右子树上。用左旋。

　　　　

　　4、对结点5还要进行右旋。

　　（1）把父节点变为黑色

　　（2）把祖父结点变为红色（爷爷）

　　（3）以爷爷结点旋转

 

　　　　

　　5、以上。上面的红黑树就没有问题了