Dominance Tree Sorts

  • Permalink
  • submit to reddit
  • Email
  • Follow


Dominance Tree Sorts

"Dominance tree sorts" is a neologism.  If anyone recognizes this 
class of sorts I would take it kindly if they would point to the 
literature (web preferred) where this class of sorts is described 
and named.  The idea doesn't seem to be explored in Knuth, though 
something may be hidden in the exercises.  Dominance tree sorts 
aare selection sorts but not tournament sorts.

Suppose we have a set S of elements and an ordering relationship 
R defined over S.  For example, S might be an array of integers, 
and R might be >, the greater than relationship.  Let x and y be 
two elements of S.  Element x is said to dominate y if (x R y).  
Again from the example, let x be 8 and y be 5.  Then x dominates 
y.

A dominance tree T over S is a tree such that (a) every element 
of S appears exactly once in T, and (b) for every element (except 
the root) the element's parent dominates it.  Here are some 
examples of dominance trees over the set {1,2,3,4,5}

          A          B        C

          5          5        5
          |          |        |
       -------     -----      4
       | | | |     |   |      |
       1 2 3 4     4   2      3
                   |          |
                  ---         2
                  | |         |
                  1 3         1
                  
Heaps are dominance trees, but not all dominance trees are heaps.  
Example B is a heap, example C is a sorted list, and in example A 
all we know is that '5' is maximal.  

A set K of comparisons (xRy) is a minimum comparison set for 
a dominance tree T if it consists exclusively of the comparisons
in the child/parent linkages.  Thus, in our example, the minimum 
comparison sets are:

K(A):  5>1, 5>2, 5>3, 5>4
K(B):  5>4, 5>2, 4>1, 4>3
K(C):  5>4, 4>3, 3>2, 2>1

Note that a minimum comparison set always has n-1 members where n 
is the cardinality of S.

An algorithm is an efficient dominance tree construction (EDTC) 
algorithm if it specifies a minimum comparison sequence that in 
turn specifies a dominance tree.

One of the important features of EDTC algorithms is that if an 
element 'loses' in a comparison it cannot appear in a later 
comparison in the comparison's sequence.  Another is that there 
is no EDTC algorithm that can guarantee that the root element has 
less than log2(n) children.  In particular there are no 
EDTC algorithms for creating heaps.

The general plan for dominance tree sorts runs as follows:  For a 
given set S we first construct a dominance tree T.  We then emit 
the root of the tree.  The children of the root are compared 
until a new root is established. In each comparison the 'loser' 
becomes a new child of the 'winner'.  EDTC algorithms are used in 
both the initial construction phase and in each emission step.  
There are quite a number of variations depending on which EDTC 
algorithms are used.

There are two major EDTC algorithms that occur to me.  The first 
is tournament pairing, also used in the tournament sort and in 
heapsort.  In the tournament pairing algorithm the set is divided
into pairs that are compared.  The winners go on to the second 
round where they are again divided into pairs that are compared.  
This is continued until a final winner is determined.  This 
requires n-1 comparisons, log2(n) rounds, and the winner, the 
root of the tree, will have log2(n) children.

The second is sequential comparison.  The first element in a 
list is compared with the second.  The winner is compared with 
the third, and so on.  This also requires n-1 comparisons.  The 
number of children of the root depends on the location of the 
root element in the list.  If the ordering of the list elements 
is random, the average number of children will n/2.  On the other 
hand, the number of children will be 1 if the list is ordered.

It turns out that we get a very efficient (as measured by the 
number of comparisons used) sort if we use tournament 
pairing to construct the initial dominance tree and sequential 
comparison in the update after emission of the root.  Each 
element has a list associated with it of elements that it 
dominates.  During construction when one element dominates 
another the losing element is appended to the winning elements 
list.  Here is a very simple example.  Let the set to be sorted 
be {2,4,3,1}.  The actions are: 

    Construction Phase
        compare (2,4); append 4 to 2's list
        compare (3,1); append 3 to 1's list
        compare (2,1); append 2 to 1's list; 1 is the root
    Emission Phase
        emit (1); compare (3,2); append 3 to 2's list; 2 is root
        emit (2); compare (3,4); append 4 to 3's list; 3 is root
        emit (3); 4 is root
        emit (4); done 

