算法合集之《左偏树的特点及其应用》.ppt
《算法合集之《左偏树的特点及其应用》.ppt》由会员分享,可在线阅读,更多相关《算法合集之《左偏树的特点及其应用》.ppt(28页珍藏版)》请在三一文库上搜索。
1、左偏树的特点及其应用,广东省中山市第一中学 黄源河,2,左偏树的定义,左偏树(Leftist Tree)是一种可并堆(Mergeable Heap) ,它除了支持优先队列的三个基本操作(插入,删除,取最小节点),还支持一个很特殊的操作合并操作。 左偏树是一棵堆有序(Heap Ordered)二叉树。 左偏树满足左偏性质(Leftist Property)。,3,左偏树的定义 左偏性质,定义一棵左偏树中的外节点(External Node) 为左子树或右子树为空的节点。 定义节点 i 的距离(dist(i) 为节点 i 到它的后代中,最近的外节点所经过的边数。 任意节点的左子节点的距离不小于右子
2、节点的距离(左偏性质)。 由左偏性质可知,一个节点的距离等于以该节点为根的子树最右路径的长度。,4,左偏树的性质,定理:若一棵左偏树有N个节点,则该左偏树的距离不超过 log(N+1) -1。,最右路径: ACG 最右路径节点数 = 3 距离 = 2,8个节点的左偏树的最大距离:log(8+1) -1 = 2,5,左偏树的操作,左偏树支持下面这些操作: MakeNull 初始化一棵空的左偏树 Merge 合并两棵左偏树 Insert 插入一个新节点 Min 取得最小节点 DeleteMin 删除最小节点 Delete 删除任意已知节点 Decrease 减小一个节点的键值,6,左偏树的操作 合
3、并,合并操作是递归进行的,合并T1和T2两棵左偏树,先将T1的右子树与T2合并,7,左偏树的操作 合并,合并操作是递归进行的,a,L1,R,先将T1的右子树与T2合并,8,左偏树的操作 合并,合并操作是递归进行的,交换左右子树并更新根节点距离,合并后的右子树距离可能大于左子树距离,9,左偏树的操作 合并,合并操作的代码如下: Function Merge(A, B) If A = NULL Then return B If B = NULL Then return A If key(B) dist(left(A) Then swap(left(A), right(A) If right(A)
4、= NULL Then dist(A) 0 Else dist(A) dist(right(A) + 1 return A End Function,10,左偏树的操作 合并,下面是一个合并的例子:,11,左偏树的操作 合并,下面是一个合并的例子:,12,左偏树的操作 合并,下面是一个合并的例子:,13,左偏树的操作 合并,下面是一个合并的例子:,18,NULL,14,左偏树的操作 合并,下面是一个合并的例子:,37,7,0,1,?,15,左偏树的操作 合并,下面是一个合并的例子:,1,1,2,26,17,37,18,8,7,16,左偏树的操作 合并,下面是一个合并的例子:,0,2,?,17,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 左偏树的特点及其应用 算法 左偏树 特点 及其 应用
链接地址:https://www.31doc.com/p-3488298.html