数据结构与算法（Python）-00/引子

Transcription

1 物理 结构 逻辑 结构 运算 -06/ 树及算法 刘云淮 北京大学大数据科学研究中心

2 目录 本章目标 树的例子 实现树 二叉堆实现的优先队列 二叉树应用 树遍历 二叉搜索树

3 本章目标 理解树数据结构及其应用 树用于实现 ADT Map 用列表来实现树 用类和引用来实现树 以递归方式实现树 用堆来实现优先队列

4 树的例子 在学习了栈 队列等线性数据结构, 以及递归算法之后 ; 本章我们来讨论一种基本的 非线性 数据结构 树 ; 树在计算机科学的各个领域中被广泛应用 操作系统 图形学 数据库管理系统 计算机网络 跟自然界中的树一样, 数据结构树也分为 : 根 枝和叶等三个部分 但一般数据结构的图示把根放在上方 叶放在下方

5 树

6 树

7 树的例子 : 生物学物种分类体系 首先我们看到分类体系是层次化的 树是一种分层结构越接近顶部的层越普遍越接近底部的层越独特界 门 纲 目 科 属 种 分类树的用法 : 辨认物种从顶端开始, 沿着箭头方向向下 门 : 脊索动物还是节肢动物? 纲 : 哺乳动物么? 目 : 食肉动物? 科 : 猫科? 属 : 猫属? 种 : 家猫!

8 树的例子 : 生物学物种分类体系 分类树的第二个特征 : 一个节点的子节点与另一个节点的子节点相互之间是隔离 独立的 猫属 Felis 和蝇属 Musca 下面都有 Domestica 的同名节点 但相互之间并无任何关联, 可以修改其中一个 Domestica 而不影响另一个 分类树的第三个特征 : 每一个叶节点都具有唯一性 可以用从根开始到达每个种的完全路径来唯一标识每个物种动物界 -> 脊索门 -> 哺乳纲 -> 食肉目 -> 猫科 -> 猫属 -> 家猫种 Animalia->Chordate->Mammal->Carnivora->Felidae->Felis->Domestica

9 树的例子 : 文件系统 :Linux

10 树的例子 : 文件系统 :Windows Windows\ Program Files\ C:\ Python27\ System32\ Fonts\ Temp\ Drivers\ Lib\ Doc\ Tools\ etc\ hosts

