scbauer wrote:
> John Machin wrote:
> > [EMAIL PROTECTED] 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
--
http://mail.python.org/mailman/listinfo/python-list
