这是另一种形式的二叉查找树，其特点为：

左、右子树深度之差的{jd1}值不大于1。

构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术

平衡树的查找性能分析：

假设深度为h的二叉平衡树上所含结点数的最小值为N_h，

则显然 N_h = N_h-1 + N_h-2 + 1

由此可以推导出：h≈log（n）

因此，在平衡树上进行查找的时间复杂度为O(log(n))

B-树是一种平衡的多路查找树：

※ 在m阶的B-树上，每个非终端结点可能含有：

n个关键字K_i（1≤i≤n） n<m

n个指向记录的指针D_i（1≤i≤n）

n+1个指向子树的指针A_i（0≤i≤n）;

• 非叶结点中的多个关键字均自小至大有序排列，即：K₁< K₂ < … < K_n;且A_i-1所指子树上所有关键字均小于K_i;A_i所指子树上所有关键字均大于K_i;
• 树中所有叶子结点均不带信息，且在树中的同一层次上;根结点或为叶子结点，或至少有两棵子树;其余非叶结点至少有 棵子树，至多有m棵子树。

#define m 3 // B树的阶，暂设为3

int keynum; // 结点中关键字个数，

// 即结点的大小

struct BTNode *parent; // 指向双亲结点的指针

KeyType key[m+1]; // 关键字（0号单元不用）

struct BTNode *ptr[m+1]; // 子树指针向量

Record *recptr[m+1]; // 记录指针向量

} BTNode, *BTree; // B树结点和B树的类型

从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找 两个

若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；

假设返回的是如下所述结构的记录:

BTNode *pt; // 指向找到的结点

int i; // 1..m，在结点中的关键字序号

int tag; // 1:查找成功，0:查找失败

} Result; // 在B树的查找结果类型

则下列算法简要地描述了B树的查找操作的实现。

Result (BTree T, KeyType K) {

// 在m阶B树T上查找关键字K，返回结果(pt,i,tag)

p=T; q=NULL; found=FALSE; i=0;

// 初始化，p指向待查结点，q指向p的双亲

while (p && !found) {

n=p->keynum; i=Search(p, K);

// 在p->key[1..keynum]中查找 i ，

// p->key[i]<=K<p->key[i+1]

if (i>0 && p->key[i]==K) found=TRUE;

//找到待查关键字

else { q=p; p=p->ptr[i]; }

if (found) return (p,i,1); // 查找成功

else return (q,i,0);

// 查找不成功，返回K的插入位置信息

} // SearchBTree

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

1）插入后，该结点的关键字个数n<m，不修改指针;

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

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

Status (BTree &T, KeyType K,

BTree q, int i ) {

// 在m阶B树T上结点*q的key[i]与key[i+1]

// 之间插入关键字K。若引起结点过大，则沿

// 双亲链进行必要的结点分裂调整，使T仍是

// m阶B树。

x = K; ap = NULL; finished = FALSE;

while (q && !finished) {

// 将x和ap分别插入到q->key[i+1]和q->ptr[i+1]

if (q->keynum < m) finished=TRUE;

// 插入完成

else { // 分裂结点*q

s= ; split(q, aq); x=q->key[s];

// 将q->key[s+1..m], q->ptr[s..m]

// 和q->recptr[s+1..m]移入新结点*ap

q=q->parent;

if (q) then i = Search(q, x);

// 在双亲结点*q中查找x的插入位置

} // else

} // while

if (!finished) NewRoot(T, q, x, ap);

// 生成含信息(T,x,ap)的新的根结点*T,

// 原T和ap为子树指针

} // InsertBTree

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

B-树的查找时间主要花费在搜索结点（访问外存）上，

即主要取决于B-树的深度

问：含N个关键字的m阶B-树的深度H为多少？

第1层 1

第2层 2

第3层 2

第4层 2( )²

第H+1层 2( )^H-1

假设m阶B-树的深度为H+1，由于第H+1层为叶子结点，而因为树中含有N个关键字，则叶子结点必为N+1个，

N+1≥2( )^H-1

H-1≤

H≤

所以，在含N个关键字的B_树上进行一次查找，需访问的结点个数不超过

如果对双链树采用以下存储表示

#define MAXKEYLEN 16 // 关键字的{zd0}长度

char ch[MAXKEYLEN]; // 关键字

int num; // 关键字长度

} KeysType; // 关键字类型

typedef enum { LEAF, BRANCH } NodeKind;

// 结点种类：{叶子，分支}

typedef struct DLTNode {

char symbol;

struct DLTNode *next; // 指向兄弟结点的指针

NodeKind kind;

union {

Record *infoptr; // 叶子结点内的记录指针

struct DLTNode *first;

// 分支结点内的孩子链指针

} DLTNode, *DLTree; // 双链树的类型

则在双链树中查找记录算法的要点如下:

假设: T为键树的根指针，K为待查关键字(字符数组)

1) 指针的初始状态: p=T->first; i=0;

2) 在同一层上继续进行查询的条件:

(p && p->symbol!=K.ch[i]) p=p->next;

// 查找关键字的第i位

继续查找关键字的下一位的条件:

(p && i<K.num-1) p=p->first; ++i;

3) 查找结束的条件:

查找成功:

( p && i==K.num-1 ) 返回p->infoptr

查找不成功:

(p == NULL) 返回 “空”指针