用qq空间做网站,网页设计实训总结与展望150字,WordPress数据库备份还原,php做网站切换语言顾得泉#xff1a;个人主页
个人专栏#xff1a;《Linux操作系统》 《C从入门到精通》 《LeedCode刷题》
键盘敲烂#xff0c;年薪百万#xff01; 一、红黑树的概念与性质
1.概念 红黑树#xff0c;是一种二叉搜索树#xff0c;但在每个结点上增加一个存储位表示结点…
顾得泉个人主页
个人专栏《Linux操作系统》 《C从入门到精通》 《LeedCode刷题》
键盘敲烂年薪百万 一、红黑树的概念与性质
1.概念 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 2.性质 1.每个结点不是红色就是黑色 2.根节点是黑色的 3.如果一个节点是红色的则它的两个孩子结点是黑色的 4.对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点 5.每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 二、红黑树结构 为了后续实现关联式容器简单红黑树的实现中增加一个头结点因为跟节点必须为黑色为了与根节点进行区分将头结点给成黑色并且让头结点的 pParent 域指向红黑树的根节点pLeft域指向红黑树中最小的节点_pRight域指向红黑树中最大的节点如下 三、红黑树的相关实现
1. 红黑树节点的定义 想要实现一颗红黑树 首先我们得有树的节点而树的节点中我们需要存该节点的父节点、该节点的右孩子、该节点的左孩子、树节点的颜色以及数据类型代码如下
enum COLOUR
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _parent;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;COLOUR _col;pairK, V _kv;RBTreeNode(const pairK, V kv):_parent(nullptr), _left(nullptr), _right(nullptr), _kv(kv), _col(RED){}
}; 这里在节点的定义中要将节点的默认颜色给成红色这个需仔细品味。 2. 红黑树的定义
红黑树的定义如下
templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;private:Node* _root nullptr;
};
3. 红黑树的插入 因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对红黑树分情况来讨论 约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点
情况一 cur为红p为红g为黑u存在且为红 解决方式将p,u改为黑g改为红然后把g当成cur继续向上调整。 情况二 cur为红p为红g为黑u不存在/u存在且为黑 解决方式 p为g的左孩子cur为p的左孩子则进行右单旋转相反 p为g的右孩子cur为p的右孩子则进行左单旋转 p、g变色–p变黑g变红 情况三 cur为红p为红g为黑u不存在/u存在且为黑 解决方式 p为g的左孩子cur为p的右孩子则针对p做左单旋转相反 p为g的右孩子cur为p的左孩子则针对p做右单旋转 则转换成了情况2 4.代码实现
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* cur _root, * parent nullptr;while (cur){if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else if (cur-_kv.first kv.first){parent cur;cur cur-_right;}else{return false;}}cur new Node(kv);if (parent-_kv.first cur-_kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;// g// p u// cif (grandfather-_left parent){Node* uncle grandfather-_right;// 情况1、uncle 存在且为红// 不需要旋转if (uncle uncle-_col RED){// 变色 parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续往上更新处理cur grandfather;parent cur-_parent;}else{// 情况2.1// 单旋// g// p// cif (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}// 情况3.1// 双旋// g// p// celse{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}// grandfather-_right parent// g// u p// celse{Node* uncle grandfather-_left;// uncle 存在且为红// 不需要旋转if (uncle uncle-_col RED){// 变色parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}// uncle 存在且为黑 或者 uncle 不存在else{// 情况2.2// 单旋// g// u p // cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}// 情况3.2// 双旋// g// u p // celse{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_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)return false;// 先统计一条路径的黑色节点与其它路径的比较int refVal 0;Node* cur _root;while (cur){if (cur-_col BLACK){refVal;}cur cur-_left;}int blacknum 0;return Check(_root, blacknum, refVal);}// 获取树的高度int Height(){return _Height(_root);}// 获取树的节点数size_t Size(){return _Size(_root);} // 查找Node* Find(const K key){Node* cur _root;while (cur){if (cur-_kv.first key){cur cur-_right;}else if (cur-_kv.first key){cur cur-_left;}else{return cur;}}return NULL;}
private:// 获取树的节点个数size_t _Size(Node* root){if (root NULL)return 0;return _Size(root-_left) _Size(root-_right) 1;}// 获取树的高度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;}// 检查是否符合红黑树规则bool Check(Node* root, int blacknum, int refVal){if (root nullptr){if (blacknum ! refVal){cout 存在黑色节点数量不相等的路径 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 有连续的红色节点 endl;return false;}if (root-_col BLACK){blacknum;}return Check(root-_left, blacknum, refVal) Check(root-_right, blacknum, refVal);}// 按中序遍历打印树的节点void _Inorder(Node* root){if (root nullptr)return;_Inorder(root-_left);cout root-_kv.first ;_Inorder(root-_right);}// 左单旋void RotateL(Node* parent){Node* subR parent-_right, * subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* parentParent parent-_parent;parent-_parent subR;// 如果 parent 是根节点就直接更新 subR 为根节点并将 subR 的_parent指向空if (_root parent){_root subR;subR-_parent nullptr;}// 否则先判断 parent 是 parentParent 的右还是左再将parentParent的左或者右连接subRelse{if (parentParent-_left parent){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}}// 右单旋void RotateR(Node* parent){Node* subL parent-_left, * subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* parentParent parent-_parent;parent-_parent subL;if (_root parent){_root subL;subL-_parent nullptr;}else{if (parentParent-_left parent){parentParent-_left subL;}else{parentParent-_right subL;}subL-_parent parentParent;}}
private:Node* _root nullptr;
}; 四、红黑树与AVL树的比较 红黑树和AVL树都是自平衡二叉查找树它们都能在插入和删除操作后通过旋转来维持树的平衡保证查找、插入和删除操作的时间复杂度大致为( O(\log n) )。然而它们在实现方式和具体性能上存在一些差异
平衡性 红黑树通过确保从根节点到叶子的最长可能路径不会超过最短可能路径的两倍来保持平衡即它允许一定程度的不平衡。 AVL树则更加严格它要求任何从根节点到叶子的路径的长度最多只相差1因此它比红黑树更接近于完全平衡。 旋转操作 红黑树通常需要进行更多的旋转以维护其性质每次插入或删除后都可能需要进行多达三次旋转但它不需要维护额外的平衡因子信息。 AVL树在每个节点上存储高度信息或平衡因子这使得它能够进行更精细的平衡操作通常在一次插入或删除后只进行常数次旋转。 空间开销 红黑树不需要存储额外的高度或平衡因子信息因此它的空间效率略高。 AVL树的每个节点都需要存储高度信息这增加了少量的内存开销。 应用场景 红黑树由于其简单性和对平衡的宽松要求在实际应用中非常流行特别是在实现标准库中的关联容器如map和set等。 AVL树通常在需要频繁进行查找操作而插入和删除操作相对较少的情况下使用因为它的高度总是最小化的这可以最大化查找效率。 结语C关于如何实现红黑树的分享到这里就结束了希望本篇文章的分享会对大家的学习带来些许帮助如果大家有什么问题欢迎大家在评论区留言~~~
