scbauer wrote:

John Machin wrote:
scba...@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