FAQ
Im working on an AVL tree that consists of balancing the tree everytime
you add an object. Im not quite grasping the concept on how to do this
with python. I have seen a few topics on the web about this, and i
clearly understand how when the balance of an AVL tree get to 2 or -2
you have to do a R, L, LR, or a RL rotation. Could anyone possibly help
me/point me in the right direction as far as checking the balance and
actually balancing the tree? Thanks in advance

Search Discussions

  • John Machin at Nov 22, 2006 at 1:16 am

    scba... at gmail.com wrote:
    Im working on an AVL tree
    Is this homework?
    that consists of balancing the tree everytime
    you add an object.
    That's a peculiar kind of AVL tree. Normally it is *not* necessary to
    balance the tree every time a node is added -- it's done only if a
    constraint is breached.
    Im not quite grasping the concept on how to do this
    with python.
    Could you do it in any other language?
    I have seen a few topics on the web about this, and i
    clearly understand how when the balance of an AVL tree get to 2 or -2
    you have to do a R, L, LR, or a RL rotation. Could anyone possibly help
    me/point me in the right direction as far as checking the balance and
    actually balancing the tree? Thanks in advance
    Perhaps if you could show us what you have done already -- I'd be
    expecting a class to represent a node, and maybe another to represent
    the root of the tree -- and give us an idea of your Python proficency
    level (so that we can tailor the advice accordingly), we could help
    you.

    Regards,
    John
  • Scbauer at Nov 23, 2006 at 12:04 am

    John Machin wrote:
    scba... at gmail.com wrote:
    Im working on an AVL tree
    Is this homework?
    Yes, this is homework.
    that consists of balancing the tree everytime
    you add an object.
    That's a peculiar kind of AVL tree. Normally it is *not* necessary to
    balance the tree every time a node is added -- it's done only if a
    constraint is breached.
    You're right the AVL Tree shouldnt be updated everytime.
    Im not quite grasping the concept on how to do this
    with python.
    Could you do it in any other language?
    No, this is an Advanced Algorithms class have to use python
    I have seen a few topics on the web about this, and i
    clearly understand how when the balance of an AVL tree get to 2 or -2
    you have to do a R, L, LR, or a RL rotation. Could anyone possibly help
    me/point me in the right direction as far as checking the balance and
    actually balancing the tree? Thanks in advance
    class AVLTree:
    """Holds operations of tree"""
    def __init__(self):

    self.__root = None
    self.__stack=[]
    stack = self.__stack

    def addNode(self, data):
    """ Add node for tree"""
    return Node(data)

    def insert(self, data):
    if self.__root == None:
    self.__root = Node(data)
    else:
    current = self.__root
    done = False
    while not done:
    if data < current.get_data():
    if current.left == None:
    current.left = Node(data)
    stack.append(current)

    done = True
    else:
    current = current.left
    else:
    if current.right == None:
    current.right = Node(data)
    stack.append(current)

    done = True
    else:
    current = current.right
    Perhaps if you could show us what you have done already -- I'd be
    expecting a class to represent a node, and maybe another to represent
    the root of the tree -- and give us an idea of your Python proficency
    level (so that we can tailor the advice accordingly), we could help
    you.
    Basically what im trying to do is use a stack to keep track of the
    items in the AVL tree so that rotations will go smoothly. Having
    problems with the stack getting initialized and actually storing the
    data there. So that i can reference the elements stack[-3].left =
    stack[-2].right and so on for balancing.

    thanks
    scbauer
  • Scbauer at Nov 23, 2006 at 12:16 am
    This is one of the errors that im getting

    Traceback (most recent call last):
    File "<pyshell#49>", line 1, in <module>
    t.insert(5)
    File "/Users/stevenbauer/Desktop/AVL.py", line 68, in insert
    stack.append(current)
    NameError: global name 'stack' is not defined
  • BearophileHUGS at Nov 23, 2006 at 12:26 am

    scbauer wrote:
    This is one of the errors that im getting
    Traceback (most recent call last):
    File "<pyshell#49>", line 1, in <module>
    t.insert(5)
    File "/Users/stevenbauer/Desktop/AVL.py", line 68, in insert
    stack.append(current)
    NameError: global name 'stack' is not defined
    def __init__(self):
    self.__root = None
    self.__stack=[]
    stack = self.__stack

    def addNode(self, data):
    .....
    stack.append(current)


    Some partial suggestions:
    - Why do you use __? Use them only when necessary. My suggestion is to
    use:
    self._stack = []
    - What's the purpose of stack = self.__stack ? It it does nothing
    there.
    - stack.append(current) can't find the stack name, because it's not
    present in this scope, it's present into the __init__ only. My
    suggestion is to use the instance attribute name.

    You can probably fix that problem now.

    Bye,
    bearophile
  • John Machin at Nov 23, 2006 at 12:29 am

    scbauer wrote:
    John Machin wrote:
    scba... at gmail.com wrote:
    Im working on an AVL tree
    Is this homework?
    Yes, this is homework.
    It was a rhetorical question :-)
    that consists of balancing the tree everytime
    you add an object.
    That's a peculiar kind of AVL tree. Normally it is *not* necessary to
    balance the tree every time a node is added -- it's done only if a
    constraint is breached.
    You're right the AVL Tree shouldnt be updated everytime.
    Im not quite grasping the concept on how to do this
    with python.
    Could you do it in any other language?
    No, this is an Advanced Algorithms class have to use python
    I meant: do you have the ability ("can") (not the permission ("may"))
    to do it in another language.
    I have seen a few topics on the web about this, and i
    clearly understand how when the balance of an AVL tree get to 2 or -2
    you have to do a R, L, LR, or a RL rotation. Could anyone possibly help
    me/point me in the right direction as far as checking the balance and
    actually balancing the tree? Thanks in advance
    class AVLTree:
    """Holds operations of tree"""
    def __init__(self):

    self.__root = None
    self.__stack=[]
    stack = self.__stack

    def addNode(self, data):
    """ Add node for tree"""
    return Node(data)

    def insert(self, data):
    if self.__root == None:
    self.__root = Node(data)
    else:
    current = self.__root
    done = False
    while not done:
    if data < current.get_data():
    if current.left == None:
    current.left = Node(data)
    stack.append(current)

    done = True
    else:
    current = current.left
    else:
    if current.right == None:
    current.right = Node(data)
    stack.append(current)

    done = True
    else:
    current = current.right
    and where's the definition of your Node class?
    Perhaps if you could show us what you have done already -- I'd be
    expecting a class to represent a node, and maybe another to represent
    the root of the tree -- and give us an idea of your Python proficency
    level (so that we can tailor the advice accordingly), we could help
    you.
    Basically what im trying to do is use a stack to keep track of the
    items in the AVL tree so that rotations will go smoothly. Having
    problems with the stack getting initialized and actually storing the
    data there. So that i can reference the elements stack[-3].left =
    stack[-2].right and so on for balancing.
    ... and avoiding trouble when there are fewer than 3 elements in the
    stack.

    I presume that you a righteous dude, and are avoiding the temptation to
    google for "AVL tree Python".

    So, I'll give you just one hint:

    Being righteous, you may wish to examine the ancient scriptures: find
    volume 3 of the gospel according to Saint Donald Knuth; therein lies a
    description (in arcane notation) of how to insert into a "balanced
    tree" without using a stack. If a dumb cluck like me could translate
    that into C (with no gotos) and get it to work, a smart lad should have
    no trouble translating it into Python.

    HTH,
    John

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
grouppython-list @
categoriespython
postedNov 22, '06 at 12:22a
activeNov 23, '06 at 12:29a
posts6
users3
websitepython.org

People

Translate

site design / logo © 2022 Grokbase