目录

一、二叉排序树

1.1 二叉排序树的定义

1.2 二叉排序树的查找

1.3 二叉排序树的插入

1.4 二叉排序树的创建

1.5 二叉排序树的删除

二、平衡二叉树

2.1 平衡二叉树的定义

2.2 平衡二叉树的插入及平衡调整

三、B树

3.1 B树的定义

3.2 B树的查找

3.3 B树的插入

3.4 B树的删除

四、B+树

4.1 基本概念

4.2 B+树的查找、插入和删除

---

一、二叉排序树

1.1 二叉排序树的定义

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 它的左、右子树也分别为二叉排序树。

二叉排序树是递归定义的。由定义可以得出二叉排序树的一个重要性质：中序遍历一棵二叉树时可以得到一个结点值递增的有序序列。

 图1.1-1 二叉排序树举例

//	二叉排序树的二叉链表存储表示	
typedef struct
{
	KeyType key;	//关键字项
	InfoType otherinfo;	//其他数据项
}ElemType;	//每个结点的数据域的类型
 
 
typedef struct BSTNode
{
ElemType data;	〃每个结点的数据域包括关键字项和其他数据项
struct BSTNode *lchild, *rchild;	//左右孩子指针
}BSTNode, *BSTree;

1.2 二叉排序树的查找

因为二叉排序树可以看成是一个有序表，所以在二叉排序树上进行査找和折半查找类似，也 是一个逐步缩小査找范围的过程。

1. 若二叉排序树为空，则查找失败，返回空指针。
2. 若二叉排序树非空，将给定值key与根结点的关键字T->data.key进行比较：
   •若key等于T->data.key,则査找成功，返回根结点地址；
   •若key小于T->data.key,则递归查找左子树；
   •若key大于T->data.key,则递归查找右子树。

 

图1.2-1 二叉排序树查找过程

复杂度分析：

含有n个结点的二叉排序树的平均查找长度和树的形态有关。当先后插入的关键字有 序时，构成的二叉排序树蜕变为单支树。树的深度为n，其平均査找长度为（n+1）/2，和顺序查找相同。
最好的情况是，二叉排序树的形态和折半查找的判定树相似，其平均査找长度和logn成正比。综合所有可能的情况，就平均而言，二叉排序树的平均査找长度仍然和logn是同数量级的。

 图1.2-2 不同形态的二叉排序树

就维护表的有序性而言，二叉排序树更加有效，无需移动记录，只需修改指针即可完成对结点的插入和删除操作。因此，对于需要经常进行插入、删除和査找运算的表，釆用二叉排序树比较好。

1.3 二叉排序树的插入

1.4 二叉排序树的创建

二叉排序树的创建是从空的二叉排序树开始的，每输入一 个结点，经过查找操作，将新结点插入到当前二叉排序树的合适位置。
一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列，就相当于在一个有序序列上插入一个记录而不需要移动其他记录。

算法步骤：

复杂度分析：

假设有n个结点，则需要n次插入操作，而插入一个结点的算法时间复杂度为O(logn)，所以创建二叉排序树算法的时间复杂度为O(n*logn)。

1.5 二叉排序树的删除

被删除的结点可能是二叉排序树中的任何结点，删除结点后，要根据其位置不同修改其双亲结点及相关结点的指针，以保持二叉排序树的特性。

 图1.5-1 在二叉排序树中删除*p步骤

图1.5-2 在二叉排序树中删除*p

 图1-5-3 在二叉排序树中删除的各类情况分析

复杂度分析：

同二叉排序树插入一样，二叉排序树删除的基本过程也是查找，所以时间复杂度仍是O(logn)。

二、平衡二叉树

2.1 平衡二叉树的定义

平衡二叉树或者是空树，或者是具有如下特征的二叉排序树：

(1 )左子树和右子树的深度之差的绝对值不超过1;

(2 )左子树和右子树也是平衡二叉树。

若将二叉树上结点的平衡因子定义为该结点左子树和右子树的深度之 差，则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。

因为AVL树上任何结点的左右子树的深度之差都不超过1,则可以证明它的深度和logn 是同数量级的。由此，其查找的时间复杂度是O(logn)。

 图2.1-1 平衡与不平衡的二叉树及结点的平衡因子

2.2 平衡二叉树的插入及平衡调整

