not a binary tree python

Ok, a little background.  The lesson for class specifically said NOT to look up what a binary tree was, and to try and make one from his english description.  I honestly didn't know what they were supposed to look like,  just that they had a way of sorting stuff out as it went into the structure....  We needed a root BinaryTreeNode,  then the BinaryTree,  where we'd put the data...  and it would have a set(), get(), delete(), and list()
the Node would have a key, value, left, right.  and when the nodes go into the binary tree they would go straight into the structure where they belong, the root node would help decide where the new set data would go somehow.....Oh and it had something to do with that crazy Doubly Linked Dictionary we made...

Realized I didn't account for putting stuff in the list that matched the key of the root node.... adding that in.  Going to pull out my string maker for some testing.
Maybe I wasn't so far off from what it's supposed to do after all.

I went and looked at:

wikipedia.. and wow... https://en.wikipedia.org/wiki/Binary_search_tree

I think it would have taken me weeks to follow that and try to guess what they are doing.  I'm going to have to redo my code, cause... this  ain't that...

So from the books description, this is the little monster I made:
                        NOT a binary tree:

from random import randint

class BSTreeNode(object):
    def __init__(self, key, value, left, right):
        self.key = key
        self.value = value
        self.left = left
        self.right = right
       
    def __repr__(self): # (<--left--[key: value]--right-->)
        leftval = self.left and self.left.value or None
        rightval = self.right and self.right.value or None
        return f"left={leftval} [{self.key}:{self.value}] right={rightval}"