How efficient is this sort?  The tests that I ran showed it to 
about equivalent to merge-insert (see Knuth, Vol 3, 5.3.1).  For 
example, sorting 32 items requires a minimum of 118 comparisons 
on average (log2(32!)).  Merge-insert needs 121.  The number 
needed by the above algorithm depends on the precise permutation.  
The average number needed is about 121.5.  For large n the number 
of comparisons required was ~ n*(log2(n) - 1.27) in the tests I 
performed; this is not far off from the best possible of whic is
~ n*(log2(n) - log2(e)) = n*(log2(n) - 1.44).

Why is this sort efficient?  It has to do with an order 
preservation property in the construction and updating of the 
dominance lists.  In the construction phase a dominance list has 
two special properties: (a) its length is longer than the lengths 
of the lists of the elements in its list, and (b) the elements in 
the list are in order of the length of their lists.  These 
properties are almost always preserved by the above algorithm.  
In turn this implies that the lengths of the dominance lists are 
slightly less than O(log2(n)) on average.

Can this be improved upon?  Possibly.  The only 
reference I can find to dominance tree sorts is a web article by 
someone called Supercat.  In the web article he in effect forces 
property (b) to hold.  (He calls it a tournament sort which is a 
bit of a misnomer.)  He gives the following results for a test 
case sorting one million items.

Number of comparisons by a perfect sort (lg(n!)) : 18,488,865
Avg # of comparisons for Tournament Sort: 18,646,425 
   (100.85% of perfect)
Avg # of comparisons for Borland C's qsort: 22,439,507 
   (121.37% of perfect)

This gives (n = 1000000) n*(log2(n) - 1.284) which is tad better 
than the simpler algorithm given here.  On the other hand 
Supercat's version requires addition comparisons of the element 
weights (integers rather than keys).

Is this a practical sort?  Possibly not.  It requires extra space 
O(n) for the lists and O(n) for the list headers.  Each 
comparison involves adding an item to a linked list, so the 
cost of the inner loop operations will be higher than it is in 
simpler sorts.  On the other hand memory is often plentiful and 
the inner loop costs should be no worse than those for an 
ordinary tree sort.


References:
   URL:   http://www.halfbakery.com/idea/Tournament_20Sort
   Title: Tournament sort
   
   Knuth, The Art of Computer Programming, Vol 3, Searching
   and Sorting.

Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Tragedy is living to an old age 
and not having any enemies to outlive.
0
Reply cri (1432) 8/17/2004 9:08:50 PM

See related articles to this posting


On Tue, 17 Aug 2004 21:08:50 GMT, cri@tiac.net (Richard Harter) wrote:

>
>Dominance Tree Sorts
Oops, should have been comp.theory.  Mea Culpa.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Tragedy is living to an old age 
and not having any enemies to outlive.
0
Reply cri 8/17/2004 9:11:34 PM

On Tue, 17 Aug 2004 21:08:50 GMT, cri@tiac.net (Richard Harter) wrote:


[snip original]

In the original text it is stated that a dominance tree is not a heap,
even though a heap is a dominance tree.  There are a couple of
corrections to make here.  The first is that 'heap' should have been
'binary heap'.  The second is that dominance trees have the heap
property and accordingly are heaps in the most general sense of
'heap'.

No mention is made in the original of fibonacci heaps and fibonacci
heap sorts.  There is an intimate relationship betweem fibonacci heap
sorts and the dominance tree sorts mentioned in my article.  However
they are different animals.

"Dominance tree sorts" may not be entirely appropriate since a
dominance tree is a heap.  However the appropriate names have all been
appropriated.

It should be possible to create a heap type that corresponds to the
heap structure used in dominance tree sorts.  I will look into this
and report my findings.




Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Tragedy is living to an old age 
and not having any enemies to outlive.
0
Reply cri (1432) 8/23/2004 6:28:45 PM

In article <41227327.365327442@news.sbtc.net>, cri@tiac.net (Richard Harter) writes:
> 
> Each 
> comparison involves adding an item to a linked list, so the 
> cost of the inner loop operations will be higher than it is in 
> simpler sorts.  On the other hand memory is often plentiful and 
> the inner loop costs should be no worse than those for an 
> ordinary tree sort.

