5 Replies - 141 Views - Last Post: 10 September 2019 - 11:02 AM Rate Topic: -----

#1 fearless_swami   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 20
  • Joined: 24-September 18

Attribute Error while printing elements of 2-3 tree...

Posted 09 September 2019 - 06:06 PM

I am getting the following error when I am printing al the elements in my 2-3 tree data structure. Here are my initializations:

class Node(object):
    def __init__(self):
        self.guide = None
        # guide points to max key in subtree rooted at node


class InternalNode(Node):
    def __init__(self):
        Node.__init__(self)
        self.child0 = None
        self.child1 = None
        self.child2 = None
        # child0 and child1 are always non-none
        # child2 is none iff node has only 2 children

    def tlist(self):
        children = self.child0.tlist()
        children.extend(self.child1.tlist())
        if not self.child2 is None:
            children.extend(self.child2.tlist())
        offset = ["               " + i for i in children]
        offset.insert(1, self.guide)
        return offset

    def __str__(self):
        return "\n".join(self.tlist())


class LeafNode(Node):
    def __init__(self):
        Node.__init__(self)
        self.value = None
        # guide points to the key

    def tlist(self):
        return [str(self.guide) + " " + str(self.value)]

    def __str__(self):
        return "\n".join(self.tlist())


class TwoThreeTree:
    def __init__(self):
        self.root = None
        self.height = -1



And here is my recursive printAll function

def printAll(p,h):
    if(h==0):
        print(p.guide)
    else:
        printAll(p.child0,h-1)
        printAll(p.child1,h-1)
    if(p.child2 != null):
        printAll(p.child2,h-1)



I know the error has something to do with the fact that the LeafNode class has no child members, but I am unsure how to fix this...any advice? thanks!

Is This A Good Question/Topic? 1
  • +

Replies To: Attribute Error while printing elements of 2-3 tree...

#2 modi123_1   User is online

  • Suitor #2
  • member icon



Reputation: 15262
  • View blog
  • Posts: 61,187
  • Joined: 12-June 08

Re: Attribute Error while printing elements of 2-3 tree...

Posted 09 September 2019 - 07:23 PM

Please copy/paste the full error message.
Was This Post Helpful? 0
  • +
  • -

#3 fearless_swami   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 20
  • Joined: 24-September 18

Re: Attribute Error while printing elements of 2-3 tree...

Posted 10 September 2019 - 05:50 AM

View Postmodi123_1, on 09 September 2019 - 07:23 PM, said:

Please copy/paste the full error message.


Here it is: Attribute Error: "LeafNode object has no attribute 'child2' "
Was This Post Helpful? 0
  • +
  • -

#4 modi123_1   User is online

  • Suitor #2
  • member icon



Reputation: 15262
  • View blog
  • Posts: 61,187
  • Joined: 12-June 08

Re: Attribute Error while printing elements of 2-3 tree...

Posted 10 September 2019 - 07:03 AM

No line number or other information?

Where's your main and all that jazz? Can't really test it without seeing what's up.
Was This Post Helpful? 0
  • +
  • -

#5 fearless_swami   User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • Posts: 20
  • Joined: 24-September 18

Re: Attribute Error while printing elements of 2-3 tree...

Posted 10 September 2019 - 10:41 AM

View Postmodi123_1, on 10 September 2019 - 07:03 AM, said:

No line number or other information?

Where's your main and all that jazz? Can't really test it without seeing what's up.



Here is the full code:

import dis

class Node(object):
    def __init__(self):
        self.guide = None
        # guide points to max key in subtree rooted at node


class InternalNode(Node):
    def __init__(self):
        Node.__init__(self)
        self.child0 = None
        self.child1 = None
        self.child2 = None
        # child0 and child1 are always non-none
        # child2 is none iff node has only 2 children

    def tlist(self):
        children = self.child0.tlist()
        children.extend(self.child1.tlist())
        if not self.child2 is None:
            children.extend(self.child2.tlist())
        offset = ["               " + i for i in children]
        offset.insert(1, self.guide)
        return offset

    def __str__(self):
        return "\n".join(self.tlist())


class LeafNode(Node):
    def __init__(self):
        Node.__init__(self)
        self.value = None
        # guide points to the key

    def tlist(self):
        return [str(self.guide) + " " + str(self.value)]

    def __str__(self):
        return "\n".join(self.tlist())


class TwoThreeTree:
    def __init__(self):
        self.root = None
        self.height = -1


class WorkSpace:
    def __init__(self):
        self.newNode = None
        self.offset = None
        self.guideChanged = None
        self.scratch = [None] * 4


def insert(key, value, tree):
    # insert a key value pair into tree (overwrite existsing value
    # if key is already present)

    h = tree.height

    if h == -1:
        newLeaf = LeafNode()
        newLeaf.guide = key
        newLeaf.value = value
        tree.root = newLeaf
        tree.height = 0

    else:
        ws = doInsert(key, value, tree.root, h)

        if ws != None and ws.newNode != None:
            # create a new root

            newRoot = InternalNode()
            if ws.offset == 0:
                newRoot.child0 = ws.newNode
                newRoot.child1 = tree.root

            else:
                newRoot.child0 = tree.root
                newRoot.child1 = ws.newNode

            resetGuide(newRoot)
            tree.root = newRoot
            tree.height = h + 1


