顺序查找、折半查找、分块查找都是对线性表进行查找操作，它是静态查找表。即我们一般不对它进行插入和删除操作，因为如果是无序的，插入删除很方便但是查找的效率过低；如果是有序的，折半查找的效率不错但是插入删除太麻烦，所以我们下面要讨论的诸多树型查找就是动态查找表，它们方便进行插入删除操作的同时查找效率也不错。值得一提的是，它们是我们为了方便查找而定义的一种逻辑结构，属于是面向查找操作的数据结构，那么我们对它们复杂的定义也不足为奇了，这里点名红黑树。

一、二叉排序树(BST树)

1.1二叉排序树的定义

又称二叉查找树、二叉搜索树、BST(BinarySearch Tree)树。

它是一棵空树，或者是具有以下性质的二叉树：

若左子树非空，则左子树上所有结点的值均小于根结点的值。
若右子树非空，则右子树上所有结点的值均大于根结点的值。
左、右子树也分别是一棵二叉排序树。

对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

1.2二叉排序树的查找

二叉排序树的查找是从根结点开始，沿某个分支逐层向下比较的过程。若二叉排序树非空，先将给定值与根结点的关键字比较，若相等，则查找成功；若不等，如果小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找。


BSTNode *BST_Search(BiTree T,ElemType key)
{//非递归
    while(T!=NULL&&key!=T->data)
    {//若树空或者查找成功退出循环
        if(key<T->data) T=T->lchild;//继续往左子树中查找
        else T=T->rchild;//继续往右子树中查找
    }
    return T;
}
BSTNode *BST_Search(BiTree T,ElemType key)
{//递归
    if (!T)	//  查找不成功 
    return NULL; 
	else if (key==T->data) //  查找成功 
	return T; 
	else if (key<T->data) 
	return SearchBST(T->lchild, key);  //在左子树中继续查找 
	else  
	return SearchBST(T->rchild, key);  // 在右子树中继续查找 
}

递归的代码同样简单，但效率更低。

1.3二叉排序树的插入

二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找的过程中，当树中不存在关键字值等于给定值的结点时再进行插入的。

插入结点的过程如下：

若原二叉排序树为空树，则直接插入结点；
若关键字k小于根结点的值，则插入到左子树，若关键字k大于根结点的值，则插入到右子树。插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。


int BST_Insert(BiTree &T,keyType k)
{//递归实现，最坏空间复杂度O(n)
    if (!T)	
  { T=（BiTree）malloc(sizeof(BSTNode));
    T->data=k;
    T->lchild=T->rchild=NULL;
    return 1; // 插入成功 
  }
    else if (k==T->data) 
	return 0; //树中已有该关键值，插入失败
	else if (k<T->data) 
	return BST_Insert(T->lchild, k);  //在左子树中插入
	else  
	return BST_Insert(T->rchild, k);  // 在右子树中插入
}
int BST_Insert(BiTree &T,keyType k)
{//非递归
    while(T!=NULL&&k!=T->data)
    {//当该插入时或者插入失败时跳出循环
        if(k<T->data) T=T->lchild;//继续往左子树中插入
        else T=T->rchild;//继续往右子树中插入
    }
    
    if (T==NULL)	
  { T=（BiTree）malloc(sizeof(BSTNode));
    T->data=k;
    T->lchild=T->rchild=NULL;
    return 1; // 插入成功 
  }
    else return 0;//树中已有该关键值，插入失败
}

可以看到插入的效率和查找相同，不需要移动其他记录的位置，它表明，二叉排序树既拥有类似于折半查找的特性，又采用了链表作为存储结构，因此是动态查找表的一种适宜表示。

1.4二叉排序树的构造

从一棵空树出发，依次输入元素，将它们插入二叉排序树中合适位置。构造BST树的过程即为依次插入给定值的过程。


void Creat_BST(BiTree &T,KeyType str[],int n)
{
    T=NULL;
    int i=0;
    while(i<n)
    {
        BST_Insert(T,str[i]);
        i++;
    }
}

