AVL Balancing

scbauer scbauer at gmail.com
Thu Nov 23 01:04:51 CET 2006


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




More information about the Python-list mailing list