首页 - 资讯 - 科技 - 教育 - 汽车 - 财经 - 健康 - 房产 - 文旅 - 娱乐 - 游戏
访谈 |股票 |创投人物 |产业 |金融 |维修 |车展 |报价 |行情 |时评 |新车 |数码 |互联网 |名企 |IT业 |能源
当前位置： 首页> 财经> 访谈 > logo制作在线_企业软件定制开发包括_sem竞价教程_网站优化效果

logo制作在线_企业软件定制开发包括_sem竞价教程_网站优化效果

时间:2025/7/11 3:38:56来源：https://blog.csdn.net/2403_82706967/article/details/146067021 浏览次数:0次
logo制作在线_企业软件定制开发包括_sem竞价教程_网站优化效果

一、红黑树

1.概念

红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出2倍，因而是接近平衡的。

2.性质

  1. 每个结点不是红色就是黑色 
  2. 根节点是黑色的  
  3. 如果一个节点是红色的，则它的两个孩子结点是黑色的（没有连续的红色节点，可以有连续的黑色节点）
  4. 每条路径均包含相同数目的黑色结点  
  5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)

3.红黑树 VS AVL树

红黑树 vs AVL 树核心对比：

1.平衡条件差异

  • AVL 树：严格平衡（任意节点左右子树高度差≤1）
  • 红黑树：弱平衡（最长路径≤2 倍最短路径）

2.高度特性

  • AVL 树：高度 h=O (log n)
  • 红黑树：高度 h=O (2 log n) → 实际测试中通常为 1.2-1.4 倍 AVL 树高度

性能差异分析：

  1. 操作复杂度对比

    操作类型AVL树红黑树
    查找O(h)O(h)
    插入O(h)O(h)
    删除O(h)O(h)

  2. 实际效率表现

  • 查找：AVL 树略优（高度更低）
  • 插入 / 删除：红黑树更优（旋转次数少）
  • 综合性能：红黑树在动态场景更高效

效率差异原因：

1.旋转成本对比

  • AVL 树：每次插入可能需多次旋转（平均 1.02 次）
  • 红黑树：最多 3 次旋转（平均 0.2 次）
  • 旋转操作对缓存不友好（破坏空间局部性）

2.常数因子影响

  • 红黑树节点需维护颜色字段（增加少量内存）
  • AVL 树需维护平衡因子（同样增加内存）
  • 红黑树的颜色检查比 AVL 树的平衡因子计算更高效

4.实现思路与代码

节点结构定义

// 定义颜色枚举类型，包含红色和黑色两种颜色
enum Colour
{RED,BLACK
};// 定义红黑树节点的模板结构体
template<class K, class V>
struct RBTreeNode
{// 指向左子节点的指针RBTreeNode<K, V>* _left;// 指向右子节点的指针RBTreeNode<K, V>* _right;// 指向父节点的指针，用于回溯操作，方便在插入和删除时调整树的结构RBTreeNode<K, V>* _parent;// 存储键值对，键类型为K，值类型为Vpair<K, V> _kv;// 节点的颜色，使用前面定义的枚举类型Colour _col;// 构造函数，用于创建新节点// 节点颜色初始化为红色，因为插入红色节点对红黑树性质的破坏相对较小RBTreeNode(const pair<K, V>& kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED){}
};// 定义红黑树的模板结构体
template<class K, class V>
struct RBTree
{// 重定义节点类型，方便后续使用typedef RBTreeNode<K, V> Node;
public:// 这里可以添加插入、删除、查找等操作的函数声明和实现// ......private:// 红黑树的根节点指针，初始化为空指针Node* _root = nullptr;public:// 记录旋转操作的次数，用于调试和性能分析int _rotateCount = 0;
};

1. 颜色枚举类型 Colour

定义了两种颜色：红色（RED）和黑色（BLACK）。红黑树通过节点的颜色来维护树的弱平衡性质。

2. 节点结构体 RBTreeNode

  • 指针成员：
    • _left 和 _right 分别指向左右子节点，用于构建树的层次结构。
    • _parent 指向父节点，这在插入和删除操作中非常重要，因为在调整树的结构时，需要回溯到父节点甚至更高层的节点来进行旋转和颜色调整。
  • 键值对 _kv：存储实际的数据，键类型为 K，值类型为 V。红黑树可以作为一种关联容器，通过键来快速查找对应的值。
  • 颜色成员 _col：节点的颜色，使用 Colour 枚举类型表示。新节点默认初始化为红色，因为插入红色节点时，只要父节点不是红色，就不会破坏红黑树的性质，相比插入黑色节点，调整的复杂度更低。

