Heap structured search trees
Introduction
Definition: A min heap structured search tree (min HSST) is a binary tree with the following properties:
As a side note, a heap structured search tree should not be confused with the breadth first array heap layout used in heapsort. HSSTs are binary trees. HSSTs are similar to Binary Search Trees (BSTs). A BST has property (a) but its version of property (b) is that the parent node’s value is in-between the maximum value in the left subtree and minimum value in the right subtree. Here is an example of a heap structured binary tree:
1
_____|____
| |
4 20
__|__ __|_
| | | |
6 12 22 30
_|_ |
| | 31
10 11
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.
Searching HSSTs: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 looks like this:
node = root
loop
if (exists? node.right and item >= node.right.value)
node = node.right
else if (exists? node.left and item >= node.left.value)
node = node.left
else if (item == node.value) return node
else error
end loop
The analogous code for searching a BST looks like this:
node = root
loop
if (item > node.value) node = node.right
else if (item < node.value) node = node.left
else if (item == node.value) return node
else error
end loop
The difference is that in a BST you compare against a node’s
value whereas in an HSST you compare against the children’s
values. For this reason the code for searching an HSST must
check the existence of the children.
Traversing HSSTs:The recursive traversal procedure is virtually identical with the analogous procedure for binary search trees;
procedure process_tree process,node
process(node)
process_tree(node.left)
process_tree(node.right)
end procedure
However the iterative version (with a stack) is dissimilar and is
simpler. Here is the pseudocode:
node = root
while (exists? node)
emit node
if (exists? node.right) push node.right
if (exists? node.left) node = node.left;
else pop node
end while
Successors and predecessors:The reason traversal is simpler for HSSTs than for BSTs has to do with the location of predecessors and successors. In a BST a successor is the leftmost element in the right subtree and the predecessor is the rightmost element in the left subtree. In an HSST things are quite different:Successor: If a node has a left child, its successor is its left child. If it does not, its successor is the right child of the junior ancestor having a right child.
Predecessor: If a node is a left child, its predecessor is its
parent. If a node is a right child, its predecessor is the
largest descendent of its sibling.
node = root
val = newnode.value
if (val < node.value)
newnode.left = root
newnode.right = nil
root = newnode
else loop
if (exists? node.right and val >= node.right.value)
node = node.right
else if (exists? node.left and val >= node.left.value)
node = node.left
else if (item == node.value) error
else
if (exists? node.right) newnode.left = node.left
else node.right = node.left
node.left = newnode
escape
end loop
Deletion:Generally speaking, to delete a node we need to know its parent because its parent contains the link to it that must be changed. Either the tree nodes contain a parent link or we can search down the tree for the node and remember the parent from the search. In discussing deletion I shall assume that the parent is known in some way.The simple way to look at deletion in an HSST is that, beginning with the node to be deleted, each node is replaced by its left child until a leaf node is reached. If we apply this to our example and delete node 1 we get:
1 4
_____|____ _____|____
| | | |
4 20 6 20
__|__ __|_ => __|__ __|_
| | | | | | | |
6 12 22 30 10 12 22 30
_|_ | | |
| | 31 11 31
10 11
However it is more profitable to think in terms of pushing right
subtrees down the chain of left children. Thus, 1’s right child,
20, becomes 4’s new right child, while 4’s old right child, 12,
becomes 6’s new right child, etc. We terminate this when we
reach a node lacking a right child. If this last node has no
children at all, the right child it receives becomes a left
child.
In the pseudocode it is convenient to have a queue with operations q.push (appends a node to the queue), q.pop (removes a node from the queue), and q.top (like g.pop, but no remove). That said, the pseudocode looks like this:
parent.link = node.left
q.push node.right
while (node.left and q.top != nil)
node = node.left
q.push node.right
q.pop node.right
end while
if (exists? node.right)
node.left = node.right
node.right = nil
end if
Final remarks:The algorithms presented here suffice for creating an HSST package. There are major remaining issues. One is balancing. Like simple BSTs, a sequence of inserts and deletes can produce an unbalanced tree. In particular, ascending and descending sequences produce vines. It is fairly straightforward to balance an HSST.How to maintain dynamically balanced trees is an open question. For BSTs are many methods, e.g., splay trees, red and black trees, AVL trees, etc. The basic algorithms for these methods cannot be adopted to HSSTs because they use rotations, and you cannot do rotations in an HSST. Why not? You can’t because in an HSST you can’t change the root of a subtree whereas in a BST you can. On the other hand you can move elements and subtrees from one branch to another so there are balancing operations available. It seems likely that there is a whole family of methods applicable to HSSTs that are quite different from the ones for BSTs. Another question, unanswerable at this point, is whether HSSTs are useful or not and, if they are, in what contexts. Finally, on a personal note, is this work novel or not? I can’t find anything on the web like this, which may not mean much. At this point I don’t have access to university libraries, which makes literature searches difficult. This page was last updated May 1, 2008. |