猹猹查叉叉『查找专题』

先来求跳表的索引高度。
如下图所示，假设每两个结点会抽出一个结点作为上一级索引的结点。
原始链表有 n 个元素，则一级索引有 n/2 个元素，二级索引有 n/4 个元素，k级索引就有 n/(2^k) 个元素，其中最高级索引一般有 2 个元素，即：最高级索引 h 满足 2 = n/(2^h)。
因此 h = log2n - 1 ，最高级索引 h 为索引层的高度再加上原始数据的那一层
最后得到：跳表的总高度为 h = log2n。

学新通

上图中加粗的箭头，表示查找元素 x 的路径，那查找过程中每一层索引最多遍历几个元素呢？

图中所示，现在到达第 k 级索引，我们发现要查找的元素 x 比 y 大比 z 小。
所以，我们需要从 y 处下降到 k-1 级索引继续查找，k-1级索引中比 y 大比 z 小的只有一个 w。
所以在 k-1 级索引中，我们遍历的元素最多就是 y、w、z。
发现 x 比 w大比 z 小之后，再下降到 k-2 级索引。
所以，k-2 级索引最多遍历的元素为 w、u、z。

其实每级索引都是类似的道理：每级索引中都是两个结点抽出一个结点作为上一级索引的结点。

结论：当每级索引都是两个结点抽出一个作为下一级索引的结点时，每层最多遍历 3 个结点。

跳表的索引高度 h = log2n，且每层索引最多遍历 3 个元素。
所以跳表中查找一个元素的时间复杂度为 O(3*logn)，省略常数即：O(logn)。

3.空间复杂度

跳表通过建立索引，来提高查找元素的效率，就是典型的“空间换时间”的思想，所以在空间上做了一些牺牲，那空间复杂度到底是多少呢？

原始链表有 n 个元素，则一级索引有 n/2 个元素，二级索引有 n/4 个元素，k级索引就有 n/(2^k) 个元素，以此类推。
所以索引节点的总和是：n/2 n/4 n/8 … 8 4 2 = n-2 ，空间复杂度是 O(n)。

如下图所示：如果每三个结点抽一个结点做为索引，索引总和数就是 n/3 n/9 n/27 … 9 3 1= n/2，减少了一半。

学新通

所以我们可以通过减少每一层的索引数来减少空间复杂度，但是相应的会造成查找效率有下降。
我们可以根据我们的应用场景来控制这个阈值，看我们更注重时间还是空间。

However，索引结点往往只需要存储 key 和几个指针，并不需要存储完整的对象！！！
所以当对象比索引结点大很多时，索引占用的额外空间就可以忽略了。

举个例子：我们现在需要用跳表来给所有学生建索引。
学生有很多属性：学号、姓名、性别、身份证号、年龄、家庭住址、身高、体重等。
学生的各种属性只需要在原始链表中存储一份即可，只需要用学生的学号（唯一标识的关键字）建立索引，所以索引相对原始数据而言，占用的空间可以忽略。

4.插入数据元素

跳表的原始链表需要保持有序，所以我们会像查找元素一样，找到元素应该插入的位置。

如下图所示，要插入数据6，整个过程类似于查找6，整个的查找路径为： 1、1、1、4、4、5。
查找到 第底层原始链表 的元素 5 时，发现 5 小于 6 但是后继节点 7 大于 6，
所以应该把 6 插入到 5 之后 7 之前。

整个时间复杂度为查找元素的时间复杂度 O(logn)。

学新通

如下图所示，假如一直往原始列表中添加数据，但是不更新索引，就可能出现两个索引节点之间数据非常多的情况。极端情况下，跳表会退化为单链表，使得查找效率从 O(logn) 退化为 O(n)。

学新通

Q：这种问题该怎么解决呢？

A：在插入数据的时候，索引节点也要相应地增加或者是需要重建索引，来避免查找效率的退化。

Q：那我们该如何去维护这个索引呢？

A1：比较容易理解的做法就是完全重建索引：

我们每次插入数据后，都把这个跳表的索引删掉全部重建。
因为索引的空间复杂度是 O(n)，即索引节点的个数是 O(n) 级别，每次完全重建索引的时间复杂度也是 O(n) 。这样造成的后果是：为了维护索引，导致每次插入数据的时间复杂度变成了 O(n)。

Q：那有没有其他效率比较高的方式来维护索引呢？

A：假如跳表每一层的晋升概率是 1/2，最理想的索引就是在原始链表中每隔一个元素抽取一个元素做为一级索引。换种说法，我们在原始链表中随机的选 n/2 个元素做为一级索引是不是也能通过索引提高查找的效率呢？——当然可以！！！因为一般随机选的元素相对来说都是比较均匀的。

如下图所示，随机选择了n/2 个元素做为一级索引

虽然不是每隔一个元素抽取一个，但是对于查找效率来讲，影响不大。
比如我们想找元素 16，仍然可以通过一级索引，使得遍历路径较少了将近一半。

学新通

如果抽取的一级索引的元素恰好是前一半的元素 1、3、4、5、7、8，那么查找效率确实没有提升，但是这样的概率太小了。

我们可以认为：当原始链表中元素数量足够大，且抽取足够随机的话，我们得到的索引是均匀的。

我们要清楚设计良好的数据结构都是为了应对巨大数据量的场景。

所以，我们可以维护一个这样的索引：随机选 n/2 个元素做为一级索引、随机选 n/4 个元素做为二级索引、随机选 n/8 个元素做为三级索引，依次类推，一直到最顶层索引。

这里每层索引的元素个数已经确定，且每层索引元素选取的足够随机——所以可以通过索引来提升跳表的查找效率。

Q：代码该如何实现，才能使跳表满足上述这个样子呢？

A：可以在每次新插入元素的时候，尽量让该元素有 1/2 的几率建立一级索引、1/4 的几率建立二级索引、1/8 的几率建立三级索引，以此类推，就能满足我们上面的条件。

现在我们就需要一个概率算法帮我们把控这个 1/2、1/4、1/8 ... ，当每次有数据要插入时，先通过概率算法告诉我们这个元素需要插入到几级索引中，然后开始维护索引并把数据插入到原始链表中。

我们可以实现一个 Random_Level（）函数：
该函数会随机生成 1~MAX_LEVEL 之间的数（MAX_LEVEL 表示索引的最高层数）。
且该方法有 1/2 的概率返回 1、1/4 的概率返回 2、1/8的概率返回 3，以此类推。

Random_Level（）函数返回 1 ，表示当前插入的该元素不需要建索引，只需要存储数据到原始链表即可（概率 1/2）
Random_Level（）函数返回 2 ，表示当前插入的该元素需要建一级索引（概率 1/4）
Random_Level（）函数返回 3 ，表示当前插入的该元素需要建二级索引（概率 1/8）
Random_Level（）函数返回 4 ，表示当前插入的该元素需要建三级索引（概率 1/16）
......以此类推

所以，通过 Random_Level（）函数，我们可以控制整个跳表各级索引中元素的个数。

重点来了： Random_Level（）函数返回 2 的时候会建立一级索引。

我们想要一级索引中元素个数占原始数据的 1/2，但是 Random_Level（）函数返回 2 的概率为 1/4，那是不是有矛盾呢？明明说好的 1/2，结果一级索引元素个数怎么变成原始链表的 1/4 ？

我们先看下图，应该就明白了。

学新通

1.假设在插入元素 6 的时候， Random_Level（）函数返回 1，则不用为 6 建立索引。

2.插入 7 的时候， Random_Level（）函数返回 3 ，所以需要为元素 7 建立二级索引。

3.特点：
当建立二级索引的时候，同时会建立一级索引；
当建立三级索引时，同时会建立一级、二级索引。

4.所以一级索引的元素数 =【原始链表元素数】*【Random_Level（）函数返回 >1 的概率】

由于 Random_Level（）函数返回值 > 1 就会建索引。
而只要是需要建索引，无论是几级索引必然需要建立一级索引。
所以一级索引中元素个数占原始数据个数的比率为 Random_Level（）函数返回值 > 1 的概率。

因为 Random_Level（）函数随机生成 1~MAX_LEVEL 的数字，且 Random_Level（）函数返回值 1 的概率为 1/2，因此 Random_Level（）函数返回值 > 1 的概率为 1 - 1/2 = 1/2。

即通过上述流程实现了一级索引中元素个数占原始数据个数的 1/2。

同理，当 Random_Level（）函数返回值 > 2 时，会建立二级或二级以上索引。
这些都会在二级索引中增加元素。
因此二级索引中元素个数占原始数据的比率为 Random_Level（）函数返回值 > 2 的概率。

Random_Level（）函数返回值 > 2 的概率为 1 -（ Random_Level（）== 1 或 ==2 的概率），即 1 - 1/2 - 1/4 = 1/4。达到了我们设计的目标：二级索引中元素个数占原始数据的 1/4。

以此类推，可以得出以下两个措施：

Random_Level（）函数，随机生成 1~MAX_LEVEL 之间的数（MAX_LEVEL表示索引的最高层数），且有 1/2的概率返回 1、1/4的概率返回 2、1/8的概率返回 3 ......
Random_Level（）函数返回 1 时不建索引、返回 2 时建一级索引、返回 3 建二级索引、返回 4 建三级索引 ......

// 该 Random_Level 方法会随机生成 1~MAX_LEVEL 之间的数，且：
// 1/2 的概率返回 1
// 1/4 的概率返回 2
// 1/8 的概率返回 3 以此类推
int Random_Level(void)
{
int level = 1;
srand(time(NULL));
while(rand()<SKIPLIST_P && level < MAX_LEVEL)
level ;
// 当 level<MAX_LEVEL，且随机数小于设定的晋升概率时，level
return level;
}

晋升概率 SKIPLIST_P 设置为 1/2，即：每两个结点抽出一个结点作为上一级索引的结点。

如果我们想节省空间利用率，可以适当的降低代码中的 SKIPLIST_P，从而减少索引元素个数。

学新通

Redis 源码中 (random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF) 在功能上等价于我代码中的 Math.random() < SKIPLIST_P ，只不过 Redis 作者使用位运算来提高浮点数比较的效率。

那此时插入数据时维护索引的时间复杂度是多少呢？

元素插入到单链表的时间复杂度为 O(1)，我们索引的高度最多为 logn。
当插入一个元素 x 时，最坏的情况就是元素 x 需要插入到每层索引中。
所以插入数据到各层索引中，最坏时间复杂度是 O(logn)。

过程大概理解了，再通过一个例子描述一下跳表插入数据的全流程。

