左偏堆的特点及其应用ppt课件.ppt

左偏树的特点及其应用 广东省中山市第一中学黄源河 1 2 左偏树的定义 左偏树 LeftistTree 是一种可并堆 MergeableHeap 它除了支持优先队列的三个基本操作 插入 删除 取最小节点 还支持一个很特殊的操作 合并操作 左偏树是一棵堆有序 HeapOrdered 二叉树 左偏树满足左偏性质 LeftistProperty 3 左偏树的定义 左偏性质 定义一棵左偏树中的外节点 ExternalNode 为左子树或右子树为空的节点 定义节点i的距离 dist i 为节点i到它的后代中 最近的外节点所经过的边数 任意节点的左子节点的距离不小于右子节点的距离 左偏性质 由左偏性质可知 一个节点的距离等于以该节点为根的子树最右路径的长度 4 左偏树的性质 定理 若一棵左偏树有N个节点 则该左偏树的距离不超过 log N 1 1 最右路径 A C G最右路径节点数 3距离 2 8个节点的左偏树的最大距离 log 8 1 1 2 5 左偏树的操作 左偏树支持下面这些操作 MakeNull 初始化一棵空的左偏树Merge 合并两棵左偏树Insert 插入一个新节点Min 取得最小节点DeleteMin 删除最小节点Delete 删除任意已知节点Decrease 减小一个节点的键值 6 左偏树的操作 合并 合并操作是递归进行的 合并T1和T2两棵左偏树 先将T1的右子树与T2合并 7 左偏树的操作 合并 合并操作是递归进行的 a L1 R 先将T1的右子树与T2合并 8 左偏树的操作 合并 合并操作是递归进行的 交换左右子树并更新根节点距离 合并后的右子树距离可能大于左子树距离 9 左偏树的操作 合并 合并操作的代码如下 FunctionMerge A B IfA NULLThenreturnBIfB NULLThenreturnAIfkey B dist left A Thenswap left A right A Ifright A NULLThendist A 0Elsedist A dist right A 1returnAEndFunction 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 左偏树的操作 合并 下面是一个合并的例子 3 10 2 0 1 18 左偏树的操作 合并 合并操作都是一直沿着两棵左偏树的最右路径进行的 一棵N个节点的左偏树 最右路径上最多有 log N 1 个节点 因此 合并操作的时间复杂度为 O logN1 logN2 O logN 19 左偏树的操作 插入 插入一个新节点把待插入节点作为一棵单节点左偏树合并两棵左偏树时间复杂度 O logN 20 左偏树的操作 删除 删除最小节点删除根节点合并左右子树时间复