OOP Python: Trying to create Binary Search Tree, gets 'attributeError' obeject gets perverted

Question

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(?)

Patrick Haugh · Accepted Answer · 2018-04-18 13:21:08Z

1

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.

edited Apr 18, 2018 at 13:21

answered Apr 17, 2018 at 12:34

Patrick Haugh

61.3k13 gold badges94 silver badges101 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

SimpleProgrammer Over a year ago

I am calling it? When I run the program I get the error message AttributeError: 'function' object has no attribute 'getLeft'. This happens on the if statement under rotateLeft() when I compare p.getLeft() == u . What o you mean by the getter/setter functions are dispensable, how else would I reach the objects' values?

SimpleProgrammer Over a year ago

Okay so I solved it using the copy.deepcopy() method which creates a copy of an object that can be altered without affecting the original object. But I am still curious about how getter/setter doesn't make sense in Python, if you care how to explain how else I should do it.

Patrick Haugh Over a year ago

@SimpleProgrammer I've made an edit to try and answer your questions. You should look into the difference between equality and identity in Python: you're expecting two objects that have the same attributes to be the same object. It's a subtle difference, but very important. You might also benefit from implementing a __str__ method so you can see the changes in your objects by printing them out. All of these "double underscore" methods can be found here. Don't read that whole page, but use it as a reference.

Collectives™ on Stack Overflow

OOP Python: Trying to create Binary Search Tree, gets 'attributeError' obeject gets perverted

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related