第 九 章 静 态 表 动 态 表 哈 希 表 9.1 基 本 概 念 (Page 214) 2 表 : 是 由 同 一 类 型 元 素 成 的 集 合 静 态 表 : 只 做 询 或 检 索 操 作 动 态 表 : 询 检 索 插 入 删 除 关 键 字 : 是 元 素 中 某 个 相 的 值, 用 它 可 以 标 识 一 个 元 素 主 关 键 字 次 关 键 字 : 根 给 定 值, 在 表 中 确 定 一 个 其 关 键 字 等 于 给 定 值 的 元 素 成 功 返 回 位 置 序 号 不 成 功 返 回 0 1
3 注 意 比 较 各 种 算 法 时 间 复 杂 度 和 空 间 复 杂 度, 算 法 的 主 要 时 间 用 于 关 键 字 的 比 较 4 9.2 静 态 表 顺 序 表 的 typedef int KT ; typedef struct{kt key ;... }ET; typedef struct{et *elem; // 元 素 存 储 空 间 基 址,0 为 空 单 元 int length;}sst; int Search_Sq(SST ST, KT key){ St.elem[0].key=key;// 设 置 哨 兵 for (i=st.length ; key!=st.elem[i].key; i--) ; return i; } 2
5 顺 序 表 的 算 法 性 能 分 析 在 等 概 率 的 情 况 下 :Pi=1/n 成 功 时 的 平 均 长 度 : (n+1)/2 不 成 功 时 的 比 较 次 : n+1 假 设 成 功 与 不 成 功 的 可 能 性 相 同, 在 等 概 率 的 情 况 下 :Pi=1/2n, 则 顺 序 的 平 均 长 度 为 : ASLss=((n+1)+(n+1)/2)/2=3(n+1)/4 有 序 表 的 折 半 折 半 ( 二 分 ): 经 过 一 次 比 较 将 表 分 割 成 两 部 分, 然 后 只 在 表 的 一 部 分 中 继 续 进 行 的 方 法 mid=(low+high)/2 6 key =13 3
7 二 分 算 法 描 述 int Search_Bin(SST ST, KT 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 low=mid+1; } return 0; }// 时 间 复 杂 度 :O(log2 n) 8 二 叉 树 的 性 质 i-1 1 在 二 叉 树 的 第 i 层 上 至 多 有 2 个 点 (i>=1); k 2 深 度 为 k 的 二 叉 树 至 多 有 2-1 个 点 (k>=1); 3 对 任 何 一 棵 二 叉 树 T, 如 果 其 终 端 点 为 n0, 度 为 2 的 点 为 n2, 则 n0=n2+1 4 具 有 n 个 点 的 完 全 二 叉 树 的 深 度 为 : log2 n +1 4
9 二 叉 判 定 树 过 程 可 用 二 叉 树 来 描 述 树 中 每 个 点 表 示 一 个 记 录, 点 中 的 值 为 该 记 录 在 表 中 的 位 置, 通 常 这 个 描 述 过 程 的 二 叉 树 为 判 定 树 在 该 树 中, 和 给 定 值 进 行 比 较 的 次 恰 为 该 点 在 判 定 树 中 的 层 次 10 性 能 分 析 比 较 次 最 多 : log2 n +1 不 超 过 判 定 树 的 深 度 时 间 复 杂 度 : O(log2 n) 此 方 法 只 能 适 用 于 有 序 表, 且 限 于 顺 序 存 储 5
11 索 引 顺 序 表 的 ( 分 块 ) 要 求 : 索 引 表 按 表 中 记 录 的 关 键 字 分 块, R 1,R 2,,R L 第 R k 块 中 所 有 关 键 字 < R k+1 块 中 的 所 有 关 键 字 k=1,2,,l-1, 称 为 分 块 有 序 对 每 块 建 立 一 个 索 引 项, 包 含 有 两 项 内 容 : 关 键 字 项 : 为 该 块 中 最 大 关 键 字 值 ; 指 针 项 : 为 该 块 第 一 个 记 录 在 表 中 位 置. 所 有 索 引 项 组 成 索 引 表 过 程 确 定 待 记 录 所 在 块 ; ( 可 以 用 顺 序 或 折 半 ) 在 块 内 顺 序. ( 块 内 只 能 用 顺 序 ) 24 12 22 1 48 7 86 13 索 引 表 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53 1 2 3 4 5 6 7 8 9 10 11 12131415 16 17 18 6
13 性 能 分 析 ASL bs =L b +L w, L b 为 确 定 块 的 平 均 长 度 ;L w 为 块 内 次 若 顺 序 : ASL bs =L b +L w =(n/s+s)/2+1 若 折 半 : ASL bs =L b +L w = log 2 (n/s+1)+s/2 三 种 方 法 比 较 顺 序 折 半 分 块 ASL 大 小 中 表 要 求 无 有 序 表 块 间 有 序 9.3 动 态 表 14 二 叉 排 序 树 (BST) 二 叉 排 序 树 的 定 义 :page 227 过 程 二 叉 排 序 树 的 插 入 和 删 除 二 叉 排 序 树 的 分 析 含 有 n 个 点 的 二 叉 排 序 树 的 平 均 长 度 和 树 的 形 态 有 关 : 最 差 的 形 态 是 : 单 支 树 ( (n+1)/2 ); 最 好 的 形 态 是 : 判 定 树 ( log 2 n ) 在 随 机 情 况 下, 二 叉 排 序 树 的 平 均 长 度 和 log n 是 等 量 级 的 7
15 算 法 当 前 BST 非 空 时, 将 给 定 值 k 与 当 前 根 点 的 关 键 字 比 较 : 若 相 等, 成 功, 束 ; 若 k 小 于 当 前 根 点 的 关 键 字, 则 将 左 子 树 作 为 当 前 BST; 若 k 大 于 当 前 根 点 的 关 键 字, 则 将 右 子 树 作 为 当 前 BST; 重 复 (1) 16 8
17 BT SearchBST ( BT T,int key ) { if ( (!T ) key = =T->data) ) return ( T ); else if (key<t->data) return ( SearchBST ( T->lchild, key ) ); else return ( SearchBST ( T->rchild, key ) ); } 18 Status Search_Bit(BT T,BT &f,bt &p, int key) { // f 是 p 的 双 亲 点 指 针 p=t; f=t ; while (p) { if (p->data==key) return TRUE; else if (key<(p->data)) { f = p ; p=p->lchild; } else { f = p ; p=p->rchild ; } } return FALSE; } 9
19 在 二 叉 排 序 树 中 插 入 关 键 字 为 key 的 点 Status Insert_Bit(BT T,int key ){ if (!Search_Bit(T, f, p, key )) { p=(btn *)malloc(sizeof(btn)); p->lchild = p->rchild = NULL; p->data = key ; if (!f ) T= p; else if (key<(f->data) ) else f->rchild=p; return OK; } return ERROR ; } f->lchild=p; 例 : 将 序 列 (45,24,53,12,24,90) 造 成 为 二 叉 排 序 树 20 10
21 BST 的 特 点 : 中 序 遍 历 BST 可 得 到 一 个 关 键 字 的 有 序 序 列 在 BST 上 插 入 新 点 时, 不 必 移 动 其 他 点, 仅 需 改 动 某 点 的 指 针 ( 因 新 点 总 是 BST 上 的 一 个 新 叶 点 ) BST 既 具 有 类 似 折 半 的 特 性 ( 与 BST 的 平 衡 度 有 关 ) 又 采 用 了 链 表 存 储 ( 折 半 不 能 为 链 表 存 储 ), 因 此, 对 于 经 常 要 进 行 插 入 和 删 除 记 录 的 有 序 表, 采 用 BST 尤 其 合 适 22 平 衡 二 叉 树 (AVL 树 ): 定 义 : 它 或 是 一 棵 空 树, 或 者 是 左 子 树 和 右 子 树 的 深 度 差 的 绝 对 值 不 超 过 1; 且 左 子 树 和 右 子 树 都 是 平 衡 二 叉 树 平 衡 因 子 BF: 是 该 点 的 左 子 树 的 深 度 减 去 它 的 右 子 树 的 深 度 平 衡 二 叉 树 上 的 所 有 点 的 平 衡 因 子 只 可 能 是 -1,0,1 在 成 二 叉 排 序 树 的 过 程 中 进 行 平 衡 化 处 理, 成 为 二 叉 平 衡 树 11
例 : 平 衡 二 叉 树 与 非 平 衡 二 叉 树 的 比 较 23 平 衡 二 叉 树 非 平 衡 二 叉 树 24 二 叉 平 衡 树 的 平 衡 调 整 的 四 种 基 本 类 型 插 入 元 素 1 插 入 元 素 9 L L 型 R R 型 12
L R 型 25 R L 型 26 L +1 h+1 LL 型 平 衡 旋 转 ( 顺 时 针 ) 失 去 平 衡 点 的 平 衡 因 子 为 2, 其 左 孩 子 的 平 衡 因 子 为 1 1 B 2 A B L h B R h-1 a A R h-1 LL 0 B 0 B L h A h B R h-1 A R h-1 13
RR 型 平 衡 旋 转 ( 逆 时 针, 与 LL 对 称 ) 失 去 平 衡 点 的 平 衡 因 子 为 -2, 其 右 孩 子 的 平 衡 因 子 为 -1 A L -2 A h-1-1 B RR 0 A 0 B B R 27 B L h-1 B R h A L h-1 B L 28 B L LR 型 平 衡 旋 转 失 去 平 衡 点 的 平 衡 因 子 为 2, 其 左 孩 子 的 平 衡 因 子 为 -1-1 B h-1 h+1 2 A 1 C C L h-1 h C R A R h-1 h-2 LR 0 B 0 C B L h-1 C L h-1 C R -1 A h-2 A R h-1 中 序 遍 历 :B L B C L C C R A A R B L B C L C C R A A R 14
29 RL 型 平 衡 旋 转 失 去 平 衡 点 的 平 衡 因 子 为 -2, 其 右 孩 子 的 平 衡 因 子 为 1-2 A A L h-1 C L h-1 1 RL 0 C B 0-1 1 B R h-1 A B C C R h-2 A L C L C R h-2 B R 中 序 遍 历 :A L A C L C C R B B R A L A C L C C R B B R 若 关 键 字 的 输 入 序 列 为 : {4,5,7,2,1,3,6} 请 造 AVL 树 4 2 6 1 3 5 7 30 15
31 平 衡 化 算 法 p p 平 衡 二 叉 排 序 树 的 类 型 定 义 : typedef struct BSTN{ lc A A rc Elemtype data; B B int bf; /* 点 的 平 衡 因 子 */ struct BSTN *Lc, *Rc; } BSTN,*BST; 1. 右 旋 处 理 :p 指 向 旋 转 处 理 前 的 左 子 树 的 根 点 void R_rotate( BST &p){ lc=p->lc ; p->lc=lc->rc ; lc->rc=p ; p=lc;} 2. 左 旋 处 理 :p 指 向 旋 转 处 理 前 的 右 子 树 的 根 点 void L_rotate(BST &p) { rc=p->rc ; p->rc= rc->lc ; rc->lc=p ; p=rc ; } 32 对 二 叉 树 T 作 左 平 衡 旋 转 void LeftBalance( BST &T){ lc =T->Lc; switch(lc->bf){ case 1: T->bf = lc->bf =0; R_rotate(T); break; case -1: rd = lc->rc; switch(rd->bf){ case 1:T->bf = -1 ; lc->bf =0;break; case 0:T->bf = lc->bf =0;break; case -1:T->bf =0;lc->bf =1; } rd->bf =0; L_rotate(T->Lc); R_rotate(T); } } 16
在 平 衡 二 叉 排 序 树 上 插 入 元 素 Status InsertAVL(BST &T, ElemType e,boolean &taller) { if(!t) { T=(BST)malloc(sizeof(BSTN)); T->data=e; T->Lc=T->Rc=NULL;T->bf =0;taller =TRUE; } else { if ( e.key==t->data.key){taller=false;return 0;} if((e.key<t->data.key){k =InsertAVL(T->Lc,e,taller); if (!k) return 0; if (taller) switch(t->bf){ case 1: LeftBalance(T);taller =FALSE;break; case 0: T->bf =1;taller =TRUE; break; case -1: T->bf =0;taller =FALSE; } } else {k = InsertAVL(T->Rc, e, taller ); 33 34 } if (!k) return 0; if (taller) switch (T->bf){ case 1: T->bf =0 ; taller=false;break; case 0:T->bf = -1 ; taller=true ; break; case -1: RightBalace(T) ; taller = FALSE ; } } } return 1; 17
35 7.4 B- 树 B- 树 的 定 义 : 一 棵 m 阶 B- 树, 或 为 空 树, 或 为 满 足 下 列 特 性 的 m 叉 树 : 树 中 每 个 点 至 多 有 m 棵 子 树 ; 若 根 点 不 是 叶 子 点, 则 至 少 有 两 棵 子 树 ; 除 根 外 的 所 有 非 终 端 点 至 少 有 m/2 棵 子 树 ; 所 有 的 点 中 包 含 下 列 信 息 (P 239) ( n, A0, K1, A1, K2, A2,..., Kn, An ) (Ki<Ki+1) 所 有 的 叶 子 点 都 出 现 在 同 一 层 次 上 例 如 :3 阶 B- 树 的 非 终 端 点 : N A0 Key1 A1 Key2 A2 一 棵 四 阶 的 B - 树 1 35 1 18 2 43 78 36 1 11 1 27 1 39 3 47 53 64 1 99 F F F F F F F F F F F F 18
37 B- 树 的 t 30 45 25 32, 38 48 3 阶 B- 树 50 Key = 38 57 B 树 的 插 入 在 B 树 中 插 入 时, 形 成 的 点 分 裂 是 由 下 层 点 逐 步 向 上 层 传 递 的, 在 极 端 情 况 下, 会 一 直 传 递 到 根 点 ( 实 际 上, 这 是 B 树 长 高 的 唯 一 途 径 ) 38 45, 57 插 入 38, 45, 57 点 分 裂 45 38 38 57 依 次 插 入 48,25,30 19
45 30, 45 25, 30, 38 48, 57 45 25 38 48, 50, 57 插 入 50, 产 生 两 次 点 分 裂 39 30 50 25 32, 38 48 试 依 次 插 入 32,15,55,35,20,41,90 57 B - 树 的 删 40 除 操 作 30 45 25 32, 38 48 1. 删 除 关 键 字 30 32 45 25 38 48 50 57 50 可 能 形 成 点 的 合 并 B- 树 的 高 度 降 低 57 32, 45 25 38 48, 57 2. 删 除 关 键 字 50 20
动 态 表 动 态 表 顺 序 表 动 态 线 性 表 中 已 经 讨 论 树 型 表 动 态 二 叉 排 序 树 平 衡 二 叉 树 41 B 树 B + 树 改 进 实 现 索 引 性 能 分 析 键 树 ( 字 树 ) 7.5 哈 希 表 ( 散 列 表 ) 42 概 念 哈 希 函 : 在 记 录 的 存 储 位 置 和 它 的 关 键 字 间 建 立 一 个 确 定 关 系 f, 是 每 个 关 键 字 和 中 一 个 唯 一 的 存 储 位 置 对 应 这 个 对 应 关 系 f 为 哈 希 函 根 这 个 思 想 建 立 的 表 为 哈 希 表 同 义 词 : 若 key1!= key2, 而 f(key1)=f(key2), 则 这 种 现 象 成 为 冲 突, 且 key1 和 key2 对 哈 希 函 f 来 说 称 为 同 义 词 关 键 字 集 A m 哈 希 函 H(k) 地 址 空 间 D n 21
43 哈 希 造 表 或 散 列 : 根 设 定 的 哈 希 函 f =H(key) 和 处 理 冲 突 的 方 法, 将 一 组 关 键 字 映 象 到 一 个 有 限 的 连 续 地 址 集 ( 区 间 ) 上, 以 关 键 字 的 哈 希 函 值 作 为 记 录 在 表 中 的 位 置, 这 一 映 象 过 程 称 为 哈 希 造 表 或 散 列 记 录 的 存 储 位 置 叫 哈 希 地 址 或 散 列 地 址 关 键 问 题 造 好 哈 希 函 的 方 法 ; 研 究 解 决 冲 突 的 方 法 44 装 填 因 子 : 表 中 填 入 的 记 录 = 哈 希 表 的 长 度 标 志 哈 希 表 的 装 满 程 度 : 越 小, 发 生 冲 突 的 可 能 性 就 越 小 ; 反, 越 大, 表 中 已 填 入 的 记 录 越 多, 再 填 记 录 时, 发 生 冲 突 的 可 能 性 就 越 大 22
45 哈 希 函 的 造 方 法 判 定 标 准 计 算 简 单 容 易 冲 突 极 少 直 接 地 址 法 : 取 关 键 字 或 关 键 字 的 某 个 线 性 函 值 为 哈 希 地 址 H(key)=key 或 H(key)=a*key+b 例 : 开 辟 60 个 记 录 的 存 储 区,key = 年 号 H(key)=key -1949 哈 希 地 址 H(1949)= 0 H(1962)= 13 H(1950)= 1 H(1963)= 14 H(1951)= 2 H(1964)= 15... H(1998)= 49 46 除 留 余 法 : 取 关 键 字 被 某 个 不 大 于 哈 希 表 表 长 m 的 p 除 后 所 得 余 为 哈 希 地 址 H(key)=key mod p ( p m) 例 : 开 辟 38 个 记 录 的 存 储 区, key = 学 号 % 1000 H(key)=key % 38 H(031)= 31 H(044)= 6 H(032)=32 H(045)= 7 H(033)= 33 H(046)= 8... H(069)= 31 H(071)=33 //031 和 069 是 同 义 词, 散 列 时 产 生 冲 突 通 常, 选 择 p m 的 某 个 质 23
47 字 分 析 法 假 设 关 键 字 是 以 r 为 基 的, 并 且 哈 希 表 中 可 能 出 现 的 关 键 字 都 是 事 先 知 道 的, 则 可 取 关 键 字 的 若 干 位 组 成 哈 希 地 址 平 方 取 中 法 取 关 键 字 平 方 后 的 中 间 几 位 为 哈 希 地 址 折 叠 法 将 关 键 字 分 割 成 位 相 同 的 几 部 分, 然 后 取 这 几 部 分 的 叠 加 和 随 机 法 选 择 一 个 随 机 函, 取 关 键 字 的 随 机 函 值 为 它 的 哈 希 地 址 即 : H(key)=random(key) 48 处 理 冲 突 的 方 法 开 放 地 址 法 :( 探 测 法 ) Hi=(H(key)+di) mod m (1) 线 性 探 测 再 散 列 :di=1,2,3,4,...,m-1 (2) 二 次 探 测 再 散 列 :di=±k*k ( 1 k m/2) (3) 伪 随 机 探 测 再 散 列 :di= 伪 随 机 列 再 哈 希 法 : 用 另 一 个 哈 希 函 2 计 算 地 址, 直 到 冲 突 不 再 发 生 链 地 址 法 : 将 所 有 的 关 键 字 为 同 义 词 的 记 录 存 储 在 同 一 线 性 链 表 中 建 立 一 个 公 共 溢 出 区 :Hash 表 分 为 基 本 表 和 溢 出 表, 所 有 发 生 冲 突 的 关 键 字 都 填 入 溢 出 表 24
49 例 : 长 度 为 16 的 哈 希 表 中 已 有 关 键 字 节 19,70,33, H(key)= key mod 13, 现 有 18, 用 开 放 地 址 法 处 理 冲 突 解 : 其 处 理 方 法 如 下 图 所 示 0 1 2 3 4 5 6 7 8 9 10 11 12 15 18 70 19 33 18 二 次 探 测 线 性 探 测 50 例 :H(key)= key mod 13, 采 用 线 性 探 测 再 散 列 法 处 理 冲 突, m=16 对 关 键 字 19,14,23,01,68,20,84,27,55,11,10,79 19,14,23,01,68,20,84,27,55,11,10,79 6 1 10 1 3 7 6 1 3 11 10 1 2 7 2 4 11 2 8 3 5 12 3 4 4... 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 14 01 68 27 55 19 20 84 79 23 11 10 25
H(key)= key mod 13 51 对 关 键 字 19,14,23,01,68,20,84,27,55,11,10,79 链 地 址 法 处 理 的 果 为 : 0 1 79 27 01 14 2 3 4 5 55 68 6 7 84 19 8 20 9 10 11 10 23 12 11 Hash 表 52 H(key)= key mod 13 对 关 键 字 19,14,23, 01,68,20,84,27, 55,11,10,79 公 共 溢 出 区 法 处 理 的 果 为 : 0 1 2 3 4 5 6 7 8 9 10 14 68 19 20 23 溢 出 表 01 84 27 55 10 79 顺 序 11 12 11 26
53 两 种 方 法 平 均 长 度 的 比 较 : 链 地 址 法 : ASL(12)=(1*6+2*4+3+4)/12=1.75 线 性 探 测 再 散 列 : ASL(12)=(1*6+2+3*3+4+9)/12=2.5 因 此, 线 性 探 测 在 散 列 在 处 理 冲 突 的 过 程 中 易 产 生 记 录 的 二 次 聚 集, 而 链 地 址 法 处 理 冲 突 时 不 会 发 生 类 似 情 况, 故 其 平 均 长 度 较 优 54 哈 希 表 算 法 描 述 1. 计 算 哈 希 地 址 #define ListLen 13 int Hash(int key) { return(key %Listlen); } 2. 哈 希 表 int Search_H(int A[ ], int key){ k=hash(key); for (i=0;i<listlen ;i++) { j=(k+i)%listlen; if (A[ j]==0 key==a[j] ) return j; } return k; } 27
55 3. 在 哈 希 表 中 插 入 关 键 字 key Insert_Hash( int H[ ] ; int key ){ k=search_h( H, key); if ( H[k]==0 ) H[k]=key ; else if (key==h[k]) printf( 表 中 已 存 在 该 关 键 字 ); else printf( 哈 希 表 已 满!! ); } main( ) { int H[ListLen], i, key; for( i=0; i<listlen; i++) H[ i ]=0; // 置 空 for(i=0;i<listlen-2 ; i++){ scanf( %d, &key); Insert_Hash(H, key); } } 56 哈 希 表 哈 希 函 造 处 理 冲 突 性 能 分 析 举 例 哈 希 (Hash) 表 定 义 直 接 定 址 法 字 分 析 法 开 放 定 址 法 若 中 存 在 和 K 相 等 的 纪 录, 则 必 定 在 f(k) 的 存 储 位 置 上, 由 此 不 需 要 进 行 比 较 便 可 直 接 取 得 所 记 录 我 们 称 f 为 哈 希 函, 这 种 思 想 形 成 的 表 叫 哈 希 表 平 方 取 中 法 再 哈 希 法 折 叠 法 链 地 址 法 除 留 余 法 公 共 溢 出 区 随 机 法 28
Hash 表 要 求 掌 握 的 内 容 57 1. 熟 练 掌 握 除 留 余 法, 会 造 Hash 函 2. 根 哈 希 函 和 处 理 冲 突 的 方 法, (1) 手 工 造 已 知 序 列 的 哈 希 表 (2) 编 写 造 哈 希 表 的 算 法 (3) 编 写 在 哈 希 表 上 的 算 法 ; (4) 在 记 录 的 概 率 相 等 的 前 提 下, 计 算 哈 希 表 平 均 长 度 本 章 重 点 58 与 有 关 的 基 本 概 念 及 存 储 静 态 表 : 顺 序 表 的, 有 序 表 的, 索 引 顺 序 表 的 动 态 表 : 二 叉 排 序 树 的 造 过 程, 插 入 及 删 除 操 作 ; 平 衡 二 叉 树 几 种 类 型 的 调 整 ;B- 树 的 定 义, 插 入 及 删 除 操 作 各 种 方 法 的 性 能 比 较 哈 希 函 及 哈 希 表 ; 哈 希 函 的 造 方 法 ; 处 理 冲 突 的 方 法 29
第 九 章 作 业 60 作 业 1. 已 知 一 组 关 键 字 为 (38,65,20,18,50,90,35, 80,100,95,61,19), 依 次 插 入 关 键 字 生 成 一 棵 二 叉 排 序 树, 问 : (1) 关 键 字 等 于 61 的 点 记 录 需 比 较 次 ; (2) 与 61 比 较 的 关 键 字 序 列 是 ; (3) 如 果 将 关 键 字 为 85 的 记 录 插 入 到 树 中, 它 将 作 为 点 的 孩 子 点 ; (4) 若 要 删 除 关 键 字 为 65 的 记 录, 可 以 取 或 替 换 65 作 为 38 点 的 右 子 树 的 根 2. 什 么 叫 平 衡 二 叉 树? 试 按 下 列 次 序 将 各 关 键 字 插 入 到 平 衡 二 叉 树 中, 画 出 重 新 平 衡 的 情 况 ( 8,9,10,2,1,5,3,6,4,7,11,12) 30
61 编 写 算 法 1. 在 二 叉 排 序 树 T( 二 叉 链 存 储 ) 中 插 入 一 个 点 p; 2. 在 二 叉 排 序 树 T 中 删 除 任 一 点 q; 3. 根 给 定 关 键 字 序 列, 生 成 一 棵 二 叉 排 序 树 4. 分 别 对 LL 型 RR 型 LR 型 RL 型 的 二 叉 排 序 树 T( T 所 指 点 的 平 衡 因 子 为 2 或 -2 ) 进 行 平 衡 化 处 理 5. 设 计 实 现 分 块 的 算 法 62 哈 希 表 作 业 设 哈 希 表 长 为 13, 散 列 函 为 H(k)=k mod 13, 关 键 字 序 列 为 7,4,1,14,100,30,5,9, 20,134; 试 求 : (1) 散 列 后 的 表 中 关 键 字 分 布 ( 假 定 解 决 冲 突 的 方 法 为 线 性 探 测 再 散 列 法 ); 求 平 均 长 度 ASL; (2) 求 出 散 列 后 的 表 的 装 填 因 子 ; (3) 用 链 地 址 法 解 决 冲 突, 给 出 相 应 的 哈 希 表, 求 ASL; (4) 分 别 计 算 该 序 列 用 顺 序 法 和 排 序 后 用 折 半 的 ASL 31
实 验 六 : 实 验 掌 握 并 实 现 算 法 ( 顺 序 算 法 折 半 哈 希 表 的 实 现 ), 并 对 各 种 技 术 的 时 间 空 间 复 杂 性 有 进 一 步 认 识 63 32