数据结构 二叉排序树.ppt

1 若它的左子树不空 则左子树上所有结点的值均小于根结点的值 1 定义 二叉排序树 二叉搜索树或二叉查找树 或者是一棵空树 或者是具有如下特性的二叉树 3 它的左 右子树也都分别是二叉排序树 2 若它的右子树不空 则右子树上所有结点的值均大于等于根结点的值 9 4二叉排序树 例如 是二叉排序树 不 对二叉排序树进行中序遍历 得到一个有序序列 1 若给定值等于根结点的关键字 则查找成功 2 若给定值小于根结点的关键字 则继续在左子树上进行查找 3 若给定值大于根结点的关键字 则继续在右子树上进行查找 否则 若二叉排序树为空 则查找不成功 2 二叉排序树的查找算法 例如 二叉排序树 查找关键字 50 50 50 35 50 30 40 35 50 90 50 80 90 95 二叉链表类型定义 typedefstructBiTNode KeyTypekey 其它成员structBiTNode lchild structBiTNode rchild BiTNode BiTree 二叉排序树的查找 BiTreebstsrch BiTreebt KeyTypek 二叉排序树的存储结构为二叉链表 函数返回结点的 关键字为k的指针 若查找不成功 返回空指针if t NULL returnNULL elseif bt key k return bt elseif bt key k return bstsrch bt rchild k elsereturn bstsrch bt lchild k 3 二叉排序树的构造特点 树结构在查找的过程中动态生成 每次插入的结点只能成为新的叶子结点例 关键字序列为 45 24 53 12 14 90 45 中序遍历 12 14 24 45 53 90 1 插入算法 statusins bstree BiTree bt BiTrees 将指针s所指的结点插入到根指针为bt的二叉排序树中if bt NULL bt s 若bt为空树 则s为根elseif s key bt key ins bstree bt lchild s elseins bstree bt rchild s 2 生成二叉排序树的算法 BiTreecrt bstree BiTree crt bstree 1 被删除的结点是叶子 2 被删除的结点只有左子树或者只有右子树 3 被删除的结点既有左子树 也有右子树 4 二叉排序树的删除算法 可分三种情况讨论 删除一个结点后 仍是二叉排序树 1 被删除的结点是叶子结点 例如 被删关键字 20 88 其双亲结点中相应指针域的值改为 空 2 被删除结点只有左子树或者只有右子树 p只有左子树 f rchild p lchild p只有右子树 f rchild p rchild 被删关键字 40 80 40 40 以其前驱替代之 然后再删除该前驱结点 被删结点 前驱结点 被删关键字 50 某结点的前驱一定在它的左子树的最右下方 3 被删除的结点既有左子树 也有右子树 5 二叉排序树的查找分析 比较次数 被查结点所在的层次数 二叉排序树的性能取决于树的形态 而二叉树的形态取决于插入结点的顺序 关键字序列 45 24 53 12 37 90 ASL 1 2 2 3 3 6 14 6 例 关键字序列 12 24 37 45 53 90 其二叉排序树为 ASL 1 2 3 4 5 6 6 21 6 12 二叉排序树的性能取决于树的形态 而二叉树的形态取决于插入结点的顺序 构造一棵接近理想平衡树的二叉排序树 平衡二叉树 AVL树 对于每个结点 左子树的深度 右子树的深度 1结点的平衡因子 左子树的深度 右子树的深度AVL树中所有结点的平衡因子只有三种值 1 0 1 是平衡树 问 平衡树是理想平衡树吗 不是平衡树 9 5平衡二叉树 如何检测二叉树是否失去平衡 当插入一个新结点时 重新计算从新插入的结点到根结点的路径上所包含结点的平衡因子 bf 如果某一结点的bf的绝对值超过1 则二叉树失去平衡 0 1 2 失去平衡 如何使失去平衡的二叉树达到平衡 需进行调整 四种调整类型 设x为插入结点 A结点为离插入结点x最近的一个失衡结点 X BL B BR A AR X AL A BL B BR X X BL B CL C CR A AR X X AL A CL C CR B BR 例 按下列关键字的次序生成一棵AVL树 13 24 37 90 53 28 98 13 13 插入点插入后结果失衡原因调整 24 37 53 90 28 98 哈希表的基本思想 一次 查找成功 ASL的T n O 1 通常设定一个一维数组空间存储记录集合 则H key 指示数组中的下标 称这个一维数组为哈希 Hash 表或散列表 称映射函数H为哈希函数 H key 为哈希地址 9 6 1什么是哈希表 9 6哈希表 例1 已知一个含100个记录的文件 其关键字均由两位十进制数字组成 则可将此文件存储在如下说明的哈希表中 rectypehashtable 100 其中 hashtable i 存放关键字为i的记录 构造这个哈希表的哈希函数为 Hash1 key key Zhao Qian Sun Li Wu Chen Han Yan Dai 例2 对于如下9个关键字 设哈希函数 f key 字符串中首字母 A 1 2 Chen Zhao Qian Sun Li Wu Han Yan Dai 问题 若添加关键字Zhou 怎么办 能否找到另一个哈希函数 例 假定一个线性表为 A 18 75 60 43 54 90 46 假定选取的哈希函数为hash3 key key 13若根据哈希函数把元素存储到哈希表H 13 中 则存储映象为 18 75 60 43 54 90 46 哈希表的查找同插入元素一样 如从表中查找关键字为60的元素时 只要利用上面的函数计算出地址H 60 60 13 8查找不成功 查找61 H 61 61 13 9 如果key1 key2 但H key1 H key2 这种现象称为 冲突 称key1和key2为同义词 在实际应用中 应尽量选择均匀的哈希函数来减少冲突 冲突不能避免时 选定一个解决冲突的方法 1 装填因子 loadfactor 负载因子 m为hash表的长度 n为填入的记录数 越大 冲突的可能性越大 越小 冲突的可能性会减小 但空间的利用率变低 为兼顾两者 在 0 6 0 9 范围内为宜 2 与采用的散列函数有关 3 与解决冲突的方法有关 方法选择的好坏也将减少或增加发生冲突的可能性 发生冲突与下列三个因素有关 9 6 2哈希函数的构造方法 构造哈希函数的目标 哈希地址尽可能均匀分布在表空间上 均匀性好 哈希地址计算尽量简单 考虑因素 函数的复杂度 关键字长度与表长的关系 关键字分布情况 元素的查找频率 例 1949年后出生的人口调查表 关键字是年份年份194919501951 人数 H key key 1948 此法仅适合于 地址集合的大小 关键字集合的大小 一 直接地址法取关键字或关键字的某个线性函数值为哈希地址即 H key key或 H key a key b其中 a b为常数 常用的构造哈希 散列 函数的方法 二 数字分析法 例如 有若干记录 关键字为8位十进制数 假设哈希表的表长为100 对关键字进行分析 取随机性较好的两位十进制数作为哈希地址 假设关键字集合中的每个关键字都是由s位数字组成 u1 u2 us 分析关键字集中的全体 并从中提取分布均匀的若干位或它们的组合作为地址 此方法仅适合于 能预先估计出全体关键字的每一位上各种数字出现的频度 三 平方取中法将k平方后的中间几位取为哈希地址 位数由表长决定 例1 时间8 40 02 m 84002 m 2 705633604 例2 四位字母标识符的hash地址 地址空间为0 999用两位数字01 26表示对应的26个字母 如 AABB的内部代码 01010202 关键字内部代码 内部代码 2H key KEYA11052501122157778355001778KEYB11052502122157800460004800AKEY01110525001233265775625265BKEY02110525004454315775625315 四 折叠法将关键字分割成位数相同的几部分 然后将这几部分叠加 舍去进位作为哈希地址 适用于关键字位数很多 而且关键字中每一位上数字分布大致均匀的情况 移位叠加 将分割之后的每一部分的最低位对齐 然后相加 间界叠加 从一端向令一端沿分割界来回折叠 然后相加 此方法适合于 关键字的数字位数特别多 例如 有一国际标准编号0 44220586 4 五 除留余数法当关键字k为整数时 用关键字除以一个整数p所得余数作为哈希的地址 H key key p p的选择很重要 若选得不好容易产生冲突 例如 p 10k k 1 2 或p为偶数等由经验可知 取p为素数 p为不超过散列表的长度m的最大素数 例如 可以让p m 并取m为素数 由于 的取值最好在 0 6 0 9 0 6 0 9 m 1 1 n m 1 7 n 例 若n 100 则m最好取113 127 139 143等素数 设定哈希函数为 H key Random key 其中 Random为伪随机函数 六 随机数法 通常 此方法用于对长度不等的关键字构造哈希函数 9 6 3处理冲突的方法 设hash表的长度为m 冲突是指j H K 的位置已有记录 0 j m 1 处理冲突 既为K另找一个 空 的地址 方法1 线性探测再散列哈希表的存储结构 typedefstruct KeyTypekey 关键字成员 其它成员 elemtypetypedefelemtypehashtable m 哈希函数如下 H key key p利用下面的公式求 下一个 地址 Hi H key di m di 1 2 3 m 1例如 已知长度为13的哈希表 现有四个记录 其关键字分别为 19 70 33 18 701933 例如 已知长度为13的哈希表 现有四个记录 其关键字分别为 19 70 33 18 哈希函数为H key key 13 则H 19 6 H 70 5 H 33 7 H 18 5 用线性探测再散列方法解决冲突 H1 H key d1 13 5 1 13 6H2 5 2 13 7 H3 5 3 13 8 18 例如 关键字集合 19 01 23 14 55 68 11 82 36 设定哈希函数 H key key 11 表长 11 191 011 232 141 551 683 若采用线性探测再散列处理冲突 116 822 365 在查找概率相同的情况下 查找成功时的ASLASLsucc 1 4 2 2 3 5 6 9 22 9 若采用线性探测再散列处理冲突 平均查找长度ASL 线性探测再散列的优点 只要哈希表未满 总能找到一个空地址 缺点 会产生二次聚集 下一个hash地址为5 6 7 8时 将争夺地址为9的空间 三 链地址法将哈希表的每一个单元存放一个指针 将所有的同义词连成一个链表 假设哈希地址在区间 0 m 1 上 则哈希表为一个指针数组 typedefstructnode 定义链表中结点KeyTypekey 其它成员 structnode next Node Nodeptr typedefNodeptrchainhash m 定义指针数组 ASLsucc 6 1 2 2 3 9 13 9 例1 关键字