On the other other hand, all that linked-list traversal likely means
poor locality of reference, which means bad cache effects.  Which,
come to think of it, is generally true of heap sorts.  If you keep
the children as an array rather than a linked list (overflows can be
handled in various ways) that should help.

Interesting idea and nice writeup, though.  I'm still thinking about
it.  On casual inspection it does look like it might be quite
amenable to being parallelized, and with SMP systems becoming ever
more common that's certainly useful.  (Of course, mergesorts are
inherently parallel and very easy to code.)

-- 
Michael Wojcik                  michael.wojcik@microfocus.com

Auden often writes like Disney.  Like Disney, he knows the shape of beasts --
(& incidently he, too, might have a company of artists producing his lines) --
unlike Lawrence, he does not know what shapes or motivates these beasts.
   -- Dylan Thomas
0
Reply mwojcik (1879) 8/26/2004 7:57:18 PM

mwojcik@newsguy.com (Michael Wojcik) wrote in message news:<cglfau0kjv@news1.newsguy.com>...
> In article <41227327.365327442@news.sbtc.net>, cri@tiac.net (Richard Harter) writes:
> > 
> > Each 
> > comparison involves adding an item to a linked list, so the 
> > cost of the inner loop operations will be higher than it is in 
> > simpler sorts.  On the other hand memory is often plentiful and 
> > the inner loop costs should be no worse than those for an 
> > ordinary tree sort.
> 
> On the other other hand, all that linked-list traversal likely means
> poor locality of reference, which means bad cache effects.  Which,
> come to think of it, is generally true of heap sorts.  If you keep
> the children as an array rather than a linked list (overflows can be
> handled in various ways) that should help.

Performance problems with heapsort are often blamed on cache effects.
No doubt this is true; however the standard heapsort has further problems
that degrade perfomance.  An obvious one is the complexity of the inner
loops.  

A more subtle issue is that the heapify process throws information
away. For example suppose we have three elements x,y,z at locations
a[n], a[2*n], a[2*n+1] and we heapify them.  We first compare y and z
and pick the dominant one, z for the sake of argument.  We then compare 
z with x, the top point in our little heap; if it dominates x we swap, 
moving z up and x down.  We now have a[n] > {a[2*n],a[2*n+1]} and that is
all we have.  However if x was the dominant one we lose the information that
a[2*n+1] > a[2*n].  That is, the data structure doesn't distinguish between
x>z>y and z>x,z>y; in the former case it records x>z (true by transitivity)
and x>y, but not z>y.  In effect 1/3 of a decision is lost.  This information
loss occurs at several points in the standard heap sort.  For this reason
the required number of comparisons for heapsort is n*[a*log2(n)+b] where a>1.

This kind of information loss does not occur either quicksort or mergesort.
Using a simplified analysis of the mergesort cost function we get 
n*(log2(n)-1.0), which is pretty close to the optimal n*(log2(n)-log2(e)).
Although quicksort doesn't throw information away, it doesn't use it
quite as efficiently (partitions are equisized) so its 'a' is greater than 1.
As noted the dominance tree sort (my version anyway) has a comparison cost
function of ~ n*(log2(n)-1.27) or better (on random data), which is better 
than mergesort but not by much.  

I'm not sure that putting the linked lists in arrays helps particularly with
the cache problem although it is easy enough to put them in arrays.  The
catch is that the references in the linked lists are scattered.  There may
be something clever that one can do with moving the data so that cache misses
are reduced but I haven't thought it out though.


> Interesting idea and nice writeup, though.  

Thanks.

>I'm still thinking about
> it.  On casual inspection it does look like it might be quite
> amenable to being parallelized, and with SMP systems becoming ever
> more common that's certainly useful.  (Of course, mergesorts are
> inherently parallel and very easy to code.)

Offhand it seems quite straightforward to parallelize it.

As a final note both mergesort and quicksort are intrinsically cache
friendly as long as there are at least two caches.
0
Reply cri (1432) 8/28/2004 3:14:34 PM

On Tue, 17 Aug 2004 21:08:50 GMT, cri@tiac.net (Richard Harter) wrote:

>
>Dominance Tree Sorts
>


[snip original article]