1.5二叉排序树的删除

需要使删除结点后的树仍满足二叉排序树的特性，删除操作的过程分3种情况讨论：

若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
若被删除结点z只有一棵左子树或右子树，则让z的子树成为z的父节点的子树，替代z的位置。
若被删除结点z有左子树和右子树，则让z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换为了第一种或第二种情况。

前二种情况比较直观，下面给出图解讨论第三种情况：

如果我们按上述操作删除48后再插入48，显然二叉排序树已经不同。

1.6二叉排序树的查找效率分析

二叉排序树的查找效率，主要取决于树的高度。

若二叉排序树的左、右子树的高度之差的绝对值不超过1，则这样的二叉排序树称为平衡二叉树，它的平均查找长度为O(logn)。

若二叉排序树是一个只有左(右)孩子的单支树，(类似于有序的线性表)，则其平均查找长度为O(n)。

明确使用(mid=(low+high)/2)时二分查找的判定树唯一，而二叉排序树的查找不唯一，相同的关键字其插入的顺序不同可能生成不同的二叉排序树。

当有序表是静态查找表时，宜选择顺序表作为其存储结构，故采用二分查找实现查找操作；

当有序表是动态查找表时，宜选择二叉排序树作为其逻辑结构，此时插入删除，查找的时间复杂度都是O(logn)。

二、平衡二叉树(AVL树)

2.1平衡二叉树的定义

平衡二叉树又称平衡二叉搜索树，是为了避免构建二叉搜索树时树的高度增长过快，降低其性能，规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过1。又称ALV树，得名于它的发明者G.M.Adelson-Velsky和E.M.Landis。

平衡二叉树是一棵空树，或者是具有以下性质的二叉树：

若左子树非空，则左子树上所有结点的值均小于根结点的值。
若右子树非空，则右子树上所有结点的值均大于根结点的值。
左、右子树也分别是一棵平衡二叉树。
左子树和右子树的高度差的绝对值不超过1。

将AVL树上结点的平衡因子定义为该结点的左子树的深度减去它的右子树的深度，则AVL树上所有结点的平衡因子只可能是-1、0、1。

1.2平衡二叉树的插入

平衡二叉树保证平衡的基本思想如下：每当在二叉排序树中插入(或删除)一个结点时，

首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。
若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

调整的对象为最小不平衡子树，即其根结点是离插入结点最近，且平衡因子的绝对值超过1的祖先结点的子树。

我们对其进行平衡旋转处理，经过旋转处理后子树深度与插入之前相同，因而不影响插入路径上所有祖先结点的平衡度。

平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径上的某个结点不再平衡，则需要做出相应调整，下面给出四种需要旋转的情况：

LL平衡旋转：由于在A结点的左孩子结点的左子树插入了新结点，A的平衡因子从1增加到2，此时我们需要进行一次右旋操作，即A的左孩子结点B向右上旋转代替结点A成为根结点，A结点向右下旋转成为根结点B的右孩子结点，而B的原右子树成为结点A的左子树。

RR平衡旋转：由于在A结点的右孩子结点的右子树插入了新结点，A的平衡因子的绝对值从1增加到2，此时我们需要进行一次左旋操作，即A的右孩子结点B向左上旋转代替结点A成为根结点，A结点向左下旋转成为根结点B的左孩子结点，而B的原左子树成为结点A的右子树。

LR平衡旋转：由于在A结点的左孩子结点的右子树插入了新结点，A的平衡因子从1增加到2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后把该C结点向右上旋转提升到A结点的位置。

RL平衡旋转：由于在A结点的右孩子结点的左子树插入了新结点，A的平衡因子的绝对值从1增加到2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后把该C结点向左上旋转提升到A结点的位置。

总结一下四种情况：