平衡二叉树的插入：（插入后仍保证平衡及二叉排序树特性）
若插入新结点破坏了平衡二叉树的平衡性，则从插入结点逆向向根结点方向，将第一个失衡结点作为新的根结点，即最小不平衡子树，然后进行调整。

 图2.2-1 平衡调整分类

LL型：单向右旋——

①将A的左孩子B右旋代替A成为新的根结点
② A右旋成为B的右孩子
③而B的原右子树成为A的左孩子

 图2.2-2 LL型实例

RR型：单向左旋——

①将A的右孩子B左旋代替A成为新的根结点
② A左旋成为B的左孩子
③而B的原左子树成为A的右孩子

  图2.2-3 RR型实例

LR型：先左旋再右旋——

①将A的左子树左旋（以B的右孩子C为子树根）
②C右旋代替A成为新的根结点

   图2.2-4 LR型实例

RL型：先右旋再左旋——

①将A的右子树右旋（以B的左孩子C为子树根）
②C右旋代替A成为新的根结点

    图2.2-5 RL型实例

在平衡的二叉排序树BBST上插入一个新的数据元素e的递归算法可描述如下。

1. 若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增1。
2. 若e的关键字和BBST的根结点的关键字相等，则不进行插入。
3. 若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同 关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加(+1)时， 分别就下列不同情况处理之：
   BBST的根结点的平衡因子为-1 (右子树的深度大于左子树的深度)：则将根结点的 平衡因子更改为0, BBST的深度不变；
   BBST的根结点的平衡因子为0 (左、右子树的深度相等)：则将根结点的平衡因子更 改为1, BBST的深度增1;
   BBST的根结点的平衡因子为1 (左子树的深度大于右子树的深度):若BBST的左子 树根结点的平衡因子为1,则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0,树的深度不变；
   若BBST的左子树根结点的平衡因子为-1,则需进行先向左、后向右的双向旋转平衡处理, 并且在旋转处理之后。修改根结点和其左、右子树根结点的平衡因子，树的深度不变。
4. 若e的关键字大于BBST的根结点的关键字,而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加(+1)时，分别就不同情况处理之。（与3类似）。

三、B树

3.1 B树的定义

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

(1)树中每个结点至多有m棵子树；

(2)若根结点不是叶子结点，则至少有两棵子树；

(3)除根之外的所有非终端结点至少有m/2向上取整棵子树；

(4)所有的叶子结点都出现在同一层次上，并且不带信息，通常称为失败结点；

(5)所有的非终端结点最多有m - 1个关键字。

 图3.1-1 B树定义

        

  在 m 阶的B-树上，每个非终端结点可能含有：
    n 个关键字 Ki（1≤ i≤n） n     n 个指向记录的指针 Di（1≤i≤n）
    n+1 个指向子树的指针 Ai（0≤i≤n）

B树特点：

1. 所有叶子结点均在同一层次，这体现出其平衡的特点。
2. 树中每个结点中的关键字都是有序的，且关键字K, “左子树”中的关键字均小于K而其“右子树”中的关键字均大于K,这体现出其有序的特点。
3. 除叶子结点外，有的结点中有一个关键字，两棵子树，有的结点中有两个关键字，三棵子树，这种4阶的B-树最多有三个关键字，四棵子树，这体现出其多路的特点。

4. 

   图3.1-2 B树存储结构

结构描述：

typedef struct BTNode {
  int  keynum;        // 结点中关键字个数，结点大小
  struct BTNode  *parent;  
                            // 指向双亲结点的指针
  KeyType   key[m+1]; // 关键字（0号单元不用）
  struct BTNode  *ptr[m+1]; // 子树指针向量
  Record        *recptr[m+1];  // 记录指针向量
} BTNode, *BTree; // B树结点和B树的类型

3.2 B树的查找

查找过程：从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找，两个过程交叉进行。若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；若查找不成功，则返回插入位置。

将给定值key与根结点的各个关键字Ki, K2,…，Kj （1<=j

• 若key = Ki (1<=i<=j),则查找成功；
• 若keyi,则顺着指针P0。所指向的子树继续向下查找；
• 若Ki < key < Ki+1（1<=i则顺着指针Pi所指向的子树继续向下查找；
• 若key>Kj，则顺着指针Pj所指向的子树继续向下查找。

