AVL Balancing

Discussion in 'Python' started by scbauer@gmail.com, Nov 22, 2006.

  1. Guest

    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
    , Nov 22, 2006
    #1
    1. Advertising

  2. John Machin Guest

    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
    John Machin, Nov 22, 2006
    #2
    1. Advertising

  3. scbauer Guest

    John Machin wrote:
    > 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, Nov 23, 2006
    #3
  4. scbauer Guest

    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
    scbauer, Nov 23, 2006
    #4
  5. Guest

    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
    , Nov 23, 2006
    #5
  6. John Machin Guest

    scbauer wrote:
    > John Machin wrote:
    > > 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
    John Machin, Nov 23, 2006
    #6
    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. Nobody

    question on AVL trees

    Nobody, Dec 24, 2004, in forum: C++
    Replies:
    0
    Views:
    329
    Nobody
    Dec 24, 2004
  2. Nobody
    Replies:
    1
    Views:
    1,446
    Dave O'Hearn
    Dec 26, 2004
  3. Nobody
    Replies:
    3
    Views:
    1,414
    Ben Pfaff
    Dec 29, 2004
  4. Paul Emmons

    AVL trees

    Paul Emmons, Jul 5, 2003, in forum: C Programming
    Replies:
    1
    Views:
    556
    Mike Wahler
    Jul 5, 2003
  5. Evangelista Sami

    question on avl trees

    Evangelista Sami, Nov 21, 2003, in forum: C Programming
    Replies:
    1
    Views:
    298
    Noah Roberts
    Nov 21, 2003
Loading...

Share This Page