Re: Binqry Tree sort


To Willem:
> Mergesort or quicksort won't work because they have a sequential stage
> that is O(n) and unparallelizable.

They are parallelizable. I read about their parallel implementation.

> Ah okay. Not sure if that makes much difference, just that you have to
> choose your interconnects very carefully.

The interconnection between processors are like theconnection between a
binary tree.

> The simplest for would probably be a bit like a neural net, with several
> rows, where each is interconnected with the next, two inputs and two outputs,
> where the node simply puts the smaller to one output and the larger to the
> other. Then is is a question of how to connect the nodes together.

Maybe you are right but I am not looking for an artificial life method
like using ANNs.

In addition we have a network (Sorting network) as a parallel
architecture for just sorting elements of set and it's base structure
is ODD-EVEN NEtwork. and the procesors do a little the same as what you
mentiond. The processor elements have 2 inputs and 2 outputs. The first
output will be the smaller value and the output will be the greater
value.

But the processors which I want to use in my bianry tree architecture
all have just one output and they send it to the parent(Upward) and to
two children through connections downward.


To Logan:

> Basically, the root node is a huge bottleneck.

The root node has no bottle neck becasue it just receives data from its
2 children not more than that. And all data go from each tree level to
the next level, upward or downward, step by step & synchronously. Think
about the pipeline idea of computer architectures of Super-Scalars .

To Chuck:

> You failed to quote context, making your post rather useless. That
> is why I asked you to read my sig and the URL it points to before
> posting again. Please do so.

OK Chuck. Is it true now?
To be honest I lost my self confidence. I'm a little afraid this time
you say: you have to answer individually. :)
Anyway, please let me know if I have other mistakes.

Thanks from all
Nejla

.

Relevant Pages

  • Re: Binqry Tree sort
    ... > choose your interconnects very carefully. ... In addition we have a network as a parallel ... But the processors which I want to use in my bianry tree architecture ...
    (comp.programming)
  • Re: to merge two binary tree
    ... node has to be taken as root node in the new tree ...etc ... Surely there must be an algorithm in Knuth. ... The root node of the merge will in general ... to a usual binary-tree insertion algorithm. ...
    (comp.lang.c.moderated)
  • RE: Newbie: Trouble accessing all nodes in a tree view
    ... My tree has a single root node named ... > a new node at a deep level on the tree. ... > listed in the collection is the root node Clients. ...
    (microsoft.public.dotnet.framework.aspnet.webcontrols)
  • Re: How to retrieve the pointer to leaf node of a Binary tree
    ... Now, just to observe, there is no 'the' leaf node; both e and c are leaf nodes. ... left-to right arithmetic expression tree walk is an LRN walk. ... The GetLeafNode method given above returns the pointer to the root node. ...
    (microsoft.public.vc.mfc)
  • Re: Root and leaf node from a hierarchical tree.
    ... Tree strucutres can have any arbitrary depth. ... | Root node has parent_id as null. ... | rootB B-child1 ... | achieve the result by just writing a sql statement. ...
    (comp.databases.oracle.server)