当前位置：首页 > news >正文

C++红黑树

news 2025/5/15 7:49:54

一.红黑树的概念和性质

1.1红黑树的概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或 Black。

通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。（可以看出AVL树和红黑树保持平衡的限制条件不同，AVL树通过平衡因子来限制）

1.2红黑树的性质

每个结点不是红色就是黑色
根节点是黑色的（指的是整棵树的根节点，不包括子树根节点）
如果一个节点是红色的，则它的两个孩子结点是黑色的
对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点
可以有连续黑色节点，不能有连续的红色节点

性质2，3，4，5就保证了红黑树的最长路径不超过最短路径的二倍，例如：

上图中只保留了最长路径和最短路径。

可以看出上图中黑色节点个数相同，因此无法再增加黑色节点个数，而根据性质5无法出现连续的红色节点，也无法增加红色节点个数，因此就保证了红黑树最长路径不能超过最短路径的2倍。

1.2.1关于路径的解释

路径指的是必须走到空才为一条路径，例如：

上图中的路径有11条。

二.红黑树节点和定义

在AVL树中增加了平衡因子来保证AVL树的平衡，而红黑树是依据颜色来限制，因此增加了表示颜色的限制元素。同时仍需要频繁的访问父亲节点，所以在红黑树中仍需要一个指向父亲的指针。

节点定义示例如下：

enum Color
{RED,BLACK
};
template<class T>
struct RBNode
{RBNode<T>* _pLeft;RBNode<T>* _pRight;RBNode<T>* _pParent;T _data;Color _color;RBNode(const T& data=T(),Color color=RED):_pLeft(nullptr),_pRight(nullptr),_pParent(nullptr),_data(data),_color(color){}};

在节点定义中将节点初始颜色设置为红色，是因为为了保证每一条路径黑色节点数保持一致的性质（该性质较难控制），设想一下：如果插入节点颜色是黑色，那么性质四就会被破坏，想重新让性质四成立，工程量巨大。因此将节点初始颜色设置为红色较佳。

三.红黑树插入操作

红黑树是在二叉搜索树的基础上加上其平衡限制条件，因此红黑树的插入可分为两步：

按照二叉搜索的树规则插入新节点
检测新节点插入后，红黑树的性质是否造到破坏

二叉搜索树插入操作前面博客已经详细介绍，这里主要解释检测部分。

约定:cur为当前节点，p为父节点，g为祖父节点，u为叔叔节点

根据u的情况，可以将插入分成两个部分：

cur为红，p为红，u存在且为红
cur为红，p为红，u存在且为黑/u不存在，g为黑

3.1 cur为红，p为红，u存在且为红

在这种情况下，只需要将p和u节点颜色变成黑色就可以解决。上图展示的是g为根节点情况，假设g不是根节点就需要继续向上调整。代码如下：

if (uncle&&uncle->_color == RED)
{parent->_color = uncle->_color = BLACK;grandparent->_color = RED;if (grandparent == nullptr){grandparent->_color = BLACK;}else{grandparent = pcur;parent = grandparent->_pParent;}
}

3.2 cur为红，p为红，u存在且为黑/u不存在，g为黑

u的情况有两种：

u不存在：那么cur一定是新插入的节点，因为如果cur不是新插入的节点，cur和p一定会有一个节点颜色是黑色，就不满足性质四：每条路径黑色节点数均相同。

左边高需要向右旋保持平衡，又为了保持红黑树性质则需要p->black,g->red

u存在：则一定是黑色的，那么cur原来节点一定是黑色的，现在看到是红色的原因就是再调整过程中将cur节点颜色由黑色改成红色。

为了保持平衡，需要先向左旋转再向右旋转，又为了保持红黑树性质则需要p->black,g->red

