Heap structured search trees
Introduction IntroductionThis 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:
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 11Unlike 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 loopThe 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 loopThe 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 procedureHowever 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 11However 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. |