📄 page362.html
字号:
<HTML><HEAD><TITLE>Leftist Trees</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html5361" HREF="page363.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5359" HREF="page361.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5353" HREF="page361.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5363" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0011310000000000000000">Leftist Trees</A></H2><P>A <em>leftist tree</em> is a tree which tends to ``lean'' to the left.The tendency to lean to the left is defined in termsof the shortest path from the root to an external node.In a leftist tree,the shortest path to an external node is always found on the right.<P>Every node in binary tree has associated with it a quantitycalled its <em>null path length</em> which is defined as follows:<P><BLOCKQUOTE> <b>Definition (Null Path and Null Path Length)</b><A NAME="defnnpl"> </A><P>Consider an arbitrary node <I>x</I> in some binary tree <I>T</I>.The <em>null path</em> of node <I>x</I>is the shortest path in <I>T</I> from <I>x</I> to an external node of <I>T</I>.<P>The <em>null path length</em><A NAME=25077> </A>of node <I>x</I> is the length of its null path.</BLOCKQUOTE><P>Sometimes it is convenient to talk about the null path length of anentire tree rather than of a node:<P><BLOCKQUOTE> <b>Definition (Null Path Length of a Tree)</b><P>The <em>null path length</em><A NAME=25082> </A>of an empty tree is zeroand the null path length of a non-empty binary tree <IMG WIDTH=113 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65811" SRC="img1421.gif" >is the null path length its root <I>R</I>.</BLOCKQUOTE><P>When a new node or subtree is attached to a given tree,it is usually attached in place of an external node.Since the null path length of a tree is the length of the shortest pathfrom the root of the tree to an external node,the null path length gives a lower bound on the cost of insertion.For example, the running time for insertion in a binary search tree,Program <A HREF="page316.html#progbinarySearchTreec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>, is at least<P> <IMG WIDTH=301 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath65793" SRC="img1422.gif" ><P>where <I>d</I> is the null path length of the tree.<P>A <em>leftist tree</em> is a tree in which the shortestpath to an external node is always on the right.This informal idea is defined more precisely in termsof the null path lengths as follows:<P><BLOCKQUOTE> <b>Definition (Leftist Tree)</b><A NAME="defnleftist"> </A>A <em>leftist tree</em><A NAME=25090> </A><A NAME=25091> </A>is a binary tree <I>T</I> with the following properties:<OL><LI> Either <IMG WIDTH=40 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline62991" SRC="img1064.gif" >; or<LI> <IMG WIDTH=113 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65811" SRC="img1421.gif" >, where both <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63147" SRC="img1085.gif" > and <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63149" SRC="img1086.gif" > are leftist trees which have null path lengths <IMG WIDTH=17 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65827" SRC="img1423.gif" > and <IMG WIDTH=17 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65829" SRC="img1424.gif" >, respectively, such that <P> <IMG WIDTH=280 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath65794" SRC="img1425.gif" ><P></OL></BLOCKQUOTE><P>Figure <A HREF="page362.html#figleftist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows an example of a leftist heap.A leftist heap is simply a heap-ordered leftist tree.The external depth of the node is shown to the right of each nodein Figure <A HREF="page362.html#figleftist1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The figure clearly shows that it is not necessarily the case in a leftist treethat the number of nodes to the left of a given node is greater thanthe number to the right.However, it is always the case that the null path length on the leftis greater than or equal to the null path length on the rightfor every node in the tree.<P><P><A NAME="25490"> </A><A NAME="figleftist1"> </A> <IMG WIDTH=575 HEIGHT=271 ALIGN=BOTTOM ALT="figure25097" SRC="img1426.gif" ><BR><STRONG>Figure:</STRONG> A leftist heap.<BR><P><P>The reason for our interest in leftist trees is illustratedby the following theorems:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theorempqueuesiv"> </A>Consider a leftist tree <I>T</I> which contains <I>n</I> internal nodes.The path leading from the root of <I>T</I> downwards to the rightmost external nodecontains at most <IMG WIDTH=87 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65837" SRC="img1427.gif" > nodes.</BLOCKQUOTE><P> extbfProofAssume that <I>T</I> has null path length <I>d</I>.Then <I>T</I> must contain at least <IMG WIDTH=29 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline65845" SRC="img1428.gif" > leaves.Otherwise, there would be a shorter path than <I>d</I>from the root of <I>T</I> to an external node.<P>A binary tree with exactly <I>l</I> leaveshas exactly <I>l</I>-1 non-leaf internal nodes.Since <I>T</I> has at least <IMG WIDTH=29 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline65845" SRC="img1428.gif" > leaves,it must contain at least <IMG WIDTH=73 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline65859" SRC="img1429.gif" > internal nodes altogether.Therefore, <IMG WIDTH=105 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65861" SRC="img1430.gif" >.<P>Since <I>T</I> is a leftist tree,the shortest path to an external node must be the path on the right.Thus, the length of the path to the rightmost external is at most <IMG WIDTH=87 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65837" SRC="img1427.gif" >.<P>There is an interesting dichotomy between AVL balanced trees and leftist trees.The shape of an AVL tree satisfies the AVL balance conditionwhich stipulates that the difference in the heights of the left andright subtrees of every node may differ by at most one.The effect of AVL balancing is to ensure thatthe height of the tree is <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" >.<P>On the other hand, leftist trees have an ``imbalance condition''which requires the null path length of the left subtree to be greater thanor equal to that of the right subtree.The effect of the condition is to ensure thatthe length of the right path in a leftist tree is <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" >.Therefore, by devising algorithms for manipulating leftist heapswhich only follow the right path of the heap,we can achieve running times which are logarithmic in the number of nodes.<P>The dichotomy also extends to the structure of the algorithms.For example, an imbalance sometimes results from an insertion in an AVL tree.The imbalance is rectified by doing rotations.Similarly, an insertion into a leftist tree may result in a violation ofthe ``imbalance condition.''That is, the null path length of the right subtree of a node my becomegreater than that of the left subtree.Fortunately, it is possible to restore the proper condition simply byswapping the left and right subtrees of that node.<P><HR><A NAME="tex2html5361" HREF="page363.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5359" HREF="page361.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5353" HREF="page361.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5363" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -