Richard Harter’s World
Site map
May 2008
Comp. Sci.
email

Heap structured search trees

Introduction
Searching HSSTs
Traversing HSSTs:
Successors and predecessors:
Insertion:
Deletion:
Final remarks:

Introduction

This note discusses basic algorithms for operating on heap structured search trees.

Definition: A min heap structured search tree (min HSST) is a binary tree with the following properties:

  1. For each node all elements in the left subtree are less than the elements in the right subtree.
  2. The parent node is less than any of its children.
A max HSST is the same as a min HSST except that “less than” is replaced by “greater than”. Hereafter in this note an HSST will be a min HSST. There are equivalent algorithms for max HSSTs with the obvious modifications.

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.

Insertion:

Insertion into an HSST is generally similar to insertion into a BST; first we search for an insertion point and then insert the new item. However there are significant differences; (a) in a BST the insertion point is always a leaf node whereas in an HSST the insertion point can be anywhere within the tree, and (b) we need existence checks on the children. The pseudocode looks like this:
    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.

Richard Harter’s World
Site map
May 2008
Comp. Sci.
email