3. 红黑树结构体 RBTree

  • 根节点指针 _root：指向红黑树的根节点，初始化为空指针，表示空树。
  • 旋转计数变量 _rotateCount：用于记录旋转操作的次数。旋转操作是红黑树调整结构的关键步骤，通过旋转可以在不破坏红黑树性质的前提下，平衡树的高度，减少查找、插入和删除操作的时间复杂度。这个变量可以用于调试和性能分析，帮助我们了解红黑树在不同操作下的调整情况。

插入

代码

    bool Insert(const pair<K, 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);cur->_col = RED;if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//平衡调整（关键步骤）while (parent && parent->_col == RED){Node* grandfather = parent->_parent;if (parent == grandfather->_left)//情况一：父节点是祖父的左孩子{Node* uncle = grandfather->_right;if (uncle && uncle->_col == RED)// 叔叔存在且为红{// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else // 叔叔不存在 或 存在且为黑{if (cur == parent->_left){//     g//   p// cRotateR(grandfather);parent->_col = BLACK;grandfather->_col = RED;}else{//     g//   p//		cRotateL(parent);RotateR(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}else // 情况二：父节点是祖父的右孩子{Node* uncle = grandfather->_left;// uncle存在且为红if (uncle && uncle->_col == RED){// 变色parent->_col = uncle->_col = BLACK;grandfather->_col = RED;// 继续向上处理cur = grandfather;parent = cur->_parent;}else{if (cur == parent->_right){RotateL(grandfather);grandfather->_col = RED;parent->_col = BLACK;}else{RotateR(parent);RotateL(grandfather);cur->_col = BLACK;grandfather->_col = RED;}break;}}}_root->_col = BLACK;// 确保根节点为黑return true;}

思路分析

1. 空树处理

  • 若根节点 _root 为空，直接创建新节点作为根，颜色设为黑色。

2. 寻找插入位置

  • 从根节点开始遍历，比较键值：

    • 若插入键 > 当前节点键，向右子树查找

    • 若插入键 < 当前节点键，向左子树查找

    • 若键已存在，返回插入失败

3. 插入新节点

  • 创建新节点（颜色为红色），链接到父节点的左/右子节点，并设置父指针。

4. 平衡调整（关键步骤）

循环条件：父节点存在且为红色（仅需处理父为红的情况）。

情况一：父节点是祖父的左孩子

  • 叔叔存在且为红：

    1. 变色：父节点和叔叔变黑，祖父变红。

    2. 继续向上处理：将祖父设为当前节点（父节点、祖父节点也要调整），继续向上调整。

  • 叔叔不存在或为黑：

    • 当前节点是父的左孩子（LL型）：

      1. 右旋祖父节点。

      2. 父变黑，祖父变红。

    • 当前节点是父的右孩子（LR型）：

      1. 先左旋父节点，转为 LL 型。

      2. 再右旋祖父节点。

      3. 当前节点变黑，祖父变红。

情况二：父节点是祖父的右孩子

  • 叔叔存在且为红：处理同情况一（变色后上移）。

  • 叔叔不存在或为黑：

    • 当前节点是父的右孩子（RR型）：

      1. 左旋祖父节点。

      2. 父变黑，祖父变红。

    • 当前节点是父的左孩子（RL型）：

      1. 先右旋父节点，转为 RR 型。

      2. 再左旋祖父节点。

      3. 当前节点变黑，祖父变红。

5. 确保根节点为黑

  • 最终将根节点颜色设为黑色。

旋转操作

左单旋和右单旋

private:void RotateL(Node* parent){++_rotateCount;Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}void RotateR(Node* parent){++_rotateCount;Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}}

红黑树的左单旋和右单旋跟AVL树的思路一样，唯一不同的是最后不需要调整平衡因子。

平衡验证

代码