分类	产生原因	解决方法
LL平衡旋转	左孩子的左子树插入结点	右旋转
RR平衡旋转	右孩子的右子树插入结点	左旋转
LR平衡旋转	左孩子的右子树插入结点	先左旋再右旋
RL平衡旋转	右孩子的左子树插入结点	先右旋再左旋

1.3平衡二叉树的删除

与平衡二叉树的插入操作类似，以删除结点w为例来说明平衡二叉树删除操作的步骤：

用二叉排序树的删除方法对结点w进行删除操作。
从结点w开始，向上回溯，找到第一个不平衡的结点z(还是要对最小不平衡树操作);y为结点z的高度最高的孩子结点；x是结点y的高度最高的孩子结点。
然后对以z为根的最小不平衡树进行平衡调整，其中x、y和z可能得位置有4种情况:

y是z的左孩子，x是y的左孩子(这种情况即为LL,右旋转)
y是z的右孩子，x是y的右孩子(这种情况即为RR,左旋转)
y是z的左孩子，x是y的右孩子(这种情况即为LR,先左旋再右旋)
y是z的右孩子，x是y的左孩子(这种情况即为LR,先左旋再右旋)

然后最小不平衡子树z就被调整为平衡了，但注意此时z的高度可能会减少，因此我们可能需要向上回溯对z的祖先结点进行平衡调整，甚至回溯到根结点(导致树高减1)。这一点与插入不同，插入结点后最小不平衡子树经过旋转处理后子树深度与插入之前相同。

举例删除操作为何类似插入操作：

下图给出删除操作可能会减少树高的情况:

总之，插入操作是因为初始左子树低，右子树高，我们往右子树插入导致不平衡，那我们一定可以通过旋转改变树形把这个插入的结点搞到左子树，旋转后整体高度不变。左子树高，右子树低同理。

删除操作是因为初始左子树低，右子树高，我们减少左子树的高度使之打破平衡界限，那我们通过旋转改变树形从右边借了一个结点使左子树的高度恢复，但如果右子树恰好需要这个结点来作为最后一层，我们借过之后右子树的高度减一，旋转后整体高度减一。

1.4平衡二叉树的查找效率分析

在平衡二叉树上进行查找的过程与二叉排序树相同。在查找的过程中，与给定值进行比较的关键字个数不超过树的深度。

假设以 $n_{h}$ 表示深度为h的AVL树中含有的最少结点数。有 $n_{h}$ = $n_{h- 1}$ + $n_{h-2}$ +1。

在平衡二叉树上进行查找的时间复杂度为O(logn)。

故求给定结点数的平衡二叉树的查找所需的最多比较次数可以先构造一个该结点树的最高平衡二叉树。

三、红黑树

3.1红黑树的定义

为了保证AVL树的平衡性，我们在插入删除时频繁地调整全树整体的拓扑结构，代价较大。因此，我们对二叉排序树不再进行高度平衡的限制(AVL树)，而进行适度平衡的限制(红黑树)。这样在保证查找效率的同时我们进行插入删除操作所付出的代价也更小，因此红黑树的实际应用更广泛，C++中的map和set(Java中的TreeMap和TreeSet)就是用红黑树实现的。

一棵红黑树是满足如下红黑性质的二叉排序树:

每个结点或是红色，或是黑色的。
根结点是黑色的。
叶结点(虚构的外部结点，NULL结点)都是黑色的。
如果一个结点是红色的，则它的两个子结点都是黑色的。
对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数量相同。

对第3条的解释：与折半查找判定树和B树(它俩的失败结点)类似，为了便于红黑树的实现和理解，引入n+1个外部叶结点，以保证红黑树中每个内部结点的左右孩子均非空。
对第4、5条的解释，从根结点到叶结点(不含叶结点)的任何一条简单路径上都至少有一半是黑结点，这两条定义结合起来，所以"任意结点左右子树的高度，相差不超过2倍"。这正是适度平衡的体现。

