AVL Balancing

[John Machin]

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