冷水滩做微网站,山东省招投标信息网,买拆车件上什么网站,成都logo标志设计文章目录 1、前言2、红黑树的概念3、红黑树的性质4、红黑树节点的定义5、红黑树的插入Insert6、红黑树的验证7、红黑树与AVL树的比较附录#xff1a; 1、前言
我们在学习了二叉搜索树后#xff0c;在它的基础上又学习了AVL树#xff0c;知道了AVL树是靠平衡因子来调节左右高… 文章目录 1、前言2、红黑树的概念3、红黑树的性质4、红黑树节点的定义5、红黑树的插入Insert6、红黑树的验证7、红黑树与AVL树的比较附录 1、前言
我们在学习了二叉搜索树后在它的基础上又学习了AVL树知道了AVL树是靠平衡因子来调节左右高度差从而让树变得平衡的。本篇我们再来学习一个依靠另一种平衡规则来控制的二叉搜索树——红黑树。
2、红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。
3、红黑树的性质
1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的则它的两个孩子结点是黑色的红色不能连续黑色可以连续 4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 概念中说到没有一条路径会比其他路径长出俩倍性质3与性质4相互牵制就可以保证这一点。
4、红黑树节点的定义
我们定义节点依然是三叉链与AVL树不同的是红黑树没有平衡因子而是保存一个代表节点颜色的属性。
enum Color
{RED,BLACK
};template class K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Color _col;RBTreeNode(const pairK, V _kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};这里我们定义的红黑树节点颜色默认给的红色但是这里是给红色还是黑色合适呢 当插入的时候我们新插入的节点颜色是黑色时就会破坏性质3新插入节点的这条路径的黑色节点数一定会比其他路径的黑色节点多一个影响整棵树。 如果是红色那插入的时候她的父节点可能是黑色没有影响可能是红色那么就会出现连续的红色节点但是它只会影响这一条路径。 这两种颜色插入黑色是一定会影响红色是可能会影响的且黑色影响整棵树红色影响它这一条路径两害取其轻我们选择红色调整的话也比较容易调整。下面我们就来尝试看插入怎么写
5、红黑树的插入Insert
红黑树的插入是在二叉搜索树插入基础上来修改的因此大的方向分两步走 1、找到插入的位置 2、插入节点后根据性质来调节平衡。
bool Insert(const pairK, V kv)
{if (nullptr _root){_root new Node(data);_root-_col BLACK; // 性质2根节点是黑色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;}}// 新增插入节点是红色只会影响父节点如果是黑色影响所有路径// 所以 new 的节点为红色cur new Node(kv);cur-_col RED;if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}// 维护处理 ...
}当来到这块时已经插入了要做的就是按照性质来检查和维护这棵树了。 1、当父亲是黑色那么就不用维护就结束了 2、当父亲是红色那么就违反了性质3不能存在连续的红色节点这时就需要调整了调整也是要分情况讨论约定cur为当前节点p为父节点g为祖父节点u为叔叔节点。 情况一cur是红色p为红色g为黑色u存在且为红色 这里看到的这棵树可能是完整的也可能是子树
如果是完整的树那么改完之后需要将g的颜色改为黑色。 如果g是子树那么g就有父节点这时g的颜色改为红色父节点颜色可能也是红色这时急需要继续向上调整了。 将pu改为黑g改为红然后把g当作cur继续向上调整。 情况二cur是红色p为红色g为黑色u不存在/u存在且为黑色
这里u有两种颜色我们分开讨论
如果u不存在那么cur一定是新增。因为u不存在g也是有一条右边路径的这条路径就两个黑色节点空结点也是黑色那么c就不存在a、b都不存在如果存在就是黑色节点那么就打破了性质3。如果存在且为黑那么这个抽象图就不全。因为父节是红色叔叔为黑色每条路径的黑色节点个数要相同因此推测出cur之前应该是黑色那么a、b就应该是红色新增节点在a/b的孩子位置。 整体就为下图
它会先经过情况一的调整方式调整完变为情况二这样然后再继续调整
此时就 以g为基点先右旋然后将父节点颜色变为黑色祖父节点颜色变为红色。旋转不清楚的同学可以看看AVL树的 情况三cur是红色p为红色g为黑色u不存在/u存在且为黑色
u不存在cur是新增。因为每条路径的黑色节点个数相同u不存在u这条路径上两个黑色节点空结点也是黑色推测出a、b、c都是不存在的那么cur就是新增如果存在只能是黑色节点那么就打破了性质3。如果存在且为黑这个抽象图依然是不完整的。因为父节点是红色叔叔为黑色每条路径的黑色节点相同因此推测出a为黑色cur之前也应该为黑色那么b、c就应该是红色新增节点在b/c的孩子位置。
图跟情况二中u存在且为黑差不多
会先经过情况一调整变为情况三这样然后进行调整
此时先以p为基点左旋再以g为基点右旋然后将cur节点变为黑色祖父节点变为红色。 如果新增的父节点在右叔叔节点在左那么也是分以上三种情况调整方式也是对应三种方式差不多这里就不过多赘述直接上代码
bool Insert(const pairK, V kv)
{if (nullptr _root){_root new Node(data);_root-_col BLACK; // 性质2根节点是黑色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;}}// 新增插入节点是红色只会影响父节点如果是黑色影响所有路径// 所以 new 的节点为红色cur new Node(kv);cur-_col RED;if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}// 不断向上调整的所以得用whilewhile (parent parent-_col RED){// 父节点是祖父节点的左// g// p u// c Node* grandfather parent-_parent;// 1、父节点在祖父的左即叔叔在右if (parent grandfather-_left){Node* uncle grandfather-_right;// 1.1 叔叔存在并且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 向上调整cur grandfather;parent cur-_parent;}// 1.2 叔叔不存在 / 叔叔存在且为黑处理方法一样else{if (cur parent-_left) // 左边高的情况{// 右单旋// g// p u// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else // 左边高右边高的情况{// 双旋// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}// 此时不用祖父位置为黑色不用在网上调整了break;}}// 2、父节点在祖父的右即叔叔在祖父的左else // parent grandfather-_right{// g// u p// cNode* uncle grandfather-_left;// 2.1 叔叔存在且叔叔为红色if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 向上调整cur grandfather;parent cur-_parent;}// 2.2 叔叔不存在 / 叔叔存在且颜色为黑处理方法一样else{if (cur parent-_right) // 右边高的情况{// g// u p// cRotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else // 右边高左边高{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}// 此时不用祖父位置为黑色不用在网上调整了break;}}}// 最后将根节点变为黑色_root-_col BLACK;return true;
}// 左单旋
void RotateL(Node* parent)
{Node* subR parent-_right;Node* subRL subR-_left;Node* parentParent parent-_parent;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;parent-_parent subR;if (_root parent) // 父节点就是根节点{_root subR;subR-_parent nullptr;}else // 子树情况{if (parentParent-_left parent){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}
}// 右单旋
void RotateR(Node* parent)
{Node* parentParent parent-_parent;Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right 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;}
}6、红黑树的验证
红色树的验证本质就是验证两方面 1、是否为二叉搜索树中序遍历是否有序 2、是否满足5条性质。
void _InOrder(Node* pRoot)
{if (pRoot nullptr)return;_InOrder(pRoot-_left);cout pRoot-_data ;_InOrder(pRoot-_right);
}bool IsBalance()
{if (_root nullptr) return true;if (_root-_col RED) return false;// 参考值int refValue 0;Node* cur _root;while (cur){if (cur-_col BLACK) refValue;cur cur-_left;}// 检查每条路径黑色节点个数// 思路以上面参考值为主对比每条路径的黑色节点个数// 当走到空就说明该路径走完了那么这个过程中记录下黑色节点个数到空时与refValue对比// 这里传进去blacknum只能是传值这样就不会影响上一层的blacknum了int blacknum 0;// 检查连续红色节点与每条路径黑色节点个数return Check(_root, blacknum, refValue);
}
bool Check(Node* root, int blacknum, const int refValue)
{if (root nullptr){if (blacknum ! refValue){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, refValue) Check(root-_right, blacknum, refValue);
}7、红黑树与AVL树的比较
红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(log_2 N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。
附录
enum Color
{RED,BLACK
};template class K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Color _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:bool Insert(const pairK, V kv){if (nullptr _root){_root new Node(data);_root-_col BLACK; // 性质2根节点是黑色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;}}// 新增插入节点是红色只会影响父节点如果是黑色影响所有路径// 所以 new 的节点为红色cur new Node(kv);cur-_col RED;if (parent-_kv.first kv.first){parent-_right cur;cur-_parent parent;}else{parent-_left cur;cur-_parent parent;}// 不断向上调整的所以得用whilewhile (parent parent-_col RED){// 父节点是祖父节点的左// g// p u// c Node* grandfather parent-_parent;// 1、父节点在祖父的左即叔叔在右if (parent grandfather-_left){Node* uncle grandfather-_right;// 1.1 叔叔存在并且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 向上调整cur grandfather;parent cur-_parent;}// 1.2 叔叔不存在 / 叔叔存在且为黑处理方法一样else{if (cur parent-_left) // 左边高的情况{// 右单旋// g// p u// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else // 左边高右边高的情况{// 双旋// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}// 此时不用祖父位置为黑色不用在网上调整了break;}}// 2、父节点在祖父的右即叔叔在祖父的左else // parent grandfather-_right{// g// u p// cNode* uncle grandfather-_left;// 2.1 叔叔存在且叔叔为红色if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 向上调整cur grandfather;parent cur-_parent;}// 2.2 叔叔不存在 / 叔叔存在且颜色为黑处理方法一样else{if (cur parent-_right) // 右边高的情况{// g// u p// cRotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else // 右边高左边高{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}// 此时不用祖父位置为黑色不用在网上调整了break;}}}// 最后将根节点变为黑色_root-_col BLACK;return true;}bool Find(const K key){Node* cur _root;while (cur){if (cur-_key key){cur cur-_right;}else if (cur-_key key){cur cur-_left;}else{return true;}}return true;}bool IsBalance(){if (_root nullptr) return true;if (_root-_col RED) return false;// 参考值int refValue 0;Node* cur _root;while (cur){if (cur-_col BLACK) refValue;cur cur-_left;}// 检查每条路径黑色节点个数// 思路以上面参考值为主对比每条路径的黑色节点个数// 当走到空就说明该路径走完了那么这个过程中记录下黑色节点个数到空时与refValue对比// 这里传进去blacknum只能是传值这样就不会影响上一层的blacknum了int blacknum 0;// 检查连续红色节点与每条路径黑色节点个数return Check(_root, blacknum, refValue);}size_t Height(){return _Height(_root);}void InOrder(){_InOrder(_root);cout endl;}private:bool Check(Node* root, int blacknum, const int refValue){if (root nullptr){if (blacknum ! refValue){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, refValue) Check(root-_right, blacknum, refValue);}// 左单旋void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;Node* parentParent parent-_parent;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;parent-_parent subR;if (_root parent) // 父节点就是根节点{_root subR;subR-_parent nullptr;}else // 子树情况{if (parentParent-_left parent){parentParent-_left subR;}else{parentParent-_right subR;}subR-_parent parentParent;}}// 右单旋void RotateR(Node* parent){Node* parentParent parent-_parent;Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right 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;}}void _InOrder(Node* pRoot){if (pRoot nullptr)return;_InOrder(pRoot-_left);cout pRoot-_data ;_InOrder(pRoot-_right);}size_t _Height(Node* pRoot){if (pRoot nullptr)return 0;int leftHeight _Height(pRoot-_left);int rightHeight _Height(pRoot-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}private:Node* _root nullptr;
};
