1.说在前面
c++支持两种类--抽象类和具体类。一个抽象类包含着没有实现代码的成员函数（纯虚函数）。具体了类没有纯虚函数。只有具体类才可以实例化（但抽象类实例化指针和引用是运行的），即只能对具体类建立实例或对象。
在这里主要讲解各种数据结构的思想，列举抽象类接口和实现一部分具体类的接口功能。
2. 数组
2.1 数组介绍
数组是有序表的一种，其内存是在物理上是连续的，对于这种数据结构而言，其优缺点如下： 优点：
- 支持下标访问随机访问，访问指定位置快时间复杂读为
O(1) - 没有额外的存储空间来存储指针之类的
缺点
- 对于插入操作比较麻烦，需要将插入位置后的元素后移一位，造成最坏情况下时间复杂度为O(n)
- 同时分配的内存是连续，一次性分配，若元素装满后还想插入元素，则需要另外开辟，将原来的元素拷贝过去再插入，造成效率低下。
对于数组，不建议自己去写一个类实现，而是使用STL中带有的vetcor，这款容器能实现按1.5或2倍扩容机制增长，且支持迭代器，是C++开发中最长用到的功能齐全的容器。
2.2 实现
2.2.1 linerList抽象类
1 |
|
2.2.2 C++实现
在线性表的数组描述中，我们用一维动态分配的数组element，变量lsitsize表示当前存储的线性表元素个数，用arrayLength表示线性表容量。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39//C++版本
template<class T>class arrayList :public linearList<T> {
public:
arrayList(int initialCapacity = 10);
arrayList(const arrayList<T>&);
~arrayList() { delete[]element; }
virtual bool empty()const { return listsize == 0; }
virtual size_t size(){return listsize; }
virtual size_t capacity() { return arrayLength; }
virtual T& get(int ) const;
virtual T& operator[](int theIndex)const;
virtual int indexOf(const T& element)const;
virtual T& erase(int theIndex);
virtual size_t insert(int theIndex, const T& theInserElement);
virtual void output(std::ostream& os)const;
private:
void checkIndex(const int indexOf)const;
//std::shared_ptr<T[]，end_connection> elememt;
//不建议使用智能指针形式的动态数组，
//因为析构函数使用的是默认delete,而不是delete[],
//若要使用则应该定义自己得删除器
void increaseLength(T*& , int , int);//扩容操作
T* element;
std::size_t listsize;
std::size_t arrayLength;
};
//删除元素，后面的元素向前移动一位
template<class T>
T& arrayLisst<T>::erase(int index){
if(index<0||index>=size())
throw out_of_range("下标访问越界");
copy(element+index+1,element+listsize,element+index);
element[--listsize].~T();
}
2.2.3 C实现
1 | //C版本 |
3. 链表
3.1 单链表介绍
链表克服了数组插入删除时的元素移动步骤，但是代价是牺牲一定的内存来存储指针，其优缺点如下 优点：
- 链表通过指针来指向下一个元素，带来的好处是插入删除无须移动插入位置后的元素的元素，也不必前移删除位置后的元素，只需要将指针指向后方元素即可。
- 通过指针来指向下一个元素，这就意味着我们不必像数组那样分配严格物理意义上的联系内存，即使内存不连续，也能成功访问。只有在需要的时候才去创建空间。大小不固定，拓展很灵活。
缺点
- 因为内存是不联系的，那么链表不支持随机访问，如果访问链表中指定位置节点，只能从头或者尾部进行遍历。
- 因为除了存储数据，还有存储相应的指针，同一长度的数组和链表，链表会造成内存的消耗多
3.2 实现
3.2.1 C++实现
1.存储结构以及类整体声明及定义
1 | //c++实现 |
2. 构造函数和拷贝构造函数
为了创建一个空链表，只需令第一个firstNode的值为NULL，链表不需要预先分配堆空间，它是随用随建立的一个形式。不过为了与arrayList相容，构造函数还是具有一个表示初始容量的形参initialCapacity 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41//构造函数
template<class T>
chain<T>::chain(int initialCapacity){
if(initialCapacity<1)
throw std::out_of_range("The capacity is wrong");
firstNode=NULL;
listSize=0;
}
//拷贝构造
template<class T>
chain<T>::chain(const chain<T>& theList){
listSize=theList.listSize;
if(listSize==0)
{
firstNode=NULL;
return;
}
chainNode<T> *sourceNode=theList.firstNode; //使用拷贝构造函数,深拷贝
firstNode=new chainNode<T>(sourcNode->element);
sourceNode=sourceNode->next;
chainNode<T> *intermediateValue=firstNode;
while(sourceNode!=NULL)
{
intermediateValue=new chainNode<T>(sourceNode->element);
sourceNode=sourceNode->next;
intermediate=intermediate->next;
}
intermediate->next=NULL;
}
//析构函数
template<class T>
chain<T>::~chain(){
while(firstNode!=NULL)
{
chianNode<T> *nextNode=firstNode->next;
delete firstNode;
firstNode=nextNode;
}
}
3. get函数 1
2
3
4
5
6
7
8
9
10
11
12template<class T>
T& chain<T>::get(int theIndex)
{
checkIndex(theIndex);
chainNode<T> *targetNode=firstNode;
while(theIndex>0)
{
targetNode=targetNode->next;
theIndex--;
}
return targetNode->element;
}
4.插入函数 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23template<class T>
void chain<T>::insert(int theIndex,const T& theElement)
{
checkIndex(theIndex);
chainNode<T> *newNode=new chainNode<T>(the Element);
if(theIndex==0)
{
newNode->next=firstNode;
firstNode=newNode;
}
else
{
chainNode<T> *insertLocation=firstNode;
while(theIndex>1)
{
insertLocation=inserLocation->next;
theIndex--;
}
newNode->next=inserLocation->next;
inserLocation->next=newNode;
}
++listSize;
}
5. 删除函数 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24template<class T>
void chain<T>::erase(int theIndex)
{
checkIndex(theIndex);
chainNode<T>* eraseNode;
if(theIndex==0)
{
eraseNode=fiirstNode;
firstNode=eraseNode->next;
}
else
{
chianNode<T> *frontNode=firstNode;
while(theIndex>1)
{
frontNode=frontNode->next;
theIndex--;
}
eraseNode=frontNode->next;
frontNode->next=eraseNode->next;
}
delete eraseNode;
listSize--;
}
- 循环链表：我们可以采用两个措施使链表的应用代码简洁高效：①把链表描述成一个单向循环链表。②在链表的前面加一个头结点。
- 双向链表：即有指向后继的指针，又有指向前驱的指针。
这里不再介绍这两个，因为实现跟单链表相似，无非就是加了指针指向。
3.2.2 C实现
1. 存储结构以及实现结构体
LinkList、next是指向结构的指针,用间接访问->符号。其中LinkList是链表的头指针，若LinkList==NULL(为空指针）,则表示链表为空。有时候我们会把头指针指向的是一个头结点（其数据域不存储任何东西或者存储链表长度等附加信息）,指针域next指向下一个结构。 1
2
3
4
5
6//c版本
//单链表的存储结构设置：
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
2. 建立单链表：这个算法是从尾到表头进行建立的（当然也可以从表头到表尾）
1 | void CreatLinkList(LinkList &L,int n) |
3. 插入操作：从头指针开始达到指定的位置，创建新节点（结构），插入。
1 | status InsertElem(LinkList &L,int i,ElemType e) |
4. 删除操作：从头指针开始达到指定的位置，改变next指针的指向，释放（free)要删除的结构（节点）
1 | status DeleteElem(LinkList &L,int i,ElemType &e) |
5. 查找操作：与顺序表一样，应用回调函数
1 | int compare(LinkList L,EemType e,int (*compare)(ElemType,ElemType)) |
3.3 双向链表介绍
链表的每一个节点给中既有指向下一个结点的指针，也有指向上一个结点的指针，可以快速的找到当前节点的前一个节点，适用于需要双向查找节点值的情况。 
双链表相对于单链表的优点：
- 删除单链表中的某个节点时，一定要得到待删除节点的前驱，得到其前驱的方法一般是在定位待删除节点的时候一路保存当前节点的前驱，这样指针的总的的移动操作为2n次，如果是用双链表，就不需要去定位前驱，所以指针的总的的移动操作为n次。
- 查找时也是一样的，可以用二分法的思路，从头节点向后和尾节点向前同时进行，这样效率也可以提高一倍。
但是市场上对于单链表的使用要超过双链表,，因为从存储结构来看，每一个双链表的节点都比单链表的节点多一个指针，如果长度是n，就需要n*lenght（32位是4字节，64位是8字节）的空间，这在一些追求时间效率不高的应用下就不适用了，因为他占的空间大于单链表的1/3，所以设计者就会一时间换空间。
3.4 应用
3.4.1 箱子排序(链表形式)
1. 箱子排序的原理
对于链表因为若用冒泡选择排序，我们时间复制度是为O(n*n)。采用箱子排序会更快，时间复杂度为O(n)。所谓的箱子排序就是将值相同的节点放到一个箱子内，然后再将排好序的箱子内的链表串接起来形参有序链表。事先分好各个箱子大小。每一个箱子都是一个链表。一个箱子的节点数目介于0~n之间。它要做的是：
- 逐个删除输入链表，把删除的节点分配到相应的箱子里；
- 把每一个箱子中的节点连接起来，使其成为一个有序链表；
注意：箱子排序适用于对有大量重复的数据进行排序，并且数据范围不大。不然试想一下假设有0~10000范围的数据，这个时候我们就得分好并管理10000个箱子，这是很麻烦的。
2. 下面以学生的划分6个优秀等级作为例子
学生结构包含：学生姓名，学生优秀等级。用大小为6的vector1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72//时间复杂度为O(2n)
//学生结构类
class studentStruct{
public:
//等级为0，1，2，3，4，5
int rank; //方便访问测试，直接将成员变量设为public
string name;
studentStruct* next;
studentStruct():rank(-1),name(""),next(NULL){}
studentStruct(int _rank,string _name):rank(_rank),name(_name),next(NULL){}
studentStruct(const stduentStrcut& s):rank(s.rank),name(s.name),next(NULL){}
studentStruct& operator=(const studentStruct* s){
name=s.name;
rank=s.rank;
next=NULL;
return *this;
}
virtual ~studentStruct()=default;
};
//箱子排序
template<class T>
T* boxSort(T* head) {
//初始化六个空的节点，标识为-1
vector<T*> vec(6); //当前索引的第一个位置
vector<T*> lastNode(6); //记录当前索引最后一个节点的位置
//遍历传入的链表，将学生节点分好箱子
while (head != NULL) {
int index = head->rank % 6;
if (vec[index] == NULL) {//该位置为空，直接存入
vec[index] = head;
lastNode[index] = head; //刚存入的就是最后一个节点
head = head->next;
lastNode[index]->next = NULL;
}
else {
T* tempNode = head->next;
head->next = lastNode[index]->next; //置NULL
lastNode[index]->next = head;
lastNode[index] = head;
head = tempNode;
}
}
//将vector内的各个分散链表串接起来,未使用lastNode版本
T* endNext = NULL;
for (auto it = vec.begin(); it != vec.end(); it++) {
if (endNext != NULL)//不是第一次进入循环，进行连接
endNext->next = *it;
endNext = *it;
while (endNext != NULL && endNext->next != NULL) {
//endNext!=NULL是防止该所谓位置无值，endNext是索引有值遍历到最后一个
endNext = endNext->next;
}
}
/*，将vector内的各个分散链表串接起来，使用lastNode版本 */
T* first=NULL,*last=NULL;
/*
for(auto i=0;i<lastNode.size();i++)
{
if(last==NULL){
last=lastNode[i];
}
else if(last!=NULL&&lastNode[i]!=NULL)
{
last->next=vec[i];
last=lastNode[i];
}
}
*/
return vec[0];
}
3.4.2 基数排序（数组形式）
对于上面的箱子排序，对于数据范围很大的数据很难有实践意义，基数排序为克服这一点而出现的。基数排序排序主要通过将数字分解进行排序，如三位数的925，技术排序可通过十进制分解，将925分解成9、2、5三个数，然后依次以个位、十位、百位进行排序。在这个过程中，因为数字只有0~9,所有仅仅需要10个桶就，然后调用三次箱子排序即可，时间复杂度为O(nm) 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18void potencySort(vector<int>& vec, int num) { //num指示按哪位排序
vector<vector<int>> tempVec(10); //二维数组，内部vector的大小看数据量
for (int i = 0; i < vec.size(); i++)
{
int index = vec[i] / num % 10;
tempVec[index].push_back(vec[i]);
}
vec.clear(); //清除里面的数据
for (int i = 0; i < 10; i++) //放回vec
{
auto it = tempVec[i].begin();
while (it != tempVec[i].end())
{
vec.push_back(*it);
++it;
}
}
}
3.4.3 并查集
要知道什么是并查集，就要先知道什么是等价类。所谓的等价类就是指再一个给的n元素的集合R中有两两配对的等价关系且已经是等价关系的最大集合（等价类是集合），如n=14.R={(1,11),(7,11),(2,12),(12,8),(11,12),(3,13),(13,14)},如果(a,b)∈R则a,b两个类是等价的，且不能在外部找到其他等价关系。等价具有自反性、对称性、传递性。即：
- 若
a∈R，则(a,a)必属于R，自反性 - 若
(a,b)∈R，则必有(b,a)∈R，对称性 - 若
(a,b)∈R，(b,c)∈R，则(a,c)∈R，传递性
等价类分为离线等价类和在线等价类。在线等价类又称为并查集
- 离线等价类：n和R已知，确定了所有的等价类关系，且每个元素只能属于一个等价类，即只能在一个集合R
在线等价类（并查集）：初始又n个元素，每个元素刚开始都属于一个独立的等价类。需要执行以下的步骤：
conbine(a,b),把包含a和b的等价类合并成一个等价类find(theElement),确定元素在哪一个等价类，目的是对给定的两个元素，确定是否属于同一个类，对同一类元素返回相同结果，否则返回不同结果
经典的机器调度和布线问题，后续树会讲到
4. 栈
4.1 栈的介绍
栈是一种重要的线性结构，通常称，栈和队列是限定插入和删除只能在表的“端点”进行操作的线性表。
- 栈的元素必须
“后进先出LIFO“。 - 栈的操作只能在这个线性表的表尾进行。
- 对于栈来说，这个表尾称为栈的栈顶（top），相应的表头称为栈底（bottom）。
- 因为栈的本质是一个线性表，线性表有两种存储形式，那么栈也有分为栈的顺序存储结构和栈的链式存储结构。
- 最开始栈中不含有任何数据，叫做空栈，此时栈顶就是栈底。然后数据从栈顶进入，栈顶栈底分离，整个栈的当前容量变大。数据出栈时从栈顶弹出，栈顶下移，整个栈的当前容量变小。
4.2 实现
栈的顺序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，先为栈分配一个合理的容量，在应用过程中，当栈的空间不够时再逐渐扩大。
按设定的的初始分量进行第一次存储分配，base可称为栈底指针，在顺序栈中，它始终指向栈底位置。若为base的值为NULL，则表明栈结构不存在。top为栈顶指针，其初值指向栈底，既top=base作为栈空的标记，每当压入心得栈顶元素时，栈顶top+1，删除-1.因此非空栈的栈顶指针始终在栈顶元素的下一个位置上
4.2.1 C++实现
1 | template<class T> |
4.2.2 C实现
1 | //顺序栈的存储结构 |
4.3 应用
栈的能应用于各式各样的后进先出的地方，比如表达式括号匹配，四则运算、迷宫问题等。
4.3.1 健壮四则运算
我的思路：
- 1、把输入的式子中其它
{}[]转化为()的形式 - 2、输入的式子可能有负值，将其转化为减法运算，既前面加0
- 3、对于
(和空运算符栈情况下，运算符直接入栈 - 4、数字判断长度后，转化为int入栈
- 5、对于
* /，运算符栈顶元素若是同级，则栈顶元素出栈运算，这样避免同出现8/2/2=8的情况 - 6、对于
+ -同级或高级的栈顶运算符也要出栈运算，注意2-2*3+2的特殊情况处理，代码129-142就是处理这种情况。 - 7、对于)，则直接出栈运算直到(即可
1 |
|
4.3.2 括号匹配
给的一个括号字符串，判断这个字符串是否有效即括号是否匹配。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26bool bracketsOK(string s) {
if (s == "")
return true;
stack<char> in_char;
auto it = s.begin();
while (it != s.end())
{
if (*it == '(' || *it == '{' || *it == '[')
in_char.push(*it);
else if (!in_char.empty()) {
char c = in_char.top();
in_char.pop();
if (c == '(' && (c + 1) != *it)
return false;
else if ((c == '[' || c == '{') && (c + 2) != *it)
return false;
}
else
return false;
++it;
}
if (!in_char.empty())
return false;
else
return true;
}
5. 队列
队列是一先进先出的线性结构，允许插入的一端叫做队尾，允许删除的一端叫队头。
5.1 链队列
一个链队列需要两个分别指示队头和队尾的指针（头指针和尾指针）才能唯一确定。和线性表的单链表一样，为操作方便，也给队列添加一头结点，并令头指针指向头结点。所以空队列的判决条件为头指针和尾指针均指在头结点。链队列的操作为单链表插入和删除操作的特殊情况，只需修改尾指针和头指针即可。读取时的时间复杂度为O(1)。插入、删除时的时间复杂度为O(1)。 
优点：
- 相比普通的队列，元素出队时无需移动大量元素，只需移动头指针。
- 可动态分配空间，不需要预先分配大量存储空间。
- 适合处理用户排队等待的情况。
缺点： -- 需要为表中的逻辑关系增加额外的存储空间。
5.2 循环队列
在循环队列中，空队特征是front = rear, 队满时也会有front = rear; 判断条件将出现二义性（到底是空还是满？） 
解决方案有三种：
- 加设标志位，让删除动作使其为1，插入动作使其为0， 则可识别当前front == rear;
- 使用一个计数器记录队列中元素个数（即队列长度）
- 人为浪费一个单元，令队满特征为 front = (rear +1)%N---空闲单元法
这里采用空闲单元法解决二义性问题。 
5.3 实现
这里我们均采用C来实现链队列和循环队列
5.3.1 链队列实现
1 | //链队列的存储结构： |
6. 跳表和哈希散列
有序链表、有序数组、跳表和哈希表的渐进性能如下：
| 数据结构 | 最坏情况 | 平均情况 |
|---|---|---|
| 有序数组 | 查找O(lngn)、插入O(n)、删除O(n) |
查找O(lngn)、插入O(n)、删除O(n) |
| 有序链表 | 查找O(n)、插入O(n)、删除O(n) |
查找O(n)、插入O(n)、删除O(n) |
| 跳表 | 查找O(n)、插入O(n)、删除O(n) |
查找O(logn)、插入O(logn)、删除O(logn) |
| 哈希表 | 查找O(n)、插入O(n)、删除O(n) |
查找O(1)、插入O(1)、删除O(1) |
在C+的STL中适用了哈希散列的容器有：unordered_map、unordered_set、hash_map、hash_multimap、hash_multiset、hash_set
6.1 跳表
对于有序数组，我们进行二分查找所需要的时间为O(logn)。但是在有序链表上仍然需要的时间为O(n)，为了提高有序链表的查找性能，可以在全部或者部分节点增加额外的指针，在查找时，通过这些指针，可以跳过链表的若干个点，不必查看所有节点来寻找 调表采用随机技术来决定链表的哪些节点应增加额外的指针，以及增加多少个指针，基于这种技术，跳表的查找、插入、删除的平均时间复杂度为O(logn),最坏情况为O(n). 1
2
3
4
5
6
7
8
9//结构skipNOde
template<class K>
struct skipNode{
K element;
skipNode<K> **next; //指针数组
skipNode(const K& ele,int size):
element(ele){next=new skipNode<K>* [size];}
}
//结构体的指针域有next数组统一管理，next[i]表示i级链表的指针，元素存储在element内
6.1.1 实现原理
在一个用有序链表中查找指定值，至多需要N次值的比较。如果链表的中部节点加一个指针，则比较次数可以减少到N/2+1。这个时候我们在查找一个数时，首先是与中部的这个节点进行值比较，如果查找的数对关键字小，则只在左半部分继续查找，若大，则在右半部分查找。如下图所示: 
上图非常形象的展现了跳表的查找操作：如果跳表有多级索引，如图建立了一级索引，则从一级索引出发.
1. 索引级数的分配
- 在跳表中对
n个元素而言，以均等分p=0.5,则最多可有链表级数为maxLevel=logn-1。 - 对于第
i级链表，每2^i个元素取一个进行连接
2. 插入和删除
在插入和删除的时候，如果要保持索引级数分配的规则结构，要耗时O(n)，我们指定i级链表有n/(2^i)个元素，在插入的时候新数据属于i级链表的概率为1/(2^i)。
插入步骤：
- 进行查找
O(logn)，找到要插入的位置 - 插入时，要为新数据分配一个级，分配过程就是我们之前说的随机数生成器完成（随机数只是尽可能的维护这种结构规则，不是严格意义上的）
- 当新数据插入
i级链表的时候，只会对0~i级链表产生影响，因此要记住这些链表的前驱 - 然后只需对next[0~i]进行重新next指针指向
对于删除，我们无法控制结构即没有生成随机数操作来中和，删除操作：
- 要删除指定节点，就必须先找到该节点所在处
- 知道节点的所找链表级数
i，则只会影响0~i级的链表 - 对
0~i级进行next指针重指向
为什么插入要随机数：试想一下，如果插入一直指定一个级数去插入，那么极端情况下将会使跳表退化成单链表，也就失去了跳表的作用，作为一种动态数据结构，我们需要某种手段来维护级数与元素个数之间的平衡。 1
2
3
4
5
6
7
8template<class T>
int skipList<T>::level()const{
//返回一个链表级数随机数
int lev=0;
while(rand()<=cutoff)
lev++;
return (lev<maxLevel)?lev:maxLevel;
}
6.2 哈希表（散列表）
哈希表就是根据设定的哈希函数和处理冲突的方法将关键字映射到一个有限的连续的地址集（哈希数组）。当关键字的范围太大，不能用理想方法表示时，可以采用并不理想的哈希表和哈希函数：哈希表的位置的数量比关键字少，哈希函数把若干个不同关键字映射到哈希表的同一个位置（哈希表的每一个位置叫一个桶），桶的数量等于哈希表的长度。
构造哈希表，最常遇到的问题无非就是：
- 冲突：当两个不同关键字经哈希函数计算后的桶相同时，冲突就发生了。但这对于一个桶可以容纳多个数对的桶来说，并没有什么影响
- 溢出：桶没有位置可以存储新的数对，就会溢出
6.2.1 实现原理
哈希表的建立会适用特定的哈希函数将关键字进行计算转化生成我们访问的下标，这样就能够建立起访问、插入、删除的O(1)操作。因此最重要的是哈希函数的选择和对下标的实现。构造哈希函数的原则是：
- ①函数本身便于计算；
- ②计算出来的地址分布均匀，即对任一关键字k，f(k) 对应不同地址的概率相等，目的是尽可能减少冲突。
以下是对哈希函数的常用思想：
- 直接定址法：取关键字某个线性函数值为哈希地址，即
H(key)=a*key+b - 数字分析法：前提关键字都是知道的，在此基础上分析数据，依数据选择取哪些位作为
key值。例子：比如现有80个8位的十进制数，只能分配长为100的哈希表供你使用，此时就要依据这8位中哪些位取值分散而从中选取2位为哈希地址来尽可能避免冲突。 - 平方取中法：取关键字平方后的中间几位为哈希地址，平方取中法比较适用于不清楚关键字的分布，且位数也不是很大的情况。
- 折叠法：将关键字分成位数相同的几部分（最后一部分的位数可以不同），然后取这些部分叠加和作为哈希地址。折叠法比较适用于不清楚关键字的分布，但是关键字位数较多 的情况
- 除留余数法：取关键字被某个不大于哈希表长m的数
p除后所得余数为哈希地址，即h（k）=k % p，其中%为模p取余运算。一般p选为质数 - 位与法：哈希数组的长度一般选择2的幂，在C/C++中位运算相对较为高效，选择2的幂作为数组长度，可以将取模运算转换成二进制位与
1 | //专业版hash<string> |
6.2.2 解决hash冲突方案
- 开放定址法: 当发生地址冲突时，按照某种方法继续探测哈希表中的其他存储单元，直到找到空位置为止。
- 再哈希法：当发生哈希冲突时使用另一个哈希函数计算地址值，直到冲突不再发生。这种方法不易产生聚集，但是增加计算时间，同时需要准备许多哈希函数。
- 链地址法：将所有哈希值相同的Key通过链表存储。key按顺序插入到链表中
- 建立公共溢出区：采用一个溢出表存储产生冲突的关键字。如果公共溢出区还产生冲突，再采用处理冲突方法处理。
7. 二叉树
7.1 树的概念
树型结构是一类重要的非线性结构。树（Tree)是n个结点的有限集，在任一非空树中：
- 有且只有一个特定的称为根（Root)的结点，没有前驱的结点称为根结点。
- 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、T3.....Tm，每一个集合本身又是一颗树，并且称为根Root的子树。
- 每一个非根结点有且只有一个父结点；
基本术语：
- 节点的度：一个节点含有的子树的个数称为该节点的度
- 叶子：度为0的节点
- 非终端节点或分支节点：度不为零的节点；
- 树的度：树内所有节点的度的最大值；
- 双亲节点或父节点：若一个结点含有子节点，则这个节点称为其子节点的父节点；
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
- 兄弟节点：具有相同父节点的节点互称为兄弟节点；
- 堂兄弟节点：双亲在同一层的节点互为堂兄弟；
- 节点的祖先：从根到该节点所经分支上的所有节点；
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙；
- 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
- 树的高度或深度：树中节点的最大层次；
- 森林：由m（m>=0）棵互不相交的树的集合称为森林；
- 有序树/无序树：如果将树中节点的各个子树看成从左到右是有次序的，则称该树为有序树，否则为无序树；
7.2 二叉树
二叉树是另一种树型结构，它的特定是每个结点至多只有两棵子树。且二叉树的子树有左右之分，其次序不能任意颠倒。也可为空树。二叉树和树的根本区别是：
- 二叉树的每个元素恰好有两颗子树。而树可有任意数量的子树
- 在二叉树中，每个元素的子树都是有序的，即左子树和右子数之分。而树的子树是无序的
- 二叉树可以为空。而树不能为空
7.3 二叉树特性
二叉树具有较多的特性，使用也比较广泛：
- 在二叉树的第
i层上至多有2^(i-1)个结点i>=1; - 深度为K的二叉树至多有
2^(k)-1个结点K>=1; - 对任何一颗二叉树
T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1; - 具有n个结点的完全二叉树的深度为
L[log2(n)]+1;(L[X]表示取不大于X的最大整数） - 如果对一颗有
n个结点的完全二叉树（深度为L[log2(n)]+1）的结点按层序编号（从第一层到L[log2(n)]+1层，每层从左到右），则对任一结点i(1<=i<=n),，有： - ①
i=1，则结点i是二叉树的根，无双亲；i>1,则其双亲时结点[i/2] - ②如果
2i>n，则结点i无左孩子，否则其左孩子为2i - ③如果
2i+1>n，则结点无右孩子，否则其右孩子为2i+1
满二叉树和完全为叉树： 满二叉树：当高度为h的二叉树恰好有2^h-1个元素时，为满二叉树 完全二叉树：最后一层的叶子只能空右左节点，不能有右节点而没有左节点,下图为完全被二叉树 
7.4 二叉树的存储结构
二叉树的存储结构一般有顺序存储和链式存储。顺序存储也成为数组形式的描述，而链式存储是二叉树最常用的存储结构，它是用两个左右孩子指针指向其左右孩子节点。
7.4.1 顺序存储
顺序存储就是用一组地址连续的存储单元依次至上而下、从左到右存储完全二叉树的节点元素，所以顺序存储结构仅适用于完全二叉树和满二叉树（否则会造成空间浪费）。二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。如上图的完全二叉树在数组形式的存储如下： 
1
2
3
typedef ElemType sqBiTree[MAX_TREE_SIZE];
sqBiTree bt;
7.4.2 链式存储结构
既然顺序存储不能满足二叉树的存储需求，那么考虑采用链式存储。由二叉树定义可知，二叉树的每个结点最多有两个孩子。因此，可以将结点数据结构定义为一个数据和两个指针域。表示方式如图 
1
2
3
4typedef stuct BiTNode{
TElemType data;
strcut BiTNode *lchild,*rchlid;
}BiTNode,*BiTree;
7.5 实现
对于二叉树的实现这里主要讲解C++语言的实现
7.5.1 结构体和实现类
1 | //节点类，用于构建树中的节点 |
7.5.2 前序遍历
前序遍历是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29//递归版本
void preOrder(std::vector<T>& vec, binaryTreeNode<T>* Node){
if(Node==NULL)
return;
vec.push_back(Node->data);
preOrder(vec,Node->lchild);
preOrder(vec,Node->rchild);
}
//非递归版本,使用栈这个辅助数据结构
void preOrder(std::vector<T>& vec, binaryTreeNode<T>* Node){
stack<binaryTreeNode<T>*> _sta;
if(Node!=NULL){
auto p=Node;
while(!_sta.empty()||p!=NULL)
{
while(p!=NULL){
vec.push_back(p->data);
_sta.push(p);
p=p->lchild;
}
if(!_sta.empty())
{
p=_sta.top();
_sta.pop();
p=p->rchild;
}
}
}
}
7.5.3 中序遍历
中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。 
1
2
3
4
5
6
7
8//递归版本
void inOrder(std::vector<T>& vec, binaryTree<T>* Node){
if(Node==NULL)
return;
inOrder(vec,Node->lchild);
vec.push_back(Node->data);
inOrder(vec,Node->rchild);
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27binaryTree<T> *GoFarLeft(binaryTree<T>* t,stack<binaryTreeNode<T>*> &S)
{ //找到t树的最左孩子的指针，用指针返回，同时压栈所有遍历过的最左指针
if(!t)
return NULL;
while(t->lchild){
S.push(t);
t=t->lchild;
}
return t;
}
void InOrder(std::vector<T>& vec,binaryTree<T>* root)
{
stack<binaryTreeNode<T>*> _sta
aotu t=GoFarLeft(root,_sta);
while(t){
vec.push_back(t->data);
if(t->rchild)
t=GoFarLeft(t->rchild,_sta);
else if(!_sta.empty()){
t=_sta.top();
_sta.pop();
}
else
t=NULL;
}
}
7.5.4 后序遍历
后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左在向右的方向访问。 
1
2
3
4
5
6
7
8//递归版本
void postOrder(std::vector<T>& vec, binaryTreeNode<T>* Node){
if(Node==NULL)
return;
postOrder(vec,Node->lchild);
postOrder(vec,Node->rchild);
vec.push_back(Node->data);
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29//strcut TreeNode {
// ElemType data;
// TreeNode *left, *right;
// TreeNode() {
// left = right = NULL;
// }
//}
void PostOrder(vector<T>& vec,binaryTreeNode<T> *root) {
auto *p = root, *r = NULL;
stack<binaryTreeNode<T>*> s;
while (p || !s.empty()) {
if (p) {//走到最左边
s.push(p);
p = p->lchild;
}
else {
p = s.top();
if (p->rchild && p->rchild != r)//右子树存在，未被访问
p = p->rchild;
else {
s.pop();
vec.push_back(p->data)
r = p;//记录最近访问过的节点
p = NULL;//节点访问完后，重置p指针
}
}//else
}//while
}
7.5.5 层次遍历
层次遍历中一般使用队列作为辅助工具，将根节点压入后，访问其左右孩子节点并压入，然后根节点出队列，依据队列的先进先出，再访问根节点的左孩子节点的孩子节点并压入，然后是根节点的右孩子节点的孩子节点压入，以此递推下去。 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void level(vector<T>& vec,binaryTreeNode<T> *root){
if(root!=NULL)
{
queue<binaryTreeNode<T>*> _que;
_que.push(root);
while(!_que.empty()){
auto t=_que.front();
_que.pop();
vec.push_back(t->data);
if(t->lchild!=NULL)
_que.push(t->lchild);
if(t->rchild!=NULL)
_que.push(t->rchild);
}
}
}
7.5.6 求树的深度
1 | std::size_t height(binaTreeNode<T>* root){ |
7.6 应用
7.6.1 并查集
在介绍链表时侯我们将来并查集的概念，知道在线等价类就是并查集。但是使用链表解决并查集不是最优解，这里我们介绍树来解决并查集问题。在在线等价类的问题当中，初始时有n个元素，每个元素都属于一个独立的等价类。需要执行以下的操作:
- ①
conbine(a,b),把包含a,b的等价类合并为一个等价类 - ②
find(Element),确定元素Element在哪一个类，目的是对给定的两个元素，确定是否属于同一个类（同类，返回相同结果，否则不同）。
1 | combine(a,b) |
并查集问题的求解策略：把每一个集合表示为一棵树。
- 在查找时：把根元素作为集合标识符，因此find(a)返回的会是根元素。当且仅当a和b属于同一集合，
find(a)==find(b)为真. - 在合并时：假设调用语句
unite(classA,classB),classA和classB分别是不同集合的根，为了把两集合合并，得让一颗树成为另一颗树的子树。合并采用重量规则：若根为i的树的结点数少于根为j的树的节点数，则将j作为i的父节点。否则，将i作为j的父节点。
1. 重量规则使用的结构（顺序结构） 1
2
3
4
5
6
7
8//重量规则使用的结构（顺序结构）
struct unionFindNode
{
ElementType data;
int parent; ///root为true时，表示树的重量，false时，为夫节点的指针(索引)
bool root;
unionFindNode(){parent=1;root=ture;}
};parent的值,节点外的数字是该节点的索引，索引也同时是该节点所表示的元素，即中间的节点的元素值是下面一个节点的parent值（下面的find函数就说明了这一点）
2. 构建重量规则的树（该树使用顺序结构的形式）
1 | void initialize(int numberOfElements) |
3. 查找
1 | int find(int index) |
4. 合并
1 | void unite(int rootA,int rootB) |
7.6.2 二叉树的右视图
7.6.3 完全二叉树
7.6.4 对称二叉树
7.6.5 平衡二叉树
7.6.6 二叉树剪枝
8. 堆
- 大根树/小根树：定义是指它的每个节点都大于/小于或等于其子节点的值。
- 大根堆/小根堆：一个大根堆/小根堆既是大根树/小根树，也是完全二叉树
下图演示的堆的初始化和删除根节点的动态演示： 
8.1 堆的操作
8.1.1 堆的插入
因为堆是完全二叉树，所以当加入一个元素形时，必须维持该堆仍为完全二叉树，即该新节点位置由此定下了。接着元素插入要依据原来是大根堆还是小根堆（即不能破环该堆的性质）。把插入的元素，沿着从新节点到根节点的路径，执行一趟冒泡操作，将新元素与其夫节点的元素比较交换，直到后者大于前者（大根堆为例）。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15/*
该方法通过查询当前堆的大小和元素比较定位插入点，进行大根堆完全二叉树形式插入即`/2`
*/
template<class T>
void push(const T& theElement){
int currentNode=++heapsize;
//通过比较寻找插入点，比插入值小的元素下沉
while(currentNode!=1&&heap[currentNode/2]<theElement)
{
heap[currentNode]=heap[currentNode/2];
currentNode/=2;
}
//插入新值
heap[currenNode]=theElement;
}
8.1.2 堆的删除
在大根堆中删除一个元素，其实就是删除根节点的元素。此时就需要重新组织，以便保持性质不变 。其策略是，从删除的位置开始为一个树,向下找，找到该树的最后一个叶子节点，删除该节点但保存元素到临时量；然后比较删除（这个删除只是指元素替换了，而不是前面那个销毁删除）节点的左右孩子，将大的放到该根节点；这时因为大孩子的被放到根节点而成为了空(没有元素），此时我们像之前一样比较该结点的左右孩子，将大的放到该结点，以此类推……，直到最后一个叶子我们与之前中间量保存的元素比较，完成删除排序，如下图所示（小根堆）： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21templaet<class T>
void pop(){
if(heapsize==0)
return;
heap[1].~T(); //销毁根节点元素
T lastElement=heap[heapsize]; //最后一个元素保存到临时变量
heap[heapsize--].~T(); //销毁最后一个元素
int currentNode=1,child=2;
while(child<heapsize)
{ //元素进行上升
if(child<heapsize&&heap[child]<heap[child+1])
child++;
//判断lastElement是否可以放在heap[child]上
if(lastElement>=heap[child]) //可以就直接退出
break;
heap[currentNode]=heap[child];
currentNode=child;
child*=2;
}
heap[currentNode]=lastElement;
}
8.1.3 堆的初始化
初始化：当堆刚开始时就要有n个元素，我们就要构建非空堆，我们需要在堆中执行n次插入操作。先将元素按层次插入，取位置在i=n/2的元素，如果以这个元素为根的子树是大根堆则不做操作，如果不是大根堆则从该节点开始的树进行检测替换，依次检查i-1,i-2……1 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22template<class T>
void initial(T *theHeap,std::size_t _heapsize){
delete[]heap;
heap =theheap;
heapsize=_heapsize;
//从下往上进行堆化，即从heapsize/2开始，直到root=1
for(size_t root=heapsize/2;root>=1;root--)
{
T rootElement=heap[root];
int child=2*root;
while(child<=heapsize)
{
if(child<heapsize&&heap[child]<heap[child+1])
child++;
if(rootElement>=heap[child])
break;
heap[child/2]=heap[child];
child*=2;
}
}
heap[child/2]=rootElement
}
9. 二叉搜索树
主要有二叉搜索树和索引二叉搜索树。二叉搜索树的查找、插入和删除操作的所需平均时间为O(log2n),最坏的情况为O(n)。对于给定一个关键字，使用二叉搜索树，可以在O(n)时间内，找到最接近它的关键字。二叉搜索树是一颗二叉树，可能为空，一颗非空的二叉搜索树满足以下特点：
- 每个元素有一个关键字，并且任意两个元素的关键字都不同（有重复值的二叉搜索树除外），因此所有的关键字都是唯一的
- 在根节点的左子树中，元素的关键字(如果有的话）都小于根节点关键字
- 在根节点的右子树中，元素的关键字都大于根节点的关键字
- 根节点的左右子树也都是二叉树
9.1 实现
9.1.1 搜索
要查找关键字为theKey的元素，先从根查找，如果根为空，则搜索树为空的；若不为空，则将theKey与根关键字比较大小，由二叉树搜索树的性质知，比根的大，则向右子数查找，若小，则向左子树查找，依次类推，直到找到或者到NULL为止。如下图查找5 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15template<class K,class E>
pair<const K,E>*binarySearchTree<K,E>::find(const K& theKey,
binaryTreeNode<const K,E>*p)const
{
while(p!=NULL)
{
if(theKey<p->element.first)
p=p->leftChild;
else if(theKey<p->element.first)
p=p->rightChild;
else
return &p->element;
}
return NULL;
}
9.1.2 插入
重复的关键字进行值更新，从根节点开始比较，直到遇到相同的关键或NULL 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34template<class K,class E>
void binarySearchTree<K,E>::insert(const pair<const K,E>&
thePair,binaryTreeNode<pair<const K,E> *p)
{
binaryTreeNode<pair<const K,E> *pp=NULL;
while(p!=NULL)
{
pp=p;
if(thePair.first<p->element.first)
p=p->leftChild;
else if(thePair.first>p->element.first)
p=p->rightChild;
else
{
p->element.second=thePair.second;
return;
}
}
binaryTreeNode<pair<const K,E> *newNode
=new binaryTreeNode<pair<const K,E>>(thePair);
if(rootNode==NULL)
{
rootNode=newNode;
rootNode->leftChild=rootNode->rightChild=NULL;
}
else
{
if(pp->element.first<thePair.first)
pp->rightChild=newNode;
else
pp->leftChild=newNode;
}
stSize++
}
9.1.3 删除
假设要删除接节点p，我们要考虑三种情况：①p是叶子；②p只有一颗非空子树；③p有两颗非空子树
- 第一种情况非常好做，只有释放叶子节点的空间即可，若是根节点，置为
NULL
- 第二种情况也较为简单 ，如果
p是根节点，则p的唯一子树的根节点成为新的搜索树的根节点。若p有父节点pp，则修改pp的指针域，使它指向p的唯一孩子，然后释放节点p
- 第三种情况较复杂，我们先将该节点的元素替换为它左子树的最大元素（或者右子树的最小的一个元素）。然后把替换的节点删除，该删除的结点如果有左子树，则该左子树变为该结点的双亲的右子树（或者删除的结点如果有右子树，则该右子树变为该结点的双亲的左子树）
1 | template<class K,class E> |
10. 平衡二叉搜索树AVL
如果搜索树的高度总是O(logn)，我们能保证查找、插入、删除的时间为O(logn)。最坏情况下的高度为O(logn)的树为平衡树（balanced tree)。但是正如上面搜索树所讲的，在大量的插入后搜索树极其容易不平衡导致元素大量在一个分支上，退化成链表，这时候查找、插入、删除的时间复杂的就不为O(logn)。平衡二叉搜索树就是为解决这个问题而得出的数据结构。
10.1 平衡二叉搜索树的定义
一颗空的二叉树是AVL树；如果T是一颗非空的二叉树，T1和T2分别是其左子树和右子数，那么当T满足以下条件时，T是一颗AVL树：
- ①
T1和T2是AVL树； - ②
|hl-hr|≤1，其中hl和hr分别是Tl和TR的高。
一颗AVL搜索树既是二叉搜索树，也是AVL树。如果用AVL搜索树来描述字典，并在对数级时间内完成每一种字典操作，那么，我们必须确定AVL树的下列特征：
- 一颗
n个元素的AVL树，其高度是O(logn) - 对于每一个
n.n≥0，都存在一颗AVL树 - 对一颗
n元素的AVL搜索树，在O(高度)=O(logn)的时间内可以实现查找 - 将一个新元素插入一颗
n元素AVL搜索树种，可以得到一颗n+1元素的AVL树，且插入用时为O(logn) - 一个元素从一颗
n元素的AVL搜索树删除，可以得到一颗n-1的AVL搜索树，而且用时为O(logn)
AVL树的描述：AVL树一般用链表进行描述，为简化插入和删除操作，我们为每一个节点添加一个平衡因子bf，假设x的左子树高度为hl,右子树高度为hr，节点x的平衡因子bf(x)定义为：
bf(x)=hl-hrbf(x)取值只能为0，-1，1
这里主要讲解平衡二叉搜索树的搜索、插入和删除操作。
10.2 搜索
同二叉搜索树一样的操作，n元素的AVL树的高度是O(logn)，所以搜索时间为O(logn)。要查找关键字为theKey的元素，先从根查找，如果根为空，则搜索树为空的；若不为空，则将theKey与根关键字比较大小，由二叉树搜索树的性质知，比根的大，则向右子数查找，若小，则向左子树查找，依次类推，直到找到或者到NULL为止。如下图查找5。实现略
10.3 插入操作
AVL树因为要保证每个结点的平衡因子要时时刻刻都符合要求，则树中每插入一个结点，都可能引起平衡被打破，所以每次插入一个结点，都要从插入的结点往上进行检查是否有哪个结点需要调整。要在插入新结点后进行平衡检查，则需要把插入结点的插入过程的下行路线上的每一个结点都依次记录下来，这个可以借助于栈来实现，在查找插入位置的过程，把每一个结点指针放入栈中．
10.3.1 插入的具体步骤
- 第一步：从根结点开始，首先查找要插入的位置。如果结点值相等则更新，如果小于则向左走，如果大于则向右走，把这个过程中的每一个结点都放入一个栈中，这样直到到达叶子结点，即找到了插入的位置．然后
new出来一个结点进行插入 - 第二部：插入完成以后进行平衡调整。取出栈中的元素进行检查：插入的结点对于取出的结点如果是左边插入，则平衡因子
+１，如果右边插入则平衡因子-１． - 第三步1：如果加减
１以后平衡因子是０，即意味着插入节点之前平衡因子只能是±１，插入该节点以后，该子树的左右子树高度相等，因此并不改变该子树的高度，也就并不影响整棵树的高度，所以树是平衡的，不需要第三步2：调整，调整结束break； 如果插入后平衡因子是
+1或者-1，则意味着该节点所在的子树的高度发生变化（因为在此之前该节点的平衡因子只能是０），所以以该节点为root的子树的高度一定是增加了，所以要向上继续检查是否有哪个节点的平衡因子因为插入了一个节点平衡因子变为±２，所以继续取出stack中的下一个节点进行上述同样的检查- 第四步：如果平衡因子是正负２，则平衡打破，需要进行调整，下面详述调整过程：
- １．
bf=-2: 如果该节点的孩子节点平衡因子是负值：则对该节点进行一次左旋转即调整完成；如该该节点的孩子节点的平衡因子是正值：则需要进行先左后右旋转． - ２．
bf=+2:如果该孩子节点bf是正值：则对该节点进行一次右旋转即可；如果孩子节点bf是负值：则对该节点进行先右后左旋转即可．
- １．
调整平衡完成以后需要将该子树的新根节点挂到之前的根节点下面．以上即整个插入过程．
10.3.2 失衡的情况
如果按二叉搜索树的插入算法会影响AVL树将不在是AVL树。如下图按二叉搜索树的方式将32插入VAL搜索树而导致失衡 
因此，插入操作必须维护各节点的|bf|≤1。插入破环原AVL搜索二叉树结构是以下情形：
- 在不平衡树中，平衡因子的值限于
2，1，0，-1，-2 - 平衡因子为
2的节点插入前平衡因子为1，同样-2的插入前为-1 - 只有从根到新插入节点路径上的节点，其平衡因子在插入后会改变
- 假设
A是离新插入节点最近的祖先，且平衡因子是-2或2（在上面的图中A是关键字为40的节点），在插入前，从A到新插入节点的路径上，所有节点的平衡因子都是0
对于平衡与失衡的判断存在与否，主要就是看A这一节点存不存在，即平衡因子变为2或-2的最近祖先节点存在与否：
A节点不存在：那么从根节点至新插入节点的途中，所有节点在插入前的平衡因子都为0或者为-1但插入左则或者为1但插入右侧，由于插入操作平衡因子增减0或1，所以从根节点到插入新节点的途径的节点平衡因子可能改变，但树的平衡不会改变。 
10.3.3 失衡的种类
A节点存在：就出现平衡因子|bf|=2的情况，破坏了平衡，此时就需要进行平衡操作。其不平衡的情况有两类
L型不平衡,新插入的节点在A的左子树中R型不平衡,新插入的节点在A的右子树中
同时，从根到新插入节点的路径上，根据A的孙节点情况，还可在细分（包含新节点的A的子树高度至少为2，因为有定义知A的平衡因子为2或-2,A才存在孙节点），此时细分为LL,LR,RL,RR。 
6节点的左子树3节点高度比右子树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种情况成为左左LL(左孩子的左子树深度大)。
6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种情况成为左右LR。
2节点的左子树1节点高度比右子树5节点小2，右子树5节点的左子树3节点高度大于右子树6节点，这种情况成为右左RL。
2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点，这种情况成为右右RR。
10.3.4 LL型平衡操作
右旋：在最小平衡子树根节点平衡因子>=2且在根节点的左孩子的左孩子插入元素即LL，要进行右旋 
右旋如上所示，绕|bf|=2的节点（以下统称为root）进行旋转，根节点的左孩子成为新的根节点，而原来的root成为其右孩子，同时若新的根节点原来的右子树成为root的左子树,如下 
10.3.5 RR型平衡操作
在最小平衡子树根节点bf>=-2且在根节点的右孩子的右孩子插入元素，进行左旋。 
其动作与LL一样，只不过方向相反。
10.3.6 LR型平衡操作
在最小平衡子树根节点80的左孩子50的右孩子70的子节点插入新元素，先绕根节点的左孩子节点50右旋，再围根节点80左旋 
10.3.7 RL型平衡操作
最小平衡子树根节点80的右孩子100的左孩子90的子节点95插入新元素，先绕根节点的右孩子节点100右旋，再围根节点80左旋 
其动态展示如下： 
10.4 删除操作
10.4.1 删除节点
执行二叉搜索树得删除操作，AVL树删除节点，首先查找要删除的节点，找到以后，要删除的节点分为两种情况：
- １.要删除的节点左右两个孩子都存在，直接删除不方便，则在右子树中查找最小的节点，将其值替换为要删除的节点的值，因为右子树的最小节点必然没有左孩子，即只有一个孩子．然后问题转化为删除这个右子树中最小的节点．（或者也可以将问题转化为删除左子树里最大的节点）
- ２.要删除的孩子节点只有一个孩子节点，则直接将仅有的一个孩子节点提上来即可．
10.4.2 平衡性检查
删除以后将进行从删除节点向上进行平衡性的检查。在查找要删除的节点的过程中，将经过的路径上的节点位置全部存放到一个stack。在平衡型检查过程种取出栈顶元素pr并弹出栈顶元素，如果删除的节点pr的key值比该节点的key值小,则必定是左树删除则pr->bf-1了，否则pr->bf+1。会造成以下三种情况：
- １．删除后如果
|pr->bf|=1：则在删除节点之前pr->bf０，即左右平衡，删除了以后左树或者右树少了一个节点，但pr这个子树的高度并没发生变化．对与pr的上面的所有节点而言树高并没有发生变化，所以调整完成． - ２．如果删除后|pr->bf|=０
,则在删除之前平衡因子是±１，现在删除节点以后变为０，则pr子树的高度减１`（发生了变化，影响到了上面的节点），则要向上（出栈）继续检查， - ３．如果删除后造成
|pr->bf|==２,则平衡打破，进行平衡调整.
11. 红黑树
平衡索引二叉树是高度平衡的二叉树，频繁的插入和删除，会引起频繁的rebalance,导致效率下降；红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转的数据结构，所以红黑树在查找，插入删除的性能都是接近O(logn),且性能稳定，所以STL里面很多结构包括map底层实现都是使用的红黑树。
1 | RB树的节点结构: |
11.1 红黑树特点
红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，通常使用红黑树。红黑树具有以下的性质：
- 每个节点非红即黑
RB1：根节点是黑的;RB1：每个叶节点（叶节点即树尾端NULL指针或NULL节点）都是黑的;RB2：如果一个节点是红色的，则它的子节点必须是黑色的，即红节点不能连续**RB3：对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点;
一个节点的阶是指从该节点到一外部节点路径上黑色指针的数量，定理：
- 设根到外部节点的路径长度length是该路径上的指针数量。如果P和Q是红-黑树中的两条从根至外部节点的路径，那么
length(P)≤2length(Q) - 令
h是一颗红-黑树的高度（不包括外部节点），n是树的内部节点数量，而r是根节点的阶，则有:- ①
h≤2r - ②
n≥2^r-1 - ③
h≤2log2(n+1)
- ①
11.2 红黑树操作
- 搜索：使用普通的二叉搜索树的搜索代码。对红黑树来说，时间复杂度为
O(logn)。比较而言，二叉搜索树、AVL、红黑树搜索都使用相同代码，而且在最坏的情况下AVL树的高度是最小的，所以在搜索为主的应用中，avl是最优的。 - 插入：红黑树的插入使用的是普通二叉搜索树插入算法，对插入的元素，需要上色。如果插入前树是空的，那么新节点是根节点，颜色应是黑色。
对红黑树的插入删除要维护其原本的性质：假设插入前的树是非空的，如果新节点的颜色是黑色，那么从根到外部节点路径上，将有一个特殊的黑色节点作为新节点的孩子。如果新节点是红色，那么可能出现两个连续的红色节点。所以把新节点赋为黑色肯定不符合RB3，而把新节点赋为红色虽然一定符合RB3,但可能违反了RB2。对红黑树的插入删除要维护其原本的性质。
11.2.1 赋为红色而造成的不平衡类型
如果是新节点赋为红色而造成RB2规则被破坏，我们就说树的平衡杯破坏了。此时平衡破坏则必有有两连续红色节点，一个是新节点u,一个是其父结点pu。而此时祖父节点gu一定是黑色的。有以下情况
- 当
pu是gu的左孩子，u也是pu的左孩子时且gu的另一个孩子（右孩子）是黑色的（为外部节点），该不平衡类型为LLb类型。 - 当
pu是gu的左孩子，u是pu的左孩子时且gu的另一个孩子（右孩子）是红色的（不是外部节点），该不平衡类型为LLr类型。
依次类推出LRb、LRr、RRb、RRr、RLb、RLr
平衡方法；
XYr型的不平衡可以通过改变颜色来处理：将pu节点变为黑色，对于LLr和LRr的gu的右孩子要由红色变为黑色，另外如果gu不是根则改为红色，如果是根节点则保持gu为黑色不变；因为gu由黑变红的情况可能导致上一层平衡破坏，如果破坏了（即原gu与gu父结点都为红）此时将gu变为u,gu父结点变为pu,gu祖父节点为gu,分析是XYr类型还是XYb类型，继续恢复平衡操作。
XYb型则需要旋转。插入后依次旋转足以保持平衡。该旋转的改变同AVL相似
附：对于删除操作，首先使用二叉搜索树的删除算法。然后进行颜色变动，需要的话还要进行一次旋转。 - 删除红色节点，不会影响规则，只需将相应的需要变色的指针变色即可。 - 删除黑色节点，会影响RB3（不是根节点时）。使用该删除算法，不会违反除RB3外的其它红黑树规则。
12. 图
图是一个用线或边连接在一起的节点(顶点）的集合。严格地说图是有限集V和E的有序对G=(V,E)。V中的元素为顶点，E为边。对于图我们需要先了解以下预备知识：
- 图的术语：顶点、边、邻接、关联、度、回路、路径、连通构件、生成树
- 图的类型：无向图、有向图和加权图
- 常用描述方法：邻接矩阵、矩阵邻接表和邻接链表
- 图的标准搜索方法：广度优先搜索和深度优先搜索
- 图的算法：寻找图的路径、寻找无向图的联通构件、寻找连通无向图的生成树
12.1 图的基本概念
- 每一条边连接两个顶定，用元组
(i,j)表示，i\j表示连接的顶点。带方向的叫有向边，不带方向叫无向边。 - 当且仅当
(i,j)是图的边，称顶定i和j是邻接的。边(i,j)关联 - 如果图的所以边都是无向的，则称图为无向图；都是有向的为有向图
- 一个图不能有重复的边，即任意两个顶点，在无向图只有一条边，有向图是
i到j即(i,j),j到i即(j,i)各一条 - 为每条边赋予值，成为权。此时成为加权有向图和加权无向图
- 简单路径：除最后一个和第一个顶点之外，其余所有顶点都要求不同（如521，525）
- 环路：一条始点和终点相同的简单路径
- 连通：图的每一对顶点之间都有一条路径
- 生成树：没有环路的连通无向图是一颗树。一个G的子图，包含G的所有顶点，且为一棵树，则称为G的生成树
- 二分图：顶点被分为两个子集A，每条边都有一个顶点在A，另一个在B
- 度：一个顶点相关联的边数
12.2 无权图的描述
无向图最常用的描述方法都是基于邻接的方式，如邻接矩阵、邻接链表和邻接数组 1
2
3
4
5
6
7
8
9
10
11
12
13
14template<class T>
class graph
{
public:
virtual ~graph(){}
virtual int numberOfVertices()const=0; //顶点数
virtual int numberofEdge()const=0; //边数
virtual bool exitsEdge(int ,int)const=0; //判断两顶点是否关联
virtual void insertEdg(int i,int j)=0; //添加边
virtual void eraseEdge(int,int)=0; //删除边
virtual int degree(int) const=0; //指定顶点的度
virtual int inDegree(int) const =0; //入度
virtual int outDegree(int) const=0; //出度
}
12.2.1 邻接矩阵
一个n顶点图G=(V,E)的邻接矩阵是一个n*n矩阵，其中每个元素是0或1（对角线上的元素都为0，因为没有自连边）。将矩阵映射到一个n*n布尔型二维数组进行存储。因为无向图的邻接矩阵是对称的即A(i,j)=A(j,i)，所以只需存储上三角或下三角元素。因为采用布尔类型1字节，所以共用了n^2字节。
- 优势：因为无向图的邻接矩阵是对称的即
A(i,j)=A(j,i)，所以只需存储上三角或下三角元素。无向图的度为所在行（或列）的元素和。同时对于有向图，出度为该行的元素和，入度为该列的元素和 - 缺点：内存空间浪费
12.2.2 邻接链表
一个顶点i的邻接表是一个线性表，它包含了所有邻接i的顶点。在一个图的邻接表中，图的每一个顶点都有一个邻接表。当邻接表用链表表示时，就是邻接链表。 我们可使用类型为链表的数组aList来描述所有邻接表（指针数组）。aList[i]->next指向顶点i的邻接表的第一个顶点的数组下标索引index，通过访问aList[index]得到该点的邻接表，(i,index)是图的一条边。。 
一个指针和一个整数需要4字节的存储空间，顶点需要8(n+1)(为了数组下标对应，不使用下标0的空间，所以n+1)字节存储n+1个next指针和index域。
12.2.3 邻接数组
在邻接数组中同邻接链表相似，只不过每一个邻接表用一个数组线性表如vector而非链表来描述。
12.3 链表类的实现
下面的程序给出了邻接链表的的数据成员和一些实现方法，仅供参考，构造函数的时间复杂度为O(n)，方法existsEdgr(i,j)的时间复杂度为O(d^out) 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37class linkedDigraph:public graph<bool>
{
protected:
int n; //顶点数
int e; //边数
vector<List> vlist; //邻接表
public:
linkedDigraph(int numberOfv=0)
{ //构造函数
if(numberOfv<0)
throw illegalParameterValue("Number of vertices must be >=0)
n=numberOfv;
e=0;
aList=new graphChain<int>[n+1];
}
//析构函数
~linkedDigraph(){delete[] aList;}
//边是否存在
bool existsEdge(int i,int j)const
{//当且仅当(i,j)时返回treu
if(i<1||j<1||i>n||j>n||vList[i].indexOf(j)==-1)
return false;
else
return true;
}
//插入边
void insertEdge(int i，int j)
{
if(aLsit[i].indexOf(j)==-1)
{
//新边
aList[i].Insert(j);
aList[j].Insert(i);
e++;
}
}
}；
12.4 图的遍历
图的遍历有广度优先搜索(BFS)和深度优先搜索(DFS)两种
12.4.1 广度优先搜索(BFS)
广度优先搜索(BFS),从一个顶点开始，搜索该顶点所有可到达顶点的，新顶点再重复搜索可到达的顶点的方法(已到达的标记为已达，避免重复到达记录，因为顶点是1~n,可使用record[u]=0(未到达)/lable(已到达),u为1~n）。这种搜索性质可使用队列实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 void bfs(int v,int reach[],int label)
{
arrayQueue<int> q(10);
reach[v]=label;
q.push(v);
while(!q.empty())
{
int w=q.front();
q.pop();
vertexIterator<T>*iw=iterator(w);
int u;
while((u=iw->next())!=0) //u的相邻点，无则返回0
if(reach[u]==0) //相邻点是没有到达过的
{
q.push(u);
reach[u]=label;
}
delete iw;
}
}
12.4.2 深度优先搜索(DFS)
深度优先搜索(DFS).从一个顶点v出发，首先将v标记为已到达，后选择一个邻接于v的尚未到达的顶点u。u再重复上述操作，直到新u不存在，即无法找到u。--->一次搜一个/递归/或栈来实现 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17void dfs(int v,int reach[],int label)
{
graph<T>::reach=reach;
graph<T>::label=label;
rDfs(v);
}
void rDfs(int v)
{ //递归
reach(v)=label;
vertexIterator<T>*iv=iterator(v);
int u;
while((u=iv->next())!=0)
if(reach[u]==0)
rDfs(u);
delete iv;
}
12.5 图的应用
12.5.1 最短路径
主要讨论带权有向图，将路径上的第一个顶点称为源点，最后一个顶点为终点。
1. 迪杰斯特拉算法
迪杰斯特拉算法是求从某个源点到其余各顶点的最短路径的算法。该算法思想是按路径长度递增的次序产生一个最短路径。描述要借助两个集合S、U
- 初始时，
S只包含起点s；U包含除s外的其他顶点，且U中顶点的距离为起点s到该顶点的距离(例如，U中顶点v的距离为(s,v)的长度，如果s和v不相邻，则v的距离为∞]。
- 初始时，
- 从U中选出距离最短的顶点k，并将顶点k加入
S中；同时，从U中移除顶点k。
- 从U中选出距离最短的顶点k，并将顶点k加入
- 更新
U中各个顶点到起点s的距离。这是由于上一步中确定了k是求出最短路径的顶点，从而可以利用k来更新其它顶点的距离；例如，l(sv)>l(sk)+l(kv),那么就得用l(sk)+l(kv)替换l(sv)
- 更新
- 重复步骤(2)和(3)，直到遍历完所有顶点。
如下所示解法： 
- 重复步骤(2)和(3)，直到遍历完所有顶点。
1 | //D算法最短路径 |
2. 弗洛伊德算法
弗洛伊德算法是求每一对顶点之间的最短路径，其实调用n次dijkstra函数也能求出每一对顶点之间的最短路径，时间复杂度为O(n*n*n)。但是在这里我们介绍比较简洁的Floyd算法。Floyd算法的基本思想,可以将问题分解:
- 第一先找出最短的距离
- 第二再考虑如何找出对应的行进路线。
如何找出最短路径呢，这里还是用到动态规划的知识，对于任何一个城市而言，i到j的最短距离不外乎存在i到j之间经过k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，在检查d(ij)与d(ik)+d(kj)的值；在此d(ik)与d(kj)分别是目前为止所知道的i到k与k到j的最短距离，因此d(ik)+d(kj)就是i到j经过k的最短距离。所以，若有d(ij)>d(ik)+d(kj)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(ij)重写为d(ik)+d(kj)，每当一个k查完了，d(ij)就是目前的i到j的最短距离。重复这一过程，最后当查完所有的k时，d(ij)里面存放的就是i到j之间的最短距离了。
实现过程：
- 写出图的初始距离矩阵
W0和初始路由矩阵R0
\[ W^0= \begin{cases} d_{ij}，当v_i与v_j间有边时\\ ∞，当v_i与v_j间无边时\\ 0，i=j \end{cases} \] \[ R^0= \begin{cases} j，当W^0<∞，i→j前次经过的中间点\\ 0，W^0=∞或i=j \end{cases} \]
- 依次将G中的各节点
K作为中间节点，求Wij的最短路径,k=1,2,3...n。当节点K为中间节点时,要更新矩阵：
\[ W^K= \begin{cases} min(W^{K-1}_{ij},W^{k-1}_{ik}+W^{k-1}_{kj}) \end{cases} \] \[ R^k_{ij}= \begin{cases} k，,W^{k-1}_{ik}+W^{k-1}_{kj}时进行更新\\ r^{k-1}_{ij}，不更新 \end{cases} \]
- 当
k=n时，得到的W矩阵即为各顶点间的最短距离，R为路径选择 如下的例题：
由R0知道经过V1作为中间节点可得W1和R1：
再由R1知道经过V2可得W2和R2
经过上面的两个图可以知道，我们对矩阵的改变其实只用看当前节点所在的行和列，有数字时可能会发生改变，此时进行d(ij)与d(ik)+d(kj)的比较看是否要更新。
12.5.2 拓扑排序
当且仅当一个有向图为有向无环图DAG，directed acyclic graph时，才能得到对应于该图的拓扑排序。每个有向无环图都至少存在一种拓扑排序。一般来说拓扑排序主要应用于判断有向图是否有环。
实现：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则必无环。一般采用邻接表，每个头节点增加一存储入度的数据域。一般为避免重复检测入度为0的点，可设一栈或队列暂存入度为0的点，也可以设置标志位isnotPutInSet
- 在有向图中选择一个没有前驱即入度为
0的顶点输出之 - 从图中删除该顶点和所有以他为头的弧，并且相应的尾顶点
入度-1 - 重复上述两步直至无法输出
- 若此时输出的顶点数小于有向图的定点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51//时间复杂度为O(n*n)
struct graph
{
int indegree;
int numberofVertices;
graph(int _in, int vertices) :indegree(_in), numberofVertices(vertices) {}
set<int> linkV;
bool isnotPutInSet = true;
~graph() = default;
};
void topoSort(vector<graph>& vec) {
set<int> zeroIndegreeVertices;
// int Size = vec.size();
//int count = 0;
auto it = vec.begin();
while (it != vec.end())
{
if (it->indegree == 0 && it->isnotPutInSet)
{
zeroIndegreeVertices.insert(it->numberofVertices);
for (auto iter = it->linkV.begin(); iter != it->linkV.end(); iter++)
{
--vec[*iter-1].indegree;
}
it->isnotPutInSet = false;
it = vec.begin();
}
else
++it;
}
if (vec.size() == zeroIndegreeVertices.size())
cout << "该图无环路" << endl;
else
cout << "该图有环路" << endl;
}
//调试
vector<graph> gvec;
graph v1(0, 1);
v1.linkV.insert({ 2,4 });
graph v2(1, 2);
v2.linkV.insert({ 3,4 });
graph v3(2, 3);
graph v4(2, 4);
v4.linkV.insert({ 3 });
gvec.push_back(v1);
gvec.push_back(v2);
gvec.push_back(v3);
gvec.push_back(v4);
topoSort(gvec);
12.5.3 最小生成树
最小代价生成树即指对带权无向图包含所有n个顶点和n-1条边，联通所有结点后代价最小的树。假设N =(V，{ E })是一个连通网，U是顶点集V的一个非空子集。若(u , v)是一条具有最小权值（代价）的边，其中u∈U， v∈(V - U)，则必存在一棵包含边（u，v）的最小生成树。最小生成树的算法有普里姆算法和克鲁斯卡尔算法。
1. 普里姆(prim)算法
算法思路：首先就是从图中的一个起点a开始，把a加入U集合，然后，寻找从与a有关联的边中，权重最小的那条边并且该边的终点b在顶点集合：(V-U)中，我们也把b加入到集合U中，并且输出边(a，b)的信息，这样我们的集合U就有：{a,b}，然后，我们寻找与a关联和b关联的边中，权重最小的那条边并且该边的终点在集合：(V-U)中，我们把c加入到集合U中，并且输出对应的那条边的信息，这样我们的集合U就有：{a,b,c}这三个元素了，依次类推，直到所有顶点都加入到了集合U。其实就是贪心算法 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53//使用邻接矩阵结构，复杂度为O(n*n)
void prim(vector<vector<int>>& vec)
{
vector<int> ve; //U集合记录顶点，
set<int> reachV; //记录已到达过的顶点
ve.push_back(0); //直接将V0加入集合U
reachV.insert(0); //0已到达过
while (ve.size() != vec.size())
{
int min = INT_MAX;
int sourceV = 0;
int toVertice = 0;
for (int i = 0; i < ve.size(); i++)
{
int vertice = ve[i];
for (int j = 0; j < vec[i].size(); j++)
{
if (min < vec[vertice][j])
continue;
else
{ //若当前记录的的min权值大于当前两节点边的权值，进行更新
if (reachV.find(j)==reachV.end()) {
min = vec[vertice][j];
toVertice = j;
sourceV = vertice;
}
}
}
}
ve.push_back(toVertice);
reachV.insert(toVertice);
cout << "V"<<sourceV+1 << " to " << "V"
<< toVertice+1 << " 权值:" << min << endl;
}
}
//调用
vector<vector<int>> vec{ {INT_MAX,6,1,5,INT_MAX,INT_MAX},
{6,INT_MAX,5,INT_MAX,3,INT_MAX},
{1,5,INT_MAX,5,6,4},
{5,INT_MAX,5,INT_MAX,INT_MAX,2},
{INT_MAX,3,6,INT_MAX,INT_MAX,6},
{INT_MAX,INT_MAX,4,2,6,INT_MAX} };
for (auto it : vec) {
for (auto i : it)
if (i == INT_MAX)
cout << "∞ ";
else
cout << i <<" ";
cout << endl;
}
prim(vec);
2. 克鲁斯卡算法
算法思路：
- （1）将图中的所有边都去掉。
- （2）将边按权值从小到大的顺序添加到图中，保证添加的过程中不会形成环
- （3）重复上一步直到连接所有顶点，此时就生成了最小生成树。这是一种贪心策略。
13. B-Tree
对存储在磁盘上的数据，B-Tree是一种适合索引方法的数据结构。
13.1 B-Tree的特点
B-Tree也称B树是一种平衡的多路查找树。一颗3阶的B树，其内部节点必须有2~3个孩子。因此可知道一颗m阶B树（空树/m叉树），必须满足以下特性：
- 树中每个结点至多有
m棵子树，即至多含有m-1个关键字 - 若根结点不是叶子结点，则至少有两棵子树
- 除根之外的所有非终端结点至少有
[m/2]棵子树，[]表示向上取整。 - 所有非终端结点包含下列信息数据
n,P0,K1,P1,K2......Kn,Pn;其中Kn为关键字，Pn为指向下面子树根节点的指针。他有：- ①当
i<j时，Ki<Kj； - ②当
i<j时，对于指针Pi指向的子树根节点的关键子都必须小于Kj，而当i>j时必须Pi所指子树根节点的关键子都必须大于Kj（即从小到大）； - ③关键子个数
[m/2]-1≤n≤m-1
- ①当
- 所有叶子结点都在同一层
1 | //存储结构 |
13.2 B-Tree的高
对于B-Tree的定理有：设T为一颗高度为h的m阶B-Tree，n为T的元素个数，d=[m/2],则有：
- \(2d^{h-1}≤n≤m^k-1\)
- \(log_m{n+1}≤h≤log_d \frac{n+1}2+1\)
则有上面的公式可以知道，一颗高度为5的200阶B-Tree至少有\(2*10^8-1\)个元素。这种高度低且一个节点有多个元素的结构很符合磁盘的一次性存储与取出大小适当数据量。
13.3 B-Tree的操作
13.3.1 B-Tree的搜索
B-Tree的搜索算法与m叉搜索树的搜索算法相同。在搜索过程中，从根部至外部节点路径上的所有内部节点通过比较关键子大小选择以哪条路径行进，直到相等或者到NULL，因此，磁盘访问次数最多是h
13.3.2 B-Tree的插入
对于B-Tree的插入，首先经过关键字搜索比较找到插入的节点，之后有如下法则
- 为空时直接插入到根节点记录
- 插入的节点为不饱和节点，则直接插入，不必做其他操作
- 如果插入的时饱和节点，则先插入，然后取中上升，其余的进行分裂
13.3.3 B-Tree的删除
B-Tree的删除会破坏规则：每个非终端节点至少含有[m/2]棵子树，即每个非终端节点的要有[m/2]-1个关键字；或者破坏了指针指向。因此为恢复该规则进行操作有：
删除叶子关键字：
- 若该叶子节点删除该关键字后，仍满足关键字数量范围，直接删除
- 若叶子结点删除该关键字后，不满足关键字数量范围，但兄弟结点关键字＞
[m/2]-1,兄弟借（途经父亲） - 若叶子结点删除该关键字后，不满足关键字数量范围，且兄弟结点关键字=
[m/2]-1,向父借，拖父下水
删除非叶子关键字:
- 向该节点要删除的关键字的左子树最大关键字或右子树最小关键字借。
- 题目已规定要向谁借，但借完不符合要求，但此时兄弟可借，直接借兄弟的
- 借完不和，兄也不可借，兄弟合并
14. B+树
14.1 B+树与B树的不同点
B+树是应文件系统所需而出的一种B-树的变型树。一棵m阶的B+树和m阶的B-树的差异在于：
非叶子结点的子树指针与关键字个数相同或者子树指针数=关键字个数+1；
非叶结点仅具有索引下一层作用，不存储数据的指针，跟记录有关的信息均存放在叶结点中。
非叶子结点的子树指针
P[i]，指向关键字值属于[K[i], K[i+1])的子树（B树是开区间）；为所有叶子结点增加一个链指针；树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。
所有关键字具体数据或者数据“地址”只存储在叶子结点。
注意：说到B+Tree的叶子节点，必须区分MySQL中的聚簇索引和非聚簇索引（二级索引），在聚簇索引的叶子节点存储的是完整的行数据，而二级索引叶子节点存储的是数据行指针,这里的行指针的实质是叶子节点保存只是行的主键值，因此非聚簇索引必须还要在聚簇索引结构上进行查找，这也是为什么它被称为二级索引
14.2 为什么B+树更适合做索引
我们先分析B+d与众不同的特点：
- 第一个就是B+树在B树的基础之上最重要的改进就是非叶子结点只存储关键字和下一层的索引，不存储Data域，只在叶子结点存储Data域；
- 第二点就是所有叶子结点增加一个链指针，使所有叶结点构成一个有序链表，因此当我们需要有序遍历所有关键字时，直接从最小关键字的叶子结点开始遍历即可。
14.2.1非叶子结点不存储Data域的好处
每一个结点可以存放更多的关键字和下一层的索引。数据库是存储在磁盘上的，我们读取数据是从磁盘读取到内存中，我们在进行磁盘预读取时，是以块的单位进行数据读取，我们在检索B/B+树的结点时，每次以块为单位将一个结点读取到内存中，若一块磁盘包含了树结点以外的数据，就造成了浪费，因此我们需要使每一个结点的数据大小正好或者接近一块磁盘的大小。于是我们在构建B+/B树时，树的阶数其实就取决于一块磁盘中能容纳多少个关键字以及相关的索引和Data域。B+树的非叶子结点不存储Data域，因此它可以存储更多个关键字和下一层索引，因此B+树会比B树更宽胖。若我需要查找的关键字正好在叶子结点，B+树所进行的I/O次数更少,因为途中经过每一层，我们都需要进行一次I/O读取一个结点，B+树会更矮，途径的层数会更少。
使得B+树查询速度更稳定，B+树所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
14.2.2所有叶结点构成一个有序链表的好处
B+树便于区间查找（这点才是B+树作为索引的关键），我们进行数据库查询大多为区间查询，B+树天然具备排序功能，B+树所有的叶子结点构成了一个有序链表，在查询大小区间的数据时候更方便，B+树查询，只需通过头结点往下找到第一个叶子结点，然后在叶子结点的链表上就行遍历即可完成区间查询，而B树的关键字大小相邻近的结点可能隔得很远，要想进行区间查询需要不停的进行中序遍历，相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。
B+树全结点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，而不需要像B树一样需要进行中序遍历，这有利于数据库做全表扫描。
总结B+树优点(选择B+树作为索引的原因)
- 因为没有非叶子节点没有存储数据，因此单一非叶子结点能存储更多的关键字索引
- 所有查询都要查找到叶子节点，查询性能稳定；
- 所有叶子节点形成有序链表，便于范围查询以及全结点遍历更快。
