开锁换锁做网站,网站外链要怎么做,基于html5的网站建设论文,网站备案域名备案1、引言
在数据结构与算法的学习与实践中#xff0c;关联容器#xff08;associative containers#xff09;是不可忽视的重要工具。作为高效管理数据的一类容器#xff0c;C 标准库中的 set 和 map 在现代软件开发中扮演着关键角色。这两个容器通过平衡二叉搜索树#x…1、引言
在数据结构与算法的学习与实践中关联容器associative containers是不可忽视的重要工具。作为高效管理数据的一类容器C 标准库中的 set 和 map 在现代软件开发中扮演着关键角色。这两个容器通过平衡二叉搜索树如红黑树的底层实现能够在 O(log n) 的时间复杂度下完成插入、查找、删除等操作因此被广泛应用于需要有序存储、快速检索和动态调整的数据集场景中。
set 容器作为一种不允许重复元素的集合类型在许多涉及集合操作的应用中具有优势比如对数据的去重处理、集合的并集和交集等。由于它保证元素的唯一性和自动排序set 是实现有序集合、去重列表等场景下不可或缺的工具。同时set 容器具有多种变体如 multiset允许重复元素的存储提供了更大的灵活性。
相比之下map 容器则是以键值对的形式存储数据的关联容器。通过基于键的快速查找map 在需要频繁检索、插入或更新数据的场景下表现出色。其键值对的存储结构不仅确保键的唯一性同时自动按键的顺序进行排序因此在实现字典、哈希表、数据库索引等应用时尤为高效。此外C 标准库中还提供了 multimap允许键重复以满足不同场景下的需求。
这两种容器的底层实现通常依赖于平衡二叉搜索树尤其是红黑树。红黑树是一种能够在插入、删除过程中始终保持平衡的自平衡二叉搜索树这使得 set 和 map 能够在任何操作中维持较低的时间复杂度。理解红黑树的结构与性质是深入理解 set 和 map 内部实现机制的关键。
本博客的目的在于通过技术深度的分析与代码实现深入讲解 C 中 set 和 map 容器的理论与实际应用。在接下来的章节中我们将首先介绍 set 和 map 的数据结构与性质分析其基本操作的实现原理。然后我们会结合具体代码**讲解这些容器的底层实现方式重点探讨红黑树在 set 和 map 中的核心作用。**最后我们还将探讨 set 和 map 在实际项目中的应用场景及优化策略为读者提供实践中的参考依据。
通过这篇博客您将不仅能够掌握 set 和 map 的基本用法还能对其内部工作原理有深入理解并且学会在不同场景下灵活运用这些容器以实现更高效、可扩展的数据结构解决方案。
如果你对 二叉搜索树 还不够了解我的这篇关于 二叉搜索树 的博客请一定不要错过《 C 修炼全景指南九 》打破编程瓶颈掌握二叉搜索树的高效实现与技巧
如果你对 **AVL 树 **还不够了解我的这篇关于 AVL 树 的博客请一定不要错过《 C 修炼全景指南十 》自平衡的艺术深入了解 AVL 树的核心原理与实现
如果你对 红黑树 还不够了解我的这篇关于 红黑树 的博客请一定不要错过《 C 修炼全景指南十一 》穿越数据的红与黑掌握数据平衡的极致艺术
2、容器的基础概念与使用
C 标准库中的 set 和 map 是两种常见的关联容器均使用自平衡二叉搜索树——通常是**红黑树Red-Black Tree**作为其底层数据结构。红黑树的平衡性保证了这些容器的操作时间复杂度始终维持在 O(log n)无论是插入、删除还是查找操作。因此set 和 map 容器在大量数据场景下具备良好的性能表现。接下来我们将通过详细的代码示例展示 set 和 map 的常见操作并结合技术深度探讨其背后的实现原理和应用场景。
2.1、容器
在讨论 set 和 map 之前有必要先了解 C 标准库中的容器分类。这些容器分为 序列式容器Sequence Containers 和 关联式容器Associative Containers它们各自有不同的结构、实现原理以及适用场景。通过理解它们的特性能够帮助我们更好地选择合适的容器来解决特定问题。
2.1.1、序列式容器Sequence Containers
序列式容器是一类用于存储和管理数据元素的线性数据结构它们主要提供了按照顺序存储元素的功能。在这些容器中元素的排列顺序与其插入顺序保持一致。序列式容器支持随机访问允许我们根据元素的存储位置进行高效的插入、删除、修改和访问。
序列式容器主要包括以下几类 string std::string 是 C 中处理字符串的标准容器基于动态数组实现并提供了一系列字符串相关的操作。 时间复杂度 随机访问O(1)尾部插入/删除摊还复杂度 O(1)中间插入/删除O(n) 使用场景与传统的 C 风格字符串使用 char 数组和空字符 \0 作为结束符相比std::string 提供了更方便、安全的接口并具备动态扩展能力能够自动管理内存。《 C 修炼全景指南二 》告别平庸实现一个比标准库更强的 C String 类 vector vector 是一种动态数组容器能够根据需要动态扩展或缩小容量。它提供了高效的随机访问和尾部插入、删除操作但在数组中间或开头插入和删除元素的效率较低因为会涉及元素的移动。 时间复杂度 随机访问O(1)尾部插入/删除摊还复杂度 O(1)中间插入/删除O(n) 使用场景适用于需要频繁随机访问或尾部操作的场景如动态数组管理、临时存储等。《 C 修炼全景指南三 》如何实现标准库般强大的 C Vector从动态扩容到移动语义到迭代器全覆盖 list list 是双向链表支持高效地在任何位置进行插入和删除操作但不支持随机访问。由于链表的元素不连续存储访问元素的时间复杂度较高因此不适用于需要频繁随机访问的场景。 时间复杂度 插入/删除O(1)随机访问O(n) 使用场景适用于需要频繁插入和删除元素但不需要随机访问的场景如任务队列、事件调度等。《 C 修炼全景指南四 》揭秘 C List 容器背后的实现原理带你构建自己的双向链表 deque deque 是双端队列支持在头部和尾部高效地插入和删除元素。与 vector 相比它在两端插入和删除元素的性能要更好但在中间插入或删除元素时效率与 vector 类似。 时间复杂度 随机访问O(1)头部/尾部插入/删除O(1)中间插入/删除O(n) 使用场景适用于双端队列操作如需要频繁从头部和尾部进行插入和删除操作的场景。 《 C 修炼全景指南五 》实现媲美 C 标准库的 stack 和 queue 容器 —— 模板、动态扩容、迭代器与线程安全详解 《 C 修炼全景指南六 》深入探索 C 标准库中的 stack 与 queue 容器适配器
序列式容器的特点
支持元素按照插入顺序存储保证顺序一致。提供灵活的内存管理和高效的线性操作。string、 vector 和 deque 支持随机访问而 list 不支持。
2.1.2、关联式容器Associative Containers
与序列式容器不同关联式容器使用的是基于特定规则进行元素存储和管理的树结构或哈希表结构。关联式容器通过键值对来管理数据自动为插入的元素进行排序或管理支持高效的查找、插入和删除操作。
关联式容器主要包括两类
有序关联式容器 使用 红黑树 作为底层数据结构确保所有元素按照某种规则排序。在有序关联式容器中元素之间有明确的顺序查找和操作的时间复杂度通常为 O(log n)。包括 set元素唯一且自动排序的集合容器。map以键值对存储数据键是唯一的并且按键排序。multiset允许重复元素的集合其他特性与 set 类似。multimap允许重复键的键值对容器其他特性与 map 类似。 无序关联式容器 使用 哈希表 作为底层数据结构通过哈希函数来管理数据。无序关联式容器不保证元素的顺序但在大多数情况下查找、插入和删除操作的平均时间复杂度为 O(1)。包括 unordered_set基于哈希表实现的集合不保证顺序元素唯一。unordered_map基于哈希表实现的键值对容器键是唯一的。unordered_multiset基于哈希表实现的集合允许重复元素。unordered_multimap基于哈希表实现的键值对容器允许重复键。
2.1.3、键值对
在 C 标准库中键值对数据结构的代表性容器主要是 std::map 和 std::unordered_map。这两种容器广泛用于需要存储和管理键值对的场景。键值对**用来表示具有一一对应关系的一种结构该结构中一般只包含两个成员变量 key 和 value key 代表键值 value 表示与 key 对应的信息。**键值对的数据结构通常用于需要根据某个键快速查找到对应值的场景。C 标准库中的 std::map 和 std::unordered_map 正是为这一需求而设计的。
键Key通常是一个唯一的标识符用来访问关联的值。在一个键值对容器中键不能重复。值Value与键相关联的数据可以是任何类型包括基础数据类型或自定义类型。
键值对容器的目标是提供高效的键查找、插入和删除操作且在查找键时能够保证键的唯一性。比如现在要建立一个英汉互译的字典那该字典中必然有英文单词与其对应的中文含义而且英文单词与其中文含义是一一对应的关系即通过该单词在词典中就可以找到与其对应的中文含义。
SGI-STL 中关于键值对的定义
template class T1, class T2
struct pair
{typedef T1 first_type;typedef T2 second_type;T1 _first;T2 _second;pair(): _first(T1()), _second(T2()){}pair(const T1 a, const T2 b): _first(a), _second(b){}
};pair 文档
2.2、set 的定义与实现原理
2.2.1、set 的定义
set 是一种无重复元素的集合容器通常用于存储需要保证唯一性的元素。它通过维护一个内部有序的结构确保元素插入时的顺序是基于元素的排序规则的。C 中的 set 默认基于 运算符的排序规则排列元素因此在迭代访问时set 中的元素总是按照升序排列。
set 的底层实现基于红黑树利用红黑树的平衡性来保证查找、插入、删除操作的时间复杂度始终为 O(log n)。每次插入新元素时set 会根据其排序规则判断该元素在树中的位置如果发现重复元素插入操作会被拒绝从而确保元素的唯一性。
三万字详解真的值得一看喔《 C 修炼全景指南十一 》穿越数据的红与黑掌握数据平衡的极致艺术
2.2.2、set 的常用操作
set 文档
红黑树作为 set 容器的底层数据结构其插入、删除、查找等操作均是通过红黑树的基本操作来实现的。
1、set 的模板参数列表
template class T, // set::key_type/value_type class Compare lessT, // set::key_compare/value_compare class Alloc allocatorT // set::allocator_type class set;T:set 中存放元素的类型实际在底层存储 value, value 的键值对 Compare:set 中元素默认按照小于来比较 Alloc:set 中元素空间的管理方式使用 STL 提供的空间配置器管理 2、set 的构造
// 构造空的 set
explicit set (const key_compare comp key_compare(), const allocator_type alloc allocator_type());// 用 (first, last) 区间中的元素构造 set
template class InputIterator
set (InputIterator first, InputIterator last,const key_compare comp key_compare(),const allocator_type alloc allocator_type());// 拷贝构造
set (const set x);3、set 的迭代器 函数声明 功能介绍
iterator begin() // 返回 set 中起始位置元素的迭代器
iterator end() // 返回 set 中最后一个元素后面的选代器
const iterator cbegin() const // 返回 set 中起始位置元素的 const 迭代器
const iterator cend() const // 返回 set 中最后一个元素后面的 const 迭代器
reverse_iterator rbegin() // 返回 set 第一个元素的反向选代器即 end
reverse iterator rend() // 返回 set 最后一个元素下一个位置的反向选代器, 即 begin
const reverse iterator crbegin() const // 返回 set 第一个元素的反向const选代器, 即 cend
const reverse iterator crend() const // 返回 set 最后一个元素下一个位置的反向 const 选代器, 即 cbegin4、set 的容量 函数声明 功能介绍
bool empty( ) const // 检测 set 是否为空, 空返回 true, 否则返回 true
size_type size() const // 返回 set 中有效元素的个数5、set 的修改操作
函数声明 功能介绍
// 在 set 中插入元素 x, 实际插入的是 x, x 构成的键值对, 如果插入成功, 返回 该元素在 set 中的位置, true, 如果插入失败, 说明 x 在 set 中已经存在, 返回 x 在 set 中的位置, false
pairiterator,bool insert(const value_type x);// 删除 set 中 position 位置上的元素
void erase (iterator position );// 删除 set 中值为 x 的元素, 返回删除的元素的个数
size_type erase (const key_type x);// 删除 set 中 [first, last) 区间中的元素
void erase (iterator first, iterator last);// 交换 set 中的元素
void swap(setKey, Compare, Allocator st);// 将 set 中的元素清空
void clear ( );// 返回 set 中值为 x 的元素的位置
iterator find (const key_type x)const// 返回 set 中值为 x 的元素的个数
size _type count (const key_type x)const插入操作 在 set 中插入元素时系统会首先通过比较元素的大小来确定其在红黑树中的插入位置。如果待插入的元素与树中的某个节点相等插入操作会终止因为 set 容器要求所有元素唯一。若插入成功红黑树的平衡性可能会被打破因此插入操作完成后可能需要进行颜色调整和旋转操作以维持树的平衡。 删除操作 删除操作与插入类似首先需要找到要删除的元素随后将其从红黑树中移除。由于删除某个节点可能会破坏红黑树的平衡删除操作完成后通常需要重新调整树的颜色或者通过左旋、右旋操作恢复平衡。 查找操作 在 set 中查找某个元素时系统会根据红黑树的性质沿树路径依次进行元素比较。如果找到与目标元素相等的节点则查找成功。由于红黑树的高度始终保持在 O(log n)因此查找操作的时间复杂度同样为 O(log n)。 2.2.3、set 使用举例
void test_set1()
{setint s1; // set默认排序为从小到大 set底层是搜索树s1.insert(10);s1.insert(20);s1.insert(5);s1.insert(2);s1.insert(1);s1.insert(8);s1.insert(14);s1.insert(44);s1.insert(23);s1.insert(0);s1.insert(2);s1.insert(1);s1.insert(8);s1.insert(14);// 排序 去重setint::iterator it s1.begin();while (it ! s1.end()){//*it 100; // set中的元素是只读的不能修改cout *it ;it;}cout endl;// 范围forfor (auto e : s1){cout e ;}cout endl;// 拷贝构造 底层默认是一个深拷贝setint s2(s1);for (auto e : s2){cout e ;}cout endl;// 删除// find()是成员函数只能用于set/multiset/map/multimap// setint::iterator pos s2.find(5);auto pos s2.find(5);// find()是泛型算法可以用于所有容器// s.find() O(logN) s.begin() O(1) s.end() O(1)// find(s.begin(), s.end(), 5) O(N) 效率会低不少// auto pos find(s2.begin(), s2.end(), 5);if (pos ! s2.end()){s2.erase(pos);}for (auto e : s2){cout e ;}cout endl;// 或者直接删s2.erase(8);s2.erase(80); // 和迭代器的区别在于删除不存在的元素不会报错for (auto e : s2){cout e ;}cout endl;
}保证唯一性的机制
set 容器的独特性质在于它保证集合中的每个元素都是唯一的。为了实现这一点set 在插入元素时总是会首先查找该元素是否已存在。如果待插入的元素已存在于树中插入操作将被拒绝。红黑树的这种有序存储结构在维持树的平衡性的同时能够在 O(log n) 的时间内完成重复元素的检测和插入决策。
以下是 set 容器的插入操作示例代码
#include set
#include iostreamint main() {std::setint s;// 插入元素s.insert(10);s.insert(5);s.insert(15);// 插入重复元素不会成功auto result s.insert(10);if (!result.second) {std::cout 元素 10 已存在 std::endl;}return 0;
}在这个示例中set 容器成功插入了 10、5、15 三个元素但在尝试插入第二个 10 时插入操作被拒绝保证了集合的唯一性。
2.3、map 的定义与实现原理
2.3.1、map 的定义
map 是一种键值对key-value pair容器其每个元素都是由唯一的**键key和与其对应的值value**组成的。与 set 类似map 中的键是有序存储的但不同之处在于map 允许通过键查找其对应的值。C 标准库中的 map 默认也基于红黑树实现因此其查找、插入和删除操作的时间复杂度为 O(log n)。
map 的核心工作机制是通过键来管理数据键的唯一性是 map 容器的关键属性。这意味着在 map 中不能有两个元素具有相同的键。当向 map 插入新元素时如果该键已存在则新元素不会插入但其值会被更新。
2.3.2、map 的常用操作
map 文档
与 set 相同map 容器的插入、删除和查找操作均依赖于红黑树的平衡性来保持高效性。每个操作的本质与 set 类似只不过 map 的每个节点不仅存储键还存储与之相关联的值。
1、map 的模板参数说明
template class Key, // map::key_typeclass T, // map::mapped_typeclass Compare lessKey, // map::key_compareclass Alloc allocatorpairconst Key,T // map::allocator_type class map;key键值对中 key 的类型 T键值对中 value 的类型 Compare比较器的类型 map 中的元素是按照 key 来比较的缺省情况下按照小于来比较一般情况下内置类型元素该参数不需要传递如果无法比较时自定义类型需要用户自己显式传递比较规则一般情况下按照函数指针或者仿函数来传递 Alloc通过空间配置器来申请底层空间不需要用户传递除非用户不想使用标准库提供的空间配置器 注意在使用 map 时需要包含头文件 2、map 的构造
函数声明 功能介绍
map() // 构造一个空的 map3、map 的迭代器 函数声明 功能介绍
begin() 和 end() // begin: 首元素的位置, end 最后一个元素的下一个位置
cbegin() 和 cend() // 与 begin 和 end 意义相同, 但 cbegin 和 cend 所指向的元素不能修改
rbegin() 和 rend() // // 反向迭代器, rbegin 在 end 位置, rend 在 begin 位置其 和 -- 操作与 begin 和 end 操作移动相反
crbegin() 和 crend() // 与 rbegin 和 rend 位置相同, 操作相同, 但 crbegin 和 crend 所指向的元素不能修改4、map 的容量与元素访问 函数声明 功能简介
bool empty( ) const // 检测 map 中的元素是否为空, 是返回 true, 否则返回 false
size_type size() const // 返回 map 中有效元素的个数
mapped type operator[](const key_type k) // 返回去 key 对应的 value问题当 key 不在 map 中时通过 operator 获取对应 value 时会发生什么问题 注意在元素访问时有一个与 operator[] 类似的操作 at() (该函数不常用)函数都是通过 key 找到与 key 对应的 value 然后返回其引用不同的是当 key 不存在时operator[] 用默认 value 与 key 构建键值对然后插入返回该默认 value at() 函数直接抛异常。
// map/multimap的下标运算符, 返回值是mapped_type, 如果key不存在, 就插入一个新的节点, value初始化为0
mapped_type operator[](const key_type key)
{return (*((this-insert(make_pair(key, mapped_type()))).first)).second;
}5、map 的修改操作
// 函数声明 功能简介
// 在 map 中插入键值对 x, 注意 x 是一个键值对, 返回值也是键值对: iterator 代表新插入元素的位置, bool代表释放插入成功
pairiterator,bool insert(const value_type x);// 删除 position 位置上的元索
void erase (iterator position);// 删除键值为 x 的元素
size_type erase( const key_type x);// 删除 [first, last) 区间中的元素
void erase(iterator first, iterator last);// 交换两个 map 中的元素
void swap(mapKey,T,Compare, Allocator mp);// 将 map 中的元素清空
void clear();// 在 map 中插入 key 为 x 的元素, 找到返回该元素的位置的迭代器, 否则返回 end
iterator find(const key_type x);// 在 map 中插入 key 为 x 的元素, 找到返回该元素的位置的 const 迭代器, 否则返回 cend
const iterator find (const key_type x) const// 返回 key 为 x 的键值在 map 中的个数, 注意 map 中 key 是唯一的, 因此该函数的返回值要么为 0, 要么为 1, 因此也可以用该函数来检测一个 key 是否在 map 中
size_type count(const key_type x) const1. 插入操作 当 map 中插入新的键值对时系统首先会查找该键是否已存在。如果键存在则插入失败但会更新与该键相关联的值。若键不存在则红黑树根据键的大小来确定新键值对的插入位置并按照红黑树的规则进行颜色调整和旋转操作以确保树的平衡性。 2. 删除操作 删除操作与 set 类似首先需要找到对应的键然后删除对应的键值对。删除完成后红黑树的平衡性可能会被破坏因此系统需要通过调整颜色或旋转操作来恢复平衡。 3. 查找操作 map 中的查找操作是通过键进行的。由于 map 是基于红黑树实现的查找过程遵循二叉搜索树的查找方式能够在 O(log n) 的时间复杂度下找到与目标键匹配的键值对。 2.3.3、map 使用举例
void test_map1()
{mapint, int m1;m1.insert(pairint, int(1, 1)); // pair是一个模板类可以用来创建pair对象m1.insert(pairint, int(3, 3));m1.insert(pairint, int(2, 2));m1.insert(pairint, int(5, 5));m1.insert(pairint, int(6, 6));m1.insert(pairint, int(4, 4)); // pair构造函数构造一个匿名对象然后插入到map中// 日常大家喜欢用make_pair()来构造pair对象因为他不用声明模板参数编译器自动推m1.insert(make_pair(7, 7)); // 函数模板构造一个pair对象mapint, int::iterator it m1.begin();while (it ! m1.end()){// cout *it ; // C不支持返回两个数cout (*it).first (*it).second endl; // operator*()返回的是节点中值的引用cout it-first it-second endl; // operator-()返回的是节点的指针 也就是pairk, v的指针it;}cout endl;// 范围forfor (auto e : m1){cout e.first e.second endl;}cout endl;
}void test_map2()
{std::mapstd::string, std::string dirt;dirt.insert(pairstd::string, std::string(sort, 排序));dirt.insert(make_pair(string, 字符串));dirt.insert(make_pair(left, 左边)); // 按照ASCII码排序std::mapstd::string, std::string::iterator it dirt.begin();while (it ! dirt.end()){cout it-first it-second endl;it;}cout endl;
}void test_map3()
{// 统计单词出现的次数string strArr[] {西瓜, 苹果, 西瓜, 苹果, 西瓜, 香蕉, 西瓜, 樱桃, 西瓜, 苹果,西瓜, 苹果, 西瓜, 香蕉, 西瓜, 樱桃, 西瓜, 苹果, 西瓜, 苹果, 西瓜, 香蕉,西瓜, 樱桃, 西瓜, 苹果, 西瓜, 苹果, 西瓜, 香蕉, 西瓜, 樱桃, 西瓜, 苹果,西瓜, 苹果, 西瓜, 香蕉, 西瓜, 樱桃, 西瓜, 苹果, 西瓜, 苹果, 西瓜, 香蕉};mapstring, int countMap;// 第一种方法for (auto str : strArr){mapstring, int::iterator pos countMap.find(str);if (pos ! countMap.end()){pos-second;}else{countMap.insert(make_pair(str, 1));}}for (auto e : countMap){cout e.first e.second endl;}cout endl;// 第二种方法for (auto str : strArr){pairmapstring, int::iterator, bool ret countMap.insert(make_pair(str, 1));if (ret.second false) // 插入失败说明已经存在{ret.first-second; // 迭代器指向的是插入的元素}}for (auto e : countMap){cout e.first e.second endl;}cout endl;// 第三种方法for (auto str : strArr){// 1、如果水果不在map中则[]会插入pairstr, 0, 返回映射对象次数的引用进行// 2、如果水果在map中则[]会返回水果对应的映射对象次数的引用对它进行countMap[str];}countMap[葡萄]; // 插入 一般不这么用countMap[葡萄] 100; // 修改cout countMap[葡萄] endl; // 查找countMap[哈密瓜] 5; // 插入 修改// 一般使用operator[]去// 1、插入 修改// 2、修改// 一般不会用他去做查找因为如果key不在会插入数据。for (auto e : countMap){cout e.first e.second endl;}cout endl;
}int main()
{// test_set1();test_map1();// test_map2();// test_map3();return 0;
}2.4、multiset multimap 的介绍
multimap 文档
在 C 标准库中除了 set 和 map还有两种关联容器——multiset 和 multimap它们允许存储多个相同的键。与 set 和 map 不同的是multiset 和 multimap 允许键重复因此在特定应用场景中如处理不唯一的集合或键值对它们非常有用。接下来我们将详细探讨 multiset 和 multimap 的理论基础、常见操作以及实际应用。 multimap 是关联式容器它是按照特定顺序存储右 key 和 value 映射成的键值对 key, value 其中多个键值对之间的 key 是可以重复的。 在 multimap 中通常按照 key 排序和唯一地标识元素而映射的 value 存储与 key 关联的内容。key 和 value 的类型可能不同通过 multimap 内部成员类型 value_type 组合在一起value_type 是组合 key 和 value 的键值对 typedef pairconst Key, T value_type; 在内部multimap 中的元素总是通过其内部比较对象按照指定的特定严格弱排序标准对 key 进行排序的 multimap 通过 key 访问单个元素的速度通常比 unordered_multimap 容器慢但是使用迭代器直接遍历 multimap 中的元素可以得到关于 key 有序的序列 multimap 在底层用二叉搜索树红黑树来实现 注意multimap 和 map 的唯一不同就是map 中的 key 是唯一的而 multimap 中 key 是可以重复的 multimap 中的接口可以参考 map 功能都是类似的 注意 multimap 中的 key 是可以重复的multimap 中的元素默认将 key 按照小于来比较multimap 中没有重载 operator[] 操作使用时与 map 包含的头文件相同 multiset multimap 使用举例
void test_multi()
{// multiset根set的区别就是允许键值冗余multisetint s1; // 使用和set一样只是multiset可以存放重复的元素s1.insert(10);s1.insert(20);s1.insert(5);s1.insert(2);s1.insert(1);s1.insert(8);s1.insert(8);s1.insert(14);s1.insert(44);s1.insert(23);s1.insert(0);s1.insert(2);s1.insert(1);s1.insert(8);s1.insert(8);s1.insert(14);for (auto e : s1){cout e ;}cout endl;auto pos s1.find(8); // 查找到的是重复元素的第一个元素地址cout *pos endl;pos;cout *pos endl;pos;cout *pos endl;pos;cout *pos endl;pos;cout *pos endl;// multimap和map的区别和上面是一样的multimapstring, int mm;mm.insert(make_pair(苹果, 1));mm.insert(make_pair(苹果, 1));mm.insert(make_pair(苹果, 3));mm.insert(make_pair(西瓜, 2));mm.insert(make_pair(西瓜, 1));for (auto e : mm){cout e.first e.second endl;}cout endl;
}3、红黑树的封装
在这章中我们将从底层的红黑树设计开始逐步深入到 set 和 map 的封装与实现。但是本章不会对红黑树讲解的那么细致如果你对红黑树还不够细致这篇三万字详解红黑树的博客请一定不要错过《 C 修炼全景指南十一 》穿越数据的红与黑掌握数据平衡的极致艺术
我们的目标是通过代码和理论结合详尽介绍红黑树的结构、迭代器的设计、平衡树的旋转与修正、键值对的存储及其复杂度分析最终展现如何通过这些基础实现 C 标准库中重要的 set 和 map 容器。
3.1、红黑树节点的设计
红黑树的每个节点不仅要存储数据还必须包含颜色信息红或黑并通过指针链接至父节点、左子节点和右子节点。这些额外的信息使红黑树能够在插入和删除操作后保持平衡并保证操作的时间复杂度为 O(log n)。
3.1.1、节点结构
我们为红黑树设计的节点结构如下
namespace Lenyiin
{enum Colour{RED,BLACK};template class Tstruct RBTreeNode{RBTreeNodeT *_left; // 左子节点RBTreeNodeT *_right; // 右子节点RBTreeNodeT *_parent; // 父节点T _data; // 节点存储的数据Colour _colour; // 节点的颜色红色或黑色// 节点的构造函数默认为红色节点RBTreeNode(const T data): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _colour(RED){}};
}3.1.2、节点结构详解
在这个节点设计中我们使用模板参数 T 来支持不同的数据类型。每个节点包含五个成员变量
_left: 指向左子节点的指针。_right: 指向右子节点的指针。_parent: 指向父节点的指针。这允许我们在树中进行向上回溯操作。_data: 存储的数据可以是任意类型。_colour: 表示节点的颜色枚举类型 Colour 包含红色和黑色两个值。
在红黑树中根节点的颜色始终是黑色新插入的节点初始为红色。当红黑树进行插入或删除操作时节点颜色可能会发生变化以维持红黑树的平衡性。
3.1.3、节点颜色的重要性
红黑树的平衡特性依赖于节点的颜色以及颜色的相关规则
每个节点要么是红色要么是黑色。根节点必须是黑色。所有叶子节点NIL 节点通常用空节点表示必须是黑色。如果一个节点是红色的那么它的两个子节点必须是黑色的即不能有两个连续的红色节点。从任一节点到其所有叶子节点的路径上必须包含相同数量的黑色节点。
这些规则的目的在于保持树的近似平衡即红黑树的高度不会超过 O(log n)从而保证其高效性。
3.1.4、节点内存管理
在实际实现中红黑树的节点通常是动态分配的。每次插入新元素时会创建一个新的节点对象并插入到树中。而在删除节点时则需要负责释放相应的内存空间。
为避免内存泄漏我们需要在红黑树的析构函数中处理节点的删除和内存释放操作。为了简化操作可以设计一个递归的删除函数
// 删除整个红黑树
void DeleteTree(Node *root)
{if (root nullptr){return;}// 递归删除左子树DeleteTree(root-_left);// 递归删除右子树DeleteTree(root-_right);// 删除当前节点delete root;
}这样当红黑树析构时我们只需调用 DeleteTree(_root) 即可销毁整棵树。
3.2、红黑树的迭代器设计
在 STL 标准库中容器类的迭代器被设计为一种通用接口允许用户以统一的方式访问容器的元素。C 标准库中 set 和 map 容器都提供了迭代器接口允许用户像操作数组一样方便地遍历容器中的元素。因此我们的红黑树封装也需要提供类似的迭代器。
设计原则
双向遍历迭代器需要支持从当前节点向前或向后移动确保可以顺序遍历容器中的元素。中序遍历顺序对于有序关联容器如 set 和 map迭代器应确保以中序遍历的顺序访问元素使得节点的遍历顺序与键值的升序或降序一致。稳定性与高效性迭代器操作应尽可能高效避免无谓的计算和内存占用并保持稳定的时间复杂度。内存安全在迭代器使用过程中应避免悬空指针等错误。
3.2.1、迭代器的基本结构
迭代器的设计通常是基于指针的它持有一个指向树节点的指针并通过重载运算符来实现对树节点的遍历操作。为了实现双向迭代器我们需要重载增量和减量--运算符保证用户能够顺利进行正向和反向的遍历。首先我们定义迭代器的结构如下
namespace Lenyiin
{template class T, class Ref, class Ptrstruct __TreeIterator{typedef RBTreeNodeT Node;typedef __TreeIteratorT, Ref, Ptr Self;Node *_node; // 当前迭代器指向的节点// 构造函数__TreeIterator(Node *node): _node(node){}// 解引用操作符Ref operator*(){return _node-data;}// 访问成员操作符Ptr operator-(){return _node-_data;}// 前置递增运算符Self operator(){// 1. 如果右不为空, 中序的下一个就是右子树的最左节点if (_node-_right){Node *subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}_node subLeft;}// 2. 如果右为空, 表示 _node 所在的子树已经完成, 下一个节点在他祖先中去找, 沿着路径往上找孩子使它的左的那个祖先else{Node *cur _node;Node *parent cur-_parent;while (parent cur parent-_right){cur parent;parent cur-_parent;}_node parent;}return *this;}// 后置递增运算符Self operator(int){Node *tmp _node;(*this);return Self(tmp);}// 前置递减运算符Self operator--(){// 1. 如果左不为空, 中序的上一个就是左树的最右节点if (_node-_left){Node *subRight _node-left;while (subRight-_right){subRight subRight-_right;}_node subRight;}// 2. 如果左为空, 表示 _node 所在的子树已经完成, 上一个节点在他祖先中去找, 沿着路径往上找孩子是它的右的那个祖先else{Node *cur _node;Node *parent cur-_parent;while (parent cur parent-_left){cur parent;parent cur-_parent;}_node parent;}return *this;}// 后置递减运算符Self operator--(int){Node *tmp _node;--(*this);return Self(tmp);}bool operator!(const Self n){return _node ! n._node;}bool operator(const Self n){return _node n._node;}};
}3.2.2、迭代器 – 详解
红黑树是一种二叉搜索树迭代器的遍历应该遵循二叉搜索树的中序遍历规则。中序遍历的顺序为左子树 - 当前节点 - 右子树这确保了迭代器访问节点时的顺序是按键值升序排列的。
例如给定如下结构的红黑树 20/ \10 30/ \ \5 15 40中序遍历的结果应该是5 - 10 - 15 - 20 - 30 - 40。
在迭代器的实现中 运算符用于实现正向的中序遍历而 -- 运算符用于实现逆向遍历。我们分别介绍这两个操作的细节。
1、前置递增运算符 (operator)
为了从当前节点移动到树中的下一个节点即中序遍历中的下一个节点我们需要找到中序后继。如果当前节点有右子节点那么下一个节点应该是其右子树的最左节点否则我们需要向上移动直到找到一个节点它是其父节点的左子树。
// 前置递增运算符
Self operator()
{// 1. 如果右不为空, 中序的下一个就是右子树的最左节点if (_node-_right){Node *subLeft _node-_right;while (subLeft-_left){subLeft subLeft-_left;}_node subLeft;}// 2. 如果右为空, 表示 _node 所在的子树已经完成, 下一个节点在他祖先中去找, 沿着路径往上找孩子使它的左的那个祖先else{Node *cur _node;Node *parent cur-_parent;while (parent cur parent-_right){cur parent;parent cur-_parent;}_node parent;}return *this;
}这个函数逻辑可以分为两种情况
如果当前节点有右子节点则它的后继节点是右子树中最左的那个节点。如果当前节点没有右子节点则需要沿着父指针向上移动直到找到一个节点它是其父节点的左子节点那么这个父节点就是当前节点的后继。
2、前置递减运算符 (operator--)
类似地前置递减运算符需要找到中序前驱。如果当前节点有左子节点则前驱节点是左子树中的最右节点否则沿着父指针向上移动直到找到一个节点它是其父节点的右子节点。
// 前置递减运算符
Self operator--()
{// 1. 如果左不为空, 中序的上一个就是左树的最右节点if (_node-_left){Node *subRight _node-left;while (subRight-_right){subRight subRight-_right;}_node subRight;}// 2. 如果左为空, 表示 _node 所在的子树已经完成, 上一个节点在他祖先中去找, 沿着路径往上找孩子是它的右的那个祖先else{Node *cur _node;Node *parent cur-_parent;while (parent cur parent-_left){cur parent;parent cur-_parent;}_node parent;}return *this;
}类似地这个函数逻辑也可以分为两种情况
如果当前节点有左子节点则它的前驱节点是左子树中最右的那个节点。如果当前节点没有左子节点则需要沿着父指针向上移动直到找到一个节点它是其父节点的右子节点那么这个父节点就是当前节点的前驱。
3.2.3、迭代器的边界处理
为了确保迭代器的健壮性特别是在处理树的边界情况时例如到达叶子节点的末尾我们需要额外处理end()和begin()的位置
end()当迭代器超出红黑树的最后一个节点时迭代器应该指向树中的“虚拟末尾”位置即 nullptr。这意味着如果调用 运算符使迭代器越过树的最后一个节点_node 应该被设置为 nullptr。begin()同理调用 -- 运算符使迭代器超出第一个节点时也应当触发相应的边界处理确保访问第一个节点之前的位置时指向 nullptr。
3.3、旋转操作
在红黑树中旋转操作是保持红黑树性质的核心步骤之一。在执行插入或删除操作时红黑树可能会违反其性质这时候通过旋转操作可以重新调整树的结构使其满足红黑树的平衡要求。旋转操作主要分为两种左旋和右旋。通过这两种操作我们可以在局部调整树的形状使得其符合红黑树的性质。
3.3.1、左旋
左旋操作是将节点向左旋转使其右子节点上升为其父节点而原节点下降为其右子节点的左子节点。这种旋转主要用于调整在右孩子方向上失衡的情况。
场景当新节点插入到某个节点的右子树的右子节点时可能导致该节点失衡。此时需要进行左旋操作来恢复平衡。
旋转过程
假设不平衡节点为 A其右子节点为 B。B 的左子树 BL 将成为 A 的右子树。B 成为新的子树根节点而 A 成为 B 的左子节点。
示例图
插入导致的结构 A\B\C单左旋后的结构 B/ \A C代码实现
// 左旋
void RotateL(Node* parent)
{Node* ppNode parent-_parent;Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL){subRL-_parent parent;}subR-_left parent;parent-_parent subR;// 1. 原来 parent 是这棵树的根, 现在 subR 是根if (parent _root){_root subR;subR-_parent nullptr;}// 2. parent 为根的树只是整棵树中的子树, 改变链接关系, 那么 subR 要顶替他的位置else{if (ppNode-_left parent){ppNode-_left subR;}else{ppNode-_right subR;}subR-_parent ppNode;}
}解释
subR 指向 A 的右子节点 B。B 的左子树 subRL 被挂接到 A 的右子树。B 成为新的根节点A 成为 B 的左子节点。
3.3.2、右旋
右旋操作是左旋的镜像操作。它将节点向右旋转使其左子节点上升为其父节点而原节点下降为其左子节点的右子节点。右旋主要用于调整在左孩子方向上失衡的情况。
场景当新节点插入到某个节点的左子树的左子节点时可能导致该节点失衡。此时需要进行右单旋操作来恢复平衡。
旋转过程
假设不平衡节点为 A其左子节点为 B。B 的右子树 BR 将成为 A 的左子树。B 成为新的子树根节点而 A 成为 B 的右子节点。
示例图
插入导致的结构 A/ B /
C 单右旋后的结构 B/ \C A代码实现
// 右旋
void RotateR(Node* parent)
{Node* ppNode 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 (parent _root){_root subL;subL-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}
}详细解释
parent 是节点 AsubL 指向 A 的左子节点 B。B 的右子树 subLR 被挂接到 A 的左子树。B 成为新的根节点A 成为 B 的右子节点。
3.3.3、旋转操作的技术细节
在红黑树的插入和删除操作中我们使用旋转操作来调整树的平衡。具体来说旋转操作的目的是减少树的高度或者说是重新分配子树的高度使得整个树的结构更加平衡。在红黑树中执行旋转操作不会破坏二叉搜索树的性质即中序遍历的顺序仍然保持不变。
左旋与右旋的对称性左旋和右旋是对称操作左旋将节点的右子树移至父节点而右旋将节点的左子树移至父节点。两者的实现过程是对称的这也使得在红黑树的调整中可以灵活运用两者来维护树的平衡。复杂度单次旋转操作的时间复杂度为 O(1) 。旋转操作只涉及指针的改变不需要遍历树的节点因此是一个非常高效的操作。调整树的高度通过左旋或右旋红黑树可以减少某个子树的高度或者在某个方向上增加子树的高度。这样就能在插入或删除节点后通过旋转调整保持红黑树的高度平衡进而保证操作的时间复杂度为 O(logn) 。
3.3.4、旋转操作在插入和删除中的作用
在红黑树的插入和删除操作中我们主要通过旋转操作来维护红黑树的性质
插入调整在插入操作中可能会出现连续的红色节点违背红黑树的性质。通过旋转和重新着色可以确保红黑树的平衡。例如在插入一个节点后如果出现 “红-红” 冲突则根据叔叔节点的颜色不同我们需要执行左旋或者右旋或者双旋操作来调整树的结构。删除调整删除操作可能会破坏红黑树的平衡特别是当删除一个黑色节点时可能导致黑高不平衡。这时候通过旋转和重新着色可以重新平衡红黑树。例如在删除节点后如果当前节点的兄弟节点是黑色的且其子节点中有一个是红色则我们可以通过旋转和重新着色使得整棵树重新满足红黑树的性质。
通过上述两种旋转操作和调整逻辑红黑树能够在插入和删除操作后依然保持其性质从而确保查找、插入、删除操作的时间复杂度始终保持在 O(logn) 。这就是红黑树高效性和实用性的重要原因之一。
3.4、插入操作
为了实现更好的封装并且适应迭代器我们可以将红黑树的插入操作做一些改进并且为后续的 set 和 map 容器提供接口。
3.4.1、插入节点的基本逻辑
首先插入的第一步仍然是按照二叉搜索树的方式进行找到合适的位置插入节点。为了更好地封装我们需要在插入时检查是否已经存在相同的键对于 set 和 map 而言键必须是唯一的。
std::pairiterator, bool Insert(const T data)
{// 按照搜索树的规则进行插入// 如果树为空新节点直接作为根节点if (_root nullptr){_root new Node(data);_root-_colour BLACK; // 根节点是黑色的return std::make_pair(iterator(_root), true);}// 插入时使用比较器来比较键的大小以支持不同的数据类型KOfT koft;Node *parent nullptr;Node *cur _root;while (cur){if (koft(cur-_data) koft(data)){parent cur;cur cur-_left;}else if (koft(cur-_data) koft(data)){parent cur;cur cur-_right;}else{// 如果键已经存在, 插入无效, 返回 false, 并且返回该键的迭代器return std::make_pair(iterator(cur), false);}}// 找到位置, 根据父节点插入新节点cur new Node(data);Node *newnode cur;if (koft(parent-_data) koft(cur-_data)){parent-_left cur;cur-_parent parent;}else{parent-_right cur;cur-_parent parent;}// 插入后需要修复红黑树的性质InsertFixUp(parent, cur);return std::make_pair(iterator(newnode), true);
}解释
插入逻辑和之前的插入逻辑类似首先找到合适的父节点然后将新节点插入到父节点的左子树或右子树中。唯一性检查在插入时我们使用 KOfT 仿函数来获取键值大小大小以作比较。如果键已经存在则返回 false 表示插入无效。插入后修复插入完成后需要调用 InsertFixUp 函数来修复红黑树的平衡性。
3.4.2、插入后修复红黑树的性质
插入后我们需要对红黑树进行调整以确保其仍然满足红黑树的五个性质。我们继续使用颜色翻转和旋转操作来修复红黑树的平衡。
void InsertFixUp(Node *parent, Node *cur)
{// 调整结点颜色// 新结点给红的还是黑的? 红色// 1. 空树。插入结点做根, 把他变黑。// 2. 插入红色节点, 他的父亲是黑色的, 结束。// 3. 插入红色节点, 他的父亲是红色的, 可以推断他的祖父存在且一定为黑色。关键看叔叔// a. 如果叔叔存在且为红, 把父亲和叔叔变黑, 祖父变红, 继续往上处理。// b. 如果叔叔存在且为黑, 或者不存在。旋转单旋 or 双旋 变色while (parent parent-_colour RED){// 关键看叔叔Node *grandfather parent-_parent;// 父节点是祖父节点的左子节点if (grandfather-_left parent){Node *uncle grandfather-_right;// 情况1: uncle 存在, 且为红if (uncle uncle-_colour RED){parent-_colour uncle-_colour BLACK;grandfather-_colour RED;// 继续向上处理cur grandfather;parent cur-_parent;}// 情况 2 or 情况 3 : uncle 不存在 or uncle 存在且为黑else{// 情况 3 : 双旋 - 变单旋if (cur parent-_right){RotateL(parent);std::swap(parent, cur);}// 第二种情况 (ps: 有可能是第三种情况变过来的)RotateR(grandfather);grandfather-_colour RED;parent-_colour BLACK;break;}}// 父节点是祖父节点的右子节点else{Node *uncle grandfather-_left;// 情况1: uncle 存在, 且为红if (uncle uncle-_colour RED){parent-_colour uncle-_colour BLACK;grandfather-_colour RED;// 继续向上调整cur grandfather;parent cur-_parent;}// 情况 2 or 情况 3 : uncle 不存在 or uncle 存在且为黑else{// 情况 3 : 双旋 - 变单旋if (cur parent-_left){RotateR(parent);std::swap(parent, cur);}// 第二种情况 (ps: 有可能是第三种情况变过来的)RotateL(grandfather);grandfather-_colour RED;parent-_colour BLACK;break;}}}// 保证根节点为黑_root-_colour BLACK;
}3.4.3、插入调整的细节分析
红黑树插入的调整过程包含颜色变换和旋转。每当插入一个新节点时需要仔细判断红黑树的结构并通过相应的调整来保持其平衡性。我们可以将插入调整过程进一步分为多个情况并通过每个情况的详细分析理解红黑树的自平衡过程。
1、情况1: 父节点和叔叔节点都是红色
当插入一个新节点时如果该节点的父节点和叔叔节点都是红色那么根据红黑树的性质需要将父节点和叔叔节点变为黑色而祖父节点则变为红色。此时由于祖父节点可能与更高层的祖先发生冲突需要继续向上调整。
if (uncle uncle-_colour RED)
{parent-_colour uncle-_colour BLACK;grandfather-_colour RED;// 继续向上处理cur grandfather;parent cur-_parent;
}在这种情况下整个子树的黑色节点数保持不变因此不会影响路径的黑色节点数。但是需要注意祖父节点变为红色可能会破坏红黑树的性质因此需要递归调整祖父节点。
2、情况2: 父节点是红色叔叔节点是黑色且当前节点是父节点的右子节点
当父节点是红色而叔叔节点是黑色时如果新插入的节点是父节点的右子节点此时会形成“Z”形的结构。为了使树保持平衡我们需要先对父节点进行左旋使当前节点成为父节点再通过右旋调整整体结构。
if (cur parent-_right)
{RotateL(parent);std::swap(parent, cur);
}3、情况3: 父节点是红色叔叔节点是黑色且当前节点是父节点的左子节点
如果新插入的节点是父节点的左子节点此时会形成“直线”形结构。此时我们需要对祖父节点进行右旋同时交换父节点和祖父节点的颜色以保持红黑树的平衡。
RotateR(grandfather);
grandfather-_colour RED;
parent-_colour BLACK;在右旋后父节点成为新的根节点而祖父节点则变为父节点的右子节点红黑树的性质得到修复。
4、特殊情况根节点的颜色调整
无论是哪种情况在插入调整完成后都需要确保红黑树的根节点始终为黑色。这是红黑树的一个基本性质保证了从根节点到叶子节点的路径中至少包含一个黑色节点。
_root-_color BLACK;这样可以避免根节点成为红色从而破坏红黑树的平衡性。
3.5、删除操作
红黑树删除操作相较于插入更加复杂原因在于删除节点后可能会破坏红黑树的平衡性和性质即根节点是黑色、红节点不能有红色子节点、每个路径黑节点数相同等。因此在删除节点后必须进行相应的调整来修复红黑树的性质。
红黑树删除通常分为以下几步
寻找要删除的节点通过红黑树的搜索性质找到要删除的节点。删除节点并调整树结构根据删除节点的子节点情况调整树的链接。修复红黑树的性质若删除的是黑色节点可能会破坏红黑树的性质因此需要通过DeleteFixUp函数进行颜色调整和旋转操作。
3.5.1、常规BST删除
首先我们按照 BST 的规则找到并删除指定的节点。红黑树的删除操作可以分为以下几种情况
节点没有子节点直接删除该节点。节点只有一个子节点删除该节点并将其子节点与其父节点连接。节点有两个子节点找到该节点的中序后继用中序后继的值替换该节点然后删除中序后继。
// 删除操作
bool Erase(const K key)
{Node *nodeToDelete _root;KOfT koft;// 1. 寻找要删除的节点while (nodeToDelete){if (koft(nodeToDelete-_data) key){nodeToDelete nodeToDelete-_left;}else if (koft(nodeToDelete-_data) key){nodeToDelete nodeToDelete-_right;}else{break; // 找到了要删除的节点}}// 节点若不存在, 直接返回 falseif (nodeToDelete nullptr){return false;}// 执行删除操作Node *parent, *child;// 保存原节点的颜色以便后续调整Colour originalColour nodeToDelete-_colour;// 2. 处理删除节点的各种情况if (nodeToDelete-_left nullptr){// 情况 1没有左子节点child nodeToDelete-_right;parent nodeToDelete-_parent;Transplant(nodeToDelete, nodeToDelete-_right);}else if (nodeToDelete-_right nullptr){// 情况 2没有右子节点child nodeToDelete-_left;parent nodeToDelete-_parent;Transplant(nodeToDelete, nodeToDelete-_left);}else{// 情况 3有两个子节点// 找到右子树中的最小节点后继节点Node *successor Minimum(nodeToDelete-_right);originalColour successor-_colour;child successor-_right;if (successor-_parent nodeToDelete){parent successor;}else{// 后继节点有右子节点用它的右子节点替换它Transplant(successor, successor-_right);successor-_right nodeToDelete-_right;successor-_right-_parent successor;parent successor-_parent;}// 用后继节点替换删除节点Transplant(nodeToDelete, successor);successor-_left nodeToDelete-_left;successor-_left-_parent successor;successor-_colour nodeToDelete-_colour; // 保持颜色不变}// 删除节点delete nodeToDelete;// 3. 修复红黑树的性质// 如果删除的节点是黑色, 需要进行调整if (originalColour BLACK){EraseFixUp(child, parent);}return true;
}代码详解
寻找要删除的节点 使用红黑树的搜索性质依次比较要删除的键值key 与当前节点的数据做对比找到对应的节点。如果节点不存在则返回false。 处理删除节点的情况 若要删除的节点没有左子节点直接用右子节点替换删除的节点。若没有右子节点则用左子节点替换删除的节点。如果有两个子节点找到右子树中的最小节点即后继节点用后继节点替换要删除的节点。调用 Transplant 函数来实现节点的替换。 修复红黑树的性质 如果删除的节点是黑色可能会破坏红黑树的性质因此需要调用 EraseFixUp 函数来进行颜色调整和旋转恢复红黑树的平衡。
3.5.4、辅助函数 Minimum
该函数用于找到指定节点的子树中的最小节点即左子树中的最左节点。
Node *Minimum(Node *node)
{while (node-_left ! nullptr){node node-_left; // 一直向左走直到找到最左节点}return node;
}3.5.3、辅助函数 Transplant
Transplant函数用于在删除节点时将一个子树替换为另一个子树。
void Transplant(Node *u, Node *v)
{// 如果u是根节点v成为新的根节点if (u-_parent nullptr){_root v;}// u是左子节点用v替换它else if (u u-_parent-_left){u-_parent-_left v;}// u是右子节点用v替换它else{u-_parent-_right v;}// 连接v与u的父节点if (v ! nullptr){v-_parent u-_parent;}
}代码详解
Transplant函数用于将节点u替换为节点v并且将v与u的父节点连接起来。若u是根节点则直接将v设为根节点否则根据u是左子节点还是右子节点分别替换其位置。
3.5.4、删除调整函数 EraseFixUp
void EraseFixUp(Node *child, Node *parent)
{while (child ! _root (child nullptr || child-_colour BLACK)){if (child parent-_left){Node *brother parent-_right;// 情况1: child 的兄弟节点 brother 是红色的if (brother-_colour RED){brother-_colour BLACK;parent-_colour RED;RotateL(parent);brother parent-_right;}// 情况2: child 的兄弟节点 brother 是黑色的, 且 brother 的两个节点都是黑色的if ((brother-_left nullptr || brother-_left-_colour BLACK) (brother-_right nullptr || brother-_right-_colour BLACK)){brother-_colour RED;child parent;parent child-_parent;}else{// 情况3: brother 是黑色的, 并且 brother 的左子节点是红色, 右子节点是黑色if (brother-_right nullptr || brother-_right-_colour BLACK){if (brother-_left){brother-_left-_colour BLACK;}brother-_colour RED;RotateR(brother);brother parent-_right;}// 情况4: brother 是黑色的, 并且 brother 的右子节点是红色if (brother){brother-_colour parent-_colour;parent-_colour BLACK;if (brother-_right){brother-_right-_colour BLACK;}RotateL(parent);}child _root;break;}}else{Node *brother parent-_left;// 情况1: child 的兄弟节点 brother 是红色的if (brother-_colour RED){brother-_colour BLACK;parent-_colour RED;RotateR(parent);brother parent-_left;}// 情况2: child 的兄弟节点 parent 是黑色的, 且 brother 的两个节点都是黑色的if ((brother-_left nullptr || brother-_left-_colour BLACK) (brother-_right nullptr || brother-_right-_colour BLACK)){brother-_colour RED;child parent;parent child-_parent;}else{// 情况3: brother 是黑色的, 并且 brother 的右子节点是红色, 左子节点是黑色if (brother-_left nullptr || brother-_left-_colour BLACK){if (brother-_right){brother-_right-_colour BLACK;}brother-_colour RED;RotateL(brother);brother parent-_left;}// 情况4: brother 是黑色的, 并且 brother 的左子节点是红色if (brother){brother-_colour parent-_colour;parent-_colour BLACK;if (brother-_left){brother-_left-_colour BLACK;}RotateR(parent);}child _root;break;}}}if (child){child-_colour BLACK;}
}EraseFixUp 代码解析
该函数通过旋转和颜色调整来修复红黑树的平衡。关键在于处理被删除节点的兄弟节点根据兄弟节点的颜色及其子节点的情况决定是进行旋转还是颜色调整确保红黑树
3.6、查找操作
红黑树不仅在插入和删除操作上表现优异其查找操作同样高效。查找的复杂度为 O(log n)这得益于红黑树的平衡特性。接下来我们将详细介绍红黑树的查找过程包括基本步骤、实现代码以及相关的性质分析。
在红黑树中查找一个键值的过程与在普通二叉搜索树中查找相似。查找时我们从根节点开始按照以下步骤进行
比较键值首先将待查找的键值与当前节点的键值进行比较。 如果相等则找到该节点返回该节点的迭代器。如果待查找的键值小于当前节点的键值则向左子树查找。如果待查找的键值大于当前节点的键值则向右子树查找。 继续查找根据比较结果继续在相应的子树中查找直到找到该键值或者遍历到叶子节点即指向空指针。
以下是红黑树查找操作的实现代码
// 查找节点
iterator Find(const K key)
{KOfT koft;Node *cur _root;while (cur){if (koft(cur-_data) key){cur cur-_left;}else if (koft(cur-_data) key){cur cur-_right;}else{return iterator(cur);}}return iterator(nullptr);
}代码解析
起始节点我们从根节点开始查找。循环条件只要当前节点不为空就持续进行比较。条件判断通过判断键值的大小关系来决定下一步的查找方向。返回结果找到节点后返回其对应的迭代器如果未找到则返回树的结束迭代器通常为nullptr。
查找操作的时间复杂度为 O(log n)。这是因为红黑树的高度是对数级别的插入和删除操作后红黑树仍然保持相对平衡因此查找过程中经过的节点数量是相对较少的。此外红黑树的性质确保了节点的分布是较为均匀的避免了出现链式结构的情况从而保持了高效的查找性能。
4、set 和 map 容器的实现
4.1、Set 容器的实现
set 的底层为红黑树因此只需在 set 内部直接封装一颗红黑树即可将该容器实现出来。
#pragma once#include RBTree.hppnamespace Lenyiin
{template class Kclass Set{struct SetKeyOfT{const K operator()(const K k){return k;}};public:// 这里RBTreeK, K, SetKeyOfT::iterator还没有实例化, 系统找不到, typename告诉编译器现在先不着急找typedef typename RBTreeK, K, SetKeyOfT::iterator iterator;typedef typename RBTreeK, K, SetKeyOfT::const_iterator const_iterator;iterator begin(){return _tree.begin();}iterator end(){return _tree.end();}const_iterator begin() const{return _tree.begin();}const_iterator end() const{return _tree.end();}std::pairiterator, bool Insert(const K key){return _tree.Insert(key);}bool Erase(const K key){return _tree.Erase(key);}iterator Find(const K key){return _tree.Find(key);}bool IsRBTree(){return _tree.IsRBTree();}private:RBTreeK, K, SetKeyOfT _tree;};
}4.2、Map 容器的实现
map 的底层为红黑树因此只需在 map 内部直接封装一颗红黑树即可将该容器实现出来。
#pragma once#include RBTree.hppnamespace Lenyiin
{template class K, class Vclass Map{struct MapKeyOfT{const K operator()(const std::pairK, V kv){return kv.first;}};public:typedef typename RBTreeK, std::pairK, V, MapKeyOfT::iterator iterator;typedef typename RBTreeK, std::pairK, V, MapKeyOfT::const_iterator const_iterator;iterator begin(){return _tree.begin();}iterator end(){return _tree.end();}const_iterator begin() const{return _tree.begin();}const_iterator end() const{return _tree.end();}std::pairiterator, bool Insert(const std::pairK, V kv){return _tree.Insert(kv);}bool Erase(const K key){return _tree.Erase(key);}V operator[](const K key){std::pairiterator, bool ret _tree.Insert(std::make_pair(key, V()));return ret.first-second;}bool IsRBTree(){return _tree.IsRBTree();}private:RBTreeK, std::pairK, V, MapKeyOfT _tree;};
}
