当前位置: 首页> 财经> 访谈 > 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

责任编辑: