第九章 查找

基本概念 查找表 关键字 查找 由同一类型的数据元素构成的集合 静态查找表 动态查找表 对查找表的查找仅是以查询为目的，不改动查找表中的数据 动态查找表 可以在查找表中插入不存在的记录，或删除某个已存在的记录 关键字 数据元素（或记录）的某个数据项，能用来标识一个数据元素 查找 指定关键字，在表中查找

基本概念（续） 查找成功 查找不成功 内查找 外查找 平均查找长度ASL——查找方法时效的度量 查找表中存在满足条件的记录 查找表中不存在满足查找条件的记录。 内查找 整个查找过程都在内存中进行。 外查找 在查找过程中需要访问外存。 平均查找长度ASL——查找方法时效的度量 为确定记录在查找表中的位置，需将关键字和给定值比较次数的期望值。 查找成功时的ASL计算方法： n：记录的个数 pi：查找第i个记录的概率，( 不特别声明时认为等概率 pi =1/n ) ci：找到第i个记录所需的比较次数

静态查找表 顺序表的查找 通常查找表中的各元素（或记录）的关键字的值是无序的。 “哨兵”：数据安排在1~n，给定值放在第0个记录处，从后向前查找，直到找到所查记录为止。记录0像哨兵一样看守着查找表下界，不会越界。 typedef struct { ElemType *elem; int length; } STable;

顺序表算法 不使用哨兵 int seq_search( SSTable l, KeyType key) { for (i = 0; i < l.length; i++) if (l.elem[i] == key) return i; return -1; } 使用哨兵 int seq_search( SSTable l, KeyType key) { l.elem[0].key=key; for (i = l.length; l.elem[i].key != key; i--); return i; }

顺序表算法:采用链表结构 无头单链表 struct ELEM *seq_search( KeyType key) { for (p = head; p != NULL; p = p->next) if (p->key == key) return p; return NULL; } 无头单链表在链尾设置专用的“哨兵”记录，可减少比较次数 struct ELEM *seq_search( KeyType key) { tail->key = key; for (p = head; p->key != key; p = p->next); return p == tail ? NULL : p; }

顺序表算法性能分析 性能分析 查找成功时 ASLs(n)= =(1+2+ ... +n)/n=(n+1)/2 查找失败时 ASLf =n+1

有序表的查找 有序表 顺序查找 折半查找（二分查找） 折半查找的限制 查找表中的各记录的关键字的值是有序的 不需比较到表尾，只需比较到比给定值大的记录 折半查找（二分查找） 将给定值与中间的记录进行比较 若找到则查找成功； 否则：若比中间记录小，则对前一半子表进行折半查找，反之对后一半子表进行折半查找 折半查找的限制 顺序表 事先排好序 折半查找的性能不是查找算法的性能极限

折半查找算法及性能分析 int binsearch (SSTable ST, keytype key) { low= 1; high = ST.length; while (low <= high) { mid = (low + high) / 2; if (key==ST.elem[mid].key) return mid; else if ( key< ST.elem[mid].key) high = mid - 1; else high = mid+1; } return 0; 查找性能分析 折半查找每次只查表的一半，其所有记录的查找路径构成一棵二叉树，称为折半查找树（或判定树），每次查找只走了该树的一条分支，故平均查找长度不超过 log2n + 1

索引顺序表的查找 索引顺序表 带索引表的顺序表 分块查找（blocking search） 35 68 93 1 10 13 23 16 索引部分一定是有序的，这部分可用折半查找等方法 顺序表本身不一定有序，要根据顺序表是否有序而选用相应的查找方法 分块查找（blocking search） 将索引部分和表体部分分开查找的方法。 索引表的平均查找长度为两部分查找之和。 35 68 93 1 10 13 最大关键字 起始地址 索引表 23 16 11 6 28 31 25 19 41 57 75 88 69 3 2 4 5 7 8 9 12 14 15 顺序表

动态查找表 二叉排序树 平衡二叉树 B-树和B＋树

二叉排序树 特点：用于频繁进行插入、删除、查找的表。 二叉排序树：空或有一个根，根的左子树若非空，则左子树上的所有结点的关键字值 均小于根结点的值。根的右子树若非空，则右子树上的所有结点的关键 字值均大于根结点的值。根结点的左右子树同样是二叉排序树。 122 250 300 110 200 99 L N P E M C Y 105 230 216

二叉排序树 1、查找算法： 思路：若根结点的关键字值等于查找的关键字，成功。 否则，若小于根结点的关键字值，查其左子树。 若大于根结点的关键字值，查其右子树。 在左右子树上的操作类似。 122 250 99 Bitree SearchBST ( BiTree T, KeyType key ) // 在二叉排序树查找关键字之值为 key 的结点，找到返回该结 // 点的地址，否则返回空。T 为二叉排序树的根结点的地址。 { if ( !T || EQ( key, T ->data. key ) ) return ( T ) ; else if ( LT( key , T ->data. key ) ) return (SearchBST ( T -> lchild, key )); else return (SearchBST ( T -> rchild, key )); } 200 300 110 105 230 216

二叉排序树的插入 执行查找算法，找出被插结点的父亲结点 判断被插结点是左/右孩子。将被插结点作为叶子插入 若二叉树为空。则首先单独生成根结点。 注意：新插入的结点总是叶子结点。 例：122、99、250、110、300、280作为二叉排序树的结点的关键字值，生成二叉排序树。 122 250 99 300 110 280

二叉排序树插入算法 struct Node *root, **pptr; /* 全局变量 */ Status SearchBst(struct Node *t, KeyType key) { if (t == NULL) return FALSE; else if (key == t->key) return TRUE; else if (key < t->key) { pptr = &t->lchild; return SearchBst(t->lchild, key); } else { pptr = &t->rchild; return SearchBst(t->rchild, key); } InsertBST (KeyType key) pptr = &root; if (!SearchBst(root, key)) { *pptr = p = malloc(sizeof(struct Node)); p->key = key; p->lchild = p->rchild = NULL;

二叉排序树的查找分析 最好和最糟情况（折半查找/顺序查找） 平均情况下，log2n数量级 下述两种情况下的成功的平均查找长度 ASL 15 60 70 30 20 50 ASL=(1+2+3+4+5+6)/6=21/6=3.5 15 60 70 30 20 50 ASL=(1+2+2+3+3+3)/6=14/6=2.3 平均情况下，log2n数量级

二叉排序树的删除（1） （1）叶子结点：直接删除，更改它的父亲结点的相应指针域为空。 如：删除数据域为 15、70 的结点。 50 50 20 60 20 60 15 30 70 30

二叉排序树的删除（2） 删除 （2）被删结点的左孩子为空或者右孩子为空： 如下图所示，删除结点的数据域为 99 的结点。 400 400 如下图所示，删除结点的数据域为 99 的结点。 400 400 99 删除 450 450 122 122 被删结点 500 500 110 250 250 99 105 200 300 200 300 110 230 105 230 216 216

二叉排序树的删除（3a） (3)被删结点的左、右子树皆不空。 维持二叉排序树的特性不变。 在中序遍历中紧靠着被删结点的结点才可以替代被删节点 做法1:左子树中最大的结点做替身, 选左子树最右结点，其右孩子必为空 110 250 300 105 200 99 230 216 400 450 500 122 250 300 110 200 99 105 230 216 400 450 500 被删结点 替身 做法：将替身的数据域复制到被删结点的数据域 将结点110的左孩子作为 110的父结点99的右孩子(选中的结点110右孩子必为空)

二叉排序树的删除（3b） 右子树中最小的结点做替身。 选右子树中的最左的结点，其左孩子指针必为空 400 122 250 300 110 200 99 105 230 216 400 450 500 被删结点 替身 450 200 500 250 99 230 300 110 216 105 做法：将替身的数据域复制到被删结点的数据域。 将结点200的右孩子作为200的父结点250的左孩子。注意：结点 200左孩子必为空

二叉排序树的删除（3c） 做法2：删除节点，原左子树补上来，原右子树做原左子树最右节点的右子树 (或对称的：原右子树补上来，原左子树做原右子树最左节点的左子树) F F P 被删结点 C CL PR Q QL S SL C CL Q QL S PR SL

二叉排序树的删除算法(1) 全局变量struct NODE **pptr; Status DeleteBST (struct Node *t，KeyType key) { if (t == NULL) // 二叉排序树 t 中不存在关键字为 key 的结点 return FALSE; else if (key == t-> key) DeleteNode(t); // 存在关键字为 key 的结点，进行删除 else if (key < t->key) { pptr = &t->lchild; DeleteBST(t->lchild, key); } else { pptr = &t->rchild; DeleteBST(t->rchild, key); } return TRUE; 主程序： pptr = &root; DeleteBST(root,key);

二叉排序树的删除算法(2) Status DeleteNode(struct Node *p) { if (p->rchild == NULL) *pptr = p->lchild ; else if (p->lchild == NULL) *pptr = p->rchild; else { *pptr = p->lchild; for (s = p->lchild; s->rchild !=NULL; s = s->rchild); s->rchild = p->rchild; } free(p);

动态查找表－平衡二叉树 起因：提高查找速度，避免最坏情况出现。如下图情况的出现。虽然完全二叉树的树型最好，但构造困难。常使用平衡树。 A B D A B C F E G

动态查找表－平衡二叉树 平衡二叉树 平衡二叉树又称 AVL树(Adelson-Velskii & Landis于 1962年发明)，它具有如下性质： 或者为空树， 或者根结点的左、右子树也均为平衡二叉树，且左、右子树的树高之差的绝对值不超过1。 平衡因子 结点的左子树高度减去右子树高度的值称为该结点的平衡因子。 平衡二叉树也可以这样定义：平衡二叉树是所有结点的平衡因子的绝对值均小于2的二叉树。结点的平衡因子为 ＋1、－1、0

动态查找表－平衡二叉树 注意：完全二叉树必为平衡树，平衡树不一定是完全二叉树。 不是平衡树 是平衡树 不是完全二叉树 14 5 3 9 28 63 53 60 50 17 18 30 +1 +2 -1 不是平衡树 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 -1 是平衡树 不是完全二叉树

平衡二叉树的插入 要求：插入之后仍保持平衡二叉树的性质不变 在平衡树中插入数据域为 2 的结点 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 -1 2 +2 原平衡因子为 0 危机结点 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 -1 平衡树

平衡二叉树的插入 插入操作解决方案： 1. 新结点插入后，找到平衡因子越轨的结点，调整以此节点为根的子树,调整后，子树高度一定要保持不变（能做到吗？） 2. 不涉及到危机结点的父亲结点 3. 仍保持平衡二叉树的性质不变。 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 -1 2 +2 原平衡因子为 0 危机结点

平衡二叉树的插入 中序序列 右旋转处理 14 12 5 3 9 28 63 53 60 50 17 18 7 30 2 危机结点 +1 -1 2 +2 原平衡因子为 0 危机结点 中序序列 右旋转处理

平衡二叉树的插入 14 12 5 3 9 28 63 53 60 50 17 18 7 30 +1 -1 2 +2 原平衡因子为 0 危机结点

平衡二叉树的插入LL 右旋转A LL 处理 A B B A B A B A B A 左处理（新插入结点出现在危机结点的左子树上进行的调整）的情况分析(设插入前树高h) 1、LL 情况：（LL：表示新插入结点在危机结点的左子树的左子树上） 危机结点 +2 +1 A B +1 B A LL 处理 AR h-2 BL h-1 BR AR h-2 BL BR h-2 右旋转A h-2 h-1 处理前：高度为 h + 1 中序序列： 处理后：高度为 h 中序序列： B A B A BL BR AR BL BR AR B A 注意：处理后 平衡因子为 0

平衡二叉树的插入LR(a) 左旋转B然后右旋转A LR 处理 A B C 2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情况A： A B +1 h-2 +2 -1 LR 处理 BL AR 危机结点 处理前： 高度为 h + 1 中序序列： 注意：处理后 平衡因子为 0,0,-1 C CL CR h-3 处理后： 高度为 h 左旋转B然后右旋转A

平衡二叉树的插入LR(b) 左旋转B然后右旋转A LR 处理 A B C LR :新插入结点在危机结点的左子树的右子树上 情况B： BL +1 h-2 +2 -1 LR 处理 BL AR 危机结点 处理前： 高度为 h + 1 中序序列： 注意：处理后 平衡因子为 +1,0,0 C CR CL h-3 处理后： 高度为 h 左旋转B然后右旋转A

平衡二叉树的插入LR(c) LR 处理 A B C 四种情况的区分： 如果 的平衡因子为＋1 则为 LL型处理；否则为 LR型处理： +1 +2 -1 LR 处理 危机结点 处理前： 高度为 2 中序序列： 注意：处理后 平衡因子为 0,0,0 C 新插入结点 处理后： 高度为 1 四种情况的区分： 如果 的平衡因子为＋1 则为 LL型处理；否则为 LR型处理： 若 的平衡因子为＋1、－1 、0 ；则分别为 LRA、LRB、LRC型处理

平衡二叉树的插入－右处理 右处理（新插入结点出现在右子树上需进行的调整）： 1、RR 情况： 处理图形和 LL 镜象相似 2、RL 情况： （RL：表示新插入结点在危机结点的右子树的左子树上） A、处理图形和 LRA 镜象相似 B、处理图形和 LRB 镜象相似 C、处理图形和 LRC 镜象相似

平衡二叉树的插入举例 FEB 2 FEB MAR APR -1 APR JUN MAY FEB MAR APR MAY JUN JUL 例：有一组关键字序列{JAN、FEB、MAR、APR、MAY、JUN、JUL、AUG、SEP、OCT、NOV、DEC}，以此建立 AVL 树。 JAN FEB 2 FEB MAR APR -1 APR JUN MAY JAN FEB MAR APR MAY JUN JUL AUG AUG AUG JUL MAY -2 LR SEP 1 SEP OCT OCT

平衡二叉树的插入举例（续） -2 SEP OCT FEB MAR APR MAY JUN JUL AUG MAR -1 RL OCT 1 JAN -2 SEP OCT JAN FEB MAR APR MAY JUN JUL AUG MAR -1 RL OCT 1 NOV NOV SEP OCT JAN FEB MAR APR MAY JUN JUL AUG RR DEC

平衡二叉树的查找分析 具有 N 个结点的平衡树，高度 h 满足： log2(N+1) ≤ h ≤ loga(sqrt(5)*(N+1)) - 2 其中：a＝ (1＋sqrt(5))/2 查找的时间复杂度O(logn)

平衡二叉树的查找分析（续） 构造一系列结点个数最少的平衡二叉树， T1, T2 , T3 ,……Th；这种树的高度分别为 1、2、3、……h。 T1 高度 h = 1 结点个 数最少 T3 高度 h = 3 结点个 数最少 T2 高度 h = 2 结点个 数最少 有th = th-2 + th-1 + 1 该数的序列为 1、2、4、7、12、20、33、54、88 ...… 而 Fibonacci 数列为：0、1、1、2、3、5、8、13、21、34、55、89…… 所以： t(h) = f(h+2) - 1；于是转化为求 Fibonacci 数的问题。 由于： f(h) ≈αh/ sqrt(5); α＝ (1＋sqrt(5))/2 ......

Fibonacci 数列和2n比较 9 34 512 10 55 1024 11 89 2048 12 144 4096 13 233 8192 14 377 16384 15 610 32768 16 987 65536 17 1597 131072 18 2584 262144 19 4181 524288 20 6765 1048576 21 10946 2097152 22 17711 4194304 23 28657 8388608 24 46368 16777216 25 75025 33554432 26 121393 67108864 27 196418 134217728 28 317811 268435456 29 514229 536870912 30 832040 1073741824 31 1346269 2147483648 32 2178309 4294967296 33 3524578 8589934592 34 5702887 17179869184 35 9227465 34359738368 36 14930352 68719476736 37 24157817 137438953472 38 39M 275G 39 63M 550G 40 102M 1100G 41 165M 2200G 42 267M 4398G 43 433M 8796G 44 701M 17592G

AVL插入算法:数据结构 struct Node { ElemType data; int bf; struct Node *lchild, *rchild; }; #define LH +1 /* 左子树高 */ #define EH 0 /* 等高 */ #define RH -1 /* 右子树高 */

AVL插入算法:右旋/左旋 void R_Rotate(struct Node **pp) { p = *pp; lc = p->lchild; p->lchild = lc->rchild; lc->rchild = p; *pp = lc; } void L_Rotate(struct Node **pp) rc = p->rchild; p->rchild = rc->lchild; rc->lchild = p; *pp = rc;

AVL插入算法:简单情况 int InsertAVL(struct Node **pp, ElemType e) //返回值：-1未插入，0高度不变，1增高 { T = *pp; if (T == NULL) { // 递归出口 *pp = T = malloc(sizeof(struct Node)); T->data = e; T->lchild = T->rchild = NULL; T->bf = EH; return 1; } else if (e.key == T->Data.key) return -1; } else if (e.key < T->Data.key) { ...

AVL插入算法:左/右子树插入 } else if (e.key < T->Data.key) { result = InsertAVL(&T->lchild, e); if (result != 1) return result; switch (T->bf) { case LH: LeftBalance(pp); return 0; case EH: T->bf = LH; return 1; case RH: T->bf = EH; return 0; } } else if (e.key > T->Data.key) { result =InsertAVL(&T->rchild, e); case RH: RightBalance(T); return 0; case EH: T->bf = RH; return 1; case LH: T->bf = EH; return 0;

AVL插入算法:平衡处理 void LeftBalance(struct Node **pp) { a = *pp; b = a->lchild; switch (b->bf) { case LH: a->bf = b->bf = EH; R_Rotate(pp); break; case RH: c = b->rchild; switch (c->bf) { case LH: a->bf = RH; b->bf = EH; break; case EH: a->bf = b->bf = EH; break; case RH: a->bf = EH; b->bf = LH; break; } c->bf = EH; L_Rotate(&a->lchild);

平衡二叉树的删除算法 参照二叉排序树中的算法，删除后修正平衡因子，若平衡性被破坏，利用单一/双重旋转恢复。

红黑树 树的每个结点都被着上了红色或者黑色，结点所着的颜色被用来检测树的平衡性 。1972年由Rudolf Bayer发明的。它的平衡性要求比AVL树梢宽松，实践证明该算法效率很高

动态查找表： B 树和 B+ 树 内存 50 75 25 15 35 60 90 为什么采用B_ 树和 B+ 树？ 海量数据存放在外存中，不可能一次全部调入内存。因此，要多次 访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。 在 1970 年由 R bayer 和 E macreight 提出用B_ 树作为索引组织文件。提高访问速度、减少时间。 例如: 用二叉树组织文件，当文件的记录个数为 100，000时，要找到给定关键字的记录，需访问外存17次（log100,000）,太长了！ 文件头，可常驻内存 索引文件 50 75 25 15 35 60 90 数据文件 95 10 20 30 40 55 70 80 内存 文件访问示意图：索引文件、数据文件存在盘上

B树 B树是一种平衡的多路查找树，主要应用在文件系统中。 一棵 m 阶的B树，或为空树，或为满足下列特性的 m 叉树： 若根结点不是叶子结点，则最少有两棵子树； 除根之外的所有非终端结点最少有 m/2 棵子树； 所有非终端结点包含(n,A0,K1,A1,K2,…,Kn,An)信息数据； 其中：n为结点中关键字个数，Ai为指向子树的指针，Ki为关键字。 A0：<K1 的结点的地址（指在该 B_ 树中） K1：关键字 A2：> K1 且 < K2 的结点的地址（指在该 B_ 树中） 余类推 ……… An：> Kn 的结点的地址（指在该 B_ 树中） 注意：K1 <K2 < …... < Kn 所有叶子结点在同一层次上，不带信息。

B树 例如：m = 4 阶B树。除根结点和叶子结点之外，每个结点的孩子个数 至少为 m/2 = 2 个；结点的关键字个数至少为 1 。 1，35 第 1 层 1，18 第 2 层 2，43，78 第 3 层(L层) 1，11 1，27 1，39 3，47，58，64 1，99 F F F F F F F F F F F F 第 4 层(L＋1层)

B树的查找算法 B树节点定义 #define m 3 typedef struct BTNode { int keynum; 从根r开始查找，如果 Ki = KEY 则查找成功，Ri 为关键字为 KEY 的记录的地址。 若 Ki < KEY < Ki+1; 在子树 Ai 中查找 若 KEY < K1;在子树 A0 中查找 若 KEY > Kn;在子树 An 中查找 若 找到叶子(r为NULL)，则查找失败。 注意：每次查找将去掉 （s-1）/s 个分支。 B树节点定义 #define m 3 typedef struct BTNode { int keynum; struct BTNode *parent; KeyType key[1+m]; /* 0号未用 *. struct BTNode *ptr[1+m]; Record *recptr[1+m]; } BTNode, *BTree;

B树的插入操作 步骤： 1、确定插入位置，将结点插入到第 L 层（注意：第 L+1 层为叶子结点） 2、找到插入位置，将关键字和其它信息按序插入。 3、若被插入结点的关键字个数 >m-1, 则该结点满。必须分裂成两个结点。否则，结束。 如结点原为： （m-1, A0, (K1, A1), (K2, A2), ……… (Km-1, Am-1)） 插入一个关键字之后变为： （m, A0, (K1, A1), (K2, A2), ……… (Km, Am)） 该结点将进行分裂： …………... (K m/2, p‘ ) …………... m/2 -1, A0, (K1, A1), ……… (K m/2 , Am/2 )） （m- m/2 , A m/2 , ……… (Km, Am)） 生成新结点 p‘, 将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。 (K m/2 , p‘) 数据项插入上层结点之中 P’ P

B树的插入操作 例如：3 阶 B 树的插入操作。m=3, m/2 - 1 = 1; 至少 1 个关键字，二个孩子结点。 3，12 7 24 30 24，30 45，70 53 90 26 100 39 50 61 85 3 12 30 24 45 70 7 24 45 70 7插入

B 树的删除操作 基本要求 删除一个关键字之后节点的关键字个数小于m/2-1，则设法合并

B+树 B+树是B树的变形，广泛应用在数据库系统中 一棵m阶B+树与一棵m阶B树的不同之处在于： 查找算法 叶子结点包含了关键字的信息及指向记录的指针，且叶子结点以关键字自小至大顺序链接 非叶子节点仅仅作为索引部分使用，不含有关键字对应的指针 B+树已不是一棵真正意义上的树型结构了，其终端结点已连成了线性有序表 查找算法 每次查找都要从树根到树叶

键树 键树 又称数字查找树； 每个结点只包含组成关键字的字符或数字 常用存储方式 孩子兄弟的二叉树表示法（双键树）； 多重链表表示法（Trie 树）

哈希表 哈希表 哈希函数 冲突 同义词 装填因子 一个有限的连续地址空间，用以容纳按哈希地址存储的记录。 记录的存储位置与它的关键字之间存在的一种对应关系。 Loc(ri)=H(keyi) 冲突 不同关键字经哈希函数运算后得到的散列地址相同 原因：将一个较大的关键字值域映射到小的线性地址空间 同义词 在同一地址出现冲突的各关键字。 装填因子 表中填入的记录数n和哈希表表长m之比

哈希函数的构造方法 设计哈希函数基本原则 几种方法 针对具体问题仔细研究 简洁、高效 散列效果好 除留余数法 H(key)=key % m, m为散列表长度,m常用2n以提高计算效率 直接定址法：H(key)=a*key+b，a、b为常数； 数字分析法： 分析关键字，找出其中几位数字作散列地址（例如：指针值） 平方取中法 关键字平方后中间几位数字与所有数字相关，可选作散列地址 折叠法 将关键字分割成位数相同的几部分相叠加作为散列地址 伪随机数法 选取一个用关键字作为种子的伪随机数发生器生成散列地址

解决冲突的方法 开放定址法 再散列法 Hi=( H(key)+di ) % m, i = 1,2,…, k (k<m)其中 di=12, -12,22, -22,…,k2 (k≤m/2)，称为二次探测再散列； di= 伪随机数，称为伪随机探测再散列； 再散列法 Hi=RHi(key), i =1,2,…,k RHi为不同的散列函数；

解决冲突的方法 链地址法 散列表设立指针，将所有散列地址为此位置的关键字记录用链表形式存储起来 常使用双向链表便于关键字的增加和删除 查找效率：与表目个数N成正比 典型的链地址法链表结构 struct NODE { ElemType key; struct NODE *next, **pprev; } struct NODE *hash[N]; 为什么要这样实现？ 考虑元素的插入和删除算法，查找算法

链表插入和删除 #define head hash[idx] 插入p p->next = head; if (head != NULL) head->pprev = &p->next; p->pprev = &head; head = p; 删除p *p->pprev = p->next; if (p->next) p->next->pprev = p->pprev; free(p);

链地址法 关键字序列(38、59、125、168、216、719、455、20) 哈希函数 H(key) = key %10 ∧ 1 2 3 ∧ 1 2 3 4 5 6 7 8 9 20 ∧ 125 ∧ 216 ∧ 38 ∧ 59 ∧ 455 ∧ 168 ∧ 719 ∧ ASL成功 = ————————— = —— = 1.375 8 11 1+1+2+1+1+2+1+2 ASL不成功 = —————————— = —— = 1.8 10 18 2+1+1+1+1+3+2+1+3+3

作业(1) 数组a[N]中存储了N个整数并且递增有序，给出一种算法判断整数x是否在数组的元素集合中，并分析算法的执行效率。 写出非递归算法，在二叉排序树中检索关键字为k的节点。 书写一个递归算法，判断一个二叉树是否为二叉排序树。 如何从二叉排序树中删除关键字值为k的节点？阐述算法思想，并写出该算法。 平衡二叉树一定比二分查找有更高的效率吗？分析平衡二叉树和折半查找两种算法各自的利弊。 写出一个算法将平衡二叉树节点p右子树树根左旋。 按照关键字序列43，33，12，29，22，18，10，57，48，35，62，40建立平衡二叉树，按步骤逐步画出平衡二叉树。

作业(2) 一个整数集合的规模为60k，每个整数的取值是随机的，值范围为0~4G。对该集合的操作有：add(x):增加元素，del(x):删除元素，search(x):检索整数x是否在集合中。设计一种数据结构，使得检索操作平均检索时间比二分查找更快，而且增加/删除操作也有较高的效率。阐述数据的组织结构和算法基本思想，并且给出时间复杂度和空间复杂度分析结果。 重新设计一种数据结构完成第8题，并比较两种方法的优缺点。