从某结点出发(不含该结点)到达一个叶结点的任一简单路径上的黑结点总数称为该结点的黑高(记为bh)。根结点的黑高为红黑树的黑高。

结论一：从根结点到叶结点的最长路径不大于最短路径的2倍。
结论二：有n个内部结点的红黑树的高度h≤2log(n+1)。

3.2红黑树的插入

红黑树的插入过程是二叉排序树的插入过程类似，不同之处在于，红黑树中插入新结点后需要进行调整（包括重新着色和旋转操作），以满足红黑树的性质。

设结点z为新插入的结点，初始色为红色。插入过程如下：

用二叉排序树的插入法插入，若结点z的父结点是黑色，结束。
如果结点z的根结点，将z着为黑色(树的黑高增1)，结束。
如果结点z不是根结点，并且z的父结点z.p是红色的，此时z.p.p为黑色的，z.p的兄弟结点的颜色未知，下面分为三种解决：

①z的叔结点y是黑色的，且z是一个右孩子。
②z的叔结点y是黑色的，且z是一个左孩子。
③z的叔结点y是红色的(z是左或右无所谓)。
结束

对于①z的叔结点y是黑色的，且z是一个右孩子。：(下图为LR,先左旋，再右旋)，旋转同时还要重新着色。

如果y(T4)是左子树还有一种对称情况(即RL，先右旋，再左旋)。

对于②z的叔结点y是黑色的，且z是一个左孩子。(下图为LL，右旋一次)，旋转同时还要重新着色。

如果y(T4)是左子树还有一种对称情况(即RR，左旋一次)

对于③z的叔结点y是红色的(z是左或右无所谓)：z的父结点z.p和叔结点y都是红色的，因为z.p.p是黑色的，将z.p和y都着为黑色，z.p.p着为红色，以在局部保持性质4、5，然后把Z.P.P作为新的结点z来重复循环。

只要满足③的条件，就会不断循环，每次循环指针z都会上移两层，直到根结点或者满足①和②的条件。

如果y是左子树一样的操作，也对应二个图，不再赘述。

3.3红黑树的构造

下面为依次插入5，4，3，2，1时红黑树的构造过程：

3.4红黑树的删除

红黑树的插入操作容易导致两个连续的红结点，破坏定义4。而红黑树的删除操作容易造成子树黑高的变化(删除黑结点会导致根结点到叶结点间的黑结点数量减少)，破坏定义5。

红黑树的删除也是先执行BST树的删除操作，我们知道BST树的删除操作分三种情况，一是无子树，二是只有左或右子树，三是有左右子树，其中第三种情况会转换为前两种情况，因此我们只需讨论前两种情况即可：

为方便对照，先将所有可能性分类，等下填到讨论的两种情况之中。设待删结点为z

1.结点z无子树

1.1结点z为红色；

1.2结点z为黑色；

2.结点z有左子树或右子树

2.1结点z为黑色，只有左子树且必为红色；

2.2结点z为黑色，只有右子树且必为红色；

注：不存在待删结点z为红色时有单一子树这种情况

3.结点z有左右子树

3.1 直接后继(前驱)结点y来替换黑色结点z并且y为红色无子树。

3.2 直接后继(前驱)结点y来替换黑色结点z并且y为黑色无子树

3.3 直接后继(前驱)结点y来替换红色结点z并且y为红色无子树。

3.4 直接后继(前驱)结点y来替换红色结点z并且y为黑色无子树。

3.5 直接后继(前驱)结点y来替换黑色结点z并且y为黑色只有左子树。

3.6 直接后继(前驱)结点y来替换黑色结点z并且y为黑色只有右子树。

3.7 直接后继(前驱)结点y来替换红色结点z并且y为黑色只有右子树。

3.8 直接后继(前驱)结点y来替换红色结点z并且y为黑色只有右子树。

待删结点只有右子树或左子树。z的子树只有一个孩子结点，该结点必然为红色，否则会破坏定义5，我们进行下图这样的转换即可。2.1、2.2、3.5、3.6、3.7、3.8都属于此情况。对于3.7、3.8我们用y来替换z时注意黑色变成红色。

