《陈越全套配套课件数据结构 DS06 树b》由会员分享，可在线阅读，更多相关《陈越全套配套课件数据结构 DS06 树b（22页珍藏版）》请在金锄头文库上搜索。
1、第4章 树 4 4二叉搜索树 定义 一个二叉搜索树是一棵二叉树 它可以为空 如果不为空 它将满足以下性质 1 非空左子树的所有键值小于其根结点的键值 2 非空右子树的所有键值大于其根结点的键值 3 左 右子树都是二叉搜索树 二叉搜索树 二叉搜索树 BST Binary Search Tree 也称二叉排序树或二 叉查找树 它是一种对排序和查找都很有用的特殊二叉树 18 10 5 20 7 22 30 1541 33 50 6 3 147 9 5 10 2118 11个元素二分查找的判定树 1 二叉搜索树的动态查找 二叉搜索树作为抽象数据结构的定义与普通二叉树相同 但操作集 中多了下列几个特别的
2、函数 Position Find ElementType X BinTree BST 从二叉搜索树BST 中查找元素X 返回其所在结点的地址 Position FindMin BinTree BST 从二叉搜索树BST中查找并返回 最小元素所在结点的地址 Position FindMax BinTree BST 从二叉搜索树BST中查找并返回 最大元素所在结点的地址 第4章 树 4 4二叉搜索树 BinTree Insert ElementType X BinTree BST BinTree Delete ElementType X BinTree BST 2 二叉搜索树的查找操作Find 第
3、4章 树 4 4二叉搜索树 查找从根结点开始 如果树为空 返回NULL 表示未找到关键 字为X的结点 若搜索树非空 则根结点关键字和X进行比较 依据比较结果 需要进行不同的处理 若根结点键值小于X 满足条件的结点将不会出现在它的左子树 接下来的搜索只需在右子树中进行 如果根结点的键值大于X 接下来的搜索将在左子树中进行 若两者比较结果是相等 搜索完成 返回指向此结点的指针 Position Find ElementType X BinTree BST if BST return NULL 查找失败 if X BST Data return Find X BST Right 在右子树中继续查找
4、else if X Data return Find X BST Left 在左子树中继续查找 else X BST Data return BST 查找成功 返回找到的结点的地址 是否应当先考察空树 都是 尾递归 3 Position IterFind ElementType X BinTree BST while BST if X BST Data BST BST Right 向右子树中移动 继续查找 else if X Data BST BST Left 向左子树中移动 继续查找 else X BST Data return BST 查找成功 返回找到的结点的地址 return NULL
5、 查找失败 由于非递归函数的执行效率高 一般采用非递归的迭代来实现查找 很容易将 尾递归 函数改为迭代函数 第4章 树 4 4二叉搜索树 4 查找最大和最小元素 第4章 树 最大元素一定是在树的最右分枝的端结点上 最小元素一定是在树的最左分枝的端结点上 18 10 15 20 7 22 9 最左端点 最右端点 4 4二叉搜索树 5 第4章 树 4 4二叉搜索树 Position FindMax BinTree BST if BST while BST Right BST BST Right 沿右分支继续查找 直到最右叶结点 return BST Position FindMin BinTree
6、 BST if BST return NULL 空的二叉搜索树 返回NULL else if BST Left return BST 找到最左叶结点并返回 else return FindMin BST Left 沿左分支继续查找 代码4 16 查找最小元素的递归函数 代码4 17 查找最大元素的迭代函数 6 二叉搜索树的插入 第4章 树 4 4二叉搜索树 分析 将元素X插入二叉搜索树BST中 关键是要找到元素应该 插入的位置 位置的确定可以利用与查找函数Find类似的方法 如 果在树BST中找到X 说明要插入的元素已存在 可放弃插入操作 如果没找到X 查找终止的位置就是X应插入的位置 30
7、1541 33 50 35 30 1541 33 50 35 7 BinTree Insert ElementType X BinTree BST if BST 若原树为空 生成并返回一个结点的二叉搜索树 BST malloc sizeof struct TreeNode BST Data X BST Left BST Right NULL else 开始找要插入元素的位置 if X Data BST Left Insert X BST Left 递归插入左子树 else if X BST Data BST Right Insert X BST Right 递归插入右子树 else X已经存在
8、 什么都不做 return BST 第4章 树 4 4二叉搜索树 代码4 18 二叉搜索树的插入算法 8 例4 8 以一年十二个月的英文缩写为键值 按从一月到十二月顺序 输入它们 即输入序列为 Jan Feb Mar Apr May Jun July Aug Sep Oct Nov Dec 将产生什么样的二叉搜索树 第4章 树 4 4二叉搜索树 Jan Feb Apr Mar JunMay Dec Oct SeptJuly Aug Nov 9 二叉搜索树的删除 第4章 树 4 4二叉搜索树 二叉搜索树的删除操作比其它操作更为复杂 有三种情况需要考虑 要删除的是叶结点 可以直接删除 然后再修改其
9、父结点的指针 图4 28 二叉搜索树叶结点的删除 30 1541 33 50 35 要删除结点 例 删除 35 10 第4章 树 4 4二叉搜索树 图4 29 具有一个子树的结点删除 要删除的结点只有一个孩子结点 删除之前需要改变其父结点的 指针 指向要删除结点的孩子结点 要删除结点 只有一个孩子 30 1541 50 35 33 30 1541 50 35 例 删除 33 11 第4章 树 4 4二叉搜索树 图4 30 具有两个子树的结点删除 要删除的结点有左 右两棵子树 为了保持二叉搜索树的有序性 替代被删除的元素的位置可以有两种选择 一种是取其右子树中的最 小元素 另一个是取其左子树中的
10、最大元素 41 50 30 15 33 35 34 例 删除 41 a 取右子树中的最小元素替代 41 35 34 50 30 15 33 b 取左子树中的最大元素替代 12 BinTree Delete ElementType X BinTree BST Position Tmp if BST printf 要删删除的元素未找到 else if X Data BST Left Delete X BST Left 左子树递归删树递归删 除 else if X BST Data BST Right Delete X BST Right 右子树递归删树递归删 除 else 找到要删删除的结结点 i
11、f BST Left 在右子树树中找最小的元素填充删删除结结点 BST Data Tmp Data BST Right Delete BST Data BST Right 在删删除结结点的右子树树中删删除最小元素 else 被删删除结结点有一个或无子结结点 Tmp BST if BST Left 有右孩子或无子结结点 BST BST Right else if BST Right 有左孩子或无子结结点 BST BST Left free Tmp return BST 13 第4章 树 4 5 平衡二叉树 平衡二叉树 例 不同的插入次序 将导致不同的深度和平均查找长度ASL a 按一月到十二月的
12、自然月份序列输入所生成的 b 输入序列为 July Feb May Mar Aug Jan Apr Jun Oct Sept Nov Dec c 输入序列则是按月份字符串从小到大的顺序排列的 Jan Feb Mar Apr Aug Dec June July May Sept Oct Nov Jan FebMar Apr Aug Dec June July May Sept Oct Nov Apr Aug Oct Sept 按ASL的定义 可以分别计算出三棵二叉搜索树的平均查找长度 ASL a 1 2 2 3 3 4 3 5 2 6 1 12 3 5 ASL b 1 2 2 3 4 4 5 1
13、2 3 0 ASL c 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 12 6 5 查找二叉搜索树 BST 的时间复杂度 最坏情况下 用查 找过程中的比较次数来衡量 它取决于树的深度 14 平衡二叉树的定义 第4章 树 4 5 平衡二叉树 定义 对于二叉树中任一结点T 其 平衡因子 Balance Factor 简称 BF 定义为BF T hL hR 其中hL和hR分别为T的左 右子树的高度 平衡二叉树 Balanced Binary Tree 又称为 AVL树 AVL树或者是一棵空树 或者是具有下列性质的非空二叉搜索树 任一结点左 右子树高
14、度差的绝对值不超过1 即 BF T 1 6 4 5 8 1 9 2 7 2 5 8 1 6 4 4 5 6 3 2 17 15 Mar Mar 0 1 May May 0 Nov Nov 0 1 2 May 0 1 Nov 0 0 2 1 Mar 0 0 0 首个不平衡的 发现者 是Mar 未必是根结点 它是调整起点位置 而 麻烦结点 Nov 在发现者右子树的右边 因而叫 RR 插入 需要RR 旋转 右单旋 一般情况 设A是首个发现者 的调整方式如下 A 1 B 0 BLBR AL RR 插入 RR 旋转 A 2 B 1 BLBR AL BL B 0 A AL BR 0 右单旋 平衡二叉树的调
15、整 第4章 树 4 5 AVL树 16 Aug May 0 1 Nov 0 0 2 1 Mar 0 1 1 Aug 0 Apr Apr 0 1 2 2 LL旋转 左单旋 May 0 1 Nov 0 0 2 1 Aug 0 1 1 1 Mar 0 0 Apr 0 首个 发现者 是Mar 麻烦结点 Apr 在发现者左子树的左边 因而 叫 LL 插入 一般情况 设A是首个发现者 的调整方式如下 A 1 B 0 BRBL AR LL 插入 A 2 B 1 BRBL AR LL 旋转 B 0 A AR BL BR 0 第4章 树 4 5 AVL树 17 May 0 1 Nov 0 0 2 1 Aug 0
16、 1 1 1 Mar 0 0 Apr 0 Jan Jan 0 1 1 2 LR 旋转 Mar 0 1 May 0 1 2 1 Aug 0 1 0 1 Jan 0 0 Apr 0 Nov 0 首个 发现者 是May 麻烦结点 Jan在左子树的右边 因而叫 LR 插入 一般情况 设A是首个发现者 的调整如下 A 1 B 0 BL AR C 0 CRCL LR 插入 A 2 B 1 BL AR C 1 CRCL OR LR 旋转 BLAR C 0 A 1 or 0 CR B 0 or 1 CL OR 左 右双旋 第4章 树 4 5 AVL树 18 DecJuly Mar 0 1 May 0 1 2 1 Aug 0 1 1 1 Jan 0 Apr 0 Nov 0 July 0 Dec 0 Feb Feb 0 1 1 2 2 RL 旋转 July 0 Dec 0 1 Aug 0 1 2 1 Jan 0 1 0 1 Feb 0 0 Apr 0 Mar 0 1 May 0 1 2 1 1 Nov 0 一般情况调整如下 A 1 B 0 BR AL C 0 CLCR RL 插入 A 2 B 1 BR A