11 树的例子 :HTML 文档 ( 嵌套标记

12 树的例子 : 域名体系 ICANN.com.cn.name... google apple facebook edu chenbin www mail pku tsinghua ruc www www its mail

13 术语与定义 节点 Node: 组成树的基本部分每个节点具有名称, 或 键值, 节点还可以保存额外数据项, 数据项根据不同的应用而变 边 Edge: 边是组成树的另一个基本部分每条边恰好连接两个节点, 表示节点之间具有关联, 边具有出入方向 ; 每个节点 ( 除根节点 恰有一条来自另一节点的入边 ; 每个节点可以有多条连到其它节点的出边 根 Root: 树中唯一一个没有入边的节点 路径 Path: 由边依次连接在一起的节点的有序列表如 : 哺乳纲 -> 食肉目 -> 猫科 -> 猫属, 是一条路径

14 术语与定义 子节点 Children: 入边均来自于同一个节点的若干节点, 称为这个节点的子节点 父节点 Parent: 一个节点是其所有出边所连接节点的父节点 兄弟节点 Sibling: 具有同一个父节点的节点之间称为兄弟节点 子树 Subtree: 一个节点和其所有子孙节点, 以及相关边的集合 0 根 1 B 2 D E C F

15 术语与定义 叶节点 Leaf Node: 没有子节点的节点称为叶节点 层级 Level: 从根节点开始到达一个节点的路径, 所包含的边的数量, 称为这个节点的层级 如 D 的层级为 2, 根节点的层级为 0 高度 Height: 树中所有节点的最大层级称为树的高度 如右图树的高度为 2 0 根 1 B 2 D E C F

16 术语与定义 : 树的定义 1 树由若干节点, 以及两两连接节点的边组成, 并具有如下性质 : 其中一个节点被设定为根 ; 每个节点 n( 除根节点, 都恰连接一条来自 节点 p 的边,p 是 n 的父节点 ; 每个节点从根开始的路径是唯一的 如果每个节点最多有两个子节点, 这样的 树称为 二叉树 binary tree

17 术语与定义 : 树的定义 2( 递归定义 树是 : 空集 ; 或者由根节点及 0 或多个子树构成 ( 其中子 树也是树, 每个子树的根到根节点具有 边相连

18 实现树 : 嵌套列表法 首先我们尝试用 Python List 来实现二叉树树数据结构 ; 递归的嵌套列表实现二叉树, 由具有 3 个元素的列表实现 : 第 1 个元素为根节点的值 ; 第 2 个元素是左子树 ( 所以第 2 个元素是一个列表 ; 第 3 个元素是右子树 ( 所以第 3 个元素也是一个列表 以右图的示例, 一个 6 节点的二叉树 根是 mytree[0], 左子树 mytree[1], 右子树 mytree[1] 嵌套列表法的优点 子树的结构与树相同, 是一种递归数据结构 可以很容易扩展到多叉树, 仅需要增加列表元素即可

19 实现树 : 嵌套列表法 我们通过定义一系列函数来辅助操作嵌套列表 BinaryTree 创建仅有根节点的二叉树 insertleft/insertright 将新节点插入 树中作为其直接的左 / 右子节点 get/setrootval 则取得或返回根节点 getleft/rightchild 返回左 / 右子树

20 实现树 : 嵌套列表法 请画出 r 的图示 请通过图示讲解操作

21 实现树 : 节点链接法 同样可以用类似链表的节点链接法来实现树 每个节点保存根节点的数据项, 以及指向 左右子树的链接 定义一个 BinaryTree 类 成员 key 保存根节点数据项成员 left/rightchild 则保存指向左 / 右子树的引用 ( 同样是 BinaryTree 对象

22 实现树 : 节点链接法 insertleft/right 方法 过程与线性表的节点插入相似 请画出 r 的图示

23 树的应用 : 解析树 Parse Tree( 语法树 将树用于表示语言中句子, 可以分析句子的各种语法成分, 对句子的各种成分进行处理 语法分析树 主谓宾, 定状补 程序设计语言的编译 词法 语法检查 从语法树生成目标代码 自然语言处理 机器翻译 语义理解

24 树的应用 : 解析树 Parse Tree( 表达式树 我们还可以将表达式表示为树结构 叶节点保存操作数, 内部节点保存操作符 全括号表达式 ((7+3*(5-2 由于括号的存在, 需要计算 * 的话, 就必须先计算 7+3 和 5-2 表达式树的层次帮助我们了解表达式计算的优先级 越底层的表达式, 优先级越高 树中每个子树都表示一个子表达式 将子树替换为子表达式值的节点, 即可实现求值

25 树的应用 : 表达式树 下面, 我们用树结构来做如下尝试从全括号表达式构建表达式解析树 利用表达式解析树对表达式求值 从表达式解析树恢复原表达式的字符串形式 首先, 全括号表达式要分解为单词 Token 列表其单词分为括号 ( 操作符 +-*/ 和操作数 0~9 这几类 左括号就是表达式的开始, 而右括号是表达式的结束

26 树的应用 : 表达式树 从左到右扫描全括号表达式的每个单词, 依据规则建立解析树如果当前单词是 "(": 为当前节点添加一个新节点作为其左子节点, 当前节点下降, 设为这个新节点 如果当前单词是操作符 ['+','-','/','*']: 将当前节点的值设为此符号, 为当前节点添加一个新节点作为其右子节点, 当前节点下降, 设为这个新节点 如果当前单词是操作数 : 将当前节点的值设为此数, 当前节点上升返回到父节点 如果当前单词是 "": 则当前节点上升返回到父节点

27 从全括号表达式建立表达式解析树 : 图示 全括号表达式 :(3+(4*5 分解为单词表 ['(', '3', '+', '(', '4', '*', '5','',''] 创建表达式解析树过程 创建空树, 当前节点为根节点 读入 '(', 创建了左子节点, 当前节点下降 读入 '3', 当前节点设置为 3, 上升到父节 点 读入 '+', 当前节点设置为 +, 创建右子节 点, 当前节点下降

28 从全括号表达式建立表达式解析树 : 图示 创建表达式解析树过程 读入 '(', 创建左子节点, 当前节点下降 读入 '4', 当前节点设置为 4, 上升到父节点 读入 '*', 当前节点设置为 *, 创建右子节点, 当前节点下降 读入 '5', 当前节点设置为 5, 上升到父节点 读入 '', 上升到父节点

29 从全括号表达式建立表达式解析树 : 思路 从图示过程中我们看到, 创建树过程中关键的是对当前节点的跟踪 当前节点创建左右子树, 可以调用 BinaryTree.insertLeft/Right 当前节点设置值, 可以调用 BinaryTree.setRootVal 当前节点下降到左右子树, 可以调用 BinaryTree.getLeft/RightChild 但是, 当前节点上升到父节点, 这个没有方法支持! 我们可以用一个栈来记录跟踪父节点 当前节点下降时, 将下降前的节点 push 入栈 当前节点需要上升到父节点时, 上升到 pop 出栈的节点即可!

30 从全括号表达式建立表达式解析树 : 代码 分解单词空树表达式开始操作数 入栈下降 入栈下降 操作符 出栈上升 表达式结束 出栈上升

31 利用表达式解析树求值 : 思路 创建了表达式解析树之后, 我们可以用来进行表达式求值 由于 BinaryTree 是一个递归数据结构, 自然地, 可以用递归算法来处理 BinaryTree, 包括求值函数 evaluate 由前述对子表达式的描述, 可以从树的底层子树开始, 逐步向上层求值, 最终得到整个表达 式的值 求值函数 evaluate 的递归三要素 : 基本结束条件 : 叶节点是最简单的子树, 没有左右子节点, 其根节点的数据项即为子表达式 树的值 缩小规模 : 将表达式树分为左子树 右子树, 即为缩小规模 调用自身 : 分别调用 evaluate 计算左子树和右子树的值, 其基本操作是将左右子树的值依 根节点的操作符进行计算, 从而得到表达式的值

32 利用表达式解析树求值 : 思路 一个增加程序可读性的技巧 : 函数引用 import operator op= operator.add

33 利用表达式解析树求值 : 代码 缩小规模 递归调用 基本结束条件

34 树的遍历 Tree Traversals 线性数据结构中, 对其所有数据项的访问比较简单直接, 对树中所有节点进行访问的操作称为 遍历 Traversal 树的非线性特点, 使得遍历操作较为复杂, 我们按照对节点访问次序的不同来区分 3 种遍历 前序遍历 (preorder: 先访问根节点, 再递归地前序访问左子树 最后前序访问右子树 ; 中序遍历 (inorder: 先递归地中序访问左子树, 再访问根节点, 最后中序访问右子树 ; 后序遍历 (postorder: 先递归地后序访问左子树, 再后序访问右子树, 最后访问根节点

35 前序遍历的例子 : 一本书的章节阅读 Book-> Ch1-> S1.1-> S1.2-> S1.2.1-> S1.2.2-> Ch2-> S2.1-> S2.2-> S2.2.1-> S2.2.2

36 树的遍历 : 递归算法代码 树遍历的代码非常简洁! 也可以在 BinaryTree 类中实现前序遍历的方法 : 需要加入子树是否为空的判断 后序遍历和中序遍历的代码仅需要调整语句顺序 :

37 后序遍历 : 表达式求值 回顾前述的表达式解析树求值, 实际上也是一个后序遍历的过程, 只是代码没有明显表现出遍历的次序 采用后序遍历法重写表达式求值代码 : 左子树右子树 根节点

38 中序遍历 : 生成全括号中缀表达式 采用中序遍历递归算法来生成全括号中缀表达式 下列代码中对每个数字也加了括号, 请自行修改代码去除 ( 课后练习

39 优先队列 Priority Queue 在第 3 章我们学习了一种 FIFO 数据结构队列 queue 队列有一种变体称为 优先队列 银行窗口取号,VIP 客户优先级高, 可以插 到队首 操作系统中执行关键任务的进程或用户特 别指定进程在调度队列中靠前

40 优先队列 Priority Queue 优先队列的出队 dequeue 操作跟队列一样, 都是从队首出队 ; 但在优先队列内部, 数据项的次序却是由 优先级 来确定 : 高优先级的数据项排在队首, 而低优先级的数据项则排在后面 这样, 优先队列的入队操作就比较复杂, 需要将数据项根据其优先级尽量挤到队列前方 思考 : 有什么方案可以用来实现优先队列? 出队和入队的复杂度大概是多少?

41 二叉堆 Binary Heap 实现优先队列 实现优先队列的经典方案是采用二叉堆数据结构二叉堆能够将优先队列的入队和出队复杂度都保持在 O(log n 二叉堆的有趣之处在于, 其逻辑结构上象二叉树, 却是用非嵌套的列表来实现的! 最小 key 排在队首的称为 最小堆 min heap 反之, 最大 key 排在队首的是 最大堆 max heap ADT BinaryHeap 的操作定义如下 : BinaryHeap(: 创建一个空二叉堆对象 ; insert(k: 将新 key 加入到堆中 ; findmin(: 返回堆中的最小项, 最小项仍保留在堆中 ; delmin(: 返回堆中的最小项, 同时从堆中删除 ; isempty(: 返回堆是否为空 ; size(: 返回堆中 key 的个数 ; buildheap(list: 从一个 key 列表创建新堆

42 ADT BinaryHeap 的操作示例

43 用非嵌套列表实现二叉堆 为了使堆操作能保持在对数水平上, 就必须采用二叉树结构 ; 同样, 如果要使操作始终保持在对数数量级上, 就必须始终保持二叉树的 平衡 树根左右子树拥有相同数量的节点 我们采用 完全二叉树 的结构来近似实现 平衡 完全二叉树, 指每个内部节点都有两个子节点, 最多可有 1 个节点例外

44 完全二叉树的列表实现及性质 完全二叉树由于其特殊性, 可以用非嵌套列表, 以简单的方式实现, 并具有很好的性质 : 如果节点在列表中的下标为 p, 那么其左子节点下标为 2p, 右子节点为 2p+1 如果节点在列表中下标为 n, 那么其父节点下标为 n//

45 堆次序 Heap Order 所谓 堆 的特性, 是指堆中任何一个节点 x, 其父节点 p 中的 key 均小于等于 x 中的 key 这样, 符合 堆 性质的二叉树, 其中任何一条路径, 均是一个已排序数列 符合 堆 性质的二叉树, 其树根节点中的 key 最小

46 二叉堆操作的实现 二叉堆初始化 采用一个列表来保存堆数据, 其中表首下标为 0 的项无用, 但为了后面代码可以用到简单的 整数乘除法, 仍保留它 insert(key 方法 首先, 为了保持 完全二叉树 的性质, 新 key 应该添加到列表末尾 问题?

47 二叉堆操作的实现 insert(key 方法 但是, 新 key 简单地加在列表末尾, 显然无法保持 堆 次序 虽然对其它路径的次序没有影响, 但对于其到根的路径可能破坏次序 于是需要将新 key 沿着路径来 上浮 到其正确位置 注意 : 新 key 的 上浮 不会影响其它路径节点的 堆 次序

48 二叉堆操作的实现 :insert 代码 与父节点交换 沿路径向上 添加到末尾 新 key 上浮

49 二叉堆操作的实现 delmin( 方法 首先, 移走整个堆中最小的 key 位于堆首位的根节点 heaplist[1] 为了保持 完全二叉树 的性质, 用最后一个节点来代替根节点 问题?

50 二叉堆操作的实现 delmin( 方法 同样, 这么简单的替换, 还是破坏了 堆 次序 解决方法 : 将新的根节点沿着一条路径 下沉, 直到比两个子节点都小 下沉 路径的选择 : 如果比子节点大, 那么选择较小的子节点交换下沉

51 二叉堆操作的实现 :delmin 代码 交换下沉 沿路径向下 唯一子节点 返回较小的 移走堆顶 新顶下沉

52 二叉堆操作的实现 buildheap(lst 方法 : 从无序表生成 堆 我们最自然的想法是 : 用 insert(key 方法, 将无序表中的数据项逐个 insert 到堆中, 但 这么做的总代价是 O(nlog n 其实, 用 下沉 法, 能够将总代价控制在 O(n 从最后节点的父节点开始因叶节点无需下沉

53 二叉堆操作的实现 思考 : 利用二叉堆来进行排序? 堆排序 算法 :O(nlog n

54 二叉搜索树 Binary Search Tree 在 ADT Map 的实现方案中, 可以采用不同的数据结构和搜索算法来保存和查找 Key, 前面已经实现了两个方案有序表数据结构 + 二分搜索算法 散列表数据结构 + 散列及冲突解决算法 下面我们来试试用二叉搜索树保存 key, 实现 key 的快速搜索

55 二叉搜索树 Binary Search Tree:ADT Map 复习一下 ADT Map 的操作 : Map(: 创建一个空映射 put(key, val: 将 key-val 关联对加入映射中, 如果 key 已经存在, 则将 val 替换原来的旧关联值 ; get(key: 给定 key, 返回关联的数据值, 如不存在, 则返回 None; del: 通过 del map[key] 的语句形式删除 key-val 关联 ; len(: 返回映射中 key-val 关联的数目 ; in: 通过 key in map 的语句形式, 返回 key 是否存在于关联中, 布尔值

56 二叉搜索树 BST 的性质 比父节点小的 key 都出现在左子树, 比父节点大的 key 都出现在右子树 右图是一个简单的 BST, 按照 70,31,93,94,14,23,73 的顺序插入 首先插入的 70 成为树根 31 比 70 小, 放到左子节点 93 比 70 大, 放到右子节点 94 比 93 大, 放到右子节点 14 比 31 小, 放到左子节点 23 比 14 大, 放到其右 73 比 93 小, 放到其左 注意 : 插入顺序不同, 生成的 BST 也不同!

57 二叉搜索树的实现 : 节点和链接结构 需要用到 BST 和 Node 两个类,BST 的 root 成员引用根节点 Node class BinarySearchTree root 引用 TreeNode 对象 size 表示节点总个数 iter ( 以后再说

58 二叉搜索树的实现 :TreeNode 类 class TreeNode key 为键值 payload 是 value left/rightchild 另外加了个 parent 引用

59 二叉搜索树的实现 :TreeNode 类

60 二叉搜索树的实现 :BST.put 方法 put(key, val 方法 : 插入 key 构造 BST 首先看 BST 是否为空, 如果一个节点都没有, 那么 key 成为根节点 root 否则, 就调用一个递归函数 _put(key, val, root 来放置 key _put(key, val, currentnode 的算法流程 如果 key 比 currentnode.key 小, 那么 _put 到 currentnode 左子树 但如果没有左子树, 那么 key 就成为左子节点如果 key 比 currentnode.key 大, 那么 _put 到 currentnode 右子树 但如果没有右子树, 那么 key 就成为右子节点

61 二叉搜索树的实现 :_put 辅助方法 注意! 这个代码没有处理插入重复 key 的情况 其实也就是把 val 替换一下的事 递归左子树 递归右子树 随手把 setitem 做了 : 可以 myziptree['pku'] =

62 二叉搜索树的实现 : BST.put 图示 插入 key=19,currentnode 的变化过程 ( 灰色 :

63 二叉搜索树的实现 : BST.get 方法 一旦 BST 构建起来, 下一个方法就是从树中按照 key 来取 val, 即在树中找到 key 所在的节点 从 root 开始, 递归向下, 直到找到, 或者下到最底层的叶节点也未找到 get 方法 查看 root 是否存在? 调用递归函数 _get _get 方法 空引用返回 None 匹配当前节点, 成功 否则递归进入左 / 右子树

64 二叉搜索树的实现 :BST.get 方法 getitem 特殊方法 实现 val= myziptree['pku'] contains 特殊方法 实现 'PKU' in myziptree 的集合判断运算符 in

65 二叉搜索树的实现 : BST.delete 方法 有增就有减, 最复杂的 delete 方法 : 首先, 看树中有多少节点, 超过 1 个的话, 就先用 _get 找到要删除的节点, 然后调用 remove 来删除, 找不到则提示错误 ; 如果仅有 1 个节点 ( 就是只有根节点了, 那就看是否匹配根 key, 能匹配的话就删除根节 点, 匹配不了则报错 delitem 特殊方法 实现 del myziptree['pku'] 这样的语句操作 复杂在 remove 方法!

66 二叉搜索树的实现 : BST.remove 方法 从 BST 中 remove 一个节点, 还仍然保持 BST 的性质, 分以下 3 种情形 节点没有子节点 节点有 1 个子节点 节点有 2 个子节点 没有子节点的情况好办, 直接删除

67 二叉搜索树的实现 : BST.remove 方法 第 2 种情形稍复杂 : 被删节点有 1 个子节点 解决 : 将这个唯一的子节点上移, 替换掉被删节点的位置 但替换操作需要区分几种情况 : 被删节点的子节点是左? 还是右子节点? 被删节点本身是其父节点的左? 还是右子节点? 被删节点本身就是根节点?

68 BST.remove 方法 左子节点删除 右子节点删除 根节点删除 左子节点删除 右子节点删除 根节点删除

69 二叉搜索树的实现 : BST.remove 方法 第 3 种情形最为复杂 : 被删节点有 2 个子节点 这时无法简单地将某个子节点上移替换被删节点 但可以找到另一个合适的节点来替换被删节点, 这个合适节点就是被删节点的下一个 key 值 节点, 即被删节点右子树中最小的那个, 称为 后继 可以肯定这个后继节点最多只有 1 个子节点 ( 本身是叶节点, 或仅有右子树 将这个后继节点摘出来 ( 也就是删除了, 替换掉被删节点

70 二叉搜索树的实现 : BST.remove 方法 BinarySearchTree 类 :remove 方法 ( 情形 3

71 二叉搜索树的实现 : BST.remove 方法 TreeNode 类 : 寻找后继节点 findsuccessor( 调用找到最小节点 findmin( 目前不会遇到 到左下角

72 二叉搜索树的实现 : BST.remove 方法 TreeNode 类 : 摘出节点 spliceout( 摘出叶节点 目前不会遇到 摘出带右子节点的节点

73 二叉搜索树的实现 : 迭代器 作为 Python 字典, 我们可以用 for i in dict: 这样的方法枚举字典中的所有 key,adt Map 也应该实现这样的迭代器功能 BinarySearchTree 类中的 iter 方法直接调用了 TreeNode 中的同名特殊方法

74 二叉搜索树的实现 : 迭代器 TreeNode 类中的 iter 迭代器 实际上是一个递归函数, 想到上节 BinaryTree 中的 str 递归方法么? yield 是对每次迭代的返回值

75 二叉搜索树 : 算法分析 ( 以 put 方法为例 其性能决定因素在于二叉搜索树的高度 ( 最大层次, 而其高度又受数据项 key 插入顺序的影响 如果 key 的列表是随机分布的话, 那么大于和小于根节点 key 的键值大致相等, 那么 BST 的高度就是 log 2 n(n 是节点的个数, 而且, 这样的树就是平衡树, put 方法最差性能为 O(log 2 n 但 key 列表分布极端情况就完全不同 按照从小到大顺序插入的话, 如右图 这时候 put 方法的性能为 O(n 其它方法也是类似情况 如何改进? 不受 key 插入顺序的影响?

76 平衡二叉搜索树 :AVL 树的定义 我们来看看能够在 key 插入时一直保持平衡的二叉搜索树 :AVL 树 AVL 是发明者的名字缩写 :G.M. Adelson-Velskii and E.M. Landis 利用 AVL 树实现 ADT Map, 基本上与 BST 的实现相同, 不同之处仅在于二叉树的生成与维护过程 AVL 树的实现中, 需要对每个节点跟踪 平衡因子 balance factor 参数, 平衡因子是根据节点的左右子树的高度来定义的, 确切地说, 是左右子树高度差 : balancefactor = height(leftsubtree height(rightsubtree 如果平衡因子大于 0, 称为 左重 left-heavy, 小于零称为 右重 right-heavy 平衡因子等于 0, 则称作平衡

77 平衡二叉搜索树 : 平衡因子 如果一个二叉搜索树中每个节点的平衡因子都在 -1,0,1 之间 则把这个二叉搜索树称为平衡树

78 平衡二叉搜索树 :AVL 树的定义 一旦在平衡树操作过程中, 有节点的平衡因子超出此范围, 则需要一个重新平衡的过程 要保持 BST 的性质! 左子树所有节点都小于根, 右子树都大于根 如右图是一个 右重 的不平衡树 思考 : 如果重新平衡, 应该变成什么样?

79 AVL 树的性能 实现 AVL 树之前, 来看看 AVL 树是否确实能够达到一个很好的性能 我们来分析 AVL 树最差情形下的性能 : 即平衡因子为 1 或者 -1 下图列出平衡因子为 1 的 左重 AVL 树, 树的高度从 1 开始, 来看看问题规模 ( 总节点数 N 和比对次数 ( 树的高度 h 之间的关系如何?

80 AVL 树性能分析 观察上图 h= 时, 总节点数 N 的变化 : h= 1, N= 1 h= 2, N= 2= 1+ 1 h= 3, N= 4= h= 4, N= 7= 观察这个通式, 很接近斐波那契数列! 定义斐波那契数列 Fi 利用 Fi 重写 Nh 斐波那契数列的性质 :Fi/Fi-1 趋向于黄金分割 Φ 可以写出 Fi 的通式

81 AVL 树性能分析 将 Fi 通式代入到 Nh 中, 得到 Nh 的通式 上述通式只有 N 和 h 了, 我们解出 h 可见, 在最差情况下,AVL 树在总节点数为 N 的搜索中, 最多需要 1.44 log(nh 的搜索次数 可以说 AVL 树的搜索时间复杂度为 O(log n

82 AVL 树的实现 既然 AVL 平衡树确实能够改进 BST 树的性能, 避免退化情形, 我们来看看向 AVL 树插入一个新 key, 如何才能保持 AVL 树的平衡性质 首先, 新 key 必定以叶节点形式插入到 AVL 树中 叶节点的平衡因子是 0, 其本身无需重新平衡 但会影响其父节点的平衡因子 : 如果作为左子节点插入, 则父节点平衡因子会增加 1; 如果作为右子节点插入, 则父节点平衡因子会减少 1 这种影响可能随着其父节点到根节点的路径一直传递上去, 直到 : 传递到根节点为止 ; 或者某个父节点平衡因子被调整到 0, 不再影响上层节点的平衡因子为止 ( 无论从 -1 或者 1 调整到 0, 都不会改变子树高度 将 AVL 树作为 BST 树子类实现,TreeNode 中增加 balancefactor

83 AVL 树的实现 :put 方法 重新定义 _put 方法即可 调整因子 调整因子

84 AVL 树的实现 :UpdateBalance 方法 重新平衡 调整父节点因子

85 AVL 树的实现 :rebalance 重新平衡 主要手段 : 将不平衡的子树进行旋转 rotation 视 左重 或者 右重 进行不同方向的旋转, 同时更新相关父节点引用 更新旋转后被影响节点的平衡因子 如图, 是一个 右重 子树 A 的左旋转 ( 并保持 BST 性质 将右子节点 B 提升为子树的根 将旧根节点 A 作为新根节点 B 的左子节点 如果新根节点 B 原来有左子节点, 则将此节点设置为 A 的右子节点 (A 的右子节点一定有空 ( 为什么?

86 AVL 树的实现 :rebalance 重新平衡 更复杂一些的情况 : 如图的 左重 子树右旋转 旋转后, 新根节点将旧根节点作为右子节点, 但是新根节点原来已有右子节点, 需要将原有 的右子节点重新定位! 原有的右子节点 D 改到旧根节点 E 的左子节点 同样,E 的左子节点在旋转后一定有空

87 AVL 树的实现 :rotateleft 代码 综合两种右重情形 仅有两个节点需要调整因子

88 AVL 树的实现 : 如何调整平衡因子 看看左旋转对平衡因子的影响 保持了次序 ABCDE ACE 的平衡因子不变 ha/hc/he 不变主要看 BD 新旧关系

89 AVL 树的实现 : 如何调整平衡因子 我们来看看 B 的变化 新 B= ha- hc 旧 B= ha- 旧 hd 而 : 旧 hd= 1+ max(hc, he, 所以旧 B= ha- (1+ max(hc, he 新 B- 旧 B= 1+ max(hc, he- hc 新 B= 旧 B+ 1+ max(hc, he- hc; 把 hc 移进 max 函数里就有 新 B= 旧 B+ 1+ max(0, - 旧 D <==> 新 B= 旧 B+ 1- min(0, 旧 D

90 AVL 树的实现 : 更复杂的情形 下图的 右重 子树, 单纯的左旋转无法实现平衡 左旋转后变成 左重 了 左重 再右旋转, 还回到 右重 所以, 在左旋转之前检查右子节点的因子 如果右子节点 左重 的话, 先对它进行右旋转 再实施原来的左旋转 同样, 在右旋转之前检查左子节点的因子 如果左子节点 右重 的话, 先对它进行左旋转 再实施原来的右旋转

91 AVL 树的实现 :rebalance 代码 右重需要左旋 右子节点左重先右旋 左重需要右旋 左子节点右重先左旋

92 AVL 树的实现 : 操练一下 如图所示的 右重 子树如何平衡? 请图示旋转过程

93 AVL 树的实现 : 结语 经过复杂的 put 方法,AVL 树始终维持平衡性质, 这样 get 方法也始终保持 O(log n 的高性能 不过,put 方法的代价有多大? 将 AVL 树的 put 方法分为两个部分 : 需要插入的新节点是叶节点, 更新其所有父节点和祖先节点的代价最多为 O(log n 如果插入的新节点引发了不平衡, 重新平衡最多需要 2 次旋转, 但旋转的代价与问题规模无 关, 是常数 O(1 所以整个 put 方法的时间复杂度还是 O(log n 课后练习 : 从 AVL 树删除一个节点, 如何保持平衡?

94 ADT Map 的实现方法小结 我们采用了多种数据结构和算法来实现 ADT Map, 其时间复杂度数量级如下表所示 : operation Sorted List Hash Table Binary Search Tree AVL Tree put O(n O(1 -> O(n O(log 2 n -> O(n O(log 2 n get O(log 2 n O(1 -> O(n O(log 2 n -> O(n O(log 2 n in O(log 2 n O(1 -> O(n O(log 2 n -> O(n O(log 2 n del O(n O(1 -> O(n O(log 2 n -> O(n O(log 2 n

95 本章总结 本章介绍了 树 数据结构, 我们讨论了如下算法 用于表达式解析和求值的二叉树 用于实现 ADT Map 的二叉搜索树 BST 树 改进了性能, 用于实现 ADT Map 的平衡二叉搜索树 AVL 树 实现了 最小堆 的完全二叉树 : 二叉堆