专注做一家男生最爱的网站,石家庄最新,电信网站备案查询,国家企业信息公示系统全国#x1f680;个人主页#xff1a;小羊 #x1f680;所属专栏#xff1a;C 很荣幸您能阅读我的文章#xff0c;诚请评论指点#xff0c;欢迎欢迎 ~ 目录 前言一、定义与性质二、红黑树节点的定义三、新增节点插入四、验证红黑树五、AVL树和红黑树比较 前言 本文仅适合了… 个人主页小羊 所属专栏C 很荣幸您能阅读我的文章诚请评论指点欢迎欢迎 ~ 目录 前言一、定义与性质二、红黑树节点的定义三、新增节点插入四、验证红黑树五、AVL树和红黑树比较 前言 本文仅适合了解二叉搜索树但不了解红黑树底层原理的同学阅读哦。 本篇文章不会带你从头到尾实现红黑树但会带你深入理解红黑树是怎么实现平衡的怎么通过旋转变换实现保持平衡以及实现平衡过程中的细节应该怎么处理等。 一、定义与性质
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 根节点是黑色的每个节点不是红色就是黑色如果一个节点是红色的则它的两个孩子一定是黑色的没有连续的红色节点对每个节点从该节点到其所有后代叶子结点的简单路径上黑色节点数目相同每个叶子节点都是黑色的此处的叶子结点指的是空节点通常是为了算路径 其中第三点和第四点是控制红黑树平衡的关键与AVL树不同的是红黑树不再关注高度只关注颜色只要控制住了颜色就控制住了高度。 二、红黑树节点的定义
维持二叉搜索树的平衡旋转处理是必要的因此红黑树的节点也需要指向其父节点。
enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Colour _col;RBTreeNode(const pairK, V kv, colour col RED):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(col){}
};上面我们将节点的默认颜色设置为红色为什么不是黑色呢
新增节点默认设置为红色或黑色都可能会破坏红黑树的性质默认为红色对红黑树的性质影响最小就算修改也更为容易。另外红黑树主要还是以黑色节点为主在红黑树中黑色节点通常都是通过变色而来的而红色节点往往都是新增的。 三、新增节点插入
虽然新增节点默认为红色但根节点必须是黑色。
bool Insert(const pairK, V kv)
{Node* pcur _root;Node* parent nullptr;if (pcur nullptr)//当前还没有节点{_root new Node(kv);_root-_col BLACK;//根节点必须是黑色的return true;}//...
}插入一个红色节点其父亲是红色时才需要处理 当父亲是红色时其爷爷一定是黑色不然在插入新节点之前红黑树就已经有问题了。 所以处理过程的关键是看叔叔大体可以分为两种情况 其中g表示grandfatherp表示parentu表示uncle。a,b,c,d,e为红黑子树。
| 情况一g为黑p为红u存在且为红 | 处理方法变色继续向上调整 上图中pcur可能为新增节点也可能之前为黑是经过变色而来的。
//当父节点存在且为红时需要调整
while (parent parent-_col RED)
{if (parent grandfather-_left){uncle grandfather-_right;}else{uncle grandfather-_left;}if (uncle uncle-_col RED)//情况一u存在且为红{parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;if (grandfather-_parent nullptr){grandfather-_col BLACK;return true;}pcur grandfather;parent pcur-_parent;grandfather parent-_parent;}//...
}| 情况二g为黑p为红u存在且为黑 / u不存在 | 处理方法旋转 变色
单旋
void RotateR(Node* parent)
{Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;subL-_right parent;if (subLR){subLR-_parent parent;}Node* parentparent parent-_parent;parent-_parent subL;if (parentparent nullptr){_root subL;}else{if (parent parentparent-_left){parentparent-_left subL;}else{parentparent-_right subL;}}subL-_parent parentparent;
}void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL){subRL-_parent parent;}subR-_left parent;Node* parentparent parent-_parent;parent-_parent subR;if (parentparent nullptr){_root subR;}else{if (parent parentparent-_left){parentparent-_left subR;}else{parentparent-_right subR;}}subR-_parent parentparent;
}双旋
//当父节点存在且颜色为红需要往上更新
while (parent parent-_col RED)
{if (parent grandfather-_left){uncle grandfather-_right;}else{uncle grandfather-_left;}//情况一u存在且为红else //情况二u存在且为黑 / 情况三u不存在{if (parent grandfather-_left pcur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_left pcur parent-_right){RotateL(parent);RotateR(grandfather);pcur-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_right pcur parent-_left){RotateR(parent);RotateL(grandfather);pcur-_col BLACK;grandfather-_col RED;}else if (parent grandfather-_right pcur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_cocl RED;}break;}
}总结 红黑树的插入主要以黑色节点为主时刻维持黑色节点的数量处理过程应尽量避免旋转能变色就不旋转黑色节点通常都是受限于红黑树的性质而不得不变色而来的红色节点通常都是新增的 不管是变色还是旋转始终都要保持插入新节点前后各路径上黑色节点的数量。 四、验证红黑树
检测其是否满足二叉搜索树(中序遍历是否为有序序列)检测其是否满足红黑树的性质
检测红黑树的性质主要检测红黑树的根节点是否为黑色、任意一个红色节点的父节点不是红色、任意节点到根节点的路径上黑色节点的数量相等。 其中检测任意节点到根节点的路径上黑色节点数量相等可以用递归处理先算出某条路径上黑色节点的数量通过递归与每条路径上黑色节点的数量最对比如果与某条路径上黑色节点的数量不相等则红黑树异常。
bool IsValidRBTree()
{Node* pRoot _root;if (nullptr pRoot){return true;}//检测根节点是否满足情况if (BLACK ! pRoot-_col){cout 违反性质二根节点必须为黑色 endl;return false;}//获取任意一条路径中黑色节点的个数size_t blackCount 0;Node* pcur pRoot;while (pcur){if (BLACK pcur-_col)blackCount;pcur pcur-_left;}//检测是否满足红黑树的性质k用来记录路径中黑色节点的个数size_t k 0;return _IsValidRBTree(pRoot, k, blackCount);
}bool _IsValidRBTree(Node* pRoot, size_t k, const size_t blackCount)
{//走到nullptr后判断k和black是否相等if (nullptr pRoot){cout k endl; if (k ! blackCount){cout 违反性质四每条路径中黑色节点的个数必须相同 endl;return false;}return true;}//统计黑色节点的个数if (BLACK pRoot-_col){k;}//检测当前节点与其双亲是否都为红色Node* pParent pRoot-_parent;if (pParent RED pParent-_col RED pRoot-_col){cout 违反性质三没有连在一起的红色节点 endl;return false;}return _IsValidRBTree(pRoot-_left, k, blackCount) _IsValidRBTree(pRoot-_right, k, blackCount);
}五、AVL树和红黑树比较
红黑树 平衡机制基于颜色和一系列规则如节点颜色、红色节点的子节点颜色、路径上黑色节点数量等允许节点之间的高度差超过1但通过保证从根节点到叶节点的任意路径上黑色节点的数量相同来避免树的高度过大在插入或删除节点时可能需要通过变色和少量的旋转操作来维持平衡 AVL树 平衡机制基于每个节点的左子树高度和右子树高度之差 严格要求所有节点的平衡因子为-1、0或1即左右子树高度差不超过1 在插入或删除节点时可能需要通过多次旋转操作来维持平衡并更新每个节点的平衡因子
红黑树相对AVL树并没有那么严格地要求平衡仅通过颜色控制最长路径中节点个数不会超过最短路径节点个数的两倍就行。
当AVL树不平衡时仅通过旋转来处理红黑树不平衡时可以变色、变色旋转处理显然红黑树插入、删除过程更有优势而AVL树查找过程更有优势。而set和map底层、Linux内核等都使用红黑树实现。 本篇文章的分享就到这里了如果您觉得在本文有所收获还请留下您的三连支持哦~
