Re: Algorithm for inserting numbers in a list?

On 8 abr, 18:36, Chris <spam_me_...@xxxxxxxxxx> wrote:
[..]

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.

Does anyone have a suggestion for a different data structure I can use?

You _can_ use a balanced search tree as long as you store the keys in
the nodes. I mean storing the full string of every key in the
corresponding node. If long strings are a problem, use a rope (http://
en.wikipedia.org/wiki/Rope_%28computer_science%29).

Cheers,
Martin
.

Relevant Pages

  • Re: Red/black tree
    ... The red-black tree uses the same kind of rotations to rebalance a binary search ... Compared with the AVL tree, ... rebalancing an r-b tree tends to be faster ...
    (borland.public.delphi.non-technical)
  • Re: Algorithm for inserting numbers in a list?
    ... The requirement that the ascending number or key assigned to an element can never change, though, makes rebalancing hard. ... Store everything in a binary tree. ...
    (comp.theory)
  • Re: Source of Guy Steele quote
    ... Steel is also interested in balancing the amount of time spent on those chunks automatically by treating all data as a tree and rebalancing the tree in different ways at runtime depending on what sort of computation needs to be done on it. ...
    (comp.lang.lisp)
  • Re: Binary Trees Help!
    ... > The effect of deleting a node 'x' before and then a node 'y' gives you ... > a tree different than if you delete the nodes in reverse order. ... even with rebalancing this could not make a ... and the trees were "sane" to begin with (can't say I tried ...
    (comp.graphics.algorithms)
  • Re: improve strlen
    ... The biggest optimization is that the code is bigger. ... each test string is tested ... The object on right side is type tree, ... The way I see it is that C is portable assembler, ...
    (comp.lang.asm.x86)