nullnullB-树，B+树和键树B-树B+树键树小结和作业复习null复习null复习2、已知长度为11的
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
{xal, wan, wil, zol, yo, xul, yum,wen,wim,zi,yon}，按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。1、按次序输入关键字：7, 6, 5, 4, 3, 2, 1，试画出AVL树的构造和调整过程。null复习含有 n 个结点的二叉平衡树能达到的最大深度：
hn = log(5 (n+1)) - 2 nullB-树定义查找过程插入操作删除操作查找性能的分析nullB-树定义B-树是一种平衡的多路查找树：nullB-树定义 一棵m阶的B-树，或为空树，或为满足下列特性的m叉树1、树中每个结点最多有m棵子树2、若根结点不是叶子结点，则至少有两棵子树nullB-树定义4、所有非终端结点中包含下列信息数据(n, A0, K1, A1, K2, A2, … , Kn, An)5、所有叶子结点都在同一层，不带信息a. n为关键字的个数，多个关键字自小至大有序排列，即：K1< K2 < … < Kn;
b.且 Ai-1 所指子树上所有关键字均小于Ki;
c.Ai 所指子树上所有关键字均大于Ki;
d.关键字的个数比子树的个数小1;nullB-树的查找过程从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找两个过程交叉进行。若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；若查找不成功，则返回插入位置。nullB-树的查找过程typedef struct {
BTNode *pt; // 指向找到的结点的指针
int i; // 1..m，在结点中的关键字序号
int tag; // 标志查找成功(=1)或失败(=0)
} Result; // 在B树的查找结果类型假设返回的是如下所述结构的记录:nullB-树的查找算法Result SearchBTree(BTree T, KeyType K) {
// 在m 阶的B-树T中查找关键字K,
//返回查找结果 (pt,i,tag)。
//若查找成功，则特征值tag=1,
//指针pt所指结点中第i个关键字等于K;
//否则特征值tag=0, 等于K的关键字应插入在
//指针pt所指结点中第i个关键字
//和第 i+1个关键字之间
} // SearchBTree… …nullB-树查找算法 p=T; q=NULL; found=FALSE; i=0;
while (p && !found) {
n=p->keynum; i=Search(p, K);
// 在p->key[1..keynum]中查找 i ，
// 使得 p->key[i]<=K
key[i+1], //没找到则i=-1
if (i>0 && p->key[i]==K) found=TRUE;
else { q=p; p=p->ptr[i]; } // q 指示 p 的双亲
}
if (found) return (p,i,1); // 查找成功
else return (q,i,0); // 查找不成功nullB-树插入结点在查找不成功之后，需进行插入。显然，关键字插入的位置必定在最下层的叶子结点，有下列几种情况：1）插入后，该结点的关键字个数n=2的树，其中的每个结点中不是包含一个或者几个关键字，而是只包含组成关键字的符号。null键树的结构特点1）关键字中的各个符号分布在从根结点到叶结点的路径上，叶结点内的符号为“结束”的标志符。因此，键树的深度和关键字集合的大小无关; 2）键树被约定为是一棵有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符‘$’小于任何其它符号。null双链树— 以二叉链表作存储结构实现的键树结点结构:first symbol next分支结点infoptr symbol next叶子结点指向孩子结点
的指针指向兄弟结点
的指针指向记录
的指针typedef enum { LEAF, BRANCH }NodeKind;
// 两种结点：{叶子 和 分支}nullHAD$HADE$R$$ES$GH$IHEHERHEREHIGHHIS…T叶子结点分支结点含关键字
的记录null双链树typedef struct DLTNode {
char symbol;
struct DLTNode *next; // 指向兄弟结点的指针
NodeKind kind;
union {
Record *infoptr; // 叶子结点内的记录指针
struct DLTNode *first;
// 分支结点内的孩子链指针
}
} DLTNode, *DLTree; // 双链树的类型null双链树#define MAXKEYLEN 16
//关键字的最大长度typedef struct {
char ch[MAXKEYLEN]; // 关键字
int num; // 关键字长度
} KeysType; // 关键字类型null双链树查找过程假设: T 为指向双链树根结点的指针，
K.ch[0..K.num-1] 为待查关键字(给定值)。则查找过程中的基本操作为进行下列比较:
K.ch[i] =? p->symbol
其中:0 ≤ i ≤ K.num-1， p 指向双链树中某个结点null双链树查找过程1.初始状态: p=T->first; i = 0;2.若 ( p && p->symbol == K.ch[i] && ifirst; i++;3.若 ( p && p->symbol != K.ch[i] )
则继续在键树的同一层上进行查找 p=p->next;null双链树查找过程若 ( p && p->symbol==K.ch[i] && i==K.num-1)
则 查找成功，返回指向相应记录的指针 p->infoptr 4.若 ( p == NULL)
则表明查找不成功，返回“空指针”;nullTrie树— 以多重链表作存储结构实现的键树结点结构:分支结点叶子结点指向记录
的指针指向下层结点的指针
每个域对应一个“字母”null0 1(A) 3 4 5(E) 9(I) … … 268(H)4(D) 19(S) 22(V) 0 18(R) 7(G) 190 5(E)THADHASHAVHEHERHEREHIGHIS叶子结点分支结点指向记录
的指针nulltypedef struct TrieNode {
NodeKind kind; // 结点类型
union {
struct { KeyType K; Record *infoptr } lf;
// 叶子结点(关键字和指向记录的指针)
struct { TrieNode *ptr[27]; int num } bh;
// 分支结点(27个指向下一层结点的指针)
}
} TrieNode, *TrieTree; // 键树类型结点结构的 C 语言描述:Trie树nullTrie树查找过程在 Trie 树中查找记录的过程:假设: T 为指向 Trie 树根结点的指针，
K.num是字符的个数，
K.ch[0..K.num-1] 为待查关键字(给定值)。则查找过程中的基本操作为：
搜索和对应字母相应的指针:
若 p 不空，且 p 所指为分支结点，
则 p = p->bh.Ptr[ord(K.ch[i])] ;
//ord将字母影射成在字母表中的位置
( 其中: 0 ≤ i ≤ K.num-1 )nullTrie树查找过程初始状态: p=T; i = 0;若 ( p && p->kind = = BRANCH && ibh.ptr[ord(K.ch[i])]; i++;若 ( p && p->kind==LEAF && p->lf.K==K)
则 查找成功，返回指向相应记录的指针 p->lf.infoptr 反之，即 ( !p || p->kind==LEAF && p->lf.K!=K )
则表明查找不成功，返回“空指针”;null小结和作业1.B-树 本节主要内容：2.B+树 3.键树1．定义2．查找过程3．插入操作4．删除操作5．查找性能的分析作业：9.14，9.18 
浙公网安备 33021202002483