现在我们要插入数据 6 到跳表中，首先 Random_Level() 返回 3，需要建二级索引。
即：一级索引和二级索引需要增加元素 6。
跳表目前最高三级索引，首先找到三级索引的1，发现6比1大比13小，所以从1下沉到二级索引。

学新通

下沉到二级索引后，发现 6 比 1 大比 7 小。
此时需要在二级索引中 1 和 7 之间加一个元素6 ，并从元素 1 继续下沉到一级索引。

学新通

下沉到一级索引后，发现 6 比 1 大比 4 大，所以往后查找，发现 6 比 4 大比 7 小。
此时需要在一级索引中 4 和 7 之间加一个元素 6 ，并把二级索引的 6 指向一级索引的 6。
最后，从元素 4 继续下沉到原始链表。

学新通

下沉到原始链表后就比较简单了，发现 4、5 比 6小，7比6大，所以将6插入到 5 和 7 之间即可。

学新通

整个插入过程的路径与查找元素路径类似。
每层索引中插入元素的时间复杂度 O(1)，所以整个插入的时间复杂度是 O(logn)。

5.删除数据

跳表删除数据时，要把索引中对应节点也要删掉。

如下图所示，如果要删除元素 9，需要把原始链表中的 9 和第一级索引的 9 都删除掉。

学新通

跳表中，删除元素的时间复杂度是多少呢？

删除元素的过程跟查找元素的过程类似，只不过在查找的路径上如果发现了要删除的元素 x，则执行删除操作。

跳表中，每一层索引其实都是一个有序的单链表，单链表删除元素的时间复杂度为 O(1)，索引层数为 logn 表示最多需要删除 logn 个元素。

删除元素的总时间包含：查找元素的时间删除 logn个元素的时间。
即 O(logn) O(logn) = 2 O(logn)。
忽略常数部分，删除元素的时间复杂度为 O(logn)。

6.知识点总结

跳表是可以实现二分查找的有序链表；
每个元素插入时随机生成它的level；
最底层包含所有的元素；
如果一个元素出现在level(x)，那么它肯定出现在x以下的level中；
每个索引节点包含两个指针，一个向下，一个向右；（笔记目前看过的各种跳表源码实现包括Redis 的zset 都没有向下的指针，那怎么从二级索引跳到一级索引呢？留个悬念，看源码吧，文末有跳表实现源码）
跳表查询、插入、删除的时间复杂度为O(log n)，与平衡二叉树接近；

在插入、删除、查找一个元素和有序输出所有元素等方面，红黑树也可以完成，且时间复杂度跟跳表是一样的。
但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。
跳表可以做到 O(logn) 的时间复杂度，来定位区间的起点，然后在原始链表中顺序往后遍历就可以了，非常高效。

7.实现代码

#include <iostream>
#include <time.h>
#include <windows.h>
#define SKIP_LIST_P 0.5f
#define MAX_LEVEL 4
using namespace std;
void Print();
int main()
{
cout << "Hello world!" << endl;
return 0;
}
/**
* 跳表的一种实现方法。
* 跳表中存储的是正整数，并且存储的是不重复的。
*
*/
typedef struct Node //跳表结点的定义
{
int key; //关键字是唯一的
int value; //数据元素的存储内容
int max_level ; //当前结点的最大索引层数
struct Node *next[];
/**柔性数组,根据该节点层数的不同指向大小不同的数组
* next[0]：表示该节点的原始链表的下一节点的索引地址
* next[1]：表示该节点的第一层索引下一节点的索引地址
* next[2]：表示该节点的第二层索引下一节点的索引地址
*.......：以此类推
*/
//structNode *next; !!!这里就不要用next了,而是用索引的方式
} Node;
typedef struct Skip_List //跳表的定义
{
int level; //跳表的索引层数,0代表只有原始链表
int num; //节点的数目
Node *head; //带头结点的链表
} Skip_List;
int Random_Level(void);
Node *Create_Node(void);
Skip_List *Create_Skip_List(void);
int Insert(Skip_List *skip_list,int key,int value);
int Delete(Skip_List *skip_list,int key);
int Modify(Skip_List *skip_list,int key,int new_value);
int Search(Skip_List *skip_list,int key,int &ret);
int Destroy(Skip_List *skip_list);
Node *Create_Node(int level,int key,int value)//创建一个结点
{
Node *node = (Node*)malloc(sizeof(Node));
if(node==NULL)
exit(1);
node->key = key;
node->value = value;
node->max_level = level;
return node;
}
Skip_List *Create_Skip_List(void)
{
Skip_List *skip_list = (Skip_List*)malloc(sizeof(Skip_List));
if(skip_list==NULL)
exit(1);
skip_list->level = 1;
skip_list->num = 0;
skip_list->head = Create_Node(MAX_LEVEL,0,0);//虚拟头节点
return skip_list;
}
/** Random_Level 会随机生成 1~MAX_LEVEL 之间的数，且：
* 1/2 的概率返回 1
* 1/4 的概率返回 2
* 1/8 的概率返回 3
* 以此类推
*/
int Random_Level(Skip_List *skip_list)
{
int level = 1;
srand(time(NULL));
int max_level = skip_list->head->max_level;
for(int i = 1; i<max_level; i )
if(rand()%2==1) //这里是SKIP_LIST_P为0.5的情况
level ;
//如果需要SKIP_LIST_P为0.25,只需要把%2改为%4即可
/*另一种方法
while((rand()0)<SKIP_LIST_P*100 && level < max_level)
level ;
*/
return level;
}
int Insert(Skip_List *skip_list,int key,int value)
{
int max_level = skip_list->head->max_level;
Node **update = (Node**)malloc(sizeof(Node*)*max_level);
//用来更新每层的索引指针,存放插入位置的前驱各层节点索引,相当于二维数组的行指针
Node *cur = NULL;
Node *pre = NULL;
/*获取插入元素的随机层数,并更新跳表的最大层数*/
int level = Random_Level(skip_list);
/*创建当前节点*/
Node *new_node = Create_Node(level,key,value);
/** 逐层查询,查找插入位置的前驱各层节点索引
* update[0] 存放第一层的插入位置前驱节点
* update[0]->next[0]表示插入位置的前驱节点的下一节点(update[0]->next[0])的第一层索引值
* update[1] 存放第二层的插入位置前驱节点
* update[1]->next[1]表示插入位置的前驱节点的下一节点(update[1]->next[0])的第二层索引值
* update[n] 存放第一层的插入位置前驱节点
* update[n]->next[n]表示插入位置的前驱节点的下一节点(update[n]->next[0])的第n层索引值
*/
pre = skip_list->head; //从第一个结点开始的最顶层开始搜索
int i; //表示当前的所在层数
for(i = max_level-1; i>=0; i--)
{
/* 各层每个节点的下一个节点不为空 && 下个节点的key小于要插入的key */
while((cur = pre->next[i])!=NULL && (cur->key<key))
pre = cur; //向后移动
update[i] = pre;//各层要插入节点的前驱节点
}
/* 当前key已经存在,返回错误 */
if ((cur != NULL) && (cur->key == key))
{
return -3;
}
/*根据最大索引层数,更新插入节点的前驱节点,前面已经更新到了[0] - [(skip_list->level-1)]*/
if (level > skip_list->level)
{
for (i=skip_list->level; i<level; i )
{
update[i] = skip_list->head;/*这部分为多新增的索引层,所以前驱节点默认为头结点*/
}
skip_list->level = level;/*更新跳表的最大索引层数*/
}
/*逐层更新节点的指针*/
for (i=0; i<level; i )
{
new_node->next[i] = update[i]->next[i];
update[i]->next[i] = new_node;
}
/*节点数目加1*/
skip_list->num ;
return 0;
}
int Delete(Skip_List *skip_list,int key)
int Modify(Skip_List *skip_list,int key,int new_value);
int Search(Skip_List *skip_list,int key,int &ret);
int Destroy(Skip_List *skip_list);
Node *FindNode(Skip_List *table,int value)
{
Node *p = table->head;
for (int i=table->levelCount-1; i>=0; i--) //从后往前搜索
{
while (p->forwards[i].data!=0 && p->forwards[i].data<value)
{
p = p->forwards i;
}
}
if (p->forwards[0].data!=NULL && p->forwards[0].data==value)
return p->forwards;
else
return NULL;
}
void insert(Skip_List *table,int value)
{
int level = Random_Level();
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->max_level = level;
Node *update = (Node*)malloc(sizeof(Node)*level);
for (int i = 0; i < level; i)
{
&update[i] = skip_list->head;
}
// record every level largest value which smaller than insert value in update[]
Node p = head;
for (int i = level - 1; i >= 0; --i)
{
while (p.forwards[i] != null && p.forwards[i].data < value)
{
p = p.forwards[i];
}
update[i] = p;// use update save node in search path
}
// in search path node next node become new node forwords(next)
for (int i = 0; i < level; i)
{
newNode.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = newNode;
}
// update node hight
if (levelCount < level) levelCount = level;
}
void delete(int value)
{
Node[] update = new Node[levelCount];
Node p = head;
for (int i = levelCount - 1; i >= 0; --i)
{
while (p.forwards[i] != null && p.forwards[i].data < value)
{
p = p.forwards[i];
}
update[i] = p;
}
if (p.forwards[0] != null && p.forwards[0].data == value)
{
for (int i = levelCount - 1; i >= 0; --i)
{
if (update[i].forwards[i] != null && update[i].forwards[i].data == value)
{
update[i].forwards[i] = update[i].forwards[i].forwards[i];
}
}
}
while (levelCount>1&&head.forwards[levelCount]==null)
{
levelCount--;
}
}
// 理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。
// 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。
// 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且：
// 50%的概率返回 1
// 25%的概率返回 2
// 12.5%的概率返回 3 ...
int randomLevel()
{
int level = 1;
while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
level = 1;
return level;
}
void printAll()
{
Node p = head;
while (p.forwards[0] != null)
{
System.out.print(p.forwards[0] " ");
p = p.forwards[0];
}
System.out.println();
}

三.分块查找

【线性查找折半查找】

1.使用条件

（1）查找表要求顺序存储；
（2）查找表分成 n 块，当块序号 i > j 时，第 i 块中的最小元素大于第 j 块中的最大元素。
【核心内涵就是：交集为0，并集为全集U，也就是对全集U的一个划分】
（3）线性表：块内可无序、块大小可不一致(可以顺序存储和链式存储)

2.查找思想

（1）首先确定所要查找关键字在哪一块中；
（2）在所确定的块中用顺序查找查找关键字。
【分块查找的过程是一个“缩小区间”的过程】