class BSTree(object):
    def __init__(self, median):
        self.median = median
        self.root = BSTreeNode(self.median, 'root_node', None, None)
        self.alist = []
        self.alist.append(self.root)   
       
    def list_tree(self):
        for i in self.alist:
            print(i)
           
    def get(self, akey):
        if akey <= self.median:
            i = self.alist.index(self.root)
            print(i)
            sideleft = len(self.alist) - i + 1
            while i >=0:
                node = self.alist[i]
                if node.key == akey:
                    return self.alist[i]
                i -= 1
        elif akey >= self.median:
            i = self.alist.index(self.root)
            length = len(self.alist)
            while i <= length:
                node = self.alist[i]
                if node.key == akey:
                    return self.alist[i]
                i += 1
    def set(self, akey, value):
        if akey < self.median:
            i = self.alist.index(self.root)
            while i >= 0:
                node = self.alist[i]               
                if node.left == None:
                    newnode = BSTreeNode(akey, value, None, self.alist[i])
                    node.left = newnode
                    self.alist.insert(i, newnode)
                    break
                elif node.left != None:
                    i -= 1
                    node = self.alist[i]
                    if node.key <= akey:
                        print(akey)
                        if i - 1 < 0:
                            #beginning of list is bigger then node
                            newnode = BSTreeNode(akey, value, self.alist[i], self.alist[i+1])
                            node.right = newnode
                            nxt = self.alist[i+1]
                            nxt.left = newnode
                            self.alist.insert(i+1, newnode)
                           
                            break
                        elif i - 1 > 0:
                            #not beginning, is bigger then node
                            newnode = BSTreeNode(akey, value, self.alist[i], self.alist[i+1])
                            node.right = newnode
                            nxt = self.alist[i+1]
                            nxt.left = newnode
                            self.alist.insert(i+1, newnode)
                            break
                        else:
                            i -= 1
               
        elif akey > self.median:
            i = self.alist.index(self.root)
            print(f" elif alist index i = {i}")
            length = len(self.alist) - 1
            node = self.alist[i]
            while i <= length:
               
                print("greater while exec.")
                if node.right == None:
                    newnode = BSTreeNode(akey, value, self.alist[i], None)
                    node.right = newnode
                    self.alist.append(newnode)
                    break
                elif node.right != None:
                    i += 1
                    node = self.alist[i]
                    #print(node)
                    #print(akey)
                    if node.key >= akey:
                        if i + 1 >= length:
                            # if last right is bigger
                            newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
                            prev = self.alist[i-1]
                            prev.right = newnode
                            node.left = newnode
                            self.alist.insert(i, newnode)
                            break
                        elif i + 1 <= length:
                            print(akey)
                            # if first-last right is bigger:                       
                            newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
                            node.left = newnode
                            prev = self.alist[i-1]
                            prev.right = newnode                           
                            self.alist.insert(i, newnode)
                            break                   
                        else:
                            i += 1
         else:
            # akey is = to self.median:
            # place the equivelant key on the left or right, depending on   

            # which side is smaller
            i = self.alist.index(self.root)
            length = len(self.alist)
            rightside = len(self.alist) - i
            leftside = 0 + i   
            if length == 1:
                node = self.alist[i]
                newnode = BSTreeNode(akey, value, None, self.alist[i])
                node.left = newnode               
                self.alist.insert(i, newnode)
            elif length > 1:
                rightside = len(self.alist) - i
                leftside = 0 + i   
                if leftside < rightside:
                    node = self.alist[i]
                    if node.left != None:
                        newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
                        node.left = newnode
                        prev = self.alist[i-1]
                        prev.right = newnode                                   
                        self.alist.insert(i, newnode)
                    else:
                        newnode = BSTreeNode(akey, value, None, self.alist[i])
                        node.left = newnode
                        self.alist.append(newnode)
                elif rightside < leftside:
                    node = self.alist[i]
                    if node.right != None:
                        newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
                        prev = self.alist[i-1]
                        prev.right = newnode
                        node.left = newnode
                        self.alist.insert(i, newnode)
                    else:
                        newnode = BSTreeNode(akey, value, self.alist[i], None)
                        node.right = newnode
                        self.alist.append(newnode)
                else:
                    # both sides are equal: add to right:
                    i = self.alist.index(self.root)
                    node = self.alist[i]
                    if node.right != None:
                        i += 1
                        newnode = BSTreeNode(akey, value, self.alist[i-1], self.alist[i])
                        prev = self.alist[i-1]
                        nxt = self.alist[i]
                        prev.right = newnode
                        nxt.left = newnode                   
                        node.left = newnode
                        print(nxt)
                        self.alist.insert(i, newnode)
                    else:
                        newnode = BSTreeNode(akey, value, self.alist[i], None)
                        node.right = newnode
                        self.alist.append(newnode)

                   
    def delete(self, node):
            i = self.alist.index(self.root)
            # take a node out.
            root = self.alist[i]
            length = len(self.alist)
            print(node.key)
            if node.value == 'root_node':
                print('DANGER! cannot remove root node!')
                return None
           
            if node.key <= root.key:
                while i >= 0:
                    i -= 1
                    current = self.alist[i]
                    if current.left == None and current == node:
                        nxt = self.alist[i+1]
                        nxt.left = None
                        self.alist.remove(current)
                        break
                    elif current.left != None and current == node:
                        nxt = self.alist[i+1]
                        prev = self.alist[i-1]
                        nxt.left = prev
                        prev.right = nxt
                        self.alist.remove(current)
                        break
                       
               
            elif node.key >= root.key:
                while i<= length - 1:
                    print(node.key)
                    i += 1
                    current = self.alist[i]
                    if current.right == None and current == node:
                        prev = self.alist[i-1]
                        prev.right = None
                        self.alist.remove(current)
                        break
                    elif current.right != None and current == node:
                        nxt = self.alist[i+1]
                        prev = self.alist[i-1]
                        nxt.left = prev
                        prev.right = nxt
                        self.alist.remove(current)
                        break
                       
    def remove(self, arbit):
        print(arbit)
        length = len(self.alist)
        for i in range(0, length):
            node = self.alist[i]
            print(f"{node.value}:{arbit} < {i} > length = {length}")
            if node.value == arbit:
                self.delete(node)
                # break is necessary!
                # a deleted node will change the size of the list.

                break


# manual test stuff.  also tested with for loops and random integers   
# I knew I was probably on the wrong track so didn't get too in depth
# no way it came this easy,  this book has been a struggle, and this wasn't.         
                               
spam = BSTree(128)
spam.set(128, 'ii')
spam.set(99, 'j')
spam.set(300, 'p')
spam.set(128, 'umm')
spam.set(200, 'o')

spam.set(400, 'l')

spam.set(600, 'y')
spam.set(128, 'juj')
spam.set(430, 'oo')

spam.set(230, 'uu')
spam.set(100, 'tt')
spam.set(44, 'y7')
spam.set(111, 'pop')
spam.set(128, 'lil')
spam.set(128, 'trt')
spam.set(-45, 'olo')
spam.list_tree()

print("****************")
#spam.remove('y7')
#spam.remove('pop')
#spam.remove('l')
#spam.remove('y')
#spam.list_tree()

Comments

Popular posts from this blog

JavaScript Ascii animation with while loops and console.log

playing with trigonometry sin in pygame

JavaScript and a Matrix