二叉排序树与 set、map

 前置知识：二叉树的概念及性质

为了保证学习效果，请保证已经掌握前置知识之后，再来学习本章节！

理解二叉排序树的概念理解二叉排序树的查找、插入、删除、构建和简单平衡的过程掌握 STL 的容器 map、set 的使用方法及其用途 二叉排序树的概念

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree）、二叉搜索树，是指一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值。若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。它的左、右子树也分别为二叉排序树。没有键值相同的结点。

转存失败重新上传取消

二叉搜索树作为一种经典的数据结构，它既有链表的快速插入与删除操作的特点，又有数组快速查找的优势。二叉排序树是基础性数据结构，用于构建更为抽象的期望数据结构，比如 set(集合)、multiset、map(关联数组)、multimap等。

二叉排序树有一个很重要的性质： 中序遍历二叉排序树可以得到一个关键字的递增序列。这也是为什么它叫二叉排序树的原因。

二叉排序树的查找、插入、删除的复杂度等于树高，期望复杂度均为 O(log_2 n)O(log2​n)，当数列有序时，二叉排序树退化成线性表，此时最坏，复杂度为 O(n)O(n)。

虽然二叉排序树的最坏效率是 O(n)O(n)，但它支持动态查询，且有很多改进版的二叉排序树可以使树高为 O(log_2 n)O(log2​n)，如 Treap、Splay、SBT(Size Balanced Tree)、AVL树(平衡树)、红黑树等。这些将在后面学习。

在二叉排序树 b 中查找元素 x 的算法：

（1）若 b 是空树，则查找失败；否则执行（2）。

（2）若 x 等于 b 的根结点的数据域之值，则查找成功；否则执行（3）。

（3）若 x 小于 b 的根结点的数据域之值，则搜索左子树；否则执行（4）。

（4）查找右子树。

向二叉排序树 b 中插入一个结点 s 的算法:

（1）若 b 是空树，则将 s 所指结点作为根结点插入；否则执行（2）。

（2）若 s->data 等于 b 的根结点的数据域之值，则返回；否则执行（3）

（3）若 s->data 小于 b 的根结点的数据域之值，则把 s 插入到左子树中；否则执行（4）。

（4）把s所指结点插入到右子树中。（新插入结点总是叶子结点）

在二叉查找树删去一个结点 *p，分三种情况讨论：

（1）若 *p 结点为叶子结点，即 PL(左子树)和 PR(右子树)均为空树，由于删去叶子结点不破坏整棵树的结构，则只需修改其双亲结点的指针即可。

（2）若 *p 结点只有左子树 PL 或右子树 PR，此时只要令 PL 或 PR 直接成为其双亲结点 *f 的左子树(当 *p 是左子树)或右子树(当 *p 是右子树)即可，做此修改也不破坏二叉查找树的特性。

（3）若 *p 结点的左子树和右子树均不空，在删去 *p 之后，为保持其他元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以令 *p 的直接前驱(in-order successor)替代 *p，然后再从二叉查找树中删去它的直接前驱。直接前驱就是指：从 *p 的左儿子开始，如果有右儿子，则不断向右继续查找，否则就找到了直接前驱。由于它的直接前驱最多只有一个儿子，因此可以按照方法 2 删除，例如下图所示。（备注：同理，也可以令 *p 的直接后继承去替代 *p，方法是类似的）

转存失败重新上传取消

代码实现将在今后学习，现在只需理解概念和原理。

在关联容器中，对象的位置取决于和它关联的键的值。键可以是基本类型也可以是类类型。关联容器是与非关联容器（顺序容器）相对应的，顺序容器中元素的位置不依赖于元素的值，而是和该元素加入容器时的位置有关。关联容器的类型有下面八种：

// 按关键字有序保存元素，底层用二叉排序树及其优化后的红黑树实现
map                      关联数组；保存关键字-值对
set                      关键字即值，只保存关键字的容器
multimap                 关键字可以重复出现的map
multiset                 关键字可以重复出现的set
 
