上海建设网站是国家级吗,做产品的往这看 国外工业设计网站大全,北京科技公司排名,电商网站wordpress文章目录一、红黑树的概念二、红黑树的性质三、红黑树节点的定义四、红黑树的插入操作五、红黑树的验证五、红黑树的删除六、红黑树与AVL树的比较七、红黑树的应用八、红黑树模拟实现一、红黑树的概念 红黑树#xff0c;是一种二叉搜索树#xff0c;但在每个结点上增加一个存…
文章目录一、红黑树的概念二、红黑树的性质三、红黑树节点的定义四、红黑树的插入操作五、红黑树的验证五、红黑树的删除六、红黑树与AVL树的比较七、红黑树的应用八、红黑树模拟实现一、红黑树的概念 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 二、红黑树的性质
每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的则它的两个孩子结点是黑色的即树中没有连续的红色节点对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点即每条路径的黑色节点数量相等每个叶子结点(这里的叶子结点指的是空结点也叫做NIL节点 都是黑色的 红黑树中第三和第四条规则构成互斥极限的最短一定是全黑极限的最长一定是一黑一红 。 三、红黑树节点的定义
enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv){}pairK, V _kv; //节点的值域Colour _col; //节点的颜色RBTreeNodeK, V* _left; //节点的左孩子RBTreeNodeK, V* _right; //节点的右孩子RBTreeNodeK, V* _parent; //节点的双亲
};四、红黑树的插入操作 红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步一、按照二叉搜索的树规则插入新节点。二、检测新节点插入后红黑树的性质是否造到破坏。 因为新节点的默认颜色是红色如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连续的红色节点此时需要对红黑树分情况来讨论。 情况一: cur为红p为红g为黑u存在且为红 cur为当前节点p为父节点g为祖父节点u为叔叔节点。此处看到的树可能是一颗完整的树但是也有可能是一颗子树。 解决方式是将将p,u改为黑g改为红。继续把g当成curg是根节点需要将g改为黑色如果g是子树且g的双亲颜色为红色则需要继续向上调整。 情况二: cur为红p为红g为黑u不存在/u存在且为黑 如果u节点不存在那么cur一定为新插入的节点否则就违反性质4。如果u节点存在则一定是黑色的cur之前也是黑色的因为新增节点是a、b节点所以现在它是红色。 解决方式如果p为g的左孩子cur为p的左孩子则进行右单旋转p为g的右孩子cur为p的右孩子则进行左单旋转。然后再将p变黑g变红。 情况三: cur为红p为红g为黑u不存在/u存在且为黑 解决方式如果p为g的左孩子cur为p的右孩子则针对p做左单旋转如果p为g的右孩子cur为p的左孩子则针对p做右单旋转。旋转后就转变为了情况二。 总结 在这三种情况中都有cur为红p为红g为黑可以看出红黑树的关键是叔叔。U存在且为红则变色继续往上处理U不存在或为黑则旋转加变色。 情况二和情况三的主要区别是单旋和双旋的不同。从图中可以看出当p g cur为一条直线的时候也就是情况二单旋即可p g cur 为一条折线的时候也就是情况三需要双旋。 代码实现
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 (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfater parent-_parent;assert(grandfater);assert(grandfater-_col BLACK);// 关键看叔叔if (parent grandfater-_left){Node* uncle grandfater-_right;// 情况一 : uncle存在且为红变色继续往上处理if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater;parent cur-_parent;}// 情况二三uncle不存在 存在且为黑else{// 情况二右单旋变色// g // p u// cif (cur parent-_left){RotateR(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况三左右单旋变色// g // p u// cRotateL(parent);RotateR(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}else // (parent grandfater-_right){Node* uncle grandfater-_left;// 情况一if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater;parent cur-_parent;}else{// 情况二左单旋变色// g // u p// cif (cur parent-_right){RotateL(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况三右左单旋变色// g // u p// cRotateR(parent);RotateL(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}}_root-_col BLACK;return true;
}五、红黑树的验证 红黑树的检测分为两步一、检测其是否满足二叉搜索树这里只需要中序遍历是否为有序序列即可。二、检测其是否满足红黑树的性质。
public:bool IsBalance(){if (_root nullptr){return true;}if (_root-_col RED){cout 根节点不是黑色 endl;return false;}int benchmark 0;return PrevCheck(_root, 0, benchmark);}
private:bool PrevCheck(Node* root, int blackNum, int benchmark){if (root nullptr){if (benchmark 0){benchmark blackNum;return true;}if (blackNum ! benchmark){cout 某条黑色节点的数量不相等 endl;return false;}else{return true;}}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return PrevCheck(root-_left, blackNum, benchmark) PrevCheck(root-_right, blackNum, benchmark);}五、红黑树的删除 红黑树的删除过于复杂可以参考 红黑树的删除 这篇博客 六、红黑树与AVL树的比较 红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(log2Nlog_2 Nlog2N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。 七、红黑树的应用 红黑树的应用场景建议观看这个视频讲解红黑树在linux中的3种应用场景
八、红黑树模拟实现
#pragma once
#includeiostream
#includeassert.h
using namespace std;enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv){}pairK, V _kv;Colour _col;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;
};templateclass K, class V
struct 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 (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfater parent-_parent;assert(grandfater);assert(grandfater-_col BLACK);// 关键看叔叔if (parent grandfater-_left){Node* uncle grandfater-_right;// 情况一 : uncle存在且为红变色继续往上处理if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater;parent cur-_parent;}// 情况二三uncle不存在 存在且为黑else{// 情况二右单旋变色// g // p u// cif (cur parent-_left){RotateR(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况三左右单旋变色// g // p u// cRotateL(parent);RotateR(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}else // (parent grandfater-_right){Node* uncle grandfater-_left;// 情况一if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfater-_col RED;// 继续往上处理cur grandfater;parent cur-_parent;}else{// 情况二左单旋变色// g // u p// cif (cur parent-_right){RotateL(grandfater);parent-_col BLACK;grandfater-_col RED;}else{// 情况三右左单旋变色// g // u p// cRotateR(parent);RotateL(grandfater);cur-_col BLACK;grandfater-_col RED;}break;}}}_root-_col BLACK;return true;}void InOrder(){_InOrder(_root);cout endl;}bool IsBalance(){if (_root nullptr){return true;}if (_root-_col RED){cout 根节点不是黑色 endl;return false;}// 黑色节点数量基准值int benchmark 0;return PrevCheck(_root, 0, benchmark);}private:bool PrevCheck(Node* root, int blackNum, int benchmark){if (root nullptr){if (benchmark 0){benchmark blackNum;return true;}if (blackNum ! benchmark){cout 某条黑色节点的数量不相等 endl;return false;}else{return true;}}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return PrevCheck(root-_left, blackNum, benchmark) PrevCheck(root-_right, blackNum, benchmark);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;Node* ppNode parent-_parent;subR-_left parent;parent-_parent subR;if (_root parent){_root subR;subR-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR){subLR-_parent parent;}Node* ppNode parent-_parent;subL-_right parent;parent-_parent subL;if (_root parent){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}
private:Node* _root nullptr;
};
