-
-
Re: A Tree class, my $0.02 contribution to the python community.
Antoon Pardon wrote:[color=blue]
> Comments are welcome:
>
> http://www.pardon-sleeuwaegen.be/antoon/avltree.html[/color]
Does this type bear any relationship at all to what most people call a
tree, which is a bifurcated data structure? Or do you call it a tree for
some other reason?
Sounds like "cdict" might be a better name ...
regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC www.holdenweb.com
PyCon TX 2006 www.python.org/pycon/
-
Re: A Tree class, my $0.02 contribution to the python community.
Op 2005-10-12, Steve Holden schreef <steve@holdenwe b.com>:[color=blue]
> Antoon Pardon wrote:[color=green]
>> Comments are welcome:
>>
>> http://www.pardon-sleeuwaegen.be/antoon/avltree.html[/color][/color]
[color=blue]
> Does this type bear any relationship at all to what most people call a
> tree, which is a bifurcated data structure? Or do you call it a tree for
> some other reason?[/color]
The underlying implementation is an AVL balanced binary tree with
inorder threading.
[color=blue]
> Sounds like "cdict" might be a better name ...[/color]
I don't know. The python dictionary type with its name, seem to refer
to how it is implemented, so I thought Tree was an appropiate name
here as it is implemented as a tree.
--
Antoon Pardon
Comment
-
Re: A Tree class, my $0.02 contribution to the python community.
Steve Holden wrote:
[color=blue]
> Does this type bear any relationship at all to what most people call a
> tree, which is a bifurcated data structure? Or do you call it a tree for
> some other reason?[/color]
I'd think that the 'avl' part would answer that question.
!google avl tree
--
Joshua Simpson -- dataw0lf.org
Lead Network Administrator/Engineer Aero-Graphics Inc.
jsimpson@aero-graphics.com
Comment
-
Re: A Tree class, my $0.02 contribution to the python community.
"Antoon Pardon" <apardon@forel. vub.ac.be> wrote:[color=blue]
> Comments are welcome:
>
> http://www.pardon-sleeuwaegen.be/antoon/avltree.html[/color]
How about adding two shortcut methods, nextkey(k) and prevkey(k), to return the next and previous
key respectively ? For instance nextkey would be equivalent to (untested):
def nextkey(self, key):
iter = self[key:]
first = iter.next()
if key not in self: return first
else: return iter.next()
Also for consistency, nextvalue(k), prevvalue(k), nextitem(k), previtem(k) would be reasonable
additions.
And a question: what does step do if the keys are not integers since you restrict step to be integer
?
George
Comment
-
Re: A Tree class, my $0.02 contribution to the python community.
Antoon Pardon wrote:[color=blue]
> I don't know. The python dictionary type with its name, seem to refer
> to how it is implemented, so I thought Tree was an appropiate name
> here as it is implemented as a tree.[/color]
I too had the impression you're talking about a tree-implementation, not
a mapping based on key compare operations.
Java calls such a thing TreeMap - so maybe TreeDict would be a suitable
name.
Diez
Comment
-
Re: A Tree class, my $0.02 contribution to the python community.
Op 2005-10-12, George Sakkis schreef <gsakkis@rutger s.edu>:[color=blue]
> "Antoon Pardon" <apardon@forel. vub.ac.be> wrote:[color=green]
>> Comments are welcome:
>>
>> http://www.pardon-sleeuwaegen.be/antoon/avltree.html[/color]
>
> How about adding two shortcut methods, nextkey(k) and prevkey(k), to return the next and previous
> key respectively ? For instance nextkey would be equivalent to (untested):[/color]
I'll file this as: I'll probably never need it, so I'm going to resist
the temptation to add them now. If i find out I'm wrong, I can still do
so later.
[color=blue]
> def nextkey(self, key):
> iter = self[key:]
> first = iter.next()
> if key not in self: return first
> else: return iter.next()[/color]
I think the if statement can be replaced by:
if not self.cmp(key, first) == 0: return first
[color=blue]
> Also for consistency, nextvalue(k), prevvalue(k), nextitem(k), previtem(k) would be reasonable
> additions.
>
> And a question: what does step do if the keys are not integers since you restrict step to be integer
> ?[/color]
It skips keys/items/values.
[color=blue][color=green][color=darkred]
>>> radio = [[/color][/color][/color]
.... 'alfa', 'bravo', 'charlie', 'delta', 'echo', 'foxtrot', 'golf', 'hotel', 'india',
.... 'juliet', 'kilo', 'lima', 'mike', 'november', 'oscar', 'papa', 'quebec', 'romeo',
.... 'sierra', 'tango', 'uniform', 'victor', 'whiskey', 'x-ray', 'yankee', 'zulu' ][color=blue][color=green][color=darkred]
>>>
>>> letters = 'abcdefghijklmn opqrstuvwxyz'
>>> from avltree import Tree
>>> t=Tree(zip(radi o,letters))
>>> t.keys('choco', None,3)[/color][/color][/color]
['delta', 'golf', 'juliet', 'mike', 'papa', 'sierra', 'victor', 'yankee'][color=blue][color=green][color=darkred]
>>> t.values('burea u',None,4)[/color][/color][/color]
['c', 'g', 'k', 'o', 's', 'w']
What would you have in mind if step would have been a string here?
--
Antoon Pardon
Comment
-
Re: A Tree class, my $0.02 contribution to the python community.
Antoon Pardon <apardon@forel. vub.ac.be> writes:[color=blue]
> The underlying implementation is an AVL balanced binary tree with
> inorder threading.[/color]
Dan Bernstein argues for switching from hash tables to crit-bit trees
(a/k/a Patricia trees), because of their guaranteed worst case
performance. He also claims:
"Crit-bit trees are faster than comparison-based structures such
as AVL trees and B-trees. They're also simpler, especially for
variable-length strings."
See:
See:
for some stuff about the dangers of hash tables.
Comment
Comment