Re: Sorted heap trees
- From: cri@xxxxxxxx (Richard Harter)
- Date: Thu, 10 Apr 2008 05:25:03 GMT
On Wed, 9 Apr 2008 19:16:44 -0700 (PDT),
matt.timmermans@xxxxxxxxx wrote:
On Apr 9, 5:35=A0pm, c...@xxxxxxxx (Richard Harter) wrote:
It turns out that there are some special situations where a
sorted heap tree is better than an ordinary BST. =A0I 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.
Hi Richard,
There are a wide variety of well-known ways for laying out a tree in
an array, and the issue of layout is usually considered separately
from what is actually in the tree nodes or how the node keys are
ordered.
The layout used by a heap is called the "breadth-first layout" in the
literature. It has many uses, including as a benchmark against which
various cache-oblivious layouts are compared, so if you google for
"breadth-first layout", you'll find lots of interesting things.
The particular ordering of nodes that you're using is called
"preorder", but the word is usually to refer to an order in which
nodes are visited, not an ordering for the nodes' keys. The
characteristics of searching in your tree are similar to those of a
"finger search tree", so you may want to goole for that to get some
more information about the application you have in mind.
Many thanks for the comments and suggestions. I wasn't
considering layout at all and wasn't thinking in terms of
embedding a tree in an array. AFAIK the heap data structure is
usually defined as a tree - the breadth first layout in an array
is a convenience. That said, a search on "breadth-first layout"
does turn up some interesting things.
It occurs to me that the layout I used might have been
misleading. I just listed the nodes sequentially because of the
limitations of ascii art.
I'm not sure that I follow your thought that the search
characteristics are similar to those of a finger search tree.
Could you elucidate.
Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.
- References:
- Sorted heap trees
- From: Richard Harter
- Re: Sorted heap trees
- From: matt . timmermans
- Sorted heap trees
- Prev by Date: Re: Sorted heap trees
- Next by Date: Goedell's Incompleteness Reconsidered
- Previous by thread: Re: Sorted heap trees
- Next by thread: Goedell's Incompleteness Reconsidered
- Index(es):
Relevant Pages
|
