(2)另外,还得确保根节点左子树的高度与右子树的高度相等。这样,二叉树的高度最小,从而检索速度最快。
平衡二叉检索树的检索使用中序遍历算法,检索效率高。默认情况下,将键值由小到大遍历。
对于set容器中的键值,不可直接去修改。因为如果把容器中的一个键值修改了,set容器会根据新的键值旋转子树,这样修改的键值很可能就不在原先那个位置上了。
1、创建set集合对象,元素的插入与中序遍历
采用insert()方法把元素插入集合中,默认情况下,将键值由小到大插入。
#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;
int main()
{
set<int> str;
//插入了5个元素;但由于8有重复,第二次插入的8并没有执行
str.insert(8); //第一次插入8,可以插入
str.insert(1);
str.insert(12);
str.insert(6);
str.insert(8); //第二次插入8,不会插入
//中序遍历集合中所有的元素
for(set<int>::iterator iter = str.begin(); iter!= str.end();iter++)
cout << *iter << " ";
cout << endl;
return 0;
}
运行结果:1 6 8 12
2、元素的反向遍历
使用反向迭代器reverse_iterator可以反向遍历集合。它需要用到rbegin()和rend()两个方法,分别给出反向遍历的开始位置和结束位置。
#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;
int main()
{
set<int> str;
//插入了5个元素;但由于8有重复,第二次插入的8并没有执行
str.insert(8); //第一次插入8,可以插入
str.insert(1);
str.insert(12);
str.insert(6);
str.insert(8); //第二次插入8,不会插入
//中序遍历集合中所有的元素
for(set<int>::reverse_iterator iter = str.rbegin(); iter!=str.rend(); iter++)
cout << *iter << " ";
cout << endl;
return 0;
}
运行结果:12 8 6 1
3、元素的删除
集合set具有高效的删除处理功能,并自动重新调整内部的红黑树的平衡。
删除某个键值的元素用erase()方法,清空集合用clear()方法。
#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;
int main()
{
set<int> str;
//插入了5个元素;但由于8有重复,第二次插入的8并没有执行
str.insert(8); //第一次插入8,可以插入
str.insert(1);
str.insert(12);
str.insert(6);
str.insert(8); //第二次插入8,不会插入
set<int>::iterator iter = str.find(6);
if(iter != str.end())
cout << "找到的值为: " << *iter<< endl;
else
cout << "没有找到" << endl;
iter = str.find(20);
if(iter != str.end())
cout << *iter <<endl;
else
cout << "没有找到" << endl;
return 0;
}
运行结果:找到的值为:6
没有找到
5、自定义比较函数
默认情况下,按照键值由小到大的顺序插入元素。由于内部数据结构都是红黑树。编写方法有两种,
(1)如果元素不是结构体,那么可以编写比较函数。下面实现键值由大道小的顺序将元素插入set中:
#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;
struct myComp
{
bool operator()(int a, int b)
{
return a > b;
}
};
int main()
{
set<int, myComp> str;
//插入了5个元素;但由于8有重复,第二次插入的8并没有执行
str.insert(8); //第一次插入8,可以插入
str.insert(1);
str.insert(12);
str.insert(6);
str.insert(8); //第二次插入8,不会插入
for(set<int, myComp>::iterator iter = str.begin(); iter !=str.end(); iter++)
cout << *iter << " ";
cout << endl;
return 0;
}
运行结果:12 8 6 1
(2)如果元素是结构体,那么,可以直接把比较函数写在结构体里面。
#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
using namespace std;
struct Info
{
string name;
float score;
bool operator < (Info a) const
{
//按score由大到小排列。如果要由小到大排列,使用">"号即可。
return a.score < score;
}
};
int main()
{
set<Info> str;
Info info;
info.name = "Jack";
info.score = 80.5;
str.insert(info);
info.name = "Tomi";
info.score = 20.5;
str.insert(info);
info.name = "Nacy";
info.score = 60.5;
str.insert(info);
for(set<Info>::iterator iter = str.begin(); iter != str.end();iter++)
cout << (*iter).name << " : " <<(*iter).score << endl;
return 0;
}
运行结果:Jack : 80.5
Nacy : 60.5
Tomi : 20.5