代码示例：以p是g的左孩子为例

	//叔叔不存在/存在颜色为黑色else{//     g//   p   u// cif (pcur == parent->_pLeft){grandparent->_color = RED;parent->_color = BLACK;RotateR(grandparent);}//      g//    p   u//      celse{grandparent->_color = RED;parent->_color = BLACK;RotateL(parent);RotateR(grandparent);}break;}
}

当p是g的右孩子也类似。

代码示例：

		//叔叔存在并且颜色为红色if (uncle && uncle->_color == RED){parent->_color = uncle->_color = BLACK;grandparent->_color = RED;if (grandparent == nullptr){grandparent->_color = BLACK;}else{grandparent = pcur;parent = grandparent->_pParent;}}//叔叔不存在/存在颜色为黑色else{//     g//   u   p//         cif (pcur == parent->_pRight){grandparent->_color = RED;parent->_color = BLACK;RotateL(grandparent);}//      g//    u   p//      celse{grandparent->_color = RED;parent->_color = BLACK;RotateR(parent);RotateL(grandparent);}break;}}
}

四.红黑树的测试

红黑树的检测分为两步：

检测其是否满足二叉搜索树(中序遍历是否为有序序列)
检测其是否满足红黑树的性质

检测是否有序：

void Inorder()
{_Inorder(_phead);cout << endl;
}
void _Inorder(node*root)
{if (root == nullptr){return;}_Inorder(root->_pLeft);cout << root->_data << " ";_Inorder(root->_pRight);
}

