6 左偏树.ppt

高级数据结构 ——左偏树 Leftist Trees Leftist Trees Linked binary tree. Can do everything a heap can do and in the same complexity. insert remove min (or max) initialize Can meld two leftist tree priority queues in O(log n) time. Extended Binary Trees Start with any binary tree and add an external node wherever there is an empty subtree. Result is an extended binary tree. A Binary Tree An Extended Binary Tree The Function s() For any node x in an extended binary tree, let s(x) be the length of a shortest path from x to an external node in the subtree rooted at x. s() Values Example s() Values Example Properties Of s() If x is an external node, then s(x) = 0. Otherwise, s(x) = min {s(leftChild(x)), s(rightChild(x))} + 1 Height Biased Leftist Trees A binary tree is a (height biased) leftist tree iff for every internal node x, s(leftChild(x)) = s(rightChild(x)) A Leftist Tree Leftist Trees – Property 1 In a leftist tree, the rightmost path is a shortest root to external node path and the length of this path is s(root). A Leftist Tree Leftist Trees—Property 2 The number of internal nodes is at least 2s(root) - 1 Because levels 1 through s(root) have no external nodes. A Leftist Tree Leftist Trees—Property 3 Length of rightmost path is O(log n), where n is the number of (internal) nodes in a leftist tree. Property 2 = n = 2s(root) – 1 = s(root) = log2(n+1) Property 1 = length of rightmost path is s(root). Leftist Trees As Priority Queues A Min Leftist Tree Some Min Leftist Tree Operations Put Operation put(7) Remove Min Remove Min Meld Two Min Leftist Trees Meld Two Min Leftist Trees Meld Two Min Leftist Trees Meld Two Min Leftist Trees Meld Two Min Leftist Trees Meld Two Min Leftist Trees Meld Two Min Leftist Trees Meld Two Min Leftist Trees Meld Two Min Leftist Trees Initializing In O(n) Time Create n single-node min leftist trees and place them in a FIFO queue. Repeatedly remove two min leftist trees from the FIFO queue, meld them, and put the resulting m