红黑树
2019-08-28 本文已影响0人
漫游之光
首先说明一点，这里实现的红黑树，和《算法》（第四版）里面的算法是一样的，不是按照《算法导论》里面的红黑树算法写的。《算法》里面的红黑树是根据2-3查找树来写的。我个人认为2-3查找树里面树向上生长的算法模型非常重要，因为向上生长可以保证空结点到根节点的距离是相同的。可以认为B树是对2-3查找树的推广，而B+树又是对B树的一种优化，B树和B+树在面试里问的概率还是比较大的。
2-3查找树
一颗2-3查找树或为一颗空树，或由以下结点组成：
- 2-结点，含有一个键和两条链接，左链接指向2-3树中的键都小于该结点，右链接指向的2-3树中的键都大于该结点。
- 3-结点，含有两个键和三条链接，左链接指向的2-3树的键都小于该结点，中链接指向的2-3树中的键都位于该结点的两个键之间，右链接指向的2-3树中的键都大于该结点。
一颗完美平衡的2-3查找树中的所有空链接到根结点的距离都应该是相同的。
2-3查找树的基本操作有3个：查找、插入和删除。
- 查找：查找算法比较简单，和二叉查找树的算法基本上是一样的，只不过多了对3结点的处理，3结点的处理也比较简单，根据需要查找的值和键的大小，决定去左边、中间、右边还是查找成功。
- 插入：插入的策略就是先找到要插入的结点的位置，然后才去将插入的结点合并到该结点的策略。可以看出，如果插入的位置是一个2结点，那么插入就结束了。如果是一个3结点，那么将其合并为一个4结点，也就是结点中有3个键。这里我们可以让一个合适的键向上传递，让父节点从2结点变为3结点或者从3结点变为4结点。如果父节点也为4结点，那么也向上传递。可以看出，最终会传递到树根，在树根，我们可以将4结点分裂为3个2结点，使得树高加1。
- 删除：根据2-3查找树的定义，2-3查找树的最小值和最大值肯定在叶子结点，但这个叶子结点可能是2结点，也有可能是3结点。我们先考虑删除叶子结点的情况，该叶子结点是3结点，那么我们可以直接删除，算法终止。但如果该叶子结点不是3结点，我们没有办法直接删除。这时候，我们可以类比插入，既然一个键可以向上传递，那么肯定也可以向下传递，所以如果从上到下的某个结点为一个3结点，那么我们可以让这个3结点向下传递，这样，最后的叶子结点就为3结点或4结点，可以直接删除。问题是，如果没有3结点怎么办，这时，如果在根结点，根的左右孩子都是2结点，那么可以合成一个4结点，让后让一个键值向下传递。这样，我们就可以保证最后删除的叶子结点肯定为3结点或4结点。如果删除的不是叶子结点，也有办法。我们可以让该结点的前驱或后继来替换这个点，然后删除对应的最小值或最大值。
红黑树
红黑二叉查找树背后的基本思想是用标准的二叉查找树（完全由2-结点构成）和一些额外的信息（替换3-结点）来表示2-3树。我们将树中的链接分为两种类型：红链接将两个2-结点连接起来构成一个3-结点，黑连接则是2-3树中的普通链接。这样，2-3树的一种等价的定义如下：
- 红链接均为左链接；
- 没有任何一个结点同时和两条红链接相连；
- 该树是完美黑色平衡的，即任意空链接到根结点的路径上的黑链接数量相同。
代码实现
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
class RBTree{
private:
static const bool RED = true;
static const bool BLACK = false;
struct Node{
int val;
Node *left;
Node *right;
bool color;
int height;
Node(int val_,bool color_):val(val_),color(color_),left(NULL),right(NULL),height(1){}
};
Node* root;
bool isRed(Node *x){
if(x == NULL){
return false;
}
return x->color == RED;
}
int getHeight(Node *x){
if(x == NULL){
return 0;
}
return x->height;
}
/* 如果右子节点是红色的而左子节点是黑色的，进行左旋转（调整为正常的3-结点） */
Node* rotateLeft(Node *h){
Node* x = h->right;
h->right = x->left;
x->left = h;
x->color = h->color;
h->color = RED;
h->height = max(getHeight(h->left) , getHeight(h->right)) + 1;
x->height = max(getHeight(x->left) , getHeight(x->right)) + 1;
return x;
}
/* 如果左子节点是红色的且它的左子节点也是红色的，进行右旋转（调整为正常的4-结点） */
Node* rotateRight(Node *h){
Node *x = h->left;
h->left = x->right;
x->right = h;
x->color = h->color;
h->color = RED;
h->height = max(getHeight(h->left) , getHeight(h->right)) + 1;
x->height = max(getHeight(x->left) , getHeight(x->right)) + 1;
return x;
}
/* 颜色转换，如果将两个子树染黑，当前结点染红，相当于2-3树的分解操作
如果将两个子树染黑，当前结点染红，相当于2-3树的合并 */
void flipColors(Node *h){
h->color = !h->color;
h->left->color = !h->left->color;
h->right->color = !h->right->color;
}
Node* put(Node *h, int val){
if(h == NULL){
return new Node(val,RED);
}
if(val < h->val){ /* 向左边插入 */
h->left = put(h->left,val);
}else if(val > h->val){ /* 向右边插入 */
h->right = put(h->right,val);
}else{
/* 不处理有相同值的情况 */
}
if(isRed(h->right) && !isRed(h->left)){
h = rotateLeft(h);
}
if(isRed(h->left) && isRed(h->left->left)){
h = rotateRight(h);
}
if(isRed(h->left) && isRed(h->right)){
flipColors(h);
}
h->height = max(getHeight(h->left) , getHeight(h->right) ) + 1;
return h;
}
int minVal(Node* x) {
if (x->left == NULL){
return x->val;
} else{
return minVal(x->left);
}
}
Node* balance(Node* h) {
if(isRed(h->right) && !isRed(h->left)){
h = rotateLeft(h);
}
if(isRed(h->left) && isRed(h->left->left)){
h = rotateRight(h);
}
if(isRed(h->left) && isRed(h->right)){
flipColors(h);
}
h->height =max( getHeight(h->left) , getHeight(h->right) ) + 1;
return h;
}
/* 从兄弟结点里借一个结点 */
Node *moveRedLeft(Node *h){
flipColors(h); /* 合并结点，父节点由3-结点变为2结点或从4-结点变为3-结点 */
if(isRed(h->right->left)){ /* 兄弟结点为3-结点，借一个，不是，就合并 */
h->right = rotateRight(h->right);
h = rotateLeft(h);
flipColors(h);
}
return h;
}
Node* deleteMin(Node *h){
if (h->left == NULL){ /* h为红色，如果没有左孩子，可以直接删除 */
return NULL;
}
if (!isRed(h->left) && !isRed(h->left->left)){ /* 左子树为2-结点 */
h = moveRedLeft(h);
}
h->left = deleteMin(h->left);
return balance(h);
}
void deleteMin(){
if(root == NULL){
return;
}
if(!isRed(root->left) && !isRed(root->right)){
root->color = RED;
}
root = deleteMin(root);
if(root != NULL){
root->color = BLACK;
}
}
Node* moveRedRight(Node *h){
flipColors(h); /* 合并结点 */
if(isRed(h->left->left)){ /* 如果左子树为3-结点，从左子树借一个，不合并 */
h = rotateRight(h);
flipColors(h);
}
return h;
}
Node* deleteMax(Node *h){
if(isRed(h->left)){
h = rotateRight(h);
}
if(h->right == NULL){
return NULL;
}
if(!isRed(h->right) && !isRed(h->right->left)){
h = moveRedRight(h);
}
h->right = deleteMax(h->right);
return balance(h);
}
void deleteMax(){
if(root == NULL){
return;
}
if(!isRed(root->left) && !isRed(root->right)){
root->color = RED;
}
root = deleteMax(root);
if(root != NULL){
root->color = BLACK;
}
}
void destroy(Node *root){
if(root == NULL){
return;
}
if(root->left != NULL){
destroy(root->left);
}
if(root->right != NULL){
destroy(root->right);
}
delete root;
}
Node* del(Node *h, int val){
if(h == NULL){ /* h结点为红色 */
return NULL;
}
if(val < h->val){
if(h->left != NULL && !isRed(h->left) && !isRed(h->left->left)){
h= moveRedLeft(h); /* 向左走，并且左结点为2-结点,先借一个 */
}
h->left = del(h->left,val);
}else{
if(isRed(h->left)){
h = rotateRight(h); /* 两红不合法，右旋 */
}
if(val == h->val && h->right == NULL){ /* 删除叶子结点 */
return NULL;
}
if(h->right != NULL && !isRed(h->right) && !isRed(h->right->left)){
h = moveRedRight(h); /* 向右走，并且右结点为2-结点，先借一个 */
}
if(val == h->val){
h->val = minVal(h->right); /* 使用右子树的最小值来替代当前值 */
h->right = deleteMin(h->right); /* 删除右子树的最小值 */
}else{
h->right = del(h->right,val);
}
}
return balance(h);
}
Node* get(Node *x,int val){
while (x != NULL) {
if(val < x->val){
x = x->left;
}else if(val > x->val){
x = x->right;
}else{
return x;
}
}
return NULL;
}
public:
RBTree():root(NULL){}
~RBTree(){
destroy(root);
}
bool contains(int val){
return get(root,val) != NULL;
}
void put(int val){
root = put(root,val);
root->color = BLACK;
}
void del(int val){
if(root == NULL){
return;
}
if(!isRed(root->left) && !isRed(root->right)){ /* 合并为一个4结点，因为下一次要调用flipColors */
root->color = RED;
}
root = del(root,val);
if(root != NULL){
root->color = BLACK;
}
}
bool checkBaLance(){
if(root != NULL){
int minHeight = isRed(root->left)?max(getHeight(root->left->left),getHeight(root->left->right)): getHeight(root->left);
int maxHeight = getHeight(root->right);
if(minHeight > maxHeight){
swap(minHeight,maxHeight);
}
if(minHeight * 2 < maxHeight){
cout<<"error "<<minHeight<<" "<<maxHeight<<endl;
return false;
}
}
return true;
}
};
int main(int argc, char const *argv[])
{
int n = 1000000;
srand(time(0));
RBTree tree;
for(int i=0;i<n;i++){
int tmp = rand() % n;
tree.put(tmp);
tree.checkBaLance();
}
for(int i=0;i<n;i++){
int tmp = rand() % n;
tree.del(tmp);
tree.checkBaLance();
}
system("pause");
return 0;
}
这个就先贴代码上去吧，这里的主要难度是算法描述和算法实现有相当大的差异，2-3树的算法描述非常简单，但红黑树的实现还是挺令人疑惑的。这里采用的都是一种递归的处理方式，我想可能主要是为了减少理解的难度。
AVL和红黑树都是通过定义一些平衡的条件，然后通过在插入删除的过程中保持这些条件来达到一种平衡。AVL树是通过旋转，而红黑树则是通过旋转和着色。
这里的实现对我来说，确实有些困难，所以基本上我都是照着书上的代码写，我又发现了书中的一些错误，上github，发现里面的错误已经修复了，并且，上一次更新就在24天前。从这里，我也意识到了，有Bug是很正常的，但如果发现Bug，我们需要及时修复。
