A Tree class, my $0.02 contribution to the python community.

Antoon Pardon wrote:

Comments are welcome:

http://www.pardon-sleeuwaegen.be/antoon/avltree.html

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/

Op 2005-10-12, Steve Holden schreef <st***@holdenweb.com>:

Antoon Pardon wrote:

Comments are welcome:

http://www.pardon-sleeuwaegen.be/antoon/avltree.html

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?
The underlying implementation is an AVL balanced binary tree with
inorder threading.
Sounds like "cdict" might be a better name ...

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

Steve Holden wrote:

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?

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.
js******@aero-graphics.com

"Antoon Pardon" <ap*****@forel.vub.ac.be> wrote:

Comments are welcome:

http://www.pardon-sleeuwaegen.be/antoon/avltree.html

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

Antoon Pardon wrote:

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.

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

Op 2005-10-12, George Sakkis schreef <gs*****@rutgers.edu>:

"Antoon Pardon" <ap*****@forel.vub.ac.be> wrote:

Comments are welcome:

http://www.pardon-sleeuwaegen.be/antoon/avltree.html
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):

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.
def nextkey(self, key):
iter = self[key:]
first = iter.next()
if key not in self: return first
else: return iter.next()
I think the if statement can be replaced by:

if not self.cmp(key, first) == 0: return first
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
?

It skips keys/items/values.

radio = [ .... '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' ]
letters = 'abcdefghijklmnopqrstuvwxyz'
from avltree import Tree
t=Tree(zip(radio,letters))
t.keys('choco',None,3) ['delta', 'golf', 'juliet', 'mike', 'papa', 'sierra', 'victor', 'yankee'] t.values('bureau',None,4)

['c', 'g', 'k', 'o', 's', 'w']
What would you have in mind if step would have been a string here?

--
Antoon Pardon

Antoon Pardon <ap*****@forel.vub.ac.be> writes:

The underlying implementation is an AVL balanced binary tree with
inorder threading.

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:

http://cr.yp.to/critbit.html

See:

http://www.cs.rice.edu/~scrosby/hash/

for some stuff about the dangers of hash tables.