待删结点没有孩子

如果待删结点没有孩子，且结点是红色的，直接删除，结束。对应1.1、3.1、3.3
如果待删结点没有孩子，且结点是黑色的。下面进行讨论分析。对应1.2、3.2、3.4

删除y(1.2时为y为z本身)后将导致先前包含y的任何路径上的黑结点数量减1，因此y的任何祖先都不再满足定义5。
简单的修正方法就是删除y时把现在占有y位置的x结点视为还有额外一重黑色，定义为双黑结点。(因为y是终端结点所以x是空叶结点)
也就是说，如果将任何包含结点x的路径上的黑结点数量加1，在此假设下，定义5得到满足，但破坏了定义1(不能存在双黑结点)，于是，删除操作的任务就转化为将双黑结点x恢复为普通结点。

分以下四种情况，区别在于x的右兄弟结点w及w的孩子结点的颜色不同：

情况1：x的兄弟结点w是红色结点。

w必须有黑色父结点和黑色孩子结点。交换w与父结点x.p的颜色，然后对x.p做一次左旋，不会破坏红黑树的任何规则。现在，x的新兄弟结点是旋转之前w的某个孩子结点，其颜色为黑色，下面要继续讨论新兄弟w的状态，这样就将情况1转换为了情况2、3、4。

情况2：x的兄弟结点w是黑色结点，且w的右孩子是红色

(下图对应RR，左旋一次)即红结点是其爷结点的右孩子的右孩子。交换w和父结点x.p的颜色，把w的右孩子着为黑色，并对x的父结点x.p做一次左旋，然后使x变为单重黑色，此时不再破坏红黑树的性质。注：灰色代表红黑均可，不影响该情况。

情况3：x的兄弟结点w是黑色结点，且w的左孩子是红色的，w的右孩子是黑色的。

(下图对应RL,先右旋再左旋)即红结点是其爷结点的右孩子结点的左孩子。交换w和其左孩子的颜色，然后对w进行一次右旋，而不破坏红黑树的任何性质。右旋过后x的新兄弟结点的右变为了红色，这样就变为了情况2，再进行左旋即可。

情况4：x的兄弟结点w是黑色结点，且w的两个孩子结点都是黑色的。

因w和x都是黑色的，我们可让x和w都去掉一层黑色，即w变为红色，x变为正常结点，为了保持局部的黑高不变，我们让x.p变为双黑结点。然后将x.p作为新的x结点来循环。如果是通过情况1进入情况4的，因为原来的x.p是红色的，将新结点变为黑色，终止循环，结束。

我们上图假设了x为左孩子结点，当x为右孩子结点时处理方式左右对称，不再赘述。

情况1、2、和3在各执行常数次的颜色改变和至多3次旋转后便终止，情况4是可能重复执行的唯一情况，每执行一次指针x上升一层，至多O(logn)次。

四、B树

4.1 B树的定义

B树，又称多路平衡查找树（或B-树、B_树）。

B树种所有结点的孩子个数的最大值称为B树的阶，通常用m表示。

一棵m阶B树或为空树，或为满足如下特性的m叉树。

树中每个结点至多有m棵子树，即至多含有m-1个关键字。
若根结点不是终端结点，则至少有两棵子树。
除根结点外的所有非叶结点至少有⌈m/2⌉棵子树，即至少含有⌈m/2⌉-1个关键字。
所有的叶结点都出现在同一层次上，并且不带信息(可视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点并不存在，指向这些结点的指针为空)
所有非叶结点的结构如下：

n $P_{0}$ $K_{1}$ $P_{1}$ $K_{2}$ $P_{2}$ ... $K_{n}$ $P_{n}$

