第12单元高级数据结构.pptVIP

int KMPStrMatching(const String T,const String P,int *N) { int i=0, j=0; int pLen=P.length(); //模式长度 int tLen=T.length(); //主串长度 if (tLenpLen) return -1; while (ipLenjtLen){ if (i==-1||P[i]==T[j]) {i++;j++;} else i=N[i]; } if (i=pLen]) return (j-pLen+1); else return -1; } 尽管时间复杂度为O(m*n), 但接近O(m+n)。 * 英文字符树 一棵子树代表具有相同前缀的关键码的集合。例如“an”子树代表具有相同前缀an-的关键码集合{and，ant} 字符树的改进 由于单词可能不等长 ，所以更好的存储是其内部结点不存储单词信息，只有叶结点才存储单词信息 字符树中的检索 首先用待查关键码的第一个字符与森林的各个根的字符相比较。 然后下一步的检索在前次比较相等的那棵树上进行.其中，用待查关键码的第二个字符与选定的这棵树的根的各个子结点进行比较。 接着再沿着前次比较相等的分支进行进一步的检索。 ... 直到进行到某一层，该层所有结点的字符都与待查关键码相应位置的字符不同，这说明此关键码在树目录里没有出现。 若检索一直进行到树叶，那么就在树目录里找到了给定的关键码。 Trie字符树的缺陷 Trie结构显然也不是平衡的 在存取英文单词时，显然t子树下的分支比z子树下的分支多很多 每次有26个分支因子使得树的结构过于庞大，给检索也带来了不便 字母在计算机中是以二进制ASCII码的形式存储的 使用每个字母的二进制编码来代表这个字母 关键码就只有编码0和1 二叉Trie树 PATRICIA 结构 为了得到更加平衡的结构，提出了Trie结构的一种变体PATRICIA “Practical Algorithm To Retrieve Information Coded In Alphanumeric” 它不是对整个关键码大小范围的划分 根据关键码每一个二进制位的编码来划分 因为每一位不是0，就是1，所以分支因子是2， 生成的树是二叉树 PATRICIA 结构图 PATRICIA 结构图 因为最大的数是63，用6位二进制表示即可 每个结点都有一个标号，表示它是比较第几位，然后根据那一位是0还是1来划分左右两个子树 在图中检索5的话，5的编码为000101 首先我们比较第0位，从而进入左子树 然后在第1位仍然是0，还是进入左子树 在第2位还是0，仍进入左子树 第3位变成了1，从而进入右子树，就找到了位于 叶结点的数字5 PATRICIA的特点 每个内部结点都代表一个位的比较，必然产生两个子结点，所以它是一个满二叉树，进行一次检索，最多只需要关键码位数次的比较即可。 12.4 二叉树结构的改进 平衡的二叉有哪些信誉好的足球投注网站树、伸展树和最佳二叉排序树，它们都是对二叉树的结构或者操作规则做部分的改进以使树保持在一种类似于平衡的状态，从而达到较好的效率。 12.4.2 平衡的二叉有哪些信誉好的足球投注网站树(AVL) BST受输入顺序影响 最好情况O(log n) 最坏情况O(n) BST如何始终保持O(log n)级的平衡状态？ Adelson-Velskii和Landis发明了AVL树 一种平衡的二叉有哪些信誉好的足球投注网站树 任何结点的左子树和右子树高度最多相差1 AVL树的性质 可以为空 具有n个结点的AVL树，高度为O(log n) 如果T是一棵AVL树 它的左右子树TL、TR也是AVL树 并且| hL-hR|≤1 hL、hR 是它的左右子树的高度 平衡因子 用bf(x)来表示结点x的平衡因子。它被定义为： bf(x)=x的右子树的高度–x的左子树的高度 对于一个AVL树中的结点平衡因子可能取值为: 0，1和-1 AVL树结点的插入 插入17后导致不平衡 重新调整为平衡结构 12 二叉有哪些信誉好的足球投注网站树的平衡旋转 A B BL AR BR h h-1 h-1 1 2 A B BL AR BR 0 0 LL型 RR型 A B BR AL BL h h-1 h-1 -1 -2 A B BR BL AL 0 0 二叉有哪些信誉好的足球投注网站树的平衡旋转 LR型 A B BL AR CL h-1 h-2 h-1 -1 2 CR C 1 A C BL AR CR -1 0 B 0 CL 二叉有哪些信誉好的足球投注网站树的平衡旋转 RL型 B C AL BR CR -1 0 A 0