I have looked into this matter in some detail.  In particular I have
gone through the relevant sections of Knuth, vol 3, Sorting and
Searching.  One problem here is that my copy is the 1973 edition (I
don't know what changes, if any, are in later editions.)  In
consequence there is a lot of more modern material, e.g., fibonacci
heaps, that is not included.  That said:

(1) A dominance tree is a heap (using the most general definition of
heap) with the additional requirement that each element loses in a
comparison no more than once.  There doesn't seem to be any need for
"dominance trees" as a description of a data structure.  On the other
hand the the term "dominance tree sorts" is useful since the term
"heap sorts", which ought to refer the class of sorts based on heaps
has instead been preempted as the label for a particular kind of
binary heap sort. 

(2) The category of dominance tree sorts is broader than that of
tournament sorts; however the standard tournament sort is isomorphic
to a dominance tree sort in which the tree is constructed using
tournament pairing and then in the selection phase the child lists of
each selection is processed sequentially.

(3) Tournament sorts (and the equivalent dominance tree sorts) are
highly efficient in terms of the average number of comparions and the
minimax number of comparisons required.  Both quicksort and heapsort
require substantially more; mergesort is comparable but is slightly
more costly.  Merge-Insert (Johnson-Trotter) sorts are slightly more
efficient but the gain is minimal.  

(4) Tournament sorts have the same comparison cost function as binary
insertion sorts.  However binary insertion sorts are expensive in
terms of data move costs.  Tournament sorts are better in terms of
data move costs but have (IMHO) messy data structures.  The equivalent
dominance tree sorts have "nicer" data structures.



 
Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Tragedy is living to an old age 
and not having any enemies to outlive.
0
Reply cri (1432) 9/21/2004 6:28:18 AM
comp.programming 10619 articles. 18 followers. Post

5 Replies
210 Views

Similar Articles

[PageSpeed] 59


  • Permalink
  • submit to reddit
  • Email
  • Follow


Reply:

Similar Artilces:

dominance tree sorts, followup
This is a followup on the "dominance tree sorts" article I did a while back. I wrote an implementation in C (the code is below). Comments on the code and/or the results are welcome. I did some timing experiments to get a handle on the efficiency of domsort. The data sets for the tests were random integers; the sizes of the data sets were powers of two, ranging from 2**8 to 2**20 (256 to 1048576). All tests were run on a 333 mhz PC running windows 98, using the djgpp environment. The optimization level (gcc) was O2. The codes tested were the domsort routine listed below, ...

Tree sorting
Hello Everyone, &nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Have anybody used Tree sorter.vi in vi library? &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; \Program Files\National Instruments\LabVIEW 7.1\vi.lib\tree\Tree Point Converter.llb\Tree Sorter.vi &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;If you have used, can you tell me, what does the inputs 'Tag' and 'Sort specific vi' mean? I could not figure out and the help is not available for this. &am...

finding all dominator trees
Hi, Is there an efficient algorithm for finding all dominator trees of a graph? That is, for every node, find its dominator tree. I'm looking for something better than simply running a dominator tree algorithm for each node in the graph. Amir > Is there an efficient algorithm for finding all dominator trees of a > graph? That is, for every node, find its dominator tree. I'm looking > for something better than simply running a dominator tree algorithm > for each node in the graph. Unless I am missing some subtlety of your situation, you should just be able to run the do...

Sorted heap trees
This is a repost to comp.programming only. 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. ...

finding all dominator trees
Hi, Is there an efficient algorithm for finding all dominator trees of a graph? That is, for every node, find its dominator tree. I'm looking for something better than simply running a dominator tree algorithm for each node in the graph. Amir ...

Sort Data With Tree
I am trying to set up a tree to sort my data. what i mean is like in access when you insert a subdata sheet and you get the plus sign and then you click on that i am trying to organize pictures by year then month then date then all the pictures in that date in to a preview pane how would i set this up in vb6 thanks and Happy Holidays !!! Take a look at the VB TreeView control. http://www.freevbcode.com/ShowCode.Asp?ID=2017 Cheers, - Merlin "WStoreyII" <papastoreyii@hotmail.com> wrote in message news:aZGHb.2977$_O1.2439@newssvr25.news.prodigy.com... > I am trying to...

sorts with binary trees
Lately, I've been looking at aspects of sorts in fortran. To compare and contrast, I've been looking at bubble and selection: subroutine bubble_sort(a) ! simple bubble sort. implicit none integer, parameter :: long =selected_int_kind(12) real, intent(inout) :: a(:) real :: temp integer(kind=long) :: start, bubble, count1, count3 count1 = 0 count3 = 0 do start = (size(a)-1), 1, -1 do bubble = start, (size(a)-1) count3 = count3+1 if ( a(bubble) .le. a(bubble+1) ) exit count...

Binqry Tree sort
Hi all, We have an unsorted set like S. We put the elements of the set sequentially on the leaves on a conplete binary tree. I'm looking for an algorithm to sort the set S with this binary tree structure. The result should be available on the leaves of the tree again. Example: S = {5, 2, 3, 1} Initial Tree: __ / \ __ __ / \ / \ ...

Sorting Tree Algorithm
Hello, I am seeking a very efficient algorithm for sorting nodes of a tree representation in what I call Parent-Child-Grandchild order. The Apl I use is APL+Win. The input representation of the tree, is a two column nested integer matrix, and might might look like this: Parent Children 1 (2 3 4) 2 (5 6 ) 3 zilda 4 zilda 5 (7 8) 6 zilda 7 zilda 8 zilda 9 zilda ( this is an orphan) 10 zilda ( another orphan) The r...

Sorted heap trees #2
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:...

non dominated sorting procedure
Hello, Has anyone every written a fast non -dominating sorting procedure under matlab? Because my version of it is quite slow, and its speed is a key issue for my algorithms performance. Regards Qreg Qreg wrote: > > > Hello, > > Has anyone every written a fast non -dominating sorting procedure > under > matlab? Because my version of it is quite slow, and its speed is a > key > issue for my algorithms performance. > > Regards > Qreg > I do not know what a non-dominating sorting procedure is, but if you provide this group with some code you have written...

rb-tree creation from sorted sequence
Hi everyone! I could not find an Algorithm-Newsgroup so I tried comp.theory as most people an this list seem to have a rather broad knowlede of CS. :-) I've been trying to find a Paper describing a method to construct a red-black tree from a sorted sequence in linear time. Does anyone remember articles/papers about this issue? Thanks Arne Arne Ehrlich wrote: > Hi everyone! > > I could not find an Algorithm-Newsgroup so I tried comp.theory > as most people an this list seem to have a rather broad knowlede > of CS. :-) > > I've been trying to find a P...

