《数据结构-B树和B键树.ppt》由会员分享，可在线阅读，更多相关《数据结构-B树和B键树.ppt（48页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、B-树，树，B+树和键树树和键树B-树B+树键树小结和作业复习复习复习ABCX2LLABCX2LRABCX-2RRABCX-2RL复习复习2、已知长度为11的表xal,wan,wil,zol,yo,xul,yum,wen,wim,zi,yon，按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。1、按次序输入关键字：7,6,5,4,3,2,1，试画出AVL树的构造和调整过程。复习复习含有含有 n n 个结点的二叉平衡树能达到的最大深度个结点的二叉平衡树能达到的最大深度：h hn n=log=log(5(n+1)-2
2、5(n+1)-2 B-树树定义定义查找过程查找过程插入操作插入操作删除操作删除操作查找性能的分析查找性能的分析B-树定义树定义B-树是一种平衡平衡的多路查找多路查找树：B-树定义树定义 一棵一棵m m阶的阶的B-B-树，或为空树，或为满足下列特性的树，或为空树，或为满足下列特性的m m叉树叉树1、树中每个结点最多有、树中每个结点最多有m棵子树棵子树2、若根结点不是叶子结点，则至少有两棵子树、若根结点不是叶子结点，则至少有两棵子树3、除根之外的所有非终端（叶子）结点至少有、除根之外的所有非终端（叶子）结点至少有 棵子树棵子树B-树定义树定义4、所有非终端结点中包含下列信息数据、所有非终端结点中包
3、含下列信息数据(n,A0,K1,A1,K2,A2,Kn,An)5、所有叶子结点都在同一层，不带信息、所有叶子结点都在同一层，不带信息a a.n n为关键字的个数，为关键字的个数，多个关键字自小至大有序多个关键字自小至大有序排列，即：排列，即：K K1 1 K K2 2 keynum;i=Search(p,K);/在在p-key1.keynum中查找中查找 i，/使得使得 p-keyi=Kkeyi+1,/没找到则没找到则i=-1 if(i0&p-keyi=K)found=TRUE;else q=p;p=p-ptri;/q 指示指示 p 的双亲的双亲 if(found)return(p,i,1);
4、/查找成功查找成功 else return(q,i,0);/查找不成功查找不成功B-树插入结点树插入结点在查找不成功之后，需进行插入。显然，在查找不成功之后，需进行插入。显然，关键关键字插入的位置必定在最下层的叶子结点字插入的位置必定在最下层的叶子结点，有下，有下列几种情况：列几种情况：1 1）插入后，该插入后，该结点的关键字个结点的关键字个数数nmn=2=2的树，的树，其中的每个结点中不是包含一个或者几个关键字，其中的每个结点中不是包含一个或者几个关键字，而是只包含组成关键字的符号。而是只包含组成关键字的符号。键树的结构特点键树的结构特点1 1）关键字中的各个符号分布在从根结点到叶结）关键字
5、中的各个符号分布在从根结点到叶结点的路径上，叶结点内的符号为点的路径上，叶结点内的符号为“结束结束”的标志的标志符。因此，键树的深度和关键字集合的大小无关符。因此，键树的深度和关键字集合的大小无关;2 2）键树被约定为是一棵有序树，即同一层中兄）键树被约定为是一棵有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结弟结点之间依所含符号自左至右有序，并约定结束符束符$小于任何其它符号。小于任何其它符号。双链树双链树 以二叉链表作存储结构实现的键树结点结构结点结构:first symbol next分支结点分支结点infoptr symbol next叶子结点叶子结点指向孩子结点的指针指
6、向兄弟结点的指针指向记录的指针typedef enum LEAF,BRANCH NodeKind;/两种结点：叶子叶子 和和 分支分支 H AD$HADE$R$ES$GH$I HEHERHEREHIGHHIST 叶子结点叶子结点分支结点分支结点含关键字含关键字的记录的记录双链树双链树typedef struct DLTNode char symbol;struct DLTNode *next;/指向兄弟结点的指针 NodeKind kind;union Record *infoptr;/叶子结点内的记录指针 struct DLTNode *first;/分支结点内的孩子链指针 DLTNode,
7、*DLTree;/双链树的类型双链树双链树#define MAXKEYLEN 16 /关键字的最大长度typedef struct char chMAXKEYLEN;/关键字 int num;/关键字长度 KeysType;/关键字类型双链树查找过程双链树查找过程假设假设:T:T 为指向双链树根结点的指针，为指向双链树根结点的指针，K.ch0.K.num-1 为待查关键字为待查关键字(给定值给定值)。则查找过程中的基本操作为进行下列比较则查找过程中的基本操作为进行下列比较:K.chi=?p-symbol 其中其中:0 i K.num-1，p 指向双链树中某个结点指向双链树中某个结点双链树查找过
8、程双链树查找过程1.1.初始状态初始状态:p=T-first;i=0;2.2.若若 (p&p-symbol=K.chi&ifirst;i+;3.3.若若 (p&p-symbol!=K.chi)则继续在键树的同一层上进行查找则继续在键树的同一层上进行查找 p=p-next;双链树查找过程双链树查找过程若若 (p&p-symbol=K.chi&i=K.num-1)则则 查找成功，返回指向相应记录的指针查找成功，返回指向相应记录的指针 p-infoptr 4.4.若若 (p=NULL)则表明查找不成功，返回则表明查找不成功，返回“空指针空指针”;Trie树树 以多重链表作存储结构实现的键树结点结构结
9、点结构:分支结点分支结点叶子结点叶子结点指向记录的指针0 1 2 3 4 5 24 25 26关键字关键字指向下层结点的指针每个域对应一个“字母”0 1(A)3 4 5(E)9(I)268(H)4(D)19(S)22(V)0 18(R)7(G)190 5(E)THADHAS HAVHEHERHEREHIGHIS叶子结点叶子结点分支结点分支结点指向记录指向记录的指针的指针typedef struct TrieNode NodeKind kind;/结点类型 union struct KeyType K;Record *infoptr lf;/叶子结点(关键字和指向记录的指针)struct Tri
10、eNode*ptr27;int num bh;/分支结点(27个指向下一层结点的指针)TrieNode,*TrieTree;/键树类型结点结构的结点结构的 C 语言描述语言描述:Trie树树Trie树查找过程树查找过程在在 Trie 树中查找记录的过程树中查找记录的过程:假设假设:T 为指向 Trie 树根结点的指针，K.num是字符的个数，K.ch0.K.num-1 为待查关键字(给定值)。则则查找过程中的基本操作为：搜索和对应字母相应的指针搜索和对应字母相应的指针:若若 p 不空，且 p 所指为分支结点，则则 p=p-bh.Ptrord(K.chi);/ord将字母影射成在字母表中的位置
11、(其中:0 i K.num-1)Trie树查找过程树查找过程初始状态初始状态:p=T;i=0;若若(p&p-kind=BRANCH&ibh.ptrord(K.chi);i+;若若(p&p-kind=LEAF&p-lf.K=K)则则 查找成功查找成功，返回返回指向相应记录的指针 p-lf.infoptr 反之，反之，即(!p|p-kind=LEAF&p-lf.K!=K)则则表明查找不成功查找不成功，返回返回“空指针”;小结和作业小结和作业1.B-树树 本节主要内容：本节主要内容：2.B+树树 3.键树键树1 1定义定义2 2查找过程查找过程3 3插入操作插入操作4 4删除操作删除操作5 5查找性能的分析查找性能的分析作业：作业：9.14，9.18