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

Discussion in 'Python' started by Antoon Pardon, Oct 12, 2005.

  1. Antoon Pardon, Oct 12, 2005
    #1
    1. Advertising

  2. Antoon Pardon

    Steve Holden Guest

    Steve Holden, Oct 12, 2005
    #2
    1. Advertising

  3. Op 2005-10-12, Steve Holden schreef <>:
    > 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
    Antoon Pardon, Oct 12, 2005
    #3
  4. Antoon Pardon

    dataw0lf Guest

    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.
    dataw0lf, Oct 12, 2005
    #4
  5. "Antoon Pardon" <> 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
    George Sakkis, Oct 12, 2005
    #5
  6. 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
    Diez B. Roggisch, Oct 12, 2005
    #6
  7. Op 2005-10-12, George Sakkis schreef <>:
    > "Antoon Pardon" <> 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, Oct 13, 2005
    #7
  8. Antoon Pardon

    Paul Rubin Guest

    Antoon Pardon <> 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.
    Paul Rubin, Oct 16, 2005
    #8
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,088
  2. shankha
    Replies:
    0
    Views:
    63
    shankha
    Dec 10, 2013
  3. Tim Golden
    Replies:
    0
    Views:
    69
    Tim Golden
    Dec 10, 2013
  4. Tim Golden
    Replies:
    0
    Views:
    83
    Tim Golden
    Dec 10, 2013
  5. Terry Reedy
    Replies:
    0
    Views:
    71
    Terry Reedy
    Dec 10, 2013
Loading...

Share This Page