其中， $K_{i}$ (i=1，2，...，n)为结点的关键字，且满足 $K_{1}$ < $K_{2}$ <...< $K_{n}$ ； $P_{i }$ (i=1，2，...，n)为指向子树根结点的指针，且指针 $P_{i-1}$ 所指子树中所有结点的关键字均小于 $K_{i}$ ， $P_{i }$ 所指子树中所有结点的关键字均大于 $K_{i}$ ，n（⌈m/2⌉-1≤n≤m-1）为结点中关键字的个数。

下图是一个4阶B树，下图只有内部结点，并没有给出第四层的叶结点(即外部结点，又或失败结点) 。注意这是一个高度为3的B树，B树高度不算叶结点。

对上述定义详细解释：

第1条解释：每个结点的包含的n关键字可以划分出n+1个区间，即n+1棵子树。

第2条解释：如果树不是空树，那么根结点至少要有一个关键字，即有两棵子树。终端结点是指最低层非叶结点，即上图第三层，叶子结点层指失败结点层。注：这里终端结点与叶子结点的概念居然不同，可见学习树概念还是要注重于应用。

第3条解释：多路查找路数不能少于一个下限。

第4条解释：B树是所有结点的平衡因子均等于0的多路平衡查找树。叶结点所在层次代表查找失败的位置。

第5条解释：结点中关键字从左到右递增有序，关键字两侧均有指向子树的指针，左边指针所指子树的所有关键字均小于该关键字，右边指针所指子树的所有关键字均大于该关键字。这是保证查找的必要信息。

4.2 B树的高度

B树的大部分操作所需的磁盘存取次数与B树的高度成正比。

下面进行分析，首先B树的高度不包括最后不带任何信息的叶结点所处的那一层。

若n≥1，则对任意一棵包含n个关键字、高度为h、阶数为m的B树：

B树的最小高度：

由于每个结点的子树最多为m，第一层1个结点，第二层m个结点，第三层m^2...

n≤(m-1)(1+m+m^2+m^3+...+m^(h-1))=m^h-1,因此有

h≥ $\log_{m}(n+1)$

B树的最大高度：

由于根结点最少1个关键字，其余非叶结点最少⌈m/2⌉-1个关键字，所以第一层1个结点，第二层2个结点，第三层2⌈m/2⌉个结点..第h+1层即叶结点层至少有2(⌈m/2⌉)^(h-1)个结点，由于叶结点有n+1个(查找失败个数)，所以n+1≥2(⌈m/2⌉)^(h-1)，因此有

h≤log⌈m/2⌉((n+1)/2) +1

两道练习题：

当m=5，n=53时， 2.5≤h≤4，即最大高度为4，最小高度为3。

当m=3，n=8时， 2≤h≤3.17 ，即最大高度为3，最小高度为2。

4.3 B树的查找

在B树上的查找与二叉查找树相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定。

B树的查找包含两个基本操作：

在B树中找结点。B树常存储在外存磁盘上，我们找到目标结点后要先在外存中把结点信息读到内存中
在结点内找关键字。这个操作是在内存中进行的，采用顺序查找或者折半查找均可。

4.4 B树的插入

与二叉排序树的插入操作相比，B树不能简单地添加到最底层非叶结点中，因为此时可能会导致不满足B树定义。

将关键字key插入B树的过程如下:

1.定位。和前面的查找操作类似，查找操作是找到失败结点的位置，但是我们定位是到失败结点对应的上一层进行插入。

2.插入。插入后检查被插入结点的关键字个数，当插入后结点个数大于m-1时，必须对结点进行分裂。

分裂的方法是：

插入key后从中间位置⌈m/2⌉把结点分为两部分，左部分放在这个原结点中，右部分放在新结点中，中间位置⌈m/2⌉的结点插入到原结点的父节点。

若原结点的父节点因为⌈m/2⌉位置结点的插入导致必须分裂，继续重复上述操作即可。

4.5 B树的删除

B树的删除要使删除后结点的关键字个数≥⌈m/2⌉-1，因此涉及结点的“合并”操作

