福州网站设计大概费用,哪儿提供邢台做网站,微小店网站建设哪家好,前端低代码开发平台一、红黑树的概念及性质
1.1 红黑树的概念 AVL树用平衡因子让树达到高度平衡 红黑树可以认为是AVL树的改良 通过给每个节点标记颜色让树接近平衡 以减少树在插入节点的旋转 在每个结点新增一个存储位表示结点颜色 可以是Red或Black 通过对任何一条从根到叶子的路径上 各个结点…
一、红黑树的概念及性质
1.1 红黑树的概念 AVL树用平衡因子让树达到高度平衡 红黑树可以认为是AVL树的改良 通过给每个节点标记颜色让树接近平衡 以减少树在插入节点的旋转 在每个结点新增一个存储位表示结点颜色 可以是Red或Black 通过对任何一条从根到叶子的路径上 各个结点着色方式的限制 红黑树确保没有一条路径会比其他路径长出 俩倍因而是接近平衡的 1.2 红黑树的性质
每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的 则它的两个孩子结点是黑色的对于每个结点 从该结点到其所有后代叶结点的简单路径上 均包含相同数目的黑色结点每个叶子结点都是黑色的 (此处的叶子结点指的是空结点) 为啥满足上面性质的红黑树就能保证 其最长路径节点个数不会超过最短路径 节点个数的两倍 由性质3可得出不能出现连续红色节点 由性质4可得出每条路径有相同黑色节点数量
极限情况下 最短路径全黑 最长路径一黑一红
由此可得出 最长路径不会超过最短路径的两倍
1.3 为什么更常用红黑树而不是AVL树
AVL树 是一颗高度平衡的二叉树 查找效率 O ( l o g N ) O(logN) O(logN) 但是这样的效率是在插入元素时 经常性的旋转换来的
红黑树 是一颗接近平衡的二叉树 假设全部黑节点有N个 整棵树的节点数量[N, 2N]之间 最短路径长度 O ( l o g N ) O(logN) O(logN) 最长路径长度 O ( 2 l o g N ) O(2logN) O(2logN) 查找效率 O ( 2 l o g N ) O(2logN) O(2logN)
10亿数据AVL树最多查找30次 红黑树最多也就查找60次 对于cpu的运行速度来说几乎可以忽略不计 但红黑树的规则相对于AVL树没那么严格 在插入元素时不会经常旋转 所以综合而言红黑树更胜一筹
如图 对于AVL树必定旋转 红黑树则不用
二、红黑树模拟实现的基本框架
2.1 红黑树节点的定义
跟AVL树一样 只是AVL树采用平衡因子 让树达到平衡 而红黑树对节点进行颜色标记 让树达到平衡 定义一个枚举表示节点颜色
enum colour
{RED,BLACK,
};template class 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){}
};template class K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:
private:Node* _root nullptr;
};2.2 红黑树的插入
还是和AVL树一样 bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);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);if (parent-_kv.first kv.first){parent-_left cur;}else{parent-_right cur;}// new的节点的parent还指向空cur-_parent parent;// 插入黑色节点还是红色节点return true;}插入走到这里如果是AVL树 此时需要更新平衡因子
红黑树采用的是标记节点颜色 让树达到平衡 需要考虑的是插入什么颜色的节点
插入黑色节点 会违反规则4影响到每条路径插入红色节点 如果插入节点的父节点也是红色节点 则会违反规则3影响当前局部节点
很明显插入红色节点更划算 所有插入的节点都默认是红色 如果违反红黑树的规则再进行调整
三、对插入节点调整的解析
如果插入节点的父节点为黑 则无需处理 如果为红则分为三种情况
情况一
cur为红p为红g为黑u存在且为红
cur为当前节点p为父节点 g为祖父节点u为叔叔节点 把p和u变黑g变红 如果grandfather的parent也为红 把grandfather改为cur 继续按刚才的步骤往后迭代 如果grandfather为根节点 把grandfather改为黑色 颜色调整结束
情况二
cur为红p为红g为黑 u不存在或u存在且为黑
此树可能是完整树也可能是子树 u节点不存在 p为g的左孩子cur为p的左孩子 则进行右单旋转 相反 p为g的右孩子cur为p的右孩子 则进行左单旋转 p、g变色–p变黑g变红 下图则是u节点存在的情况 c为下面4种情况的 任意一种包含一个黑节点的红黑树 d和e可能是空或者一个红节点 插入新节点更新完后 继续往后更新 就是情况二的u存在的情况
情况三
cur为红p为红g为黑 u不存在或u存在且为黑 跟情况二完全类似 只是情况三为双旋 情况二是单旋 p为g的左孩子cur为p的右孩子 则针对p做左单旋转 相反 p为g的右孩子cur为p的左孩子 则针对p做右单旋转
则转换成了情况2 此图为u不存在 u存在参考情况二
四、红黑树插入代码的全部实现
详解都在代码注释 各位友友们请耐心看完
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);if (parent-_kv.first kv.first){parent-_left cur;}else{parent-_right cur;}// new的节点的parent还指向空cur-_parent parent;// 如果新插入节点破坏了红黑树规则// 则更新节点颜色while (parent parent-_col RED){Node* grandfather parent-_parent;if (grandfather-_left parent){Node* uncle grandfather-_right;// 情况1u存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续往上调整cur grandfather;parent cur-_parent;}else // 情况23u不存在或者u存在且为黑旋转处理{// 如果插入节点在父节点的左c、p、g呈一条斜线// g// p u// cif (parent-_left cur){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED; }else{// 插入节点在父节点的右c、p、g呈一条折线// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;// parent-_col RED; // 父亲本就是红变一下双重保险grandfather-_col RED;}break;}}else // (grandfather-_right parent){Node* uncle grandfather-_left;// 情况1u存在且为红变色处理并继续往上处理if (uncle uncle-_col RED){parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续往上调整cur grandfather;parent cur-_parent;}else // 情况23u不存在或者u存在且为黑旋转处理{// g// u p// cif (parent-_right cur){RotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK; // 做个双保险无论那种情况把根都变成黑的return true;
}五、红黑树全部代码模拟实现
gitee链接
✨✨✨✨✨✨✨✨ 本篇博客完感谢阅读 如有错误之处可评论指出 博主会耐心听取每条意见 ✨✨✨✨✨✨✨✨
