做网站如何获利合肥房产网官方网站

做网站如何获利,合肥房产网官方网站,青岛网站开发哪家服务专业,北京酒店团购网站建设前言#xff1a;在计算机科学的浩瀚领域中#xff0c;数据结构是构建高效算法的基石#xff0c;而树结构因其出色的层次性和查找效率#xff0c;成为处理动态数据集合的核心选择。二叉搜索树作为基础的树结构#xff0c;虽能实现快速的插入、删除与查找操作#xff0c;但…前言在计算机科学的浩瀚领域中数据结构是构建高效算法的基石而树结构因其出色的层次性和查找效率成为处理动态数据集合的核心选择。二叉搜索树作为基础的树结构虽能实现快速的插入、删除与查找操作但在极端情况下如数据有序插入会退化为线性结构导致时间复杂度骤升至O(n)难以满足大规模数据处理的性能需求。为解决这一痛点平衡二叉树应运而生而红黑树作为平衡二叉树的经典实现之一凭借其精妙的着色规则与旋转机制在保证树结构相对平衡的同时将各项操作的时间复杂度稳定在O(log n)成为众多底层系统的优选数据结构。从C STL中的set、map容器实现到Linux内核的进程调度再到数据库的索引模块红黑树的身影无处不在。它既兼顾了平衡二叉树的高效性能又通过简化的平衡维护规则降低了实现难度实现了性能与复杂度的优雅平衡。然而红黑树的着色规则、旋转策略以及平衡维护逻辑对初学者而言往往具有一定的理解门槛尤其在C手动实现场景中容易在复杂的节点操作与指针管理中陷入困惑。本文旨在打破这种认知壁垒从红黑树的基本定义与核心性质出发逐步拆解其插入操作中的平衡维护机制深入剖析旋转操作的原理与应用场景并结合实例帮助读者直观理解各项规则的设计初衷。无论你是刚接触平衡二叉树的初学者还是希望夯实底层基础的开发人员相信通过本文的系统梳理都能对红黑树形成清晰、完整的认知进而掌握这一高效数据结构的核心逻辑与应用价值。接下来就让我们一同走进红黑树的世界探寻其平衡之美的底层密码。一、红黑树的概念1、概念红黑树和前面我们学习的AVL树一样也是一种自平衡二叉搜索树其每个结点会额外再带一个代表颜色的数据然后其通过控制结点的颜色来对我们的树结构进行控制使高度近似平衡从而保持我们的插入、查找、删除操作的时间复杂度稳定在O(logN)。如上图就是我们的红黑树了。2、规则每个结点不是红色就是黑色根结点是黑色的如果一个节点是红色的则它的两个孩子节点 必须是黑色的每个节点到其NULL节点的简单路径上均包含相同数量的黑色节点那么对于上面的四个规则我们如何理解呢1、红黑树中每个节点都有颜色的属性且只又红和黑两种不会出现其他的。2、整棵树的根节点必须是黑色的3、不能出现连续的两个红色的节点4、简单路径不重复经过节点的路径。3、红黑树控制平衡结构的原理前面我们的AVL树是通过控制左右子树之间的高度差然后控制树的平衡的那么我们的红黑树是如何通过控制节点之间的颜色然后达到控制树的平衡的呢首先由规则4我们可以得知从根节点到NULL节点的每条路径都有相同的黑色节点所以极端情况下最短路径就是全是黑色节点的情况那么我们设最短路径长度为bh。然后由规则2和规则3可知任意一条路径都不会有连续的红色节点那么极端情况下最长路径就是一黑一红的情况那么最长路径就是2hb的情况了。那么结合上面的情况我们假设任意一个从根节点到NULL的简单路径的长度为x那么x的长度就在hb和2hb之间。例如下面这种情况我们从根节点到NULL节点的任意一条简单路径都满足上面的要求。4、红黑树的效率假设N是红黑树中节点的数量h是最短路径的长度那么2^h-1N2^2*h-1那么由此可以推出h约等于logN那么最长路径为2*logN所以红黑树的时间复杂度还是为O(logN)。那么红黑树和AVL树之间有啥不一样的呢红黑树的表达要比AVL树要抽象很多AVL树通过控制高度差更加直观的控制了树的平衡。而红黑树通过4条规则来控制间接的使得树平衡其两个的时间效率是一样的但是对于数据的插入来说插入相同数量的节点红黑树的旋转次数要少一点其对于平衡的控制就没有这么的严格。二、 红黑树的实现1、红黑树的节点结构其结构和AVL树的结构差不多就是其不需要平衡因子了然后要加一个颜色然后颜色中我们使用一个枚举枚举中为红色和黑色。上面就是我们的节点结构可以发现我们对于节点的颜色的初始化默认是Red至于为啥我们后面来看。2、insert红黑树的插入红黑树节点的插入的位置其和二叉搜索树的插入是一样的所以我们不进行详细讲解了。然后当树初始为空的时候那么插入的节点就为根节点然后要注意的是将根节点的颜色变为黑的。下面就是其他位置进行插入那么我们插入一个节点后要如何保持树的平衡呢要是非空树插入那么新增节点必须是红色的这是因为非空树插入那么新增节点要是为黑色的话就违反了规则4。、然后要是父亲节点是黑色的话那么就不会违反规则此时插入就可以结束了。要是父亲节点是红色的那么此时就违反了规则3那么就要进一步分析了新插入节点cur是红然后父亲节点parent是红的然后父亲节点的父亲节点是黑色的那么就是父亲节点的兄弟节点还没定。根据父亲节点的兄弟的情况分为下面几种情况进行处理情况1uncle存在且是红色的这种情况就是uncle存在且为红色那么我们如何进行调整呢首先就是我们将爷爷节点变成红然后父亲节点和uncle节点都变黑那么两个子树的简单路径的黑色节点数量都没变满足规则4。然后我们此时调整还没完成要防止出现连续的两个红色节点呢那么我们继续向上调整检查到我们的爷爷节点变成红色会不会和爷爷节点的父亲节点形成连续的红色节点要是没有也就是爷爷节点的父亲节点是黑色的那么我们的调整就可以结束了。代码如下情况2uncle存在且为黑或者uncle不存在上面这种情况就是使用我们的单旋变色处理然后要是插入在a这个位置那么我们就需要进行双旋变色处理了。代码如下完整的插入代码bool Insert(const pairK, V kv) { //树为空直接为根节点颜色要变为黑 if (_rootnullptr) { _root new Node(kv); _root-_co Black; return true; } //树不为空找到合适位置插入 Node* cur _root; Node* parent nullptr; while (cur) { parent cur; if (cur-_kv.firstkv.first) { cur cur-_left; } else if (cur-_kv.first kv.first) { cur cur-_roght; } else { //不支持相同数据插入 return false; } } //循环结束将新增结点和树进行链接 cur new Node(kv); if (parent-_kv.firstkv.first) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; while (parent parent-_co Red) { Node* grandfather parent-_parent; if (grandfather-_leftparent) { Node* uncle grandfather-_right; //叔叔存在且为红 if (uncleuncle-_coRed) { parent-_co Black; uncle-_co Black; grandfather-_co Red; cur grandfather; parent cur-_parent; grandfather parent-_parent; } else // 叔叔不存在或者叔叔存在且为黑-旋转变色 { if (cur parent-_left) { // g // p u //c // 右单旋 RotateR(grandfather); parent-_col Black; grandfather-_col Red; } else { // g // p u // c // 左右单旋 RotateL(parent); RotateR(grandfather); cur-_col Black; grandfather-_col Red; } break; } } else // grandfather-_right parent { // g // u p Node* uncle grandfather-_left; // 叔叔存在且为红-》变色即可 if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfather-_col RED; // 继续往上处理 cur grandfather; parent cur-_parent; } else // 叔叔不存在或者存在且为黑 { // 情况二叔叔不存在或者存在且为黑 // 旋转变色 // g // u p // c if (cur parent-_right) { RotateL(grandfather); parent-_col BLACK; grandfather-_col RED; } else { // g // u p // c RotateR(parent); RotateL(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } } _root-_co Black; return true; }下面是在红黑树中的旋转代码其和AVL树都是一样的就是不需要对平衡因子进行修改。代码如下void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* parentParent parent-_parent; subL-_right parent; parent-_parent subL; if (parent _root) { _root subL; subL-_parent nullptr; } else { if (parentParent-_left parent) { 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; Node* parentParent parent-_parent; subR-_left parent; parent-_parent subR; if (parent _root) { _root subR; subR-_parent nullptr; } else { if (parentParent-_left parent) { parentParent-_left subR; } else { parentParent-_right subR; } subR-_parent parentParent; } }3、红黑树的判断那么我们如何判断一棵树符合红黑树的结构呢我们可以看红黑树的规则首先就是要保证根节点是黑色节点那么我们可以判断当前根节点是否为红色要是红色的那么我们就直接返回false。为啥不去判断其是否为黑色呢这是因为我们还要规则3和规则4要符合。然后我们再去判断规则3其是否存在连续的两个红色节点要是存在那么就也是返回false。最后我们再去判断规则4我们可以遍历整个树然后使用容器将到每个NULL节点的黑色节点数量使用容器记录下来比如我们可以使用set容器然后要是容器中不止一个数据那么我们的树结构就不符合这个方式简单就是效率不是很高那么我们还可以先记录一个路径的黑色节点数量然后再将这个数据和任意路径的黑色节点数量进行比较看看其是否相等。代码如下4、红黑树的前序遍历这个和我们前面学习二叉树是一样的。代码如下5、查找find这个和二叉搜索树是一样的代码如下三、完整代码#pragma once #includeiostream using namespace std; //枚举 enum color { Red, Black }; //红黑树节点 templateclass K,class V struct BRNode { BRNode(const pairK,Vkv) :_kv(kv), _parent(nullptr), _left(nullptr), _right(nullptr), _co(Red) { } pairK, V _kv; BRNodeK, V* _parent; BRNodeK, V* _left; BRNodeK, V* _right; enum color _co; }; templateclass K,class V class RBTree { typedef BRNodeK, V* Node; public: bool Insert(const pairK, V kv) { //树为空直接为根节点颜色要变为黑 if (_rootnullptr) { _root new Node(kv); _root-_co Black; return true; } //树不为空找到合适位置插入 Node* cur _root; Node* parent nullptr; while (cur) { parent cur; if (cur-_kv.firstkv.first) { cur cur-_left; } else if (cur-_kv.first kv.first) { cur cur-_roght; } else { //不支持相同数据插入 return false; } } //循环结束将新增结点和树进行链接 cur new Node(kv); if (parent-_kv.firstkv.first) { parent-_right cur; } else { parent-_left cur; } cur-_parent parent; while (parent parent-_co Red) { Node* grandfather parent-_parent; if (grandfather-_leftparent) { Node* uncle grandfather-_right; //叔叔存在且为红 if (uncleuncle-_coRed) { parent-_co Black; uncle-_co Black; grandfather-_co Red; cur grandfather; parent cur-_parent; grandfather parent-_parent; } else // 叔叔不存在或者叔叔存在且为黑-旋转变色 { if (cur parent-_left) { // g // p u //c // 右单旋 RotateR(grandfather); parent-_col Black; grandfather-_col Red; } else { // g // p u // c // 左右单旋 RotateL(parent); RotateR(grandfather); cur-_col Black; grandfather-_col Red; } break; } } else // grandfather-_right parent { // g // u p Node* uncle grandfather-_left; // 叔叔存在且为红-》变色即可 if (uncle uncle-_col RED) { parent-_col uncle-_col BLACK; grandfather-_col RED; // 继续往上处理 cur grandfather; parent cur-_parent; } else // 叔叔不存在或者存在且为黑 { // 情况二叔叔不存在或者存在且为黑 // 旋转变色 // g // u p // c if (cur parent-_right) { RotateL(grandfather); parent-_col BLACK; grandfather-_col RED; } else { // g // u p // c RotateR(parent); RotateL(grandfather); cur-_col BLACK; grandfather-_col RED; } break; } } } _root-_co Black; return true; } bool IsBalance() { if (_root nullptr) return true; if (_root-_col RED) return false; // 黑色节点数量参考值 Node* leftMost _root; int blackRef 0; while (leftMost) { if (leftMost-_col BLACK) blackRef; leftMost leftMost-_left; } return Check(_root, 0, blackRef); } void InOrder() { _InOrder(_root); cout endl; } 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 nullptr; } private: void RotateR(Node* parent) { Node* subL parent-_left; Node* subLR subL-_right; parent-_left subLR; if (subLR) subLR-_parent parent; Node* parentParent parent-_parent; subL-_right parent; parent-_parent subL; if (parent _root) { _root subL; subL-_parent nullptr; } else { if (parentParent-_left parent) { 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; Node* parentParent parent-_parent; subR-_left parent; parent-_parent subR; if (parent _root) { _root subR; subR-_parent nullptr; } else { if (parentParent-_left parent) { parentParent-_left subR; } else { parentParent-_right subR; } subR-_parent parentParent; } } bool Check(Node* cur, int blackNum, const int blackNumRef) { if (cur nullptr) { if (blackNum ! blackNumRef) { cout 黑色节点的数量不相等 endl; return false; } return true; } if (cur-_col RED cur-_parent cur-_parent-_col RED) { cout cur-_kv.first - 连续的红色节点 endl; return false; } if (cur-_col BLACK) blackNum; return Check(cur-_left, blackNum, blackNumRef) Check(cur-_right, blackNum, blackNumRef); } void _InOrder(Node* root) { if (root nullptr) return; _InOrder(root-_left); cout root-_kv.first ; _InOrder(root-_right); } private: Node* _rootnullptr; };