Re: Algorithm for inserting numbers in a list?

On 8 abr, 18:36, Chris <spam_me_...@xxxxxxxxxx> wrote:
I have a list of N elements. Each element needs to be assigned an
ascending number, such that the number assigned to the first element is
less than the one for the second, which is less than the third, ... The
number assigned to an element can never change.
[..]

Does it have to be a number? Could it be something else?

You might use pointers to the nodes of the trees. Balancing the tree
doesn't change them. They are not "ascending numbers", but they refer
ascending positions within the in-order traversal of the tree. That
is, using the tree, you can check whether one is lesser or greater
than other one in terms of their positions in the sequence (in
logarithmic time). Of course, this is valid only while you have the
tree... But if you don't, you can map some unique identifiers to the
pointers...

Could you give some more details? Why do you need such a structure?

Cheers,
Martin
.

Relevant Pages

  • Re: Algorithm for inserting numbers in a list?
    ... They are not "ascending numbers", ... ascending positions within the in-order traversal of the tree. ... I've come to the conclusion that using word numbers is not a good idea because of the difficulties pointed out by multiple people above -- the keys could get very long. ... So what this means is that each word needs to be duplicated -- once in the main structure, and once in each secondary structure. ...
    (comp.theory)
  • Re: Modeling weird Windows pathnames
    ... We know that the first element is always the root, ... multiple trees), rather than a single rooted tree. ... "a" should resolve to ...
    (comp.lang.java.programmer)
  • Algorithm for inserting numbers in a list?
    ... Each element needs to be assigned an ascending number, such that the number assigned to the first element is less than the one for the second, which is less than the third, ... ... I've been fooling with using unlimited-length keys instead of integers, where the number of bits increases as you need to further subdivide the space between two adjacent elements. ... My thought is that this problem is not unlike building a tree, except that most tree-building algorithms have some means of rebalancing the tree as one branch gets too long. ... The requirement that the ascending number or key assigned to an element can never change, though, makes rebalancing hard. ...
    (comp.theory)
  • Symboling dotted list
    ... This is homework:) please don't tell my teacher. ... I have a problem adding symbol as a first element over a dotted list, ... actually tree. ...
    (comp.lang.lisp)
  • Re: Algorithm for inserting numbers in a list?
    ... ascending number, such that the number assigned to the first element is ... already exist is close to 100%, IMO, but it is not clear what ... -Le Chaud Lapin- ...
    (comp.theory)