这是另一种形式的二叉查找树，其特点为： 左、右子树深度之差的{jd1}值不大于1。 称有这种特性的二叉树为平衡树。 构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术 平衡树的查找性能分析： 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。 假设深度为h的二叉平衡树上所含结点数的最小值为Nh， 则显然 Nh = Nh-1 + Nh-2 + 1 由此可以推导出：h≈log（n） 因此，在平衡树上进行查找的时间复杂度为O(log(n))
三、B-树 1．B-树的定义 B-树是一种平衡的多路查找树： ※ 在m阶的B-树上，每个非终端结点可能含有： n个关键字Ki（1≤i≤n） n<m n个指向记录的指针Di（1≤i≤n） n+1个指向子树的指针Ai（0≤i≤n）;
B-树结构的C语言描述如下: #define m 3 // B树的阶，暂设为3 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树的类型
2.查找过程： 从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找 两个 过程交叉进行。 若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置； 若查找不成功，则返回插入位置。 假设返回的是如下所述结构的记录: typedef struct { 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
3．插入 在查找不成功之后，需进行插入。显然，关键字插入的位置必定在最下层的非叶结点，有下列几种情况： 1）插入后，该结点的关键字个数n<m，不修改指针; 2）插入后，该结点的关键字个数n=m，则需进行“结点分裂”，令s = 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) { Insert(q, i, x, ap); // 将x和ap分别插入到q->key[i+1]和q->ptr[i+1] if (q->keynum < m) finished=TRUE; // 插入完成 else { // 分裂结点*q 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
4．删除 和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于
5．查找性能的分析 B-树的查找时间主要花费在搜索结点（访问外存）上， 即主要取决于B-树的深度 问：含N个关键字的m阶B-树的深度H为多少？ 先推导每一层所含最少结点数： 第1层 1 第2层 2 第3层 2 第4层 2 第H+1层 2 假设m阶B-树的深度为H+1，由于第H+1层为叶子结点，而因为树中含有N个关键字，则叶子结点必为N+1个， 由此， N+1≥2( H-1≤ H≤ 所以，在含N个关键字的B_树上进行一次查找，需访问的结点个数不超过
四、双链树的查找算法 如果对双链树采用以下存储表示 #define MAXKEYLEN 16 // 关键字的{zd0}长度 typedef struct { 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) 返回 “空”指针 |
棵子树，至多有m棵子树。
; split(q, aq); x=q->key[s];
