Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > A Tree class, my $0.02 contribution to the python community.

Reply
Thread Tools

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

 
 
Antoon Pardon
Guest
Posts: n/a
 
      10-12-2005
Comments are welcome:

http://www.pardon-sleeuwaegen.be/antoon/avltree.html
 
Reply With Quote
 
 
 
 
Steve Holden
Guest
Posts: n/a
 
      10-12-2005
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/

 
Reply With Quote
 
 
 
 
Antoon Pardon
Guest
Posts: n/a
 
      10-12-2005
Op 2005-10-12, Steve Holden schreef <(E-Mail Removed)>:
> 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
 
Reply With Quote
 
dataw0lf
Guest
Posts: n/a
 
      10-12-2005
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.
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
George Sakkis
Guest
Posts: n/a
 
      10-12-2005
"Antoon Pardon" <(E-Mail Removed)> 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


 
Reply With Quote
 
Diez B. Roggisch
Guest
Posts: n/a
 
      10-12-2005
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
 
Reply With Quote
 
Antoon Pardon
Guest
Posts: n/a
 
      10-13-2005
Op 2005-10-12, George Sakkis schreef <(E-Mail Removed)>:
> "Antoon Pardon" <(E-Mail Removed)> 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
 
Reply With Quote
 
Paul Rubin
Guest
Posts: n/a
 
      10-16-2005
Antoon Pardon <(E-Mail Removed)> 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.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Samsung's latest contribution to P&S mediocrity Rich Digital Photography 6 09-03-2009 01:35 PM
eric4 request for contribution Detlev Offenbach Python 0 01-12-2008 01:34 PM
eric4 request for contribution Detlev Offenbach Python 0 01-12-2008 08:50 AM
My humble contribution - wrapper script for dcraw (linux) bizcotti@gmail.com Digital Photography 1 04-01-2007 01:57 AM
B tree, B+ tree and B* tree Stub C Programming 3 11-12-2003 01:51 PM



Advertisments