Sorting the Cell Array
Hey, I am having some trouble with phylogentic trees. After opening up a tree, I use the get function to extract the branch distances and node names (10 external leafs and 9 internal branches). However, they are not in the proper order. I want to sort the leafs and branches so I have it set up as shown below: *distance will be the branch and leaf distances extracted from the tree. Leaf1 distance Leaf2 distance .... Leaf10 distance Branch1 distance Branch2 distance .... Branch9 distance However, the results are usually Branches first then Leafs and they are out of order... for ...

Sorted List (binary tree) why no built-in/module?
Unless I've totally missed it, there isn't a binary tree/sorted list type arrangement in Python. Is there a particular reason for this? Sometimes it might be preferable over using a list and calling list.sort() all the time ;) On a somewhat unrelated note, does anyone know how python searches lists when you do things list list.index(n), is it a binary search, or does it just scan the list? ...

Binary Search Tree Vs Quick Sort
I have started to implement my own version of a binary search tree, i use this data structure to sort my own version of a doubly linked link list. It seems to work rather well but i would like to try and speed it up. Is using a Binary Search Tree as good as Quick Sort? From what i remember from the lectures I attended they are both O ( n log n ). I understand that both of these sorts run best when the pivot/root item is the half value from the list. If the list is already in order they both become O(n^2) to do nothing at all. What is the best way of selecting Pseudo Random items from...

Is it possible to auto-sort the feature tree in Numerical order?
Our parts and assys are named with the parts number. Ex. 9990012345 Is it possible to sort the feature tree in numerical order? We are using SolidWorks 2003, should be upgrading in a couple of weeks to 2004. I have it in my list of macro's to create. You could only do it on assemblys because the assembly component order isn't history based. Corey "SW Monkey" <google311.50.spydermonkey@spamgourmet.com> wrote in message news:1104261482.443260.314050@f14g2000cwb.googlegroups.com... > Our parts and assys are named with the parts number. Ex. 9990012345 > > ...

