I am trying to create a Randomized Binary Search Tree. I am following the instructions (pseudo code) on this web page. Also I am doing this with TEAP (Tree Heap) technique of given the elements different priorities and thus making a balanced Binary Search Tree.
The code is what follows:
import random
class TreapNode:
"""Skapar en nod för det randomiserade binära sökträdet"""
def __init__(self, value = None, parent = None, left_child = None, right_child = None):
self.val = value
self.pri = random.randint(-1000, 1000)
self.par = parent
self.left = left_child
self.right = right_child
def addParent(self, p):
"""Tilldelar noden en förälder"""
self.par = p
def addLeft(self, lc):
"""Tilldelar noden ett barn till vänster"""
self.left = lc
def addRight(self, rc):
"""Tilldelar noden ett barn till höger"""
self.right = rc
def addValue(self, val):
"""Tilldelar noden ett värde, en s.k. adress"""
self.val = val
def getParent(self):
"""Returnerar nodens förälder"""
return self.par
def getLeft(self):
"""Returnerar nodens vänstra barn"""
return self.left
def getRight(self):
"""Returnerar nodens högra barn"""
return self.right
def getValue(self):
"""Returnerar nodens värde/adress"""
return self.val
def getPriority(self):
"""Returnerar nodens prioritet"""
return self.pri
class BalancedBinaryTree:
"""Skapar ett tomt binärt sökträd som är välbalanserat"""
def __init__(self):
self.root = None
self.size = 0
self.string = []
def rotate_left(self, u): # privat
"""Byter plats på noden u och dess högra barn genom rotation""" #denna algoritm bevarar
w = u.getRight() #"binära-sökträds" egenskapen
w.addParent(u.getParent) #hos varje nod
if w.getParent() != None:
p = w.getParent()
if p.getLeft() == u:
w.getParent().addLeft(w)
else:
w.getParent().addRight(w)
u.addRight(w.getLeft())
if u.getRight() != None:
u.getRight().addParent(u)
u.addParent(w)
w.addLeft(u)
if w.getParent() == None:
self.root = w
def rotate_right(self, u): # privat
"""Byter plats på noden u och dess vänstra barn genom rotation""" #denna algoritm bevarar
w = u.getLeft() #"binära-sökträds" egenskapen
w.addParent(u.getParent()) #hos varje nod
if w.getParent() != None:
if w.getParent().getLeft() == u:
w.getParent().addLeft(w)
else:
w.getParent().addRight(w)
u.addLeft(w.getRight())
if u.getLeft() != None:
u.getLeft().addParent(u)
u.addParent(w)
w.addRight(u)
if w.getParent() == None:
self.root = w
def add(self, val):
"""Låter användaren lägga till ett värde, men bara om det inte redan finns"""
u = TreapNode(value = val)
if self.add_node(val, u):
self.bubble_up(u)
self.size += 1
self.string.append(val)
return True
return False
def bubble_up(self, u): # prviat
"""Om prioriteten hos u är lägre än dess förälder, så byter u och föräldern plats"""
while u.getParent() != None and u.getParent().getPriority() > u.getPriority():
if u.getParent().getRight() == u:
self.rotate_left(u.getParent())
else:
self.rotate_right(u.getParent())
if u.getParent() == None:
self.root = u
def findString(self, val):
"""Låter användaren söka efter specifika värden. Returnerar värdet om det finns, annars None"""
w = self.root
while w != None:
if val < w.getValue():
w = w.getLeft()
elif val > w.getValue():
w = w.getRight()
else:
return w.getValue()
return None
def add_node(self, val, node): # privat
"""Tilldelar ett löv ett barn med värdet val""" # här bryts inte "binär-
p = self.find_last(val) # sökträds" regeln
return self.add_child(p, node)
def find_last(self, val): #privat
"""Finner lämplig nod som kan tilldelas ett barn till höger/vänster med värdet val"""
w = self.root
prev = None
#if w != None:
# print(w.getValue())
#else:
# print(w)
while w != None:
prev = w
if val < w.getValue():
w = w.getLeft()
elif val > w.getValue():
w = w.getRight()
else:
return w
return prev
def add_child(self, p, u): #privat
"""Tilldelar en nod p ett barn u till höger/vänster"""
if p == None:
self.root = u
else:
if u.getValue() < p.getValue():
p.addLeft(u)
u.addParent(p)
elif u.getValue() > p.getValue():
p.addRight(u)
u.addParent(p)
else:
print(u.getValue())
print(p.getValue())
return False
return True
def getSize(self):
return self.size
def orderedString(self):
if self.size == 0:
msg = "[]"
return msg
else:
orderedlist = sorted(self.string)
return orderedlist
def main():
# Testkod till TreapNode() klassen
nod = TreapNode()
nod.addParent(TreapNode(value = "abc", left_child = nod))
assert nod.getParent().getValue() == "abc"
assert nod.getParent().getLeft() == nod
assert -1000 <= nod.getPriority() <= 1000
nod.addRight(TreapNode(value=10, parent=nod))
nod.addValue("abcd")
assert nod.getRight().getValue() == 10
assert nod.getValue() == "abcd"
# Testkod till BalancedBinaryTree
tree = BalancedBinaryTree()
assert tree.orderedString() == "[]"
assert tree.getSize() == 0
assert tree.findString("abc") == None
tree.add("abc")
tree.add("aaa")
tree.add("bbb")
assert tree.orderedString() == ['aaa', 'abc', 'bbb']
assert tree.getSize() == 3
tree.add("hej")
tree.add("min")
tree.add("van")
tree.add("pa")
tree.add("andra")
tree.add("sidan")
tree.add("jorden")
tree.add("omg")
tree.add("lol")
tree.add("sos")
assert tree.orderedString() == ['aaa', 'abc', 'andra', 'bbb', 'hej', 'jorden', 'min', 'pa', 'sidan', 'van']
assert tree.getSize() == 10
tree.add("hej") # finns redan i trädet
assert tree.getSize() == 10 # alltså finns ingen dublett
assert tree.findString("hej") == "hej"
assert tree.findString("jorden") == "jorden"
assert tree.findString("sos") == "sos"
assert tree.findString("aldrig") == None
assert tree.findString("nagonsin") == None
# Tidskomplexitet för alla operationer:
#
# add() = O(nlog(n)) där n är antalet element
# findString() = O(log(n))
# getSize() = O(1)
# orderedString() = O(n), eftersom sorted() måste jämföra n element
if __name__ == "__main__":
main()
Now, when I execute this code I get an error message that says AttributeError: 'function' object has no attribute 'getLeft'. Alright, so I check the object that is passed to the function, and this seems to happen:
The element, that is the nodeobject, is passed, eventually, to the rotate_left(self,u) method. Here the parameter u is the nodeobject. I "reach" inside within this nodeobject to get its leftchild. Then in turn I 'reach' within this object back to the Nodeobject, leftchildobjects so called parent. Now things get mixed up: The Parentobject is perverted in some way. It should be identical to the Nodeobject, but I cannot see what I am doing wrong. If I print the nodeobject and its leftchild and leftchildParent, you will notice the difference.
Nodeobject <__main__.TreapNode object at 0x7fcd32c90898>
Leftchildobject <__main__.TreapNode object at 0x7fcd32c908d0>
Leftchildobjects parent (this should obviously be Nodeobject above) <bound method TreapNode.getParent of <__main__.TreapNode object at 0x7fcd32c90898>>
What is happening in the last step?
EDIT
def rotate_left(self, u):
"""Byter plats på noden u och dess högra barn genom rotation"""
p = TreapNode()
p.addParent(u.getRight())
p.addParent(u.getParent)
if p.getParent() != None:
if p.getParent().getLeft() == u:
p.getParent().addLeft(p)
else:
p.getParent().addRight(p)
u.addRight(p.getLeft())
if u.getRight() != None:
u.getRight().addParent(u)
u.addParent(p)
p.addLeft(u)
if p.getParent() == None:
self.root = p
Here is the method where something doesn't work. The if statement if p.getParent().getLeft() == u raises an error namely AttributeError: 'function' object has no attribute 'getLeft'. What exactly am I supposed to do not to raise this error, it looks fine to me(?)
getParent is a method, you have to call it to get the value.
w.addParent(u.getParent())
It's worth noting that the getter/setter pattern doesn't really make sense in Python, and your code would be greatly simplified without it.
EDIT:
Look at the line p.addParent(u.getParent). What's happening there is that you are assigning u.getParent to be the parent of p. But u.getParent is a method. So when you do p.getParent().getLeft(), that's equivalent to u.getParent.getLeft(), which doesn't work because that method does not have a getLeft method.
As to getters and setters: what makes you think you need them? Your method could just as easily be
def rotate_left(self, u):
"""Byter plats på noden u och dess högra barn genom rotation"""
p = TreapNode()
p.par = u.right
p.par = u.par # Is this what you intend to happen?
if p.par: # None is falsy
if p.par.left == u:
p.par.left = p
else:
p.par.right = p
u.right = p.left
if u.right:
u.right.par = u
u.par = p
p.left = u
if not p.par:
self.root = p
I also don't see a __eq__ method defined in your objects. The default __eq__ method only returns True if the two objects are the same instance. Since you use == in your code, that's probably not what you want.