检测是否符合红黑树性质：

	bool IsBSTree(){if (_phead == nullptr){return true;//空树也是合法的红黑树}// 检测根节点是否满足情况if (_phead->_color == RED){cout << "违反性质2：根节点为黑色" << endl;return false;}// 获取任意一条路径中黑色节点的个数size_t blackcount = 0;node* pcur = _phead;while (pcur){if (pcur->_color == BLACK){blackcount++;}pcur = pcur->_pLeft;}// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数size_t k = 0;return _IsBSTree(_phead, k, blackcount);}
private:bool _IsBSTree(node* root, size_t k, const size_t blackcount){//走到null之后，判断k和blackcount是否相等if (root == nullptr){if (k != blackcount){cout << "违反性质4：每一条路径的黑色节点数应该相同" << endl;return false;}return true;}// 统计黑色节点的个数if (root->_color == BLACK){k++;}// 检测当前节点与其双亲是否都为红色node* parent = root->_pParent;if (parent && parent->_color == RED && root->_color == RED){cout << "违反性质3：没有连在一起的红色节点" << endl;return false;}return _IsBSTree(root->_pLeft,k,blackcount) && _IsBSTree(root->_pRight,k,blackcount);}

完整代码示例：

#pragma once
#include <iostream>
using namespace std;
enum Color
{RED,BLACK
};
template<class T>
struct RBNode
{RBNode<T>* _pLeft;RBNode<T>* _pRight;RBNode<T>* _pParent;T _data;Color _color;RBNode(const T& data=T(),Color color=RED):_pLeft(nullptr),_pRight(nullptr),_pParent(nullptr),_data(data),_color(color){}};
template<class T>
class RBTree
{typedef RBNode<T> node;
public:RBTree(){}bool insert(const T& data){if (_phead == nullptr){_phead = new node(data);_phead->_color = BLACK;return true;}node* parent = nullptr;node* pcur = _phead;while (pcur){//parent = pcur;if (data < pcur->_data){parent = pcur;pcur = parent->_pLeft;}else if (data > pcur->_data){parent = pcur;pcur = parent->_pRight;}else{return false;}}//node* newnode = new node(data);pcur = new node(data);pcur->_color = RED;if (data > parent->_data){parent->_pRight = pcur;}else{parent->_pLeft = pcur;}pcur->_pParent = parent;while (parent && parent->_color == RED){node* grandparent = parent->_pParent;if (parent == grandparent->_pLeft){node*uncle = grandparent->_pRight;//叔叔存在并且颜色为红色if (uncle&&uncle->_color == RED){parent->_color = uncle->_color = BLACK;grandparent->_color = RED;pcur=grandparent;parent = pcur->_pParent;}//叔叔不存在/存在颜色为黑色else{//     g//   p   u// cif (pcur == parent->_pLeft){RotateR(grandparent);grandparent->_color = RED;parent->_color = BLACK;}//      g//    p   u//      celse{RotateL(parent);RotateR(grandparent);grandparent->_color = RED;//parent->_color = BLACK;pcur->_color = BLACK;//newparent->_color = BLACK;}break;}}else{node* uncle = grandparent->_pLeft;//叔叔存在并且颜色为红色if (uncle && uncle->_color == RED){parent->_color = uncle->_color = BLACK;grandparent->_color = RED;pcur = grandparent;parent = pcur->_pParent;}//叔叔不存在/存在颜色为黑色else{//     g//   u   p//         cif (pcur == parent->_pRight){RotateL(grandparent);grandparent->_color = RED;parent->_color = BLACK;}//      g//    u   p//      celse{RotateR(parent);//node* newparent = grandparent->_pLeft;RotateL(grandparent);grandparent->_color = RED;//newparent->_color = BLACK;pcur->_color = BLACK;//parent->_color = BLACK;}break;}}}_phead->_color = BLACK;return true;}void Inorder(){_Inorder(_phead);cout << endl;}bool IsBSTree(){if (_phead == nullptr){return true;//空树也是合法的红黑树}// 检测根节点是否满足情况if (_phead->_color == RED){cout << "违反性质2：根节点为黑色" << endl;return false;}// 获取任意一条路径中黑色节点的个数size_t blackcount = 0;node* pcur = _phead;while (pcur){if (pcur->_color == BLACK){blackcount++;}pcur = pcur->_pLeft;}// 检测是否满足红黑树的性质，k用来记录路径中黑色节点的个数size_t k = 0;return _IsBSTree(_phead, k, blackcount);}
private:void _Inorder(node*root){if (root == nullptr){return;}_Inorder(root->_pLeft);cout << root->_data << " ";_Inorder(root->_pRight);}bool _IsBSTree(node* root, size_t k, const size_t blackcount){//走到null之后，判断k和blackcount是否相等if (root == nullptr){if (k != blackcount){cout << "违反性质4：每一条路径的黑色节点数应该相同" << endl;return false;}return true;}// 统计黑色节点的个数if (root->_color == BLACK){k++;}// 检测当前节点与其双亲是否都为红色node* parent = root->_pParent;if (parent && parent->_color == RED && root->_color == RED){cout << "违反性质3：没有连在一起的红色节点" << endl;return false;}return _IsBSTree(root->_pLeft,k,blackcount) && _IsBSTree(root->_pRight,k,blackcount);}// 右单旋void RotateR(node* parent){node* subl = parent->_pLeft;node* sublr = subl->_pRight;parent->_pLeft = sublr;subl->_pRight = parent;if (sublr){sublr->_pParent = parent;}node* pparent = parent->_pParent;parent->_pParent = subl;if (_phead == parent){_phead = subl;subl->_pParent = nullptr;}else{if (pparent->_pLeft == parent){pparent->_pLeft = subl;}else{pparent->_pRight = subl;}subl->_pParent = pparent;}}// 左单旋void RotateL(node* parent){node* subr = parent->_pRight;node* subrl = subr->_pLeft;parent->_pRight = subrl;if (subrl)subrl->_pParent = parent;node* pparent = parent->_pParent;subr->_pLeft = parent;parent->_pParent = subr;if (pparent == nullptr){_phead = subr;subr->_pParent = nullptr;}else{if (pparent->_pLeft == parent){pparent->_pLeft = subr;}else{pparent->_pRight = subr;}subr->_pParent = pparent;}}
private:node* _phead;
};

查看全文

http://www.xdnf.cn/news/449083.html