网站备案幕布ps,官网建设开发哪家公司好,做马来西亚生意的网站,电子公章印章在线制作目录 一、红黑树的概念
二、红黑树的性质
三、红黑树节点的定义
四、红黑树的插入#xff08;步骤#xff09;
1.为什么新插入的节点必须给红色#xff1f;
2、插入红色节点后#xff0c;判定红黑树性质是否被破坏
五、插入出现连续红节点情况分析图解#xff08;看…目录 一、红黑树的概念
二、红黑树的性质
三、红黑树节点的定义
四、红黑树的插入步骤
1.为什么新插入的节点必须给红色
2、插入红色节点后判定红黑树性质是否被破坏
五、插入出现连续红节点情况分析图解看uncle节点
5.1、uncle存在且为红
5.2、uncle不存在
1、单旋
2、双旋
5.3、uncle存在且为黑
1、单旋
2、双旋
六、插入总结
1、红黑树插入的两种步骤 2、插入代码
七、红黑树总结及代码 一、红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制
红黑树确保——没有一条路径会比其他路径长出两倍因而是接近平衡的 二、红黑树的性质 1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的则它的两个孩子结点是黑色的 没有连续的红节点 4. 从任一结点到其所有后代叶结点的简单路径上均包含相同数目的黑结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是NIL空结点) 最优情况全黑或每条路径都是一黑一红的满二叉树高度logN 最差情况每颗子树左子树全黑右子树一黑一红。高度2*logN。 可以发现最坏情况的时间复杂度和AVL树一样都是O(logN)但是红黑树这种近似平衡的结构减少了大量旋转综合性能优于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){}
}; 四、红黑树的插入步骤 1.为什么新插入的节点必须给红色
1新节点给红色可能出现连续红节点
2如果新节点给黑色必定会违反性质4其每条路径的黑色节点数量相同 2、插入红色节点后判定红黑树性质是否被破坏
因为新节点的默认颜色是红色所以
1双亲节点的颜色是黑色没有违反红黑树任何 性质则不需要调整
2双亲节点为红色就会出现连续的红节点此时需要对红黑树分情况来讨论见下一部分 五、插入出现连续红节点情况分析图解看uncle节点
约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点
下面的分析都是以p为g的左孩子为例 5.1、uncle存在且为红 cur插入后p和u变黑g变红
1g没有父亲g为根g变黑
2g有父亲。其为黑结束其为红后把g当成cur继续向上调整
5.2、uncle不存在
u不存在则cur一定是新插入的节点。
如果cur不是新插入的节点则cur和p一定有一个节点是黑色否则每条路径黑色节点不相同
下图为解释 1、单旋 右单旋 2、双旋 左单旋 右单旋 5.3、uncle存在且为黑
uncle存在且为黑是情况一变来的所以cur原来的节点一定是黑色的。
现在其是红色的原因是cur的子树在调整过程中将cur的颜色由黑变红。
1、单旋 右单旋
2、双旋 左单旋 右单旋 六、插入总结
1、红黑树插入的两种步骤 1、uncle存在且为红 2、uncle不存在 或者 uncle存在且为黑 通过分析
uncle不存在的单旋 和 uncle存在且为黑的单旋 可以写在一起
uncle不存在的双旋 和 uncle存在且为黑的双旋 可以写在一起
不论uncle存在或者不存在都不影响此步的单旋或者双旋。 当p为g的右孩子时操作都相反。
详细步骤见其中while (parent parent-_col RED)这一步。 2、插入代码
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* grandfather parent-_parent;//p为g左孩子if (parent grandfather-_left){Node* uncle grandfather-_right;// 情况1u存在且为红 if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else // u不存在 或 存在且为黑{//情况2.1 3.1if (cur parent-_left){// g// p// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else//情况2.2 , 3.2{// g// p// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}//p为g右孩子else // parent grandfather-_right{Node* uncle grandfather-_left;// u存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else{if (cur parent-_right){// g// p// cRotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;
} 七、红黑树总结及代码
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(logN)红黑树不追求绝对平衡只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数 所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。 using namespace std;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
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* grandfather parent-_parent;//p为g左孩子if (parent grandfather-_left){Node* uncle grandfather-_right;// 情况1u存在且为红 if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else // u不存在 或 存在且为黑{//情况2.1 3.1if (cur parent-_left){// g// p// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else//情况2.2 , 3.2{// g// p// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}//p为g右孩子else // parent grandfather-_right{Node* uncle grandfather-_left;// u存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else{if (cur parent-_right){// g// p// cRotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}void RotateL(Node* parent){_rotateCount;Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;if (curleft){curleft-_parent parent;}cur-_left parent;Node* ppnode parent-_parent;parent-_parent cur;if (parent _root){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}void RotateR(Node* parent){_rotateCount;Node* cur parent-_left;Node* curright cur-_right;parent-_left curright;if (curright)curright-_parent parent;Node* ppnode parent-_parent;cur-_right parent;parent-_parent cur;if (ppnode nullptr){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}bool CheckColour(Node* root, int blacknum, int benchmark){if (root nullptr){if (blacknum ! benchmark)return false;return true;}if (root-_col BLACK){blacknum;}if (root-_col RED root-_parent root-_parent-_col RED){cout root-_kv.first 出现连续红色节点 endl;return false;}return CheckColour(root-_left, blacknum, benchmark) CheckColour(root-_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root nullptr)return true;if (root-_col ! BLACK){return false;}// 基准值int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}return CheckColour(root, 0, benchmark);}int Height(){return Height(_root);}int Height(Node* root){if (root nullptr)return 0;int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}private:Node* _root nullptr;public:int _rotateCount 0;
};
