做单屏网站 高度是多少,公司起什么名字好,松原网站建设哪家专业,中企动力做的网站升级收费红黑树一、红黑树的概念二、红黑树的接口2.1 插入三、验证四、源码一、红黑树的概念 红黑树也是一个二叉搜索树#xff0c;他是通过对任何一条从根到叶子的路径上各个结点着色方式的限制#xff0c;最长路径长度不超过最短路径长度的 2 倍保持近似平衡。他在每个节点添加了一…
红黑树一、红黑树的概念二、红黑树的接口2.1 插入三、验证四、源码一、红黑树的概念 红黑树也是一个二叉搜索树他是通过对任何一条从根到叶子的路径上各个结点着色方式的限制最长路径长度不超过最短路径长度的 2 倍保持近似平衡。他在每个节点添加了一个变量用来表示颜色 Black或者Red为了满足上面的条件着色必须满足性质 1️⃣每个结点不是红色就是黑色 2️⃣ 根节点是黑色的 3️⃣ 如果一个节点是红色的则它的两个孩子结点是黑色的(没有连续的红色节点) 4️⃣ 对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点 5️⃣ 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 由此可以满足最长路径长度不超过最短路径长度的 2 倍通过第四点就可以看出。
既然不能保证绝对平衡那么搜索性能肯定不如AVL树那么为什么还要有红黑树呢 首先要知道AVL树保持平衡的方法是频繁的旋转而红黑树则不需要严格的平衡会少很多旋转。 二、红黑树的接口
红黑树节点定义 节点需要有个颜色的变量可以使用枚举的方法
enum Colour
{RED,BLACK,
};template class K, class V
struct RBTreeNode
{RBTreeNode(const pairK, V kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}pairK, V _kv;AVLNodeK, V* _left;AVLNodeK, V* _right;AVLNodeK, V* _parent;Colour _col;
};2.1 插入
我们可以看到节点初始化的时候默认为RED因为如果要插入BLACK那么一定会导致错误不满足对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点。 所以只能把新节点默认设置为RED因为如果是红色有可能父节点是黑色这样就没有出现连续的红色。 总结一下 插入黑色节点一定有问题插入红色节点有可能会出问题。 插入的流程根AVL树一样检查父亲节点如果是黑就结束如果是红就要调整红黑树。
为了方便说明cur为当前节点p为父节点g为祖父节点u为叔叔节点 首先要知道最主要的是看u 情况一cur为红p为红g为黑u存在且为红 : 为什么要看u节点因为如果cur为红且p为红那么g一定为黑。所以唯一的变数就为u
它的调整方法为 首先p肯定要变黑而为了使g两边的子树黑节点数目相同u也要变黑。至于g我们先把它变红因为如果这颗树是子树而g还是黑那么相当于这颗子树的黑节点多了一个会影响到别的子树。如果g为根那么就把g变为黑。 这里要注意继续往上处理 把g当成cur继续向上调整。
举个例子 可以看到绿色部分就为上面的抽象图就这么往上循环改变颜色即可。
情况二cur为红p为红g为黑u不存在/u为黑 此时要对u分情况讨论
1️⃣ u不存在时那么cur一定是新增节点因为如果cur不是新增节点那么cur和p一定有一个节点为黑这样就不满足黑节点数目相同的条件。 处理方式就为右单旋
2️⃣ u存在且为黑 总结一下 u不存在则cur是新增节点u存在那么就是由情况一变换过来的。 情况二的处理方法就是旋转变色。 情况三: cur为红p为红g为黑u不存在/u为黑 情况三与情况二的区别就是情况二是直线情况三是折线经过AVL的学习我们知道这种情况要双旋。 情况三也是由其他情况变过来的。 此时我们就需要进行双旋调整红黑树。 左单旋后变成了情况二那么按照情况二的方法进行右旋即可。 以上三种情况的代码如下
while (parent parent-_col RED)
{// 找g 与 uNode* g parent-_parent;if (parent g-_left){Node* u g-_right;// 情况一 u存在且为红if (u u-_col RED){parent-_col u-_col BLACK;g-_col RED;// 继续往上处理cur g;parent cur-_parent;}else // 情况二或情况三{if (cur parent-_left)// 情况二{// g// p// cRotateR(g);parent-_col BLACK;g-_col RED;}else// 情况三{// g// p// cRotateL(parent);RotateR(g);// c// p gcur-_col BLACK;g-_col RED;}break;}}else{Node* u g-_left;// 情况一if (u u-_col RED){u-_col parent-_col BLACK;g-_col RED;cur g;parent cur-_parent;}else{// 情况二// g// p// cif (cur parent-_right){RotateL(g);parent-_col BLACK;g-_col RED;}else// 情况三{// g// p// cRotateR(parent);RotateL(g);cur-_col BLACK;g-_col RED;}break;}}
}
// 上面有可能把_root的颜色变为红
_root-_col BLACK;
return true;
}三、验证
想要验证是否是红黑树首先要保证是搜索树中序遍历有序。 其次还要判断根节点是否为黑是否有两个红的相连检查红节点的父亲每条路径上的黑节点数目相同随便找一条路径测出标准值。
怎么测每条路径的黑节点数目是否相同 测一条路径的黑节点数目当作标准值递归过程中遇到黑节点就记录到空说明该路径走完比对标准值如果不同就返回false。 bool _IsBalance(Node* root, int i, int flag)
{if (root nullptr){if (i ! flag){cout errno: 左右子树黑色节点数目不同 endl;return false;}return true;}// 红节点时判断父亲if (root-_col RED){if (root-_parent-_col RED){cout errno: 红-红 endl;return false;}}if (root-_col BLACK){i;}return _IsBalance(root-_left, i, flag) _IsBalance(root-_right, i, flag);
}bool IsBalance()
{if (_root nullptr){return true;}if (_root-_col ! BLACK){return false;}// 找标准值Node* cur _root;int flag 0;while (cur){if (cur-_col BLACK){flag;}cur cur-_left;}int i 0;return _IsBalance(_root, i, flag);
}四、源码
#pragma once
#include iostream
#include cstdlib
#include cassert
#include stringusing namespace std;enum Colour
{RED,BLACK,
};template class K, class V
struct RBTreeNode
{RBTreeNode(const pairK, V kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){}pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Colour _col;
};template class K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:bool insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* parent nullptr;Node* cur _root;while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else return false;}cur new Node(kv);if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;while (parent parent-_col RED){// 找g 与 uNode* g parent-_parent;if (parent g-_left){Node* u g-_right;// 情况一 u存在且为红if (u u-_col RED){parent-_col u-_col BLACK;g-_col RED;// 继续往上处理cur g;parent cur-_parent;}else // 情况二或情况三{if (cur parent-_left)// 情况二{// g// p// cRotateR(g);parent-_col BLACK;g-_col RED;}else// 情况三{// g// p// cRotateL(parent);RotateR(g);// c// p gcur-_col BLACK;g-_col RED;}break;}}else{Node* u g-_left;// 情况一if (u u-_col RED){u-_col parent-_col BLACK;g-_col RED;cur g;parent cur-_parent;}else{// 情况二// g// p// cif (cur parent-_right){RotateL(g);parent-_col BLACK;g-_col RED;}else// 情况三{// g// p// cRotateR(parent);RotateL(g);cur-_col BLACK;g-_col RED;}break;}}}// 上面有可能把_root的颜色变为红_root-_col BLACK;return true;}void RotateL(Node* parent){Node* top parent-_parent;Node* right parent-_right;parent-_right right-_left;if (right-_left) right-_left-_parent parent;right-_left parent;parent-_parent right;if (top)// 子树{if (parent top-_left) top-_left right;else top-_right right;right-_parent top;}else// 完整的树{_root right;_root-_parent nullptr;}}void RotateR(Node* parent){Node* top parent-_parent;Node* left parent-_left;Node* leftR left-_right;parent-_left leftR;if (leftR) leftR-_parent parent;left-_right parent;parent-_parent left;if (top){if (parent top-_left) top-_left left;else top-_right left;left-_parent top;}else{_root left;_root-_parent nullptr;}}void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first root-_kv.second endl;_Inorder(root-_right);}void Inorder(){_Inorder(_root);}bool _IsBalance(Node* root, int i, int flag){if (root nullptr){if (i ! flag){cout errno: 左右子树黑色节点数目不同 endl;return false;}return true;}// 红节点时判断父亲if (root-_col RED){if (root-_parent-_col RED){cout errno: 红-红 endl;return false;}}if (root-_col BLACK){i;}return _IsBalance(root-_left, i, flag) _IsBalance(root-_right, i, flag);}bool IsBalance(){if (_root nullptr){return true;}if (_root-_col ! BLACK){return false;}// 找标准值Node* cur _root;int flag 0;while (cur){if (cur-_col BLACK){flag;}cur cur-_left;}int i 0;return _IsBalance(_root, i, flag);}private:Node* _root nullptr;
};void test()
{RBTreeint, int bb;const int N 10000;srand(time(0));for (int i 0; i N; i){size_t x rand();bb.insert(make_pair(x, x));}/*int a[] { 16, 3, 7, 11, 9, 26, 18, 14};for (auto e : a){bb.insert(make_pair(e, e));}*/cout bb.IsBalance();
}
