Sorted heap trees


This is a repost to comp.theory.

I'm looking at a data structure that I have (re)invented that I
am calling a sorted heap tree. I dare say there is an official
name but I haven't a clue as to what it might be. What I am
looking for are references, preferably on-line, and anything
useful I can snarf up.

A sorted heap tree is a heap tree with the further requirement
that left and right subtrees are partitions. That is, all of the

elements of the left subtree are less than the elements of the
right subtree. For example, here is a sorted heap tree in
outline form.

T: 1
L: 2
L: 3
L: 4
R: 5
R: 6
L: 7
R: 8
R: 9
L: 10
L: 11
R: 12
R: 13
L: 14
R: 15

This is a sorted tree, albeit not a BST. The recursive traversal

routine is

procedure traverse node
print node.data
traverse node.left
traverse node.right


There are four types of sorted heap trees, because we can
exchange left and right, and the direction of ordering.

Searches are necessarily asymetric. That is, in this tree we
first compare with the right child and then with the left.

Sorted heap trees are analogous with binary search trees - for
every type of BST, e.g., splay trees, AVL trees, etc, there are
corresponding sorted heap trees.

It turns out that there are some special situations where a
sorted heap tree is better than an ordinary BST. I am wondering
if anyone knows the proper name for these type of trees and of
any references, e.g., properties, uses, adaptations of standard
algorithms for them.





Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.

Relevant Pages

  • Re: Sorted heap trees
    ... A sorted heap tree is a heap tree with the further requirement ... albeit not a BST. ... procedure traverse node ... Richard Harter, cri@xxxxxxxx ...
    (sci.math.research)
  • Sorted heap trees
    ... I'm looking at a data structure that I have invented that I ... A sorted heap tree is a heap tree with the further requirement ... albeit not a BST. ... procedure traverse node ...
    (comp.programming)
  • Sorted heap trees
    ... I'm looking at a data structure that I have invented that I ... A sorted heap tree is a heap tree with the further requirement ... albeit not a BST. ... procedure traverse node ...
    (sci.math.research)