当被删关键字k不在最底层非叶结点中时，用k的前驱或后继来代替k，下面只需讨论删除最底层非叶结点中关键字的情况。
当被删关键字在最底层非叶结点中时，有下面三种情况：

直接删除关键字，删除后仍满足B树定义，直接删除。
兄弟够借。即被删关键字所在结点的兄弟结点的关键字个数≥⌈m/2⌉。我们可以调整该结点，左或右兄弟结点及其双亲结点中的关键字，以达到新的平衡。
兄弟不够借。即被删关键字所在结点和其左右兄弟结点的目前关键字个数都为⌈m/2⌉-1。那么我们可以将被删关键字结点、父节点中的关键字和其左或右兄弟结点进行合并。合并过后父结点的关键字个数会减1，继续判断父结点是否满足B树定义。

五、B+树

5.1 B+树的定义

B+树是应数据库所需而出现的一种B树的变形树。

一棵m阶的B+树需满足下列条件：

每个分支结点最多有m棵子树(孩子结点)。
非叶根结点至少有两棵子树，其他每个分支结点至少有⌈m/2⌉棵子树。
结点的子树个数和关键字个数相等。
所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互衔接起来。
所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针。注：子结点关键字最小值也可，将在后面讲解。

5.2 B树与B+树的对比

在B+树中，具有n个关键字的结点只含有n棵子树，每一个关键字为其指向的子树根结点最大关键字。在B树中，具有n个关键字的结点含有n+1个棵子树，因为每一个关键字分为含有比它小关键字的子树和比它大关键字的子树。
在B+树中，每个非根内部结点的关键字个数n的范围是⌈m/2⌉≤n≤m，根结点2≤n≤m。在B树中，每个非根内部结点的关键字个数n的范围是⌈m/2⌉-1≤n≤m-1，根结点1≤n≤m-1。
在B+树中，叶结点包含全部信息，所以非叶结点仅起索引作用，非叶结点中每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
在B+树中，叶结点包含了全部关键字，非叶结点中出现的关键字也会出现在叶结点中；而在B树中，内部结点的关键字都是不重复的。

5.3 B+树的两种查找运算：

一种是从最小关键字开始的顺序查找(有一个头指针指向关键字最小的叶结点)

一种是从根结点开始的多路查找，假如要查找63

继续:

每一次无论查找成功与否，查找路径都是一条从根结点到叶结点的路径。

内部结点也可以是包括下一级索引块的最小值，查找操作是类似的，不再赘述。如图：

六、小结

二叉排序树既拥有类似于折半查找的特性，查找效率可以达到O(logn),又采用了链表作为存储结构，插入删除很高效。因此是动态查找表的一种适宜表示。

二叉排序树可能会在一些极端情况下退化成线性表，为了避免树的高度增长太快，我们使用平衡二叉树对其进行限制，防止这种极端情况的出现，保证我们的查找效率都是O(logn)。

平衡二叉树的维护太过困难，插入和删除操作后需要频繁调整全树整体拓扑结构，维护这种高度平衡所付出的代价比获得的效益大的多。因此如果我们需要频繁的插入删除又需要一定的查找效率，我们使用红黑树这一种放宽平衡条件的树形查找结构。

B树是应用于文件系统的一种平衡的多路查找树，B树的查找操作涉及外存的存取，而磁盘IO的时间代价昂贵，因此我们需要降低树的深度选择多路查找树。

B+树是应文件系统所需而出的B树的变种，实际应用于文件索引和数据库索引。B+树单一结点由于不含有关键字对应记录的存储地址，因此可以存储更多的关键字，使得查询的IO次数更少，同时B+树的查找路径从根结点到叶结点，查询效率更加稳定。此外B+树在范围查找上的优势更大，因为叶结点形成有序链表。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/418799

二叉排序树、平衡二叉树、红黑树、B树、B+树_二叉树 平衡二叉树 红黑树