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

A

Antoon Pardon

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.
 
D

dataw0lf

Steve said:
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
 
G

George Sakkis

Antoon Pardon said:

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
 
D

Diez B. Roggisch

Antoon said:
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
 
A

Antoon Pardon

Op 2005-10-12 said:
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.
.... '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?
 
P

Paul Rubin

Antoon Pardon said:
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.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,482
Members
44,900
Latest member
Nell636132

Latest Threads

Top