# Heap structured search trees

### 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.