Prev: BPL = L ?
Next: large datasets for classification and regression
From: Richard Harter on 12 Apr 2008 15:12

Heap structured search trees is my latest neolgism. A (min) heap

is a binary tree such that the children of a node are greater
than their parent. A heap structured search tree is a heap such
that for each node all of the elements of the left subtree are
less than the any of the elements of right subtree.

In many applications, e.g., heapsort, a heap will be embedded in
an array with a breadth-first distribution of nodes. However it
need not be, and in this note a heap structured search tree is an

abstract binary tree. Because of the ordering it is searchable
using O(log N) comparisons.

Here is an example of a heap structured binary tree:
(fixed format required for readability)

1
_____|_____
| |
4 20
__|__ __|_
| | | |
6 11 22 30
| |
10 31

Unlike ordinary binary search trees, if there is but a single
child, it doesn't matter whether it is a left child or a right
child; however it is convenient to adopt the convention that all
single children are left children.

To search a heap structured search tree we first compare with the

right child, then with the left, and finally with the parent.
Thus the pseudocode (modulo corner cases) looks like this:

node <- root
loop
if (item >= node.right.value) node <- node.right
else if (item >= node.left.value) node <- node.left
else if (item == node.value) return node
else return not_found
end loop

Except for the direction of comparison in the left child test,
the same pseudocode can be used for ordinary binary search trees.

The recursive tree traversal routine looks like this:

procedure process_tree process,node
process(node)
process_tree(node.left)
process_tree(node.right)
end procedure

Again this code is the same as that for binary search trees
except for a slight change in the order of operations. One might

suppose that all operations on binary search trees and heap
structured search trees are equivalent except for slight
reorderings. This is not the case.

If we try to implement traversal iteratively using a stack the
resulting code is simpler and more efficient. Below is simple
pseudocode for each alternative. The pseudocode assumes a stack
with push and pop operations.

Heap structured search tree:

procedure process_tree process, node
while (node != nil)
while (node != nil)
process(node)
if (node.right) push node
node = node.left
end while
pop node
end while
end procedure

Binary search tree:

procedure process_tree process, node
while (node != nil)
while (node != nil )
push node
node = node.left
end while
pop node
while (node != nil)
process (node)
if (node.right != nil)
node = node.right
break
else pop node
end while
end while
end procedure

Clearly the pseudocode for heap structured search trees is
simpler than that for binary search trees. (To be fair, devising

iterative traversal code for binary search trees is tricky, and
there may well a better version.) Not only is the binary search
tree code more complicated, it is more expensive. In the binary
search tree code every node is pushed onto the stack; in the heap
structured search tree only the right children are pushed onto
the stack.

Why is this so? The reason is that in the binary search tree
version is that we have to push parent nodes onto the stack
whereas in the heap structured search tree version we do not. In
a heap structured search tree each left child is the immediate
successor of its parent; in consequence the parent can be
processed immediately whereas in an ordinary binary search tree
the processing of the parent must be deferred until the entire
left subtree has been processed.

Richard Harter, cri(a)tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
 | 
Pages: 1
Prev: BPL = L ?
Next: large datasets for classification and regression