Re: Sorted heap trees
- From: cri@xxxxxxxx
- Date: Fri, 28 Mar 2008 21:33:12 -0700 (PDT)
On Mar 28, 3:10 pm, "Stephen Howe" <sjhoweATdialDOTpipexDOTcom> wrote:
"Richard Harter" <c...@xxxxxxxx> wrote in message >
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.
Sorry It is not clear enough.
You say , "This is a sorted tree, albeit not a BST"
Does that mean a parent node may have more than 2 children?
A binary search tree has the property that C1 < P < C2. These trees
have
the property that either C1 < C2 < P or C1 > C2 > P.
I wasn't thinking in terms of more than two children, but that's a
natural
generalization. If you have k children then you would have k
partitions.
If so, are saying that all elements reachable under
C1 < C2 < C3 ... < CN?
or
C1 > C2 > C3 ... > CN?
where C1 is child1, C2 child2 and all is children in turn etc
Also if P is parent node are you saying
P < C1 < C2 < C3 ... < CN?
or
P > C1 > C2 > C3 ... > CN?
Of course. These trees are heaps that satisfy an additional
constraint,
namely that the subtrees partition the data.
Cheers
Stephen Howe
.
- References:
- Sorted heap trees
- From: Richard Harter
- Re: Sorted heap trees
- From: Stephen Howe
- Sorted heap trees
- Prev by Date: Re: Online Matrimony
- Next by Date: Re: Sorted heap trees
- Previous by thread: Re: Sorted heap trees
- Next by thread: Re: Sorted heap trees
- Index(es):
Relevant Pages
|
