Python 3.x Changing Starter Code Please just don\'t copy and paste read the ques

Question

Python 3.x Changing Starter Code Please just don't copy and paste read the question:

What I understand from this question is that I have some starter code that I need to change to work with KVTreenodes which are classes I cannot change the KVTreenode file which must be imported. I also have a testcase to make sure that it's working but since it is so long I'll post it on pastebin(https://pastebin.com/u7zPyRfB)

Here is the starter Code:

KVTreenode.py

Question 2 (15 points): Purpose: To adapt some working code to a slightly modified purpose. Degree of Difficulty: Moderate In class we discussed binary search trees, and basic operations on them. The code for these operations can be found in the file bstprim.py on the Assignment 9 Moodle page. In this question, you will adapt the bstprim.py file to use the key-value TreeNode class As we also discussed in class, the KVTreeNode class is variant of the treenode class. The key-value treenode allows us to organize the data according to a key, and store a data value associated with it. You can find the implementation in file KVTreeNode. py. Adapt the primitive BST functions from bstprim.py to use the KVTreellode class. The KVTreeNodes in the tree should have the binary search tree property on the keys, but not the values. The functions you need to adapt are as follows: member prim(t,k) Returns the tuple True, v, if the key k appears in the tree, with associated value v. If the key k does not appear in the tree, return the tuple False, None. insert prim(t,k,v) Stores the value v with the key k in the Table t . If the key k is already in the tree, the value v replaces the value currently associated with it. In this case, it returns the tuple (False, t) even though t did not change structure in this case . If the key is not already in the tree, the key and value are added to the tree. In this case the function returns the tuple (True, t2). Here, t2 is the same tree as t, but with the new key, value added to it. delete_prim(t,k) If the key k is in the tree t, delete the node containing k (and its value) from the tree and return the pair (True, t2) where t2 is the tree after deleting the key-value pair, return the pair (False t) if the key k is not in the given tree t (t is unchanged).

Explanation / Answer

import KVTreeNode as TN

def member_prim(tnode, key):
    """
    Purpose:
        Check if value is stored in the binary search tree.
    Preconditions:
        :param tnode: a KVTreeNode with the BST property
        :param key: a key
    Postconditions:
        none
    :return: a pair True, value if key is in the tree
             a pair False, None if the key is not in the tree
    """
    if tnode is None:
        return False, None
    elif tnode.key is key:
        return True, tnode.value
    elif key < tnode.key:
        return member_prim(tnode.left, key)
    else:
        return member_prim(tnode.right, key)

def insert_prim(tnode, key, value):
    """
    Insert a new key,value into the binary search tree.
    Preconditions:
        :param tnode: a KVTreeNode with the BST property
        :param key: a key
    Postconditions:
        If the key is not already in the tree, it is added.
        If the key is already in the tree, the old value is replaced
        with the given value.
    Return
        :return: tuple (flag, tree)
        flag is True if insertion succeeded;
                tree contains the new key-value
        flag is False if the value is already in the tree,
                the value stored with the key is changed
    """
    if tnode is None:
        return True, TN.KVTreeNode(key, value)
    else:
        if tnode.key is key:
            tnode.value = value
            return False, tnode
        elif key < tnode.key:
            left, left_val = insert_prim(tnode.left, key, value)
            if left:
                tnode.left = left_val
                return True, tnode
            else:
                return False, tnode
        else:
            right, right_val = insert_prim(tnode.right, key, value)
            if right:
                tnode.right = right_val
                return True, tnode
            else:
                return False, tnode

    return False, None

def delete_prim(tnode, key):
    """
    Delete a value from the binary search tree.
    Preconditions:
        :param tnode: a KVTreeNode with the BST property
        :param key: a key
    Postconditions:
        If the key is in the tree, it is deleted. The tree
        retains the binary search tree property.
        If the key is not there, there is no change to the tree.
    Return
        :return: tuple (flag, tree)
        flag is True if deletion succeeded;
                tree is the resulting without the value
        flag is False if the value was not in the tree,
                tree returned unchanged
    """
    def delete(tnode):
        if tnode is None:
            return False, tnode
        else:
            ckey = tnode.key
            if ckey == key:
                return reconnect(tnode)
            elif key < ckey:
                flag, subtree = delete(tnode.left)
                if flag:
                    tnode.left = subtree
                return flag, tnode
            else:
                flag, subtree = delete(tnode.right)
                if flag:
                    tnode.right = subtree
                return flag, tnode

    def reconnect(delthis):
        if delthis.left is None and delthis.right is None:
            # the deleted node has no children
            return True, None
        elif delthis.left is None:
            # the deleted node has one child
            return True, delthis.right
        elif delthis.right is None:
            # the deleted node has one child
            return True, delthis.left
        else:
            # the deleted node has two children
            left = delthis.left
            right = delthis.right
            # walk all the way to the right from left
            walker = left
            while walker.right is not None:
                walker = walker.right
            walker.right = right
            return True, left

    return delete(tnode)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.