Re: Sorted heap trees
- From: matt.timmermans@xxxxxxxxx
- Date: Wed, 9 Apr 2008 19:16:44 -0700 (PDT)
On Apr 9, 5:35 pm, 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. 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.
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.
Cheers,
Matt
.
- Follow-Ups:
- Re: Sorted heap trees
- From: Richard Harter
- Re: Sorted heap trees
- References:
- Sorted heap trees
- From: Richard Harter
- Sorted heap trees
- Prev by Date: Sorted heap trees
- Next by Date: Re: Sorted heap trees
- Previous by thread: Sorted heap trees
- Next by thread: Re: Sorted heap trees
- Index(es):
Relevant Pages
|