typedef struct
{
DataType key; //关键值
int address; //分块的首地址【下标表示】
int length; //当前分块的长度
} IndexNode; //索引表的结点
typedef struct
{
IndexNode index[MAX_BLOCKS_NUM];//存放索引表结点的数组
int block_num; //索引表中结点的数目,也就是分块数目
int Blocks_Prefix_Sum[MAX_BLOCKS_NUM];//前缀和,也即是块的右侧和左侧边界下标
} IndexTable; //索引表
void Prefix_Sum(IndexTable s)
{
memset(s.Blocks_Prefix_Sum,0,sizeof(int)*MAX_BLOCKS_NUM);
//第一个是0,一共会有n-1个内部边界点,最后一个是右边界点
for(int i=1; i<=s.block_num; i )
s.Blocks_Prefix_Sum[i] = s.Blocks_Prefix_Sum[i-1] s.index[i].length;
}
int Index_Block_Search(IndexTable s,DataType target)
{
int i = 0;
int j = 0;
while(s.index[i].key<target && i<s.block_num)
i ;//找到在哪一个块中搜索
if(i<s.block_num)
{
j = s.Blocks_Prefix_Sum[i];
int UpperLimit = s.Blocks_Prefix_Sum[i 1];
while(j<=UpperLimit)
{
if(s.index[j].key==target)
return j;
j ;
}
}
return -1;
}

四.二叉查找树【二叉排序树】

1.基本概念

二叉排序树要么是一棵空树，要么满足如下性质：

1. 对于每个结点，如果其左子树非空，则左子树的所有结点的关键值都小于该(根)结点的关键值； 2.如果其右子树非空，则右子树的所有结点的关键值都大于该(根) 结点的关键值。
3.左、右子树本身又是一棵二叉排序树。

简单地讲：左子树结点值 < 根结点值 < 右子树结点值【递归定义的数据结构】

二叉排序树的优点：

◆用二叉排序树作为目录树，把一个记录的关键码和记录的地址作为二叉排序树的结点，按关键码值建成二叉排序树。
◆能像有序表那样进行高效查找；
◆能像链表那样灵活插入、删除。

算法分析：平均查找长度 ASL = O(log2n) ~ O(n) ！！！

如何来保证平均查找长度是O(log2n)呢？ —— 平衡二叉树。

2.代码实现

1.结构定义

