网站怎么做vga头,龙岩网站建设方案书,吉林省软环境建设网站,织梦网站后台怎么登陆前言#xff1a;本篇文章我们继续来分享C中的另一个复杂数据结构——红黑树。 目录
一.红黑树概念
二.红黑树性质
三.红黑树实现
1.基本框架
2.插入
3.判断平衡 四.完整代码
总结 一.红黑树概念
红黑树#xff0c;是一种二叉搜索树#xff0c;但在每个结点上增加一个…前言本篇文章我们继续来分享C中的另一个复杂数据结构——红黑树。 目录
一.红黑树概念
二.红黑树性质
三.红黑树实现
1.基本框架
2.插入
3.判断平衡 四.完整代码
总结 一.红黑树概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出两倍因而是接近平衡的。 二.红黑树性质 每个结点不是红色就是黑色 根节点是黑色的 如果一个节点是红色的则它的两个孩子结点是黑色的不存在连续的红色节点 对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点每条路径都存在相同数量的黑色节点 每个叶子结点都是黑色的(此处的叶子结点指的是空结点NULL)
如何理解红黑树最长路径不超过最短路径的二倍呢 从性质能够看出红黑树每一条路径上都有相同数量的黑色节点。红黑树每条路径上可以存在连续的黑色节点但不能存在连续的红色节点。所以最短路径即为全是黑色节点的路径。最长路径则为一黑一红相间的路径。 三.红黑树实现
1.基本框架
红黑树与AVL树相比多了节点颜色这一信息为了实现这一信息我们使用枚举
enum Colour
{RED,BLACK
};templateclass K,class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_col(RED){}
};
templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:private:Node* _root nullptr;size_t _size 0;
};
同时我们多创建一个_size成员变量用于记录节点数量。 2.插入
红黑树插入的基本步骤与二叉搜索树和AVL树一样都是按照左子节点比根节点小右子节点比根节点大的规则唯一不同的是红黑树的插入要考虑其性质。其中最值得注意的性质为
不存在连续的红节点每条路径上的黑节点数相等 其中能够看出第二条才是最关键的因此我们每次新插入节点时必须插入红节点。
此时我们会面临两种情况
父节点为黑色插入即结束无需调整。父节点为红色不满足上述性质1需要调整。
下面我们来看特殊情况
父亲为红节点那么只有将父节点变为黑色节点才能够满足性质。
但是如果父亲变为黑节点就说明该路径上同样多出一个黑节点而唯一的处理手段就是让父亲的父亲也就是爷爷节点变为红色节点。
此时又存在问题那就是关于父亲的兄弟节点也就是叔叔节点那么叔叔节点存在三种情况
叔叔节点同样为红色。叔叔节点不存在。叔叔节点为黑色。
如果叔叔节点为红色为了满足各路径黑节点数量相同叔叔节点则需要和父节点一起变为黑色。
如果叔叔节点不存在为了满足性质需要将该子树从爷爷节点的位置进行旋转。
如果叔叔节点为黑色而父节点为红色如果还要满足性质说明子节点原本应为黑色是因为经过了上述的调整而作为爷爷节点变成了红色。此时我们仍需从爷爷节点的位置进行旋转。
分析完上述完整情况之后还有关于新插入节点的两种情况
父节点为爷爷节点的左子节点同时新增节点也为父节点的左子节点为一条斜线。父节点为爷爷节点的左子节点但是新增节点也为父节点的有子节点为一条折线。
斜线情况下我们在需要旋转时只需单旋即可
而当为折线时就需要进行双旋先变为斜线在进行调整。
同时父节点也需要考虑是爷爷节点的左节点还是右节点两种情况彼此的规则相反。
按照上边的步骤我们能够得出代码情况
//插入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 (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);cur-_col RED;//新增节点给红色if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//parent是黑色就结束while (parent parent-_col RED){Node* Grandfather parent-_parent;if (parent Grandfather-_left){Node* uncle Grandfather-_right;if (uncle uncle-_col RED)//叔叔存在且为红直接变色{parent-_col BLACK;uncle-_col BLACK;Grandfather-_col RED;//继续往上处理cur Grandfather;parent Grandfather-_parent;}else//叔叔不存在或叔叔存在但为黑{if (cur parent-_left)//左边直接右旋{RotateR(Grandfather);parent-_col BLACK;Grandfather-_col RED;}else//右边则左右双旋{RotateL(parent);RotateR(Grandfather);cur-_col BLACK;Grandfather-_col RED;}break;}}else{Node* uncle Grandfather-_left;if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;Grandfather-_col RED;cur Grandfather;parent Grandfather-_parent;}else{if (cur parent-_right){RotateL(Grandfather);Grandfather-_col RED;parent-_col BLACK;}else{RotateR(parent);RotateL(Grandfather);cur-_col BLACK;Grandfather-_col RED;}break;}}}_root-_col BLACK;return true;} 需要考虑的情况确实很多但如果自己画图认真分析理解起来还是易如反掌的。 3.判断平衡
判断红黑树的平衡我们自然要从其性质入手
首先就是判断根节点是否为黑色。其次容易判断的是是否有两个相邻的红色节点注意这里我们不去判断一个节点与其子节点反而去判断一个节点与其父节点。因为如果判断子节点则可能需要判断两次而父节点则只需判断一次。最后就是判断所有路径上的黑节点数量是否相同。
其中前两种都比较容易想到代码方式最重要的是如何比较黑节点的数量。
我们可以通过增加参数的方式。来记录到达每个节点位置时该路径上出现过的黑节点的数量。而如何进行比较因为每条路径上黑节点的数量都必须相同所以我们直接记录一下最左边的一条路径上黑节点的数量然后求出一条路径上的黑节点数之后就进行比较即可。 //判断平衡bool IsBalance(){if (_root-_col RED)return false;int refnum 0;Node* cur _root;while (cur){if (cur-_col BLACK)refnum;cur cur-_left;}return Check(_root, 0, refnum);}bool Check(Node* root, int BlackNum,const int refnum){if (root nullptr){if (refnum ! BlackNum){cout 存在黑色节点个数不相等 endl;return false;}cout BlackNum endl;return true;}if (root-_col RED root-_parent-_col RED){cout root-_kv.first -存在连续的红色节点 endl;return false;}if (root-_col BLACK)BlackNum;return Check(root-_left, BlackNum,refnum) Check(root-_right, BlackNum,refnum);} 四.完整代码
enum Colour
{RED,BLACK
};templateclass K,class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_col(RED){}
};
templateclass 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 (cur-_kv.first kv.first){parent cur;cur cur-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv);cur-_col RED;//新增节点给红色if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//parent是黑色就结束while (parent parent-_col RED){Node* Grandfather parent-_parent;if (parent Grandfather-_left){Node* uncle Grandfather-_right;if (uncle uncle-_col RED)//叔叔存在且为红直接变色{parent-_col BLACK;uncle-_col BLACK;Grandfather-_col RED;//继续往上处理cur Grandfather;parent Grandfather-_parent;}else//叔叔不存在或叔叔存在但为黑{if (cur parent-_left)//左边直接右旋{RotateR(Grandfather);parent-_col BLACK;Grandfather-_col RED;}else//右边则左右双旋{RotateL(parent);RotateR(Grandfather);cur-_col BLACK;Grandfather-_col RED;}break;}}else{Node* uncle Grandfather-_left;if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;Grandfather-_col RED;cur Grandfather;parent Grandfather-_parent;}else{if (cur parent-_right){RotateL(Grandfather);Grandfather-_col RED;parent-_col BLACK;}else{RotateR(parent);RotateL(Grandfather);cur-_col BLACK;Grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}//右单旋void RotateR(Node* parent){//定义左子节点Node* subL parent-_left;//定义左子节点的右子节点Node* subLR subL-_right;//调整parent-_left subLR;//判空if (subLR)subLR-_parent parent;//调整subL-_right parent;Node* ppNode parent-_parent;parent-_parent subL;if (parent _root)//判断是否为根{_root subL;_root-_parent nullptr;}else//不是根节点调整父节点指向{if (ppNode-_left parent)ppNode-_left subL;elseppNode-_right subL;subL-_parent ppNode;}}//左单旋void RotateL(Node* parent){//定义右子节点Node* subR parent-_right;//定义右子节点的左子节点Node* subRL subR-_left;//调整parent-_right subRL;//判空if (subRL)subRL-_parent parent;//调整subR-_left parent;Node* ppNode parent-_parent;parent-_parent subR;if (parent _root)//判断是否为根{_root subR;_root-_parent nullptr;}else//不是根节点调整父节点指向{if (ppNode-_left parent)ppNode-_left subR;elseppNode-_right subR;subR-_parent ppNode;}}//遍历void InOrder(){inOrder(_root);cout endl;}void inOrder(const Node* root){if (root nullptr){return;}inOrder(root-_left);cout root-_kv.first : root-_kv.second endl;inOrder(root-_right);}//判断平衡bool IsBalance(){if (_root-_col RED)return false;int refnum 0;Node* cur _root;while (cur){if (cur-_col BLACK)refnum;cur cur-_left;}return Check(_root, 0, refnum);}bool Check(Node* root, int BlackNum,const int refnum){if (root nullptr){if (refnum ! BlackNum){cout 存在黑色节点个数不相等 endl;return false;}cout BlackNum endl;return true;}if (root-_col RED root-_parent-_col RED){cout root-_kv.first -存在连续的红色节点 endl;return false;}if (root-_col BLACK)BlackNum;return Check(root-_left, BlackNum,refnum) Check(root-_right, BlackNum,refnum);}
private:Node* _root nullptr;//size_t _size 0;
}; 总结
关于红黑树的知识就分享这么多喜欢本篇文章记得一键三连我们下期再见
