Re: Algorithm for inserting numbers in a list?

I wrote:

On your first pass, you might simply assign consecutive numbers. On
your second pass, if you need to insert a number between two
consecutive elements (n and n+1), you simply add a level, and number
the newly inserted elements n.1, n.2, n.3, etc. On later passes, you
may add numbers with even more components.

Note that the hard case here is where you are continually adding
levels to the left of some sequence, you need a way to add space
there, e.g. by starting counting sequences at 2 (if 1 is your lowest
number, or numbering sequences from 1 if 0 is your lowest number),
reserving 1 (or 0) as the number for entries added to the left edge of
some sub-tree. e.g:

2
3
4
....

then
1.2// added before two
1.3
1.4
...
2
2.2 // added between 2 and 3
2.2.2 // added between 2.2 and 2.3
2.2.3
2.2.3.1.2 // added between 2.2.3 and 2.2.3.2
2.2.3.2 // added between 2.2.3 and 2.2.4
2.2.4
...
2.3
2.4
...
3
4

You can do a similar construction with a modified trinary numbering of
binary trees, 0 means left child, 1 means self, 2 means right child.
0001
001
0021
01
0201
021
0221
1
2001
201
2021
21
2201
221
2221

Note that all numbers of nodes in the tree are a string of 0's and 2's
with a terminal 1. You can use lexicographic ordering to know where
two elements in the tree are relative to each other, and the "key"
(number) is the path to take from the root to find the element in the
tree.

You would also do perfectly well using the constructions Torben and
Andy mentioned (e.g. perhaps better). The rational numbers form a
nice representation of any finite digit sequence. I believe if you
prepend a "0." onto the trinary numbering you have a nice trinary
rational number in the open interval (0,1).

Worth mentioning, is that you can separate the numbering system (how
you form the keys) from the method you use to search for elements in
your "tree". That is, if you number based on an artificial tree that
you never rebalance, you may get quite long keys. However, you can
build a separate search structure which you do rebalance as needed
that allows you to look up the entries quite efficiently and does not
suffer perfromance degradation due to the order elements are added,
except as the actual key comparison does.

Hope this helps,
-Chris

******************************************************************************
Chris Clark Internet: christopher.f.clark@xxxxxxxxxxxxxxxxxxxxxx
Compiler Resources, Inc. or: compres@xxxxxxxxxxxxx
23 Bailey Rd Web Site: http://world.std.com/~compres
Berlin, MA 01503 voice: (508) 435-5016
USA fax: (978) 838-0263 (24 hours)
------------------------------------------------------------------------------
.

Relevant Pages

  • Re: OT? evolution explains what?
    ... > tree ring info but I'm wondering if there is anything more you can add ... > original starting cell, right? ... Best evidence at the moment is that it was RNA, ... sequence 18S rna genes, common to all living things (apart from viruses, ...
    (uk.philosophy.atheism)
  • Re: The complete infinite binary tree has only countably many infinite paths, says WM.
    ...   That is not what you must do. ... Denote the leading node of any sequence of nodes by its number followed ... In that infinite tree, ...
    (sci.logic)
  • Re: Balancing a Binary Tree
    ... you do not have to rebalance the tree when adding/removing data. ... absolutely the minimal average search time, ... the absolute optimum balance. ...
    (comp.programming)
  • Re: Compact subsets of {0,1}^N
    ... > the case where a is the empty sequence, ie a sequence of length 0: ... > T be the tree of all finite sequences a such that S_a intersect K ... > f(every finite initial segment of a) is an initial segment of f. ... each of which is a sibling. ...
    (sci.math)
  • Re: Compact subsets of {0,1}^N
    ... >the intersection of a descending sequence of nonnul closed subsets of K. ... >> a sibling if it is the empty string or an n-sibling for some n. ... t' starts with t if and only if t' is a descendant of t; ... and in the other we're thinking about the tree structure. ...
    (sci.math)