typedef struct BST_Node
{
DataType data;
struct BST_Node *left;
struct BST_Node *right;
} BST_Node;
BST_Node *Create_BST_Node(int data)
{
BST_Node *node = (BST_Node*)malloc(sizeof(BST_Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}

2.创建结点

BST_Node *Create_BST_Node(int data)
{
BST_Node *node = (BST_Node*)malloc(sizeof(BST_Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}

3.插入结点

从根节点开始，遇键值较大者就向左，遇键值较小者就向右，一直到末端，就是插入点。

学新通

void Insert(BST_Node *&root,DataType data)
{
BST_Node *new_node = Create_BST_Node(data);
if(root==NULL)
{
root = new_node;
return;
}
if(Search(root,data))
{
cout<<"结点已经存在！"<<endl;
return;
}
BST_Node *parent,*p;
parent = NULL;
p = root;
while(p)//插入的时候一定是作为叶子节点插入的！！！
{
parent = p;
if(data < root->data)
p = p->left;
else
p = p->right;
}
if(data < parent->data)
parent->left = new_node;
else
parent->right = new_node;
}

4.删除结点

学新通

分为三种情况：

1.叶子节点直接删除即可。

2.如果A只有一个子节点，就直接将A的子节点连至A的父节点上，并将A删除。

学新通

3.如果A有两个子节点，就以右子树中的最小节点【也就是所有比A大的数中的最小值】取代A。

【因为：左<根<右，这里要找一个新的根，满足大于左子树所有结点，且小于右子树所有结点】

学新通

4.A是根节点，则将A的右孩子直接作为根节点。

当我们删除的节点是根节点时，需要先根据其parent来确认一下将要删除的节点是否时根节点。
如果它是根节点，那么它的parent将是null。
当树中只有一个节点的时候，也就是根节点就是叶子节点的时候，仅需要将root置为null即可；
如果当前根节点只有一个子树，我们将其子树的根节点赋予给root即可(root是当前结构内的根指针，是管理类中的字段)；
而根节点有两个节点的时候，使用以上算法并没有什么影响，因为根字段的指向并没有变化，变化的是值，而被删除的节点时另外的节点，即右子树中值最小的节点，或者左子树中值最大的节点。

a.递归版本

bool Delete(BST_Node *&root, DataType data)//递归版本
{
BST_Node *p = root;
BST_Node *parent = NULL;
if(p==NULL)
return false;
if(p->data == data) //找到要删除的节点了
{
//叶子结点
if (!p->right && !p->left)
root = NULL;
// 只有一个左节点
else if (!p->right&&p->left)
root = p->left;
// 只有一个右节点
else if (!p->left&&p->right)
root = p->right;
//左右节点都不空
else
{
BST_Node *s = NULL;
s = p->right;
//没有左孩子
if (!s->left)
s->left = p->left;
//有左孩子
else
{
while (s->left)//找到右子树中的最小结点
{
parent = s; //记录双亲结点
s = s->left;
}
parent->left = s->right;
s->left = p->left;
s->right = p->right;
}
root = s;
}
free(p);
cout<<"删除成功！"<<endl;
return true;
}
else if(data > p->data) //向右找
return Delete(p->right, data);
else //向左找
return Delete(p->left, data);
}

b.非递归版本

void Delete_Pro(BST_Node *&root,DataType data)//非递归版本
{
if(root==NULL)
{
cout<<"树为空,无法进行删除操作！"<<endl;
return;
}
BST_Node *p = root;
BST_Node *parent = NULL;
if(p->data==data)//要删除的点为根节点
{
if(p->left==NULL && p->right==NULL)//只有根节点
root = NULL;
else if(p->left && p->right)//根节点左右子树都有
{
BST_Node *right_min_node = p->right;//找到的肯定是一个没有左子树的结点
BST_Node *right_min_node_parent = p;//而且该节点肯定是其双亲结点的左孩子
while(right_min_node->left)//找到了p的右子树中的最小结点
{
right_min_node_parent = right_min_node;
right_min_node = right_min_node->left;
}
right_min_node_parent->left = right_min_node->right;
//因为结点没有左孩子,有没有右孩子都可以这么操作
right_min_node->left = p->left;//该节点要继承p的左右子树
right_min_node->right = p->right;
//其实这里直接把值换掉就好了
}
else //只有左子树或者只有右子树
root = p->left ? p->left : p->right;
free(p);
p = NULL;
return;
}
while(p)
{
if(p->data==data)//找到要删除的结点了
{
if(p->left==NULL && p->right==NULL)//是叶子结点
{
if(parent->left == p)
parent->left = NULL;
else
parent->right = NULL;
}
else if(p->left!=NULL && p->right==NULL)//只有一个左节点
{
if(parent->left == p)
parent->left = p->left;
else
parent->right = p->left;
}
else if(p->left==NULL && p->right!=NULL)//只有一个右节点
{
if(parent->left == p)
parent->left = p->right;
else
parent->right = p->right;
}
else//左右节点都不为空
{
BST_Node *right_min_node = p->right;//找到的肯定是一个没有左子树的结点
BST_Node *right_min_node_parent = p;//而且该节点肯定是其双亲结点的左孩子
while(right_min_node->left)//找到了p的右子树中的最小结点
{
right_min_node_parent = right_min_node;
right_min_node = right_min_node->left;
}
right_min_node_parent->left = right_min_node->right;//因为结点没有左孩子,有没有右孩子都可以这么操作
right_min_node->left = p->left;//该节点要继承p的左右子树
right_min_node->right = p->right;
//其实这里直接把值换掉就好了
if(parent->left == p)
parent->left = right_min_node;
else
parent->right = right_min_node;
}
free(p);
p = NULL;
return;
}
else if(data < p->data)
{
parent = p;
p = p->left;
}
else
{
parent = p;
p = p->right;
}
}
cout<<"没有找到该节点！"<<endl;
}

5.创建二叉搜索树

BST_Node *Create_BST(void)
{
cout<<"请输入结点的个数："<<endl;
int num;
cin>>num;
cout<<"请输入结点的数值："<<endl;
BST_Node *root = NULL;
for(int i=0; i<num; i )
{
int temp;
cin>>temp;
Insert(root,temp);
}
return root;
}

6.遍历二叉搜索树

这里只用中序遍历即可，由于【左<根<右】的性质，中序序列是一个升序的序列。

void Print_BST(BST_Node *root)
{
if(root==NULL)
return;
if(root->left)
Print_BST(root->left);
cout<<root->data<<"-->";
if(root->right)
Print_BST(root->right);
}

7.查找元素

a.按值查找

BST_Node *Search(BST_Node *root,DataType target)
{
if(root==NULL)
return NULL;
if(target==root->data)
{
cout<<"查找成功！"<<endl;
return root;
}
if(target<root->data)
return Search(root->left,target);
else
return Search(root->right,target);
}
BST_Node *Search_Pro(BST_Node *root,DataType target)
{
BST_Node *p = root;
while(p)
{
if(p->data==target)
break;
if(target<root->data)
p = p->left;
else
p = p->right;
}
return p;
}

b.找最大值

BST_Node *Search_Max(BST_Node *root)
{
if(root==NULL)
return NULL;
if(root->right)
return Search_Min(root->right);
return root;
}

c.找最小值

BST_Node *Search_Min(BST_Node *root)
{
if(root==NULL)
return NULL;
if(root->left)
return Search_Min(root->left);
return root;
}

8.可运行总代码

#include <iostream>
#include <queue>
#include <memory.h>
#include <algorithm>
#define DataType int
using namespace std;
typedef struct BST_Node
{
DataType data;
struct BST_Node *left;
struct BST_Node *right;
} BST_Node;
BST_Node *Create_BST_Node(int data);
BST_Node *Create_BST(void);
void Insert(BST_Node *&root,DataType data);
bool Delete(BST_Node *&root,DataType data);
BST_Node *Search(BST_Node *root,DataType target);
BST_Node *Create_BST_Node(int data)
{
BST_Node *node = (BST_Node*)malloc(sizeof(BST_Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
void Insert(BST_Node *&root,DataType data)
{
BST_Node *new_node = Create_BST_Node(data);
if(root==NULL)
{
root = new_node;
return;
}
if(Search(root,data))
{
cout<<"结点已经存在！"<<endl;
return;
}
BST_Node *parent,*p;
parent = NULL;
p = root;
while(p)//插入的时候一定是作为叶子节点插入的！！！
{
parent = p;
if(data < root->data)
p = p->left;
else
p = p->right;
}
if(data < parent->data)
parent->left = new_node;
else
parent->right = new_node;
}
BST_Node *Create_BST(void)
{
cout<<"请输入结点的个数："<<endl;
int num;
cin>>num;
cout<<"请输入结点的数值："<<endl;
BST_Node *root = NULL;
for(int i=0; i<num; i )
{
int temp;
cin>>temp;
Insert(root,temp);
}
return root;
}
bool Delete(BST_Node *&root, DataType data)//递归版本
{
BST_Node *p = root;
BST_Node *parent = NULL;
if(p==NULL)
return false;
if(p->data == data) //找到要删除的节点了
{
//叶子结点
if (!p->right && !p->left)
root = NULL;
// 只有一个左节点
else if (!p->right&&p->left)
root = p->left;
// 只有一个右节点
else if (!p->left&&p->right)
root = p->right;
//左右节点都不空
else
{
BST_Node *s = NULL;
s = p->right;
//没有左孩子
if (!s->left)
s->left = p->left;
//有左孩子
else
{
while (s->left)//找到右子树中的最小结点
{
parent = s; //记录双亲结点
s = s->left;
}
parent->left = s->right;
s->left = p->left;
s->right = p->right;
}
root = s;
}
free(p);
cout<<"删除成功！"<<endl;
return true;
}
else if(data > p->data) //向右找
return Delete(p->right, data);
else //向左找
return Delete(p->left, data);
}
void Delete_Pro(BST_Node *&root,DataType data)//非递归版本
{
if(root==NULL)
{
cout<<"树为空,无法进行删除操作！"<<endl;
return;
}
BST_Node *p = root;
BST_Node *parent = NULL;
if(p->data==data)//要删除的点为根节点
{
if(p->left==NULL && p->right==NULL)//只有根节点
root = NULL;
else if(p->left && p->right)//根节点左右子树都有
{
BST_Node *right_min_node = p->right;//找到的肯定是一个没有左子树的结点
BST_Node *right_min_node_parent = p;//而且该节点肯定是其双亲结点的左孩子
while(right_min_node->left)//找到了p的右子树中的最小结点
{
right_min_node_parent = right_min_node;
right_min_node = right_min_node->left;
}
right_min_node_parent->left = right_min_node->right;
//因为结点没有左孩子,有没有右孩子都可以这么操作
right_min_node->left = p->left;//该节点要继承p的左右子树
right_min_node->right = p->right;
//其实这里直接把值换掉就好了
}
else //只有左子树或者只有右子树
root = p->left ? p->left : p->right;
free(p);
p = NULL;
return;
}
while(p)
{
if(p->data==data)//找到要删除的结点了
{
if(p->left==NULL && p->right==NULL)//是叶子结点
{
if(parent->left == p)
parent->left = NULL;
else
parent->right = NULL;
}
else if(p->left!=NULL && p->right==NULL)//只有一个左节点
{
if(parent->left == p)
parent->left = p->left;
else
parent->right = p->left;
}
else if(p->left==NULL && p->right!=NULL)//只有一个右节点
{
if(parent->left == p)
parent->left = p->right;
else
parent->right = p->right;
}
else//左右节点都不为空
{
BST_Node *right_min_node = p->right;//找到的肯定是一个没有左子树的结点
BST_Node *right_min_node_parent = p;//而且该节点肯定是其双亲结点的左孩子
while(right_min_node->left)//找到了p的右子树中的最小结点
{
right_min_node_parent = right_min_node;
right_min_node = right_min_node->left;
}
right_min_node_parent->left = right_min_node->right;//因为结点没有左孩子,有没有右孩子都可以这么操作
right_min_node->left = p->left;//该节点要继承p的左右子树
right_min_node->right = p->right;
//其实这里直接把值换掉就好了
if(parent->left == p)
parent->left = right_min_node;
else
parent->right = right_min_node;
}
free(p);
p = NULL;
return;
}
else if(data < p->data)
{
parent = p;
p = p->left;
}
else
{
parent = p;
p = p->right;
}
}
cout<<"没有找到该节点！"<<endl;
}
void Print_BST_Unit(BST_Node *root)
{
if(root==NULL)
return;
if(root->left)
Print_BST_Unit(root->left);
cout<<root->data<<"-->";
if(root->right)
Print_BST_Unit(root->right);
}
void Print_BST(BST_Node *root)
{
if(root==NULL)
{
cout<<"Empty Tree！"<<endl;
return;
}
Print_BST_Unit(root);
cout<<"NULL"<<endl;
}
BST_Node *Search_Min(BST_Node *root)
{
if(root==NULL)
return NULL;
if(root->left)
return Search_Min(root->left);
return root;
}
BST_Node *Search_Max(BST_Node *root)
{
if(root==NULL)
return NULL;
if(root->right)
return Search_Min(root->right);
return root;
}
BST_Node *Search(BST_Node *root,DataType target)
{
if(root==NULL)
return NULL;
if(target==root->data)
{
cout<<"查找成功！"<<endl;
return root;
}
if(target<root->data)
return Search(root->left,target);
else
return Search(root->right,target);
}
BST_Node *Search_Pro(BST_Node *root,DataType target)
{
BST_Node *p = root;
while(p)
{
if(p->data==target)
break;
if(target<root->data)
p = p->left;
else
p = p->right;
}
return p;
}
int main()
{
BST_Node *root = Create_BST();
Print_BST(root);
int cnt = 0;
while(cnt!=5)
{
cout<<"请输入要查询的元素："<<endl;
int temp;
cin>>temp;
if(Search(root,temp)==NULL)
cout<<"查找失败"<<endl;
cnt ;
}
cnt = 0;
while(cnt!=5)
{
cout<<"请输入要删除的元素："<<endl;
int temp;
cin>>temp;
if(!Delete(root,temp))
cout<<"未找到该元素"<<endl;
Print_BST(root);
cnt ;
}
return 0;
}

9.关于二叉排序树的习题

参见鼠鼠数树树

五.平衡二叉树（AVL）

1.基本概念

1.结构定义

可以是一棵空二叉树；
且左子树和右子树高度之差的绝对值不超过1；
其左子树和右子树都是高度平衡的二叉树。

2.平衡因子

结点的平衡因子 BF (Banlanced Factor) 定义为：结点左子树 - 右子树的高度。

【AVL中的任意结点的 BF 只可能是 -1、0、 1】

【含义分别是：左子树比右子树矮、左子树与右子树等高、左子树比右子树高】

3.最小不平衡子树

下图，新插入节点37，该树不再是平衡二叉树。因为此时节点58的左右子树高度差为2。

学新通

最小不平衡子树：从新插入节点向上查找，第一个 abs（BF）> 1 的节点为根的子树。

新插入节点向上查找，节点58左右子树高度差为2，以58为根节点的子树就是最小不平衡子树。

特别注意：
新插入节点，可能导致平衡二叉树出现多棵不平衡的子树。
此时，我们只需要调整最小不平衡子树，就能让整棵树平衡 。

学新通

——————————————————————————————-————————————

3.左旋【RR】

将根节点绕右儿子逆时针下压。

前提条件：【RR】（插入的结点 == 最小不平衡二叉树根节点的右孩子的右子树）

【右右：需要向左移动】

左旋的操作：

根节点成为右孩子的左孩子。【逆时针】
右孩子原本的左子树成为根节点的右子树。【位置不变】

学新通

假设失衡节点为节点 former_root ，先暂存节点 former_root 的右孩子为节点 new_root ；
将 new_root 的左孩子节点放置到 former_root 的右孩子处；
令节点 new_root 的左孩子为节点 former_root ；
更新节点 former_root 的高度；
更新节点 new_root 的高度。

——————————————————————————————-————————————

4.右旋【LL】

将根节点绕左儿子顺时针下压。

前提条件：【LL】（插入的结点 == 最小不平衡二叉树根节点的左孩子的左子树）

【左左：需要向右移动】

右旋的操作：

根节点成为左子节点的右子树。【顺时针】
左子节点原本的右子树成为根节点的左子树【位置不变】

学新通

假设失衡节点为节点 former_root ，先暂存节点 former_root 的左孩子为节点 new_root ；
将 new_root 的右孩子节点放置到 former_root 的左孩子处；
令节点 new_root 的右孩子为节点 former_root ；
更新节点 former_root 的高度；
更新节点 new_root 的高度。

——————————————————————————————-————————————

5.先右后左【RL】

以右孩子为根节点进行右旋，再按原始的根节点左旋。

前提条件：【RL】（插入的结点 == 最小不平衡二叉树根节点的右孩子的左子树）

【右左：那就先右后左】

学新通

【图画错了】

假设失衡节点为节点 former_root ，先对节点 former_root 的右孩子进行【RR】型旋转；
令节点 former_root 的右孩子为步骤 1 中调整后的根节点；
对节点 former_root 进行【LL】型旋转。

——————————————————————————————-————————————

6.先左后右【LR】

以左儿子为根节点进行左旋，再按原始的根节点右旋。

前提条件：【LR】（插入的结点 == 最小不平衡二叉树根节点的左孩子的右子树）

【左右：那就先左后右】

假设失衡节点为节点 former_root ，先对节点 former_root 的左孩子进行【RR】型旋转；
令节点 former_root 的左孩子为步骤 1 中调整后的根节点；
对节点 former_root 进行【LL】型旋转。

学新通

2.代码实现

1.数据结构

typedef struct AVL_Node
{
int data; //节点保存的数据值
int height; //节点当前的高度
int key; //节点的键值（关键字）
AVL_Node *parent; //指向双亲节点
AVL_Node *left; //指向左孩子
AVL_Node *right; //指向右孩子
} AVL_Node;
typedef struct AVL_Tree
{
int NodeNum;
AVL_Node *root;
} AVL_Tree;

2.计算高度

【高度：从叶子节点高度为 1 开始计算；深度：从根节点深度为 1 开始计算】

利用递归算法来计算

int Height(AVL_Node *root)
{
if(root==NULL)
return 0;
if(root->left!=NULL && root->right==NULL)
return Height(root->left) 1;
else if(root->left==NULL && root->right!=NULL)
return Height(root->right) 1;
else
return max(Height(root->left),Height(root->right)) 1;
}
___________________________________________________________________________________________
int Height(AVL_Node *root)
{
if(root==NULL)
return 0;
if(root->left==NULL && root->right==NULL)
return 1;
return max(Height(root->left),Height(root->right)) 1;
}

3.旋转操作

a.RR要左旋

AVL_Node *AVL_RR_Pro(AVL_Node *former_root)//失衡节点为former_root
{
AVL_Node *new_root = former_root->right;//将失衡节点former_root的右孩子暂时保存为new_root
// 左旋，右儿子成为新的根节点
//这个必须先更新！！！
// 右儿子的左子树成为根节点的右子树
former_root->right = new_root->left; //令former_root的右孩子设置为new_root的左孩子
if(new_root->left)
new_root->left->parent = former_root;
new_root->parent = former_root->parent; //继承旧根节点的双亲节点
new_root->left = former_root; //令新根节点的左孩子为former_root
// 根节点成为右儿子的左子树
former_root->parent = new_root; //更新旧根节点的双亲节点
former_root->height = Height(former_root);//这里顺序不能颠倒
new_root->height = Height(new_root);
return new_root; //返回新的根节点
}
___________________________________________________________________________________________
AVL_Node *AVL_RR(AVL_Node *former_root)
{
AVL_Node *new_root = former_root->right;
former_root->right = new_root->left;
new_root->left = former_root;
former_root->height = Height(former_root);//这里顺序不能颠倒
new_root->height = Height(new_root);
return new_root;
}

b.LL要右旋

AVL_Node *AVL_LL_Pro(AVL_Node *former_root)//失衡节点为former_root
{
AVL_Node *new_root = former_root->left;//将失衡节点former_root的左孩子暂时保存为new_root
// 右旋，左儿子成为新的根节点
//这个必须先更新！！！
//左儿子的右子树为根节点的左子树
former_root->left = new_root->right; //令former_root的左孩子为new_root的右孩子
if(new_root->right)
new_root->right->parent = former_root;
new_root->parent = former_root->parent; //继承旧根节点的双亲节点
new_root->right = former_root; //令新根节点的右孩子为former_root
// 根节点成为左儿子的右子树
former_root->parent = new_root; //更新旧根节点的双亲节点
former_root->height = Height(former_root);//这里顺序不能颠倒
new_root->height = Height(new_root);
return new_root; //返回新的根节点
}
___________________________________________________________________________________________
AVL_Node *AVL_LL(AVL_Node *former_root)
{
AVL_Node *new_root = former_root->left;
former_root->left = new_root->right;
new_root->right = former_root;
former_root->height = Height(former_root);//这里顺序不能颠倒
new_root->height = Height(new_root);
return new_root;
}

c.RL先右后左

AVL_Node *AVL_RL(AVL_Node *root)
{
root->right = AVL_LL(root->right);//右旋右儿子【右旋是LL】
return root = AVL_RR(root); //左旋根节点【左旋是RR】
}

d.LR先左后右

AVL_Node *AVL_LR(AVL_Node *root)
{
root->left = AVL_RR(root->left);//左旋左儿子【左旋是RR】
return root = AVL_LL(root); //右旋根节点【右旋是LL】
}

4.插入操作

1.插入节点时，与二叉搜索树的插入一样，需要先根据大小关系确定插入位置。

2.完成插入后，如果导致当前树不平衡，需要旋转使其平衡
（1）从左儿子插入的，有L L、LR两种情况。
（2）从右儿子插入的，有RR、RL两种情况。

3.不管是否调整了平衡因子，都需要更新根节点的高度

AVL_Node *Insert(AVL_Node *&root,int val)
{
if(root==NULL)
root = Create_AVL_Node(val);//最后肯定是作为叶子节点插入的
else if(val < root->data) //小的插在左子树中(统一用" <" !!!)
{
root->left = Insert(root->left,val);
root->height = Height(root);//插入完成后要更新高度
//如果插入后不平衡了,就需要调整
if(Height(root->left) - Height(root->right) == 2)//不平衡的情况肯定是左大于右
{
//这里第一步插在了左子树中
if(val < root->left->data) //在左子树的左子树中
root = AVL_LL(root); //进行右旋调整
else //在左子树的右子树中
root = AVL_LR(root); //先左后右
}
}
else if(root->data < val) //大的插在右子树中
{
root->right = Insert(root->right,val);
root->height = Height(root);//插入完成后要更新高度
if(Height(root->right) - Height(root->left) == 2)//不平衡的情况肯定是右大于左
{
//这里第一步插在了右子树中
if(root->right->data < val) //在右子树的右子树中
root = AVL_RR(root); //进行左旋调整
else //在右子树的左子树中
root = AVL_RL(root); //先右后左
}
}
else
{
cout<<"插入了重复的数值！！！"<<endl;
}
return root;
}

5.删除操作

删除节点比插入节点的操作还要稍微复杂一点。
因为插入时，进行一次平衡处理【一次平衡处理可能包含多次旋转】，整棵树都会处于平衡状态。而在删除时，需要进行多次平衡处理，才能保证树处于平衡状态。

◼ 删除操作与插入操作是对称的（镜像），但可能需要的平衡化次数多。

◼ 因为平衡化不会增加子树的高度，但可能会减少子树的高。

◼ 在有可能使树增高的插入操作中，一次平衡化能抵消掉树增高。

◼ 而在有可能使树减低的删除操作中，平衡化可能会带来祖先结点的不平衡。

AVL树的删除操作前半部分和二叉查找树相同。

删除二叉搜索树中的节点:

（1）被删除节点是叶子节点，直接删除
（2）被删除节点有右子树，将后继节点上提，再递归删除后继节点
（3）被删除节点只有左子树，将前驱节点上提，在递归删除前驱节点

删除后要检查树是否失去平衡，如果失衡就需要重新调整平衡，并更新节点高度。

可以分为如下几种情况：

学新通

1.删除叶子节点

情况一：删除节点后二叉树没有失去平衡

学新通

删除节点后树没有失去平衡，这种情况下只需要更新节点的高度.

情况二：删除节点后二叉树失去平衡

学新通

RE型失衡只有在删除操作时才可能出现（在插入时不可能出现）。
RE型失衡的旋转方式和RR型失衡【右旋】的旋转方式一模一样。

【虽然删除节点时的失衡情况多了 LE 和 RE ，但是旋转的方式依旧是（LL、RR、LR、RL）】

2.删除带有一个子节点的节点

学新通

3.删除带有两个子节点的节点

删除带有两个子节点的节点时，需要找到待删除的节点的后继节点或者前驱节点。

需要注意的是，删除节点时不会出现“后继节点不是删除节点的子节点，且后继节点有右子树”这种情况，如下图

学新通

上图的14节点已经失衡了，在插入的时候就会被调整，所以不会出现“后继节点不是删除节点的子节点，且后继节点有右子树”这种情况

a.实现一

AVL_Node *Remove(AVL_Node *&root, int val)
{
if(root == NULL)//二叉搜索树中：搜到底了还没有就是没有了
{
cout<<"没有此节点【"<<val<<"】删除失败！！！"<<endl;
cout<<endl;
return NULL;
}
if(root->data > val)//在左子树进行节点删除
root->left = Remove(root->left, val);
else if(root->data < val)
root->right = Remove(root->right, val);
else//找到了对应的节点，按情况删除
{
/**1.为叶子节点*/
if (root->left == NULL && root->right == NULL)
root = NULL;
/**2.只有右子树*/
else if (root->right != NULL)
{
AVL_Node *successor = Successor(root);
root->data = successor->data;//后继节点上提
//在右子树中删除后继节点
root->right = Remove(root->right, successor->data);
}
/**3.只有左子树或者左右子树都有*/ //Q：为什么这里可以合并
else
{
AVL_Node * preSuccessor = PreSuccessor(root);
root->data = preSuccessor->data;//前驱节点上提
//在左子树中删除前驱节点
root->left = Remove(root->left, preSuccessor->data);
}
}
//删除完成后可能需要调整平衡度
if(root == NULL)
return NULL;//这个是删除完后看root是否为空了
//左子树比右子树高,说明删除的是右子树的节点
if (Height(root->left) - Height(root->right) >= 2)
{
// 模拟在左子树插入的情况：在左儿子的左子树插入 or 在左儿子的右子树插入
if (Height(root->left->left) > Height(root->left->right))
return AVL_LL(root);//左左：右旋
else
return AVL_LR(root);//左右：先左后右
}
//在左子树删除节点
else if (Height(root->right) - Height(root->left) >= 2)
{
// 模拟在右子树插入节点
if (Height(root->right->right) > Height(root->right->left))
return AVL_RR(root);//右右：左旋
else
return AVL_RL(root);//右左：先右后左
}
//else 无需调整
root->height = Height(root);
return root; //更新root的高度并返回
}
AVL_Node *PreSuccessor(AVL_Node *root)// 寻找前驱节点
{
if (root==NULL)
return NULL;
root = root->left;//在左子树寻找最右节点
while (root->right)
root = root->right;
return root;
}
AVL_Node *Successor(AVL_Node *root)// 寻找后继节点
{
if(root==NULL)
return NULL;
root = root->right;//在右子树寻找最左节点
while(root->left)
root = root->left;
return root;
}

b.实现二

AVL_Node *Delete(AVL_Node *&root,int val)
{
AVL_Node *Successor_Node = NULL; //后继节点
AVL_Node *parent = NULL; //后继节点的双亲节点
AVL_Node *temp = NULL; //临时保存待释放节点的子树,避免free后找不到左右子树
if(root==NULL)//二叉搜索树中：搜到底了还没有就是没有了
{
cout<<"没有此节点【"<<val<<"】删除失败！！！"<<endl;
cout<<endl;
return NULL;
}
else if(root->data < val)//大的往右子树中找
{
root->right = Delete(root->right,val);
//由于是删去节点：所以失衡一定是左边高于右边【L】
if(Height(root->left) - Height(root->right) >= 2)
{
temp = root->left;
if(Height(temp->left) >= Height(temp->right))//LL型或LE型失衡的情况处理方式相同
root = AVL_LL(root);
else
root = AVL_LR(root);//LR型失衡
}
root->height = Height(root);
}
else if(val < root->data)//小的往左子树中找
{
root->left = Delete(root->left,val);
if(Height(root->right) - Height(root->left) >= 2)
{
temp = root->right;
if(Height(temp->right) >= Height(temp->left))//RR或RE型失衡的处理方式相同
root = AVL_RR(root);
else
root = AVL_RL(root);//RL型失衡
}
root->height = Height(root);
}
else
{
if(root->left==NULL && root->right==NULL);//若待删除节点为叶子节点
else if(root->left==NULL && root->right!=NULL)
temp = root->right;
else if(root->left!=NULL && root->right==NULL)
temp = root->left;
else//若待删除节点既有左子树也有右子树
{
Successor_Node = Successor(root);//搜索后继节点
parent = Parent_Of_Successor_Fun(root); //搜索后继节点的父节点
if(root->right==Successor_Node) //后继节点为待删除节点的右儿子【说明右儿子没有左子树】
Successor_Node->left = root->left; //后继节点有右子树和没有右子树的操作相同
//把后继节点上提
else if(root->right!=Successor_Node && Successor_Node->right==NULL)
{
//后继节点不为待删除节点的右子树，并且该后继节点没有右子树
Successor_Node->left = root->left;
Successor_Node->right = root->right;
parent->left = NULL;
}
else//后继节点不为待删除节点的右子树，并且该后继节点有右子树
{
parent->left = Successor_Node->right;
//后继节点的右子树作为后继节点父节点的左子树
Successor_Node->left = root->left;
Successor_Node->right = root->right;
}
//删除节点时不会出现“后继节点不是删除节点的子节点，且后继节点有右子树”
free(root);
root = Successor_Node;//关键！！！
Successor_Node->height = Height(Successor_Node);
return root;
}
free(root);
root = NULL;//关键！！！
return temp;
}
return root;
}

可运行总代码

【一天多的努力呜呜呜，终于弄出来了耶耶耶】

#include <iostream>
#include <queue>
#include <memory.h>
#include <algorithm>
#define DataType int
using namespace std;
typedef struct AVL_Node
{
int data; //节点保存的数据值
int height; //节点当前的高度
int key; //节点的键值（关键字）
AVL_Node *parent; //指向双亲节点
AVL_Node *left; //指向左孩子
AVL_Node *right; //指向右孩子
} AVL_Node;
int Height(AVL_Node *root);
AVL_Node *AVL_LL(AVL_Node *&former_root);
AVL_Node *AVL_RR(AVL_Node *&former_root);
AVL_Node *AVL_LR(AVL_Node *&former_root);
AVL_Node *AVL_RL(AVL_Node *&former_root);
AVL_Node *Create_AVL_Node(int val);
AVL_Node *Create_AVL_Tree_By_Array(int arr[],int n);
AVL_Node *Create_AVL_Tree_By_Input(void);
AVL_Node *Insert(AVL_Node *&root,int val);
void Print_AVL(AVL_Node *tree);
void Print_AVL_Unit(AVL_Node *root);
void Print_AVL_Level(AVL_Node *root);
AVL_Node *Delete(AVL_Node *&root,int val);
AVL_Node *Remove(AVL_Node *&root, int val);
AVL_Node *Successor(AVL_Node *root);
AVL_Node *PreSuccessor(AVL_Node *root);
AVL_Node *parent_Fun(AVL_Node *root);
int main()
{
int arr[5] = {10,20,30,40,50};
AVL_Node *tree = Create_AVL_Tree_By_Array(arr,5);
Print_AVL(tree);
Print_AVL_Level(tree);
for(int i=0; i<5; i )
{
cout<<"请输入要删除的元素数值【Delete】"<<endl;
int val;
cin>>val;
Delete(tree,val);
Print_AVL(tree);
Print_AVL_Level(tree);
}
for(int i=0; i<5; i )
{
cout<<"请输入要插入的元素数值"<<endl;
int val;
cin>>val;
Insert(tree,val);
Print_AVL(tree);
Print_AVL_Level(tree);
}
for(int i=0; i<5; i )
{
cout<<"请输入要删除的元素数值【Remove】"<<endl;
int val;
cin>>val;
Remove(tree,val);
Print_AVL(tree);
}
return 0;
}
AVL_Node *Create_AVL_Node(int val)
{
AVL_Node *root = (AVL_Node*)malloc(sizeof(AVL_Node));
root->data = val;
root->height = 1;//因为新建的节点肯定是作为叶子节点插入的,所以高度一定为1
root->key = val;
root->parent = NULL;
root->left = NULL;
root->right = NULL;
return root;
}
AVL_Node *Create_AVL_Tree_By_Array(int arr[],int n)
{
AVL_Node *root = NULL;
for(int i=0; i<n; i )
root = Insert(root,arr[i]);
return root;
}
AVL_Node *Create_AVL_Tree_By_Input(void)
{
cout<<"请输入节点的个数："<<endl;
int n;
cin>>n;
AVL_Node *root = NULL;
cout<<"请输入各个节点的数值："<<endl;
int temp;
for(int i=0; i<n; i )
{
cin>>temp;
root = Insert(root,temp);
}
cout<<endl;
return root;
}
void Search_AVL(AVL_Node *root,int val)
{
if(root==NULL)
{
cout<<"查找失败"<<endl;
return;
}
if (root->data == val)
printf("查找值存在，值为%d\n", root->data);
else if(val < root->data)
Search_AVL(root->left,val); //递归查找左子树
else if(root->data < val)
Search_AVL(root->right,val); //递归查找右子树
}
int Height(AVL_Node *root)
{
if(root==NULL)
return 0;
if(root->left==NULL && root->right==NULL)
return 1;
return max(Height(root->left),Height(root->right)) 1;
}
AVL_Node *AVL_LL_Pro(AVL_Node *former_root)//失衡节点为former_root
{
AVL_Node *new_root = former_root->left;//将失衡节点former_root的左孩子暂时保存为new_root
// 右旋，左儿子成为新的根节点
//这个必须先更新！！！
//左儿子的右子树为根节点的左子树
former_root->left = new_root->right; //令former_root的左孩子为new_root的右孩子
if(new_root->right)
new_root->right->parent = former_root;
new_root->parent = former_root->parent; //继承旧根节点的双亲节点
new_root->right = former_root; //令新根节点的右孩子为former_root
// 根节点成为左儿子的右子树
former_root->parent = new_root; //更新旧根节点的双亲节点
former_root->height = Height(former_root);//这里顺序不能颠倒
new_root->height = Height(new_root);
return new_root; //返回新的根节点
}
AVL_Node *AVL_LL(AVL_Node *&former_root)
{
AVL_Node *new_root = former_root->left;
former_root->left = new_root->right;
new_root->right = former_root;
former_root->height = Height(former_root);//这里顺序不能颠倒
new_root->height = Height(new_root);
return new_root;
}
AVL_Node *AVL_RR_Pro(AVL_Node *former_root)//失衡节点为former_root
{
AVL_Node *new_root = former_root->right;//将失衡节点former_root的右孩子暂时保存为new_root
// 左旋，右儿子成为新的根节点
//这个必须先更新！！！
// 右儿子的左子树成为根节点的右子树
former_root->right = new_root->left; //令former_root的右孩子设置为new_root的左孩子
if(new_root->left)
new_root->left->parent = former_root;
new_root->parent = former_root->parent; //继承旧根节点的双亲节点
new_root->left = former_root; //令新根节点的左孩子为former_root
// 根节点成为右儿子的左子树
former_root->parent = new_root; //更新旧根节点的双亲节点
former_root->height = Height(former_root);//这里顺序不能颠倒
new_root->height = Height(new_root);
return new_root; //返回新的根节点
}
AVL_Node *AVL_RR(AVL_Node *&former_root)
{
AVL_Node *new_root = former_root->right;
former_root->right = new_root->left;
new_root->left = former_root;
former_root->height = Height(former_root);//这里顺序不能颠倒
new_root->height = Height(new_root);
return new_root;
}
AVL_Node *AVL_LR(AVL_Node *&root)
{
root->left = AVL_RR(root->left);//左旋左儿子【左旋是RR】
return root = AVL_LL(root); //右旋根节点【右旋是LL】
}
AVL_Node *AVL_RL(AVL_Node *&root)
{
root->right = AVL_LL(root->right);//右旋右儿子【右旋是LL】
return root = AVL_RR(root); //左旋根节点【左旋是RR】
}
AVL_Node *Insert(AVL_Node *&root,int val)
{
if(root==NULL)
root = Create_AVL_Node(val);//最后肯定是作为叶子节点插入的
else if(val < root->data) //小的插在左子树中(统一用" <" !!!)
{
root->left = Insert(root->left,val);
root->height = Height(root);//插入完成后要更新高度
//如果插入后不平衡了,就需要调整
if(Height(root->left) - Height(root->right) == 2)//不平衡的情况肯定是左大于右
{
//这里第一步插在了左子树中
if(val < root->left->data) //在左子树的左子树中
root = AVL_LL(root); //进行右旋调整
else //在左子树的右子树中
root = AVL_LR(root); //先左后右
}
}
else if(root->data < val) //大的插在右子树中
{
root->right = Insert(root->right,val);
root->height = Height(root);//插入完成后要更新高度
if(Height(root->right) - Height(root->left) == 2)//不平衡的情况肯定是右大于左
{
//这里第一步插在了右子树中
if(root->right->data < val) //在右子树的右子树中
root = AVL_RR(root); //进行左旋调整
else //在右子树的左子树中
root = AVL_RL(root); //先右后左
}
}
else
{
cout<<"插入了重复的数值！！！"<<endl;
}
return root;
}
void Print_AVL(AVL_Node *tree)
{
Print_AVL_Unit(tree);
cout<<endl;
}
void Print_AVL_Unit(AVL_Node *root)
{
if(root==NULL)
{
cout<<"Empty Tree!"<<endl;
return ;
}
if(root->left)
Print_AVL_Unit(root->left);
cout<<root->data<<" ";
if(root->right)
Print_AVL_Unit(root->right);
}
AVL_Node *PreSuccessor(AVL_Node *root)// 寻找前驱节点
{
if (root==NULL)
return NULL;
root = root->left;//在左子树寻找最右节点
while (root->right)
root = root->right;
return root;
}
AVL_Node *Successor(AVL_Node *root)// 寻找后继节点
{
if(root==NULL)
return NULL;
root = root->right;//在右子树寻找最左节点
while(root->left)
root = root->left;
return root;
}
AVL_Node *Parent_Of_Successor_Fun(AVL_Node *root)// 寻找后继节点的双亲结点
{
if(root==NULL)
return NULL;
AVL_Node *parent = root;
root = root->right;//在右子树寻找最左节点的双亲结点
while(root->left)
{
parent = root;
root = root->left;
}
return parent;
}
AVL_Node *Remove(AVL_Node *&root, int val)
{
if(root == NULL)//二叉搜索树中：搜到底了还没有就是没有了
{
cout<<"没有此节点【"<<val<<"】删除失败！！！"<<endl;
cout<<endl;
return NULL;
}
if(root->data > val)//在左子树进行节点删除
root->left = Remove(root->left, val);
else if(root->data < val)
root->right = Remove(root->right, val);
else//找到了对应的节点，按情况删除
{
/**1.为叶子节点*/
if (root->left == NULL && root->right == NULL)
root = NULL;
/**2.只有右子树*/
else if (root->right != NULL)
{
AVL_Node *successor = Successor(root);
root->data = successor->data;//后继节点上提
//在右子树中删除后继节点
root->right = Remove(root->right, successor->data);
}
/**3.只有左子树或者左右子树都有*/ //Q：为什么这里可以合并
else
{
AVL_Node * preSuccessor = PreSuccessor(root);
root->data = preSuccessor->data;//前驱节点上提
//在左子树中删除前驱节点
root->left = Remove(root->left, preSuccessor->data);
}
}
//删除完成后可能需要调整平衡度
if(root == NULL)
return NULL;//这个是删除完后看root是否为空了
//左子树比右子树高,说明删除的是右子树的节点
if (Height(root->left) - Height(root->right) >= 2)
{
// 模拟在左子树插入的情况：在左儿子的左子树插入 or 在左儿子的右子树插入
if (Height(root->left->left) > Height(root->left->right))
return AVL_LL(root);//左左：右旋
else
return AVL_LR(root);//左右：先左后右
}
//在左子树删除节点
else if (Height(root->right) - Height(root->left) >= 2)
{
// 模拟在右子树插入节点
if (Height(root->right->right) > Height(root->right->left))
return AVL_RR(root);//右右：左旋
else
return AVL_RL(root);//右左：先右后左
}
//else 无需调整
root->height = Height(root);
return root; //更新root的高度并返回
}
AVL_Node *Delete(AVL_Node *&root,int val)
{
AVL_Node *Successor_Node = NULL; //后继节点
AVL_Node *parent = NULL; //后继节点的双亲节点
AVL_Node *temp = NULL; //临时保存待释放节点的子树,避免free后找不到左右子树
if(root==NULL)//二叉搜索树中：搜到底了还没有就是没有了
{
cout<<"没有此节点【"<<val<<"】删除失败！！！"<<endl;
cout<<endl;
return NULL;
}
else if(root->data < val)//大的往右子树中找
{
root->right = Delete(root->right,val);
//由于是删去节点：所以失衡一定是左边高于右边【L】
if(Height(root->left) - Height(root->right) >= 2)
{
temp = root->left;
if(Height(temp->left) >= Height(temp->right))//LL型或LE型失衡的情况处理方式相同
root = AVL_LL(root);
else
root = AVL_LR(root);//LR型失衡
}
root->height = Height(root);
}
else if(val < root->data)//小的往左子树中找
{
root->left = Delete(root->left,val);
if(Height(root->right) - Height(root->left) >= 2)
{
temp = root->right;
if(Height(temp->right) >= Height(temp->left))//RR或RE型失衡的处理方式相同
root = AVL_RR(root);
else
root = AVL_RL(root);//RL型失衡
}
root->height = Height(root);
}
else
{
if(root->left==NULL && root->right==NULL);//若待删除节点为叶子节点
else if(root->left==NULL && root->right!=NULL)
temp = root->right;
else if(root->left!=NULL && root->right==NULL)
temp = root->left;
else//若待删除节点既有左子树也有右子树
{
Successor_Node = Successor(root);//搜索后继节点
parent = Parent_Of_Successor_Fun(root); //搜索后继节点的父节点
if(root->right==Successor_Node) //后继节点为待删除节点的右儿子【说明右儿子没有左子树】
Successor_Node->left = root->left; //后继节点有右子树和没有右子树的操作相同
//把后继节点上提
else if(root->right!=Successor_Node && Successor_Node->right==NULL)
{
//后继节点不为待删除节点的右子树，并且该后继节点没有右子树
Successor_Node->left = root->left;
Successor_Node->right = root->right;
parent->left = NULL;
}
else//后继节点不为待删除节点的右子树，并且该后继节点有右子树
{
parent->left = Successor_Node->right;
//后继节点的右子树作为后继节点父节点的左子树
Successor_Node->left = root->left;
Successor_Node->right = root->right;
}
//删除节点时不会出现“后继节点不是删除节点的子节点，且后继节点有右子树”
free(root);
root = Successor_Node;//关键！！！
Successor_Node->height = Height(Successor_Node);
return root;
}
free(root);
root = NULL;//关键！！！
return temp;
}
return root;
}
void Print_AVL_Level(AVL_Node *root)
{
if(root==NULL)
{
cout<<"Empty Tree!"<<endl;
return;
}
queue<AVL_Node*> q;
q.push(root);
int len;
while(!q.empty())
{
len = q.size();
for(int i=0; i<len; i )
{
AVL_Node *temp = q.front();
if(temp)
{
printf("%-4d【%-2d】 ",temp->data,temp->height);
q.push(temp->left);
q.push(temp->right);
}
else
printf("NULL【】 ");
q.pop();
}
cout<<endl;
}
}

下述二叉树中，哪一种满足性质:从任一结点出发到根的路径上所经过的结点序列按其关键字有序

(A) 二叉排序树 (B) 赫夫曼树 (C) AVL树 (D) 堆【分析】

➢ 对于选项A，根据二叉排序树的结构特点我们可以知道，二叉排序树的中序遍历结果是一个有序序列，而在中序遍历中，父结点并不总是出现在孩子结点的前面（或后面），故该选项不正确。

➢ 对于选项B，根据赫夫曼树的结构特点我们可以知道，在赫夫曼树中所有的关键字只出现在叶结点上，其非叶结点上并没有关键字值，显然不正确。

➢ 对于选项C，AVL树其本质上也是一种二叉排序树，只不过是平衡化之后的二叉排序树，故该选项也是不正确的。

➢ 对于选项D，堆的概念我们会在堆排序中给大家介绍，根据建堆的过程，不断地把大者“上浮” ，将小者“筛选”下去，最终得到的正是一个从任一结点出发到根的路径上所经过的结点序列按其关键字有序的树状结构。

判断是否是平衡二叉树

bool Judge_AVL(AVL_Node *root) //判断平衡二叉树
{
int hl,hr;
if(root==NULL)
return true;
else
{
hl = Height(root->left);
hr = Height(root->right);
if(abs(hl-hr) <= 1) //就是要判断节点的高度是否平衡,然后是不是二叉搜索树
return Judge_AVL(root->left) && Judge_AVL(root->right);
else
return false;
}
}

六.B树

0.结构作用

表的大小超过了内存大小，从磁盘中读取这些节点，由于 AVL 每次都只能读取一个节点，所以性能不是很好。

AVL 在高度上采取相对平衡『存在一个范围』的策略

B树保持查找树在高度上的绝对平衡，而允许节点的子树个数(分支个数)在一定范围内变化。
【高度上绝对平衡，宽度上相对平衡，且不再是二叉结构】
【多路平衡查找树】
【为空或者 m叉树】

规定B树的阶——节点中的儿子个数的最大值【最多能有这么多个儿子指针】

【也就是 m叉树】：m ——『目的是为了一次找到多个节点』

1.基本概念

1.内部节点：是存储了具体的有意义的信息和数据的节点，里面包含了关键字和指针等内容。

2.外部节点：不包含信息的节点，类似于折半查找判定树中的查找失败节点。

3.终端节点：属于内部节点，且为最后一层的内部节点，树中倒数第二层的节点。

4.叶子结点：属于外部节点，且为树中倒数第一层的节点，不包含信息。【用空指针来代替】

5.关键字：（Ki）也就是存储的数值，在节点中升序排列着，且每两个关键字之间构成一个区间。
【这个区间的所有数值都存储在两个关键字之间的指针所指的节点中】
【注意关键字还要有一个配套的对应记录的存储地址，不然没有任何意义】

6.节点指针：（Pi）也就是节点的儿子指针，指向的是一个新的节点。【一个指针代表一个区间】

7.B树的高度：也就是磁盘存取的次数【或者说成正比】
但是为了要求明确，这里实际上是指内部节点的高度，也就是不包含最后一层叶子结点。

对任意一棵包含了 n 个关键字、高度为 h、阶数为 m 的B-树：

1.由于每个节点最多有m棵子树，m-1和关键字，所以 h >= logm（n 1）。

2.第一层至少1个节点，第二层至少2个节点。

【高度是存在范围的】

#include <iostream>
#define MAX_NUM 100
#define MIN_NUM 50
假设 B树的阶为 m = 101 .
MAX_NUM 是节点中关键字的最大数目：MAX_NUM = m-1 .
MIN_NUM 是节点中关键字的最小数目：MIN_NUM = ceil(m/2)-1
KeyType 为节点中关键字的类型
using namespace std;
typedef int KeyType;
typedef struct BTreeNode
{
int key_num; //节点中当前拥有的关键字个数
keyType key[MAX_NUM 1]; //节点中关键字的数值,从小到大排列,且key【0】不使用
string Location[MAX_NUM 1]; //节点中关键字对应记录的地址（使用字符串进行存储）
struct BTreeNode *parent; //指向双亲节点,方便进行分裂借取合并等操作
struct BTreeNode *Son[MAX_NUM 1];//存储指向儿子的指针,且Son【0】需要使用
} BTreeNode;

2.结构性质

1.每个结点最多有有m个子树。
【也就是最多有 m个孩子指针，m个点位，因此就最多有 m-1个坑，来放 m-1个关键字】

2.根节点如果不是终端结点，则至少有两颗子树。
【至少有两个儿子指针（点位）和一个关键字（坑）】【2～m】

3.分支结点【非根非终端】至少有「m/2」[向上取整]棵子树，也就是该节点中至少有（「m/2」- 1）（向上取整）个关键字。
【也可以理解为：每个节点至少有ceil（m / 2）-1 个兄弟节点】

4.所有的终端节点都位于B-树中的倒数第二层，内部节点范围内的最后一层。

5.所有的叶子节点『查找失败节点』都位于B-

BTreeNode *SearchBTree(BTreeNode root,KeyType target,int &pos,string &location)
{
root->key[0] = target; //设置哨兵
int i = root->key_num; //从后往前搜索
while(root->key[i] < target)
i--; //找到第一个小于等于target的数
if(i>0 && root->key[i]==k) //查找成功
{
pos = i; //返回pos下标
location = root->Location[i];//返回location关键字对应记录的地址
return root; //返回指向节点的指针
}
//节点内查找失败,但是有:root->key[i]<target<root->key[i 1]
if(root->Son[i]) //这里说明root是内部节点，还可以往下搜索
DiskRead(root->Son[i]);
//从磁盘中,将下一个需要查找的节点读入内存中
else //说明为叶子节点,查找失败
{
cout<<"Not Found!"<<endl;
return NULL;
//可以增加插入操作,查找插入关键字的位置
//则应当令pos = i，并返回root
}
return SearchBTree(root->Son[i],target,pos,loaction);//递归地查找下一个节点
}
外部查找的读盘次数不超过树高 h：O（h）
内部查找中,每个节点的关键字数目 ley_num 不超过 m：O（m）
故时间复杂度为：O（m*h）

树中的最后一层。

6.所有非终端节点包含下列信息：
『n，A0，k1，A1，K2，，，An-1，Kn，An』
ki为关键字，且为升序排列，同时Ai中所有结点的关键字都夹在ki与ki 1之间。
n个关键字 Ki ➕ n个指向关键字的指针 Pi ➕ n 1个指向子树的指针Ai。
非叶结点中的多个关键字均是从小到大有序排列。
【K1＜K2＜....... ＜Kn】【Ki-1＜Ai-1＜Ki】

3.查找操作

1.在B树中找节点。【磁盘中进行】【找到后将节点信息度入内存】

2.在节点中找关键字。【内存中进行】【在节点内用顺序查找法 / 折半查找法】

【若找到了则直接返回，查找成功】
【若没有找到，则按照对应的指针信息，到其所指的子树中去查找（区间）：也就是索引查找】【当查找到叶子节点时，对应指向它的指针其实是空指针，就说明没有这个关键字，查找失败】

查找成功，返回被查找关键字的所在节点的指针和关键字在节点中的位置。
『类似于二叉排序树的查找，只是每个节点内部还有有序表，可以进行顺序和二分查找』
查找失败，则返回插入位置『到达了叶子结点』

学会量化和抽象『数学问题』

4.插入操作

1.查找不成功后进行插入。
2.插入的位置一定在最下层的非叶结点处。
3.如果有重复的则不再插入。

1.定位：

按照查找算法，找出需要插入该关键字的某个终端节点（会找到表示失败的叶子节点），这样就确定了最底层中非叶节点的插入位置。
【插入位置一定是倒数第二层中的某个终端节点】
【层数的增加只会由于节点的分裂操作产生，而不会因为插入操作产生】

2.插入：

在B树中，每个非叶节点的关键字个数都是在区间「ceil（m / 2）- 1，m-1 」之间。
1.如果插入后该节点中的关键字个数小于等于m-1，则可以直接插入。『没有溢出』

2.双亲为空，则建一个新的节点。（也就是为根节点）

3.如果插入后关键字个数为m个『关键字最多m-1个，子树最多m个，也就是m个点，m-1个坑』，则需要进行节点的分裂。

从中间位置处：s = ceil（m/2）分为两个部分。
左侧部分：保留在原节点中。【 A0～As-1】
右侧部分：放在新节点中。【As 1～Am-1】
中间位置的节点：插入到原节点的双亲节点中去。【As】

如果此时导致了其双亲节点的关键字也达到了m个，则对其双亲节点同样进行分裂操作。
以此类推，直至出现第一个符合要求的节点为止，或者到根节点为止。

m为3时，ceil（m / 2）- 1 为1，m-1 为2，关键字个数区间：「1，2」，至少有1个兄弟节点。

m为4时，ceil（m / 2）- 1 为1，m-1 为3，关键字个数区间：「1，3」，至少有1个兄弟节点。

m为5时，ceil（m / 2）- 1 为2，m-1 为4，关键字个数区间：「2，4」，至少有2个兄弟节点。

m为6时，ceil（m / 2）- 1 为2，m-1 为5，关键字个数区间：「2，5」，至少有2个兄弟节点。

5.建立操作

从空树开始逐个插入关键字即可，插入新关键字时，需要自底向上分裂节点。

6.删除操作

先找到关键字所在的节点：

如果不是终端节点，且有 x = Ki ：
则在删去了 Ki 后，以该节点 p 中 Ai 所指示的子树中的最小关键字，或者 Ai-1 所指示的子树中的最大关键字来代替 Ki ，指向子树的指针即为 q 。

【前驱关键词或者后继关键词】
【寻找方式类似于：左子树中的最右侧点，与右子树中的最左侧点】

然后再q中删去相应的关键字。【先替换后删除】
这样就把非终端节点的删除操作，转化为了终端节点的删除操作。

接下来就只需要讨论 在终端节点中的删除操作 ：

1.若关键字个数大于等于 ceil（m / 2），则直接删去即可。

2.相邻兄弟够借：

如果关键字个数正好为 ceil（m / 2）-1，
且与此节点相邻的兄弟节点中的关键字个数大于等于ceil（m / 2），
（m>= 3，所以肯定会有兄弟节点的！！！）
那么只需要调整该节点和左（右）兄弟节点以及其双亲节点（父子换位法），以达到新的平衡。

父子换位法：首先把两个儿子所夹的关键字 K 覆盖掉待删除关键字。
如果是借的左兄弟节点——就拿左兄弟节点中的最后一个关键字覆盖掉K，然后直接删除它即可；
如果借的是右兄弟节点——就拿右兄弟节点中的第一个关键字覆盖掉K，然后直接删除右兄弟节点中的第一个关键字即可。

3.兄弟不够借：

该节点和与其相邻的左右兄弟节点（如果存在）的关键字个数都是 ceil（m / 2）-1，
则将该关键字删除后，与左（右）兄弟节点以及双亲节点中所夹的那个关键字进行合并。
（肯定会有兄弟节点的）

在合并过程中，双亲节点中的关键字个数会减1，如果双亲节点中的关键字减少到了ceil（m / 2）-1，则需要继续进行借取操作或者合并操作（反正不愁没有兄弟哈哈），直至符合要求为止。
【自底向上】

4.如果双亲节点是根节点，且关键字减少到0：

则直接将根节点删除，合并后的新节点成为根节点。
（根节点关键字为1时，有两棵子树）

#include <iostream>
#define MAX_NUM 100
#define MIN_NUM 50
/**
假设 B树的阶为 m = 101 .
MAX_NUM 是节点中关键字的最大数目：MAX_NUM = m-1 .
MIN_NUM 是节点中关键字的最小数目：MIN_NUM = ceil(m/2)-1
KeyType 为节点中关键字的类型
*/
using namespace std;
typedef int KeyType;
typedef struct BTreeNode
{
int key_num; //节点中当前拥有的关键字个数
keyType key[MAX_NUM 1]; //节点中关键字的数值,从小到大排列,且key【0】不使用
string Location[MAX_NUM 1]; //节点中关键字对应记录的地址（使用字符串进行存储）
struct BTreeNode *parent; //指向双亲节点,方便进行分裂借取合并等操作
struct BTreeNode *Son[MAX_NUM 1];//存储指向儿子的指针,且Son【0】需要使用
} BTreeNode;
//应当还需要实现将字符串转化为二进制数 or 八进制数 or十六进制数
BTreeNode *SearchBTree(BTreeNode root,KeyType target,int &pos,string &location)
{
root->key[0] = target; //设置哨兵
int i = root->key_num; //从后往前搜索
while(root->key[i] < target)
i--; //找到第一个小于等于target的数
if(i>0 && root->key[i]==k) //查找成功
{
pos = i; //返回pos下标
location = root->Location[i];//返回location关键字对应记录的地址
return root; //返回指向节点的指针
}
//节点内查找失败,但是有:root->key[i]<target<root->key[i 1]
if(root->Son[i]) //这里说明root是内部节点，还可以往下搜索
DiskRead(root->Son[i]);
//从磁盘中,将下一个需要查找的节点读入内存中
else //说明为叶子节点,查找失败
{
cout<<"Not Found!"<<endl;
return NULL;
//可以增加插入操作,查找插入关键字的位置
//则应当令pos = i，并返回root
}
return SearchBTree(root->Son[i],target,pos,loaction);//递归地查找下一个节点
}
/**
外部查找的读盘次数不超过树高 h：O（h）
内部查找中,每个节点的关键字数目 ley_num 不超过 m：O（m）
故时间复杂度为：O（m*h）
*/

七.B 树

1.结构性质

(m 阶 B 树 所需要满足的性质）

1.每个分支节点最多有m棵子树。（m个儿子节点，m个指针，m个关键字）

2.非叶根节点至少有两棵子树。（至少有两个关键字和两个指针）

3.分支节点至少有ceil（m / 2）棵子树。（至少有ceil（m / 2）个关键字）

4.节点的子树和关键字的个数是相等的。（！！！区别于B树）

5.所有分支节点（索引的索引，有点类似跳表）中，仅包含它的各个儿子节点（下一级的索引块）中的最大关键字中以及指向各个儿子的指针。

6.所有的叶子节点加起来，包含了全部的关键字信息以及指向相应记录的指针。
同一叶子节点中的关键字之间，和不同的叶子节点之间按从小到大的顺序，从左至右排列。
并且相邻叶子节点会相互链接起来。

7.在 B 树中一般有两个头指针：一个指向根节点，一个指向关键字最小的叶子节点。

「因此就有两种查找运算：一种从最小关键字开始的顺序查找；另一种从根节点开始的多路查找」

2.主要区别

1.内部节点性质

B 树：n个关键字的节点含有n个指针，n个儿子。（即每个关键字对应一个儿子）

B树：n个关键字的节点含有n 1个指针，n 1个儿子。
（插在两边，每个关键字对应两个相邻的左侧与右侧儿子指针）

2.关键字的个数要求

B 树：分支节点（非根非叶）关键字数区间为：【ceil（m / 2），m】根节点为：【2，m】

B树：分支节点（非根非叶）关键字数区间为：【ceil（m / 2）- 1，m-1】根节点为：【1，m-1】

3.外部节点性质

B 树：叶子节点中包含了信息，所有非叶节点仅仅起到索引的作用。
【非叶节点中的每个索引项只包含了对应子树的最大关键字和指向该子树的指针】
（并不会含有该关键字对应的记录的存储地址）

B树：叶子节点不包含任何信息，且为查找失败节点。
【非叶节点中存储了各个关键字和指向所夹区间的指针】

4.是否有重复

B 树：叶子节点加起来就包含了所有关键字，包括在非叶节点中的所有已出现的关键字。
（存在重复）

B树：叶子节点没有信息，终端节点与其他节点中的关键字不会重复。（不存在重复）

八.散列法【哈希查找 / Hash】

参见《哈哈哈哈希》

这篇好文章是转载于：学新通技术网