private:bool CheckColour(Node* root, int blacknum, int benchmark){if (root == nullptr){if (blacknum != benchmark)路径黑色节点数是否一致。return false;return true;}if (root->_col == BLACK){++blacknum;}//是否存在连续红色节点。if (root->_col == RED && root->_parent && root->_parent->_col == RED){cout << root->_kv.first << "出现连续红色节点" << endl;return false;}return CheckColour(root->_left, blacknum, benchmark)&& CheckColour(root->_right, blacknum, benchmark);}bool IsBalance(Node* root){if (root == nullptr)return true;if (root->_col != BLACK)//确保根节点为黑色。{return false;}// 统计最左路径黑色节点数作为基准值。int benchmark = 0;Node* cur = _root;while (cur){if (cur->_col == BLACK)++benchmark;cur = cur->_left;}return CheckColour(root, 0, benchmark);//调用 CheckColour 递归验证。}public:bool IsBalance(){return IsBalance(_root);}

思路分析

1.IsBalance 入口函数：

  • 确保根节点为黑色。

  • 统计最左路径黑色节点数作为基准值。

  • 调用 CheckColour 递归验证。

2.CheckColour 递归检查：

  • 路径黑色节点数是否一致。

  • 是否存在连续红色节点。

二、map和set的封装实现

1.红黑树改造

1.1 节点结构改造

template<class T>
struct RBTreeNode {RBTreeNode<T>* _left;RBTreeNode<T>* _right;RBTreeNode<T>* _parent;T _data;          // 存储数据（set存key，map存pair）Colour _col;      // 节点颜色RBTreeNode(const T& data): _data(data), _col(RED), _left(nullptr), _right(nullptr), _parent(nullptr) {}
};

设计要点：

  • 使用模板参数T统一存储数据类型

  • set实例化时T=K，map实例化时T=pair<const K,V>

  • 保持红黑树基础结构（三叉链、颜色标记）

1.2 红黑树模板参数设计

template<class K, class T, class KeyOfT>
class RBTree {// K: 键值类型// T: 节点数据类型// KeyOfT: 仿函数，用于提取比较键值
};

关键参数说明：

参数set实例化map实例化
KKey类型Key类型
TKey类型pair<const Key, Value>
KeyOfTSetKeyOfT（返回自身）MapKeyOfT（返回pair.first）

1.3 仿函数实现细节

// Set侧的键值提取
struct SetKeyOfT {const K& operator()(const K& key) {return key;  // 直接返回Key本身}
};// Map侧的键值提取
struct MapKeyOfT {const K& operator()(const pair<K, V>& kv) {return kv.first;  // 仅提取pair中的Key部分}
};

作用：

  • 统一比较接口，避免直接比较pair类型的对象

  • 保证比较逻辑的一致性（只使用Key部分进行比较）

2.迭代器系统实现

2.1 迭代器核心结构

template<class T, class Ptr, class Ref>
struct __TreeIterator {typedef RBTreeNode<T> Node;Node* _node;// 支持普通迭代器构造const迭代器__TreeIterator(const __TreeIterator<T, T*, T&>& it): _node(it._node) {}// 解引用操作符Ref operator*() { return _node->_data; }// 成员访问操作符Ptr operator->() { return &_node->_data; }// 前置++操作符Self& operator++() {if (_node->_right) {// 右子树存在，找右子树最左节点Node* subLeft = _node->_right;while (subLeft->_left) {subLeft = subLeft->_left;}_node = subLeft;} else {// 右子树不存在，向上查找祖先Node* cur = _node;Node* parent = cur->_parent;while (parent && cur == parent->_right) {cur = parent;parent = parent->_parent;}_node = parent;}return *this;}
};

遍历特性：

  • 实现红黑树的中序遍历（升序访问）

  • 时间复杂度：均摊O(1)

  • 空间复杂度：O(1)（无需栈结构）

2.2 容器迭代器定义 

// map侧迭代器定义
typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator;// set侧迭代器定义
typedef typename RBTree<K, K, SetKeyOfT>::const_iterator iterator;

关键差异：

容器迭代器类型可修改性
map普通迭代器可修改value，不可修改key
setconst迭代器完全不可修改元素

3.插入操作深度解析

3.1 插入函数改造

pair<iterator, bool> Insert(const T& data)
{// [1] 空树处理if (_root == nullptr) {_root = new Node(data);_root->_col = BLACK;return make_pair(iterator(_root), true);}// [2] 查找插入位置Node* parent = nullptr;Node* cur = _root;KeyOfT kot;while (cur) {parent = cur;if (kot(cur->_data) < kot(data))cur = cur->_right;else if (kot(cur->_data) > kot(data))cur = cur->_left;elsereturn make_pair(iterator(cur), false);}// [3] 创建新节点cur = new Node(data);cur->_col = RED;  // 新节点初始为红色// ... 连接节点 ...// [4] 平衡调整（核心逻辑）while (parent && parent->_col == RED) {// 处理红红冲突// 包含颜色翻转、旋转等操作...}_root->_col = BLACK;  // 确保根节点为黑色return make_pair(iterator(newnode), true);
}

关键改进点：

  • 返回值改为pair<iterator, bool>，便于获取插入位置

  • 使用KeyOfT仿函数统一比较逻辑

3.2 返回值处理

// map侧直接转发
pair<iterator, bool> insert(const pair<K, V>& kv) {return _t.Insert(kv);
}// set侧需要处理const迭代器
pair<iterator, bool> insert(const K& key) {auto ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);
}

特殊处理：

  • set的iterator本质是const_iterator，防止修改Key值

  • 通过迭代器构造函数实现普通迭代器到const迭代器的转换（具体实现见迭代器核心结构处的代码）

4.容器完整实现

map完整实现

template<class K, class V>
class map {struct MapKeyOfT {const K& operator()(const pair<const K, V>& kv) {return kv.first;}};typedef RBTree<K, pair<const K, V>, MapKeyOfT> RBTree;
public:typedef typename RBTree::iterator iterator;iterator begin() { return _t.begin(); }iterator end() { return _t.end(); }V& operator[](const K& key) {pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& kv) {return _t.Insert(kv);}private:RBTree _t;
};

set完整实现

template<class K>
class set {struct SetKeyOfT {const K& operator()(const K& key) {return key;}};typedef RBTree<K, K, SetKeyOfT> RBTree;
public:typedef typename RBTree::const_iterator iterator;iterator begin() const { return _t.begin(); }iterator end() const { return _t.end(); }pair<iterator, bool> insert(const K& key) {auto ret = _t.Insert(key);return pair<iterator, bool>(ret.first, ret.second);}private:RBTree _t;
};

 

 

关键字：logo制作在线_企业软件定制开发包括_sem竞价教程_网站优化效果

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

责任编辑：
>> 相关文章
>> 热门图片
小程序外包公司发展前景_优化方案数学2024电子版_成都网络营销搜索推广_百度一下首页登录
小程序外包公司发展前景_优化方案数学2024电子版_成都网络营销搜索推广_百度一下首页登录
官网维护是什么意思_公开招标网站_最新舆情信息网_怎么找到当地的微信推广
官网维护是什么意思_公开招标网站_最新舆情信息网_怎么找到当地的微信推广
手机银行网站建设_广告联盟平台哪个好_网络黄页推广软件哪个好_关键词规划师工具
手机银行网站建设_广告联盟平台哪个好_网络黄页推广软件哪个好_关键词规划师工具
流程图制作网页_简历电子模版免费下载_武汉seo搜索引擎_网络营销活动策划方案模板
流程图制作网页_简历电子模版免费下载_武汉seo搜索引擎_网络营销活动策划方案模板
无锡网站制作优化排名_网页生成app在线_友情链接平台网站_亚马逊站外推广网站
无锡网站制作优化排名_网页生成app在线_友情链接平台网站_亚马逊站外推广网站
seo发展现状_成都教育行业网站建设_百度广告电话号码是多少_百度竞价账户
seo发展现状_成都教育行业网站建设_百度广告电话号码是多少_百度竞价账户
东莞广告设计公司排名_北京实创装修公司官网_无限制访问国外的浏览器_seogw
东莞广告设计公司排名_北京实创装修公司官网_无限制访问国外的浏览器_seogw
有创意的网络公司名字大全_简述网站开发技术_什么是seo技术_公司地址怎么弄在百度上显示
有创意的网络公司名字大全_简述网站开发技术_什么是seo技术_公司地址怎么弄在百度上显示
>> 热门搜索
评论排行
图片新闻
更多>>
十大免费行情软件网站下载_温州快建网站_深圳优化网站方法_怎么做网站?
logo制作在线_企业软件定制开发包括_sem竞价教程_网站优化效果
公众号开发难吗_b2c跨境电商平台有哪几个_绍兴seo网站推广_关键词优化seo公司
实战：MyBatis适配多种数据库：MySQL、Oracle、PostGresql等
点击排行

邮箱：809451989@qq.com 网站地图
未经过本站允许,请勿将本站内容传播或复制