如果在自上而下的查找过程中，找到了值为炽y的关键字，则査找成功；如果直到叶子结点也未找到，则査找失败。

复杂度分析：

根据B-树的定义，第一层至少有1个结点；第二层至少有2个结点；由于除根之外的每个非终端结点至少有棵子树，则第三层至少有2个结点；……；依次类推，第h+1层 至少有2（）^（h-1）个结点。而h+1层的结点为叶子结点。若m阶B树中具有N个关键字，则叶子结点即查找不成功的结点为N+1,由此有：

这就是说，在含有N个关键字的B-树上进行查找时，从根结点到关键字所在结点的路径上涉及的结点数为h

3.3 B树的插入

在查找不成功之后，需进行插入。显然，关键字插入的位置必定在最下层的非叶结点。

有下列几种情况：

1）插入后，该结点的关键字个数n

2）插入后，该结点的关键字个数 n=m，则需进行“结点分裂”      令 s = ，在原结点中保留（A0，K1，……  ， Ks-1，As-1），建新结点（As，Ks+1，……  ，Kn，An）；将（Ks，p）插入双亲结点；

 3）若双亲为空，则建新的根结点

 图3.3-1 插入举例1（三阶B树）

  图3.3-1 插入举例2（三阶B树）

   图3.3-1 插入举例3（三阶B树）

算法步骤：

1. 在B-树中查找给定关键字的记录，若查找成功，则插入操作失败；否则将新记录作为空指针p插入到查找失败的叶子结点的上一层结点（由q指向）中。
2. 若插入新记录和空指针后，q指向的结点的关键字个数未超过m-1,则插入操作成功， 否则转入步骤3。
3. 以该结点的第个关键字为拆分点，将该结点分成3个部分：左边部分、、右边部分。左边部分仍然保留在原结点中；右边部分存放在一个新创建的结点（由p指向）中；关键字值为的记录和指针p插入到q的双亲结点中。因q的双亲结点增加一个新的记录，所以必须对q的双亲结点重复2和3的操作，依次类推，直至由q指向的结点是根结点，转入步骤4。
4. 由于根结点无双亲，则由其分裂产生的两个结点的指针p和q,以及关键字为的的 记录构成一个新的根结点。此时，B-的高度增加1.

 

3.4 B树的删除

    和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于-1，否则，要从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字)，则父结点下移，进行结点的“合并”。

图3.4-1 删除举例1

 图3.4-2 删除举例2

四、B+树

4.1 基本概念

一棵m阶的B+树和m阶的B-树的差异在于：

（1） 有n棵子树的结点中含有n个关键字；

（2） 所有的叶子结点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶 子结点本身依关键字的大小自小而大顺序链接；

（3） 所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小)关键字。

例如，图所示为一棵3阶的B+树，通常在B+树上有两个头指针，一个指向根结点， 另一个指向关键字最小的叶子结点。因此，可以对B+树进行两种查找运算：一种是从最小关键字起顺序查找，另一种是从根结点开始，进行随机查找。

 

图4.1-1 —棵3阶的B+树

4.2 B+树的查找、插入和删除

在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。

查找：若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。 因此，在B+树中，不管查找成功与否，每次査找都是走了一条从根到叶子结点的路径。B+树査 找的分析类似于B树。

在 B+ 树上，既可以进行缩小范围的查找，也可以进行顺序查找；
在进行缩小范围的查找时，不管成功与否，都必须查到叶子结点才能结束；
若在结点内查找时，给定值≤Ki，则应继续在 Ai 所指子树中进行查找。

B+树不仅能够有效地查找单个关键字，而且更适合查找某个范围内的所有关键字。例如，在 B+树上找出范围在［a, b］之间的所有关键字值。处理方法如下：通过一次查找找出关键字a,不管它是否存在，都可以到达可能出现a的叶子结点，然后在叶子结点中查找关键字值等于a或大于a的那些关键字，对于所找到的每个关键字都有一个指针指向相应的记录，这些记录的关键字在所需要的范围。如果在当前结点中没有发现大于b的关键字，就可以使用当前叶子结点的最后 一个指针找到下一个叶子结点，并继续进行同样的处理，直至在某个叶子结点中找到大于b的关键字，才停止査找。

插入和删除：

类似于B树进行，即必要时，也需要进行结点的“分裂”或“归并”。