def doInsert(key, value, p, h):
    # auxiliary recursive routine for insert

    if h == 0:
        # we're at the leaf level, so compare and
        # either update value or insert new leaf

        leaf = p  #downcast (unnecessary in python)
        cmp = 0
        if key < leaf.guide:
            cmp = -1
        elif key > leaf.guide:
            cmp = 1

        if cmp == 0:
            leaf.value = value
            return None

        # create new leaf node and insert into tree
        newLeaf = LeafNode()
        newLeaf.guide = key
        newLeaf.value = value

        offset = 1
        if cmp < 0:
            offset = 0
        # offset == 0 => newLeaf inserted as left sibling
        # offset == 1 => newLeaf inserted as right sibling

        ws = WorkSpace()
        ws.newNode = newLeaf
        ws.offset = offset
        ws.scratch = [None] * 4

        return ws

    else:
        q = p  # downcast (unnecessary in python)
        pos = 2
        ws = None

        if key <= q.child0.guide:
            pos = 0
            ws = doInsert(key, value, q.child0, h - 1)

        elif key <= q.child1.guide or q.child2 is None:
            pos = 1
            ws = doInsert(key, value, q.child1, h - 1)

        else:
            pos = 2
            ws = doInsert(key, value, q.child2, h - 1)
        if ws != None:
            if ws.newNode != None:
                # make ws.newNode child # pos + ws.offset of q
                sz = copyOutChildren(q, ws.scratch)

                ws.scratch.insert(pos + ws.offset, ws.newNode)

                if sz == 2:
                    ws.newNode = None
                    ws.guideChanged = resetChildren(q, ws.scratch, 0, 3)
                else:
                    ws.newNode = InternalNode()
                    ws.offset = 1
                    resetChildren(q, ws.scratch, 0, 2)
                    resetChildren(ws.newNode, ws.scratch, 2, 2)

            elif ws.guideChanged:
                ws.guideChanged = resetGuide(q)

        return ws


def copyOutChildren(q, x):
    # copy children of q into x, and return # of children

    sz = 2
    x[0] = q.child0
    x[1] = q.child1
    if q.child2 != None:
        x[2] = q.child2
        sz = 3

    return sz


def resetGuide(q):
    # reset q.guide, and return true if it changes.

    oldGuide = q.guide
    if q.child2 != None:
        q.guide = q.child2.guide
    else:
        q.guide = q.child1.guide

    return q.guide != oldGuide


def resetChildren(q, x, pos, sz):
    # reset q's children to x[pos..pos+sz), where sz is 2 or 3.
    # also resets guide, and returns the result of that

    q.child0 = x[pos]
    q.child1 = x[pos + 1]

    if sz == 3:
        q.child2 = x[pos + 2]
    else:
        q.child2 = None

    return resetGuide(q)


#Used to convert from memory object to function object
# def objects_by_id(id_):
#     for obj in gc.get_objects():
#         if id(obj) == id_:
#             return obj
#     raise Exception("No found")



# def printAll(p,h):
#     if(h==0):
#         print(p.guide)
#     else:
#         printAll(p.child0,h-1)
#         printAll(p.child1,h-1)
#     if(p.child2 is not None):
#         printAll(p.child2,h-1)


def printAll(p,h):
    if(h==0):
        print(p.guide)
    else:
        printAll(p.child0,h-1)
        printAll(p.child1,h-1)
    if(p.child2 is not None and isinstance(p,InternalNode)):
        printAll(p.child2,h-1)



def main():
    t1 = TwoThreeTree()
    insert("a",1,t1)
    insert("b",2,t1)
    insert("c",3,t1)
    insert("d",4,t1)
    print(t1.height)
    printAll(t1.root,t1.height)

main()




Was This Post Helpful? 0
  • +
  • -

#6 modi123_1   User is online

  • Suitor #2
  • member icon



Reputation: 15262
  • View blog
  • Posts: 61,187
  • Joined: 12-June 08

Re: Attribute Error while printing elements of 2-3 tree...

Posted 10 September 2019 - 11:02 AM

Think about this recursive function. If you have an IDE that allows debugging and stepping through, put a break point here and hit each iteration. Consider what happens in lines 228,229, 231.

224def printAll(p,h):
225    if(h==0):
226        print(p.guide)
227    else:
228        printAll(p.child0,h-1)
229        printAll(p.child1,h-1)
230    if(p.child2 is not None and isinstance(p,InternalNode)):
231        printAll(p.child2,h-1)


Consider what happens when you try and send a 'none' child object back into the function. 'none' wouldn't have child0-2 attributes would it? Not likely.

Now you are at a cross roads. You could add more checking at the start of the function to pass over 'non' objects, or take responsibility when calling and making sure that 'child' attribute isn't calling the function in the first place with a 'none'.

Example:
def printAll(p,h):
    if(h==0):
        print(p.guide)
    else:
        if(p.child0 is not None):
            printAll(p.child0,h-1)

        if(p.child1 is not None):
            printAll(p.child1,h-1)

        if(p.child2 is not None and isinstance(p,InternalNode)):
            printAll(p.child2,h-1)

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1