// 无序关联容器
unordered_map            用哈希函数组织的map，无序
unordered_set            用哈希函数组织的set，无序
unordered_multimap       哈希组织的map；关键字可以重复
unordered_multiset       哈希组织的set，关键字可以重复

Copy

set 可以方便快速地实现排序和去重操作

set 的含义是集合，它是一个 有序 的容器，里面的元素都是排序好的，支持插入、删除、查找等操作，就像一个集合一样。所有的操作的都是严格在 O(log n)O(logn) 时间之内完成，效率非常高。 set 和 multiset 的区别是：set 插入的元素不能相同，但是 multiset 可以相同。

// 1- 定义
#include 
set s;     // 元素必须可比较大小，元素类型必须要支持 < 运算，结构体需要重载 <

// 2- 插入
s.insert(key);    // 插入

// 3- 删除
s.erase(key);     // 删除值为 key 的元素
s.erase(iter);    // 删除迭代器 iter 指向的元素，例如 s.erase(s.begin());
s.erase(iter1, iter2); // 删除区间 [iter1, iter2) 的所有元素，例如 s.erase(s.begin(), s.end());
s.clear();        // 清空集合

// 4- 求大小
int siz = s.size();         // 求集合大小
bool flag = s.empty();      // 集合判空

// 5-查询
if(s.find(key) != s.end())           // find 函数返回一个指向被查找到元素的迭代器
    cout << "exist" << endl;
if(s.count(key) == 1)               // count 返回某个值元素的个数
    cout << "exist" << endl;


set::iterator iter = s.lower_bound(key);   // 求 key 的下界，返回指向大于等于某值的第一个元素的迭代器
set::iterator iter = s.upper_bound(key);   // 求 key 的上界，返回大于某个值元素的迭代器

// auto 类型推断关键字 在NOI系列比赛中无法使用！
auto iter = s.lower_bound(key);   // 求 key 的下界，返回指向大于等于某值的第一个元素的迭代器
auto iter = s.upper_bound(key);   // 求 key 的上界，返回大于某个值元素的迭代器

// 6-遍历
set::iterator iter;             // 正向遍历
for(iter=s.begin(); iter!=s.end(); iter++)
{
    cout<<*iter<::reverse_iterator riter;    // 反向遍历
for(riter=s.rbegin(); riter!=s.rend(); riter++)
{
    cout<<*riter<::iterator it = s.begin();    // 最小值
cout << *it << endl;
set::iterator it = s.end();      // 最大值
cout << *(--it) << endl;



// ..... 还有很多，请自行查阅相关资料 

Copy

实现 01 标记：元素类型任意（string）、大小不受限

01 桶标记：元素只能是整型，并且元素大小受限

multiset<> 使用方法和 set<> 相同，区别是键值可重复。

map 是一个 关键字—值 对的集合，适用于处理一对一的具有映射关系的数据

map提供一对一的数据处理能力，由于这个特性，它完成有可能在我们处理一对一数据的时候，在编程上提供快速通道。map 中的第一个值称为关键字(key)，每个关键字只能在 map 中出现一次，第二个称为该关键字的值(value)，可以重复。

map 内部自建一颗红黑树(一 种非严格意义上的平衡二叉树)，这颗树具有对数据自动排序的功能，所以在 map 内部所有的数据都是有序的。

// 定义，以 string, int 对为例
#include 

Copy

所有之前学过的数组标记类题目都可以用 map 去实现！如果想练习更多 map 的使用，可以到数组标记类问题中去找。

实现计数标记：元素类型任意（string）、大小不受限

桶计数标记：元素只能是整型，并且元素大小受限

哈希（映射）

字符串统计类问题

常用 map 类型：map mp;、map mp;、map mp;

multimap； 键值可重复，用法和 map 基本相同。需要注意的是：

multimap 不支持下标运算符，因为键并不能确定一个唯一元素。

和 map 相似，multimap 也不能使用 at() 函数。

P1189 找朋友

P2348 家谱

P2814 安迪的第一个字典

P2815 USACO2.2 派对灯 Party Lamps