recommended libraries for B-trees / linked lists / sort etc . . .
Hi, I'd like to write an applet, which will create many objects (all of the same type) , which can be identified by two integers X and Y. At a later moment I'd like to retrieve the previously created / calculated object by specifying it's X and Y value. I think, that a B-tree might be the right data structure for storing my data, as I will continiously add / search / remove elements. Instead of implementing one more version of a B-Tree or a similiar structure I wanted to know whether there are already good open source libraries, that implement such data structures (B-Tree...

Trees? Subprojects? Threads? Or How do I sort multiple levels of nested relations?
Hi all, I'm not sure exactly what words to use or how to Google this. (I keep coming up with BOL links.) So, I'm going to ask the group for a starting point or proper terms to even describe what I'm doing. Is this a "thread handler? Or a "hierarchy tree" or what? ----------------------- Basically, I'm working on a project that will be a task and project tracking tool. What I've been asked to do is provide functionality for two things at a Manager level. 1. Radar lists 2. sub projects. Both of them involve the possibility of having a 1. Project 1.A Sub...

trees, trees, trees
there is a table with the following data: col1 col2 A B B C Z A Z D M N M P X Y columns col1 and col2 are in parent-child relation. from the above table one can conclude the following three hierarchies: Z-A-B-C M X \ / \ | D N P Y the problem: is there a way to get the following result? col1 col3 A Z/A/B/C/D B Z/A/B/C/D Z Z/A/B/C/D M M/N/P X X/Y or col1 col3 A Z/A/B/C/D B Z/A/B/C/D C Z/A/B/C/D D Z/A/B/C/D Z Z/A/B/C/D M M/N/P N M/N/P P M/N/P X X...

Sorting out sort
I'm trying to extract a column from a flatfile database and print it alphabetically. I can get the data out, but I can't get it to sort. The database is pipe-separated in a plain text file and looks like this: Ref_no|Title|County|Another_field|And_another|And_another 1234|A Name|Devon|Data here|More data here|And more data 1234|A Name|Somerset|Data here|More data here|And more data 1234|A Name|Nottinghamshire|Data here|More data here|And more data 1234|A Name|Essex|Data here|More data here|And more data .... and so on My routine is as follows: #open the file open (INFILE, 'dat...

sorted or .sort() ?
My poor understanding is that the difference between `sorted(somelist, key=lambda x:...)` and `somelist.sort(lambda x,y...)` is that one returns a new list and the other sorts in-place. Does that mean that .sort() is more efficient and should be favored when you can (i.e. when you don't mind changing the listish object)? Peter Bengtsson <peterbe@gmail.com> writes: > My poor understanding is that the difference between `sorted(somelist, > key=lambda x:...)` and `somelist.sort(lambda x,y...)` is that one > returns a new list and the other sorts in-place. Yes. > Does th...

B tree, B+ tree and B* tree
I understand what B tree is. However I don't have any material covering B+ and B* trees. Is B+ tree also the same as B* tree? What differences between B tree and B+/B* trees? Thanks for your help! "Stub" <stub@asof.com> wrote: > I understand what B tree is. However I don't have any material covering B+ > and B* trees. > > Is B+ tree also the same as B* tree? > > What differences between B tree and B+/B* trees? In comp.lang.c only C trees are on-topic. For C++ trees try comp.lang.c++. For B/B+/B* trees try comp.programming. Regards -- ...

R-trees, R+-trees and R*-trees
Hi, I see R-trees, R+-trees and R*-trees on the web. And there are tons of paper. But I'm not sure what is the difference between them. Would you please help me? And are there any free implemenation of these trees in C++? Best wishes, Peng PengYu.UT@gmail.com wrote: > Hi, > > I see R-trees, R+-trees and R*-trees on the web. And there are tons of > paper. But I'm not sure what is the difference between them. Would you > please help me? And are there any free implemenation of these trees in > C++? > Go here: http://www.nist.gov/dads/ Regards Stefan > Bes...