Page 225 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 11.1.1 Leftist Trees

A leftist tree is a tree which tends to ``lean’’ to the left. The tendency to lean to the left is defi ned
in terms of 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.

Every node in binary tree has associated with it a quantity called its null path length which is
defined as follows:

Null Path and Null Path Length

Consider an arbitrary node x in some binary tree T. The null path of node x is the shortest path in
T from x to an external node of T.

The null path length of node x is the length of its null path.
Sometimes it is convenient to talk about the null path length of an entire tree rather than of a
node:

Null Path Length of a Tree

The null path length of an empty tree is zero and the null path length of a non-empty binary tree
T = {R, T , T } is the null path length its root R.
L R
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 path from the root
of the tree to an external node, the null path length gives a lower bound on the cost of insertion.

Example: The running time for insertion in a binary search tree, is at least
dτ + Ω(d)
(compare)
where d is the null path length of the tree.
A leftist tree is a tree in which the shortest path to an external node is always on the right. This

informal idea is defined more precisely in terms of the null path lengths as follows:

Definition (Leftist Tree)
A leftist tree is a binary tree T with the following properties:

1. Either T = l; or
2. T = {R, T , T }, where both T and T are leftist trees which have null path lengths d and d ,
R
L
R
R
L
L
respectively, such that d ≥ d .
L R
Figure 11.1 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 node in Figure 11.1. The fi gure
clearly shows that it is not necessarily the case in a leftist tree that the number of nodes to the left
of a given node is greater than the number to the right. However, it is always the case that the
null path length on the left is greater than or equal to the null path length on the right for every
node in the tree.

220 LOVELY PROFESSIONAL UNIVERSITY