Question

In: Computer Science

Lab 5: Binary Search Tree Implement operations for a Binary Search Tree class starting from the...

Lab 5: Binary Search Tree

Implement operations for a Binary Search Tree class starting from the template provided under the PolyLearn assignment, using the class TreeNode that is also provided. You may (should) implement helper methods that make your code easier to write, read, and understand. You will also need to write test cases of your own as you develop the methods. You may use iterative and/or recursive functions in your implementation.

The following starter files are available .

• binary_search_tree.py

• binary_search_tree_tests.py

Complete the implementations

. • binary_search_tree.py

• binary_search_tree_tests.py

• queue_array.py

The incomplete functions in binary_search_tree.py must be completed and tested

The following is raw code for each file

=========================

binary_search_tree.py

from queue_array import Queue

class TreeNode:
    def __init__(self, key, data, left=None, right=None):
        self.key = key
        self.data = data
        self.left = left
        self.right = right

    def __eq__(self, other):
        return ((type(other) == TreeNode)
                and self.key == other.key
                and self.data == other.data
                and self.left == other.left
                and self.right == other.right
                )

    def __repr__(self):
        return ("TreeNode({!r}, {!r}, {!r}, {!r})".format(self.key, self.data, self.left, self.right))

class BinarySearchTree:

    def __init__(self): # Returns empty BST
        self.root = None

    def is_empty(self): # returns True if tree is empty, else False
        pass

    def search(self, key): # returns True if key is in a node of the tree, else False
        pass

    def insert(self, key, data=None): # inserts new node w/ key and data
        # If an item with the given key is already in the BST, 
        # the data in the tree will be replaced with the new data
        # Example creation of node: temp = TreeNode(key, data)
        pass

    def find_min(self): # returns a tuple with min key and data in the BST
        # returns None if the tree is empty
        pass

    def find_max(self): # returns a tuple with max key and data in the BST
        # returns None if the tree is empty
        pass

    def tree_height(self): # return the height of the tree
        # returns None if tree is empty
        pass

    def inorder_list(self): # return Python list of BST keys representing in-order traversal of BST
        pass

    def preorder_list(self):  # return Python list of BST keys representing pre-order traversal of BST
        pass
        
    def level_order_list(self):  # return Python list of BST keys representing level-order traversal of BST
        # You MUST use your queue_array data structure from lab 3 to implement this method
        q = Queue(25000) # Don't change this!
        pass

======================

binary_search_tree_tests.py

import unittest
from binary_search_tree import *

class TestLab4(unittest.TestCase):

    def test_simple(self):
        bst = BinarySearchTree()
        self.assertTrue(bst.is_empty())
        bst.insert(10, 'stuff')
        self.assertTrue(bst.search(10))
        self.assertEqual(bst.find_min(), (10, 'stuff'))
        bst.insert(10, 'other')
        self.assertEqual(bst.find_max(), (10, 'other'))
        self.assertEqual(bst.tree_height(), 0)
        self.assertEqual(bst.inorder_list(), [10])
        self.assertEqual(bst.preorder_list(), [10])
        self.assertEqual(bst.level_order_list(), [10])

if __name__ == '__main__': 
    unittest.main()

==========================

queue_array.py

# Queue ADT - circular array implementation

class Queue:
    """Implements an efficient first-in first-out Abstract Data Type using a Python List"""

    def __init__(self, capacity, init_items=None):
        """Creates a queue with a capacity and initializes with init_items"""
        self.capacity= capacity         # capacity of queue
        self.items = [None]*capacity    # array for queue
        self.num_items = 0              # number of items in queue
        self.front = 0                  # front index of queue (items removed from front)
        self.rear = 0                   # rear index of queue (items enter at rear)
        if init_items is not None:      # if init_items is not None, initialize queue
            if len(init_items) > capacity:
                raise IndexError
            else:
                self.num_items = len(init_items)
                self.items[:self.num_items] = init_items
                self.rear = self.num_items % self.capacity # % capacity addresses length=capacity

    def __eq__(self, other):
        return ((type(other) == Queue)
            and self.capacity == other.capacity
            and self.get_items() == other.get_items()
            )

    def __repr__(self):
        return ("Queue({!r}, {!r})".format(self.capacity, self.get_items()))

    # get_items returns array (Python list) of items in Queue
    # first item in the list will be front of queue, last item is rear of queue
    def get_items(self):
        if self.num_items == 0:
            return []
        if self.front < self.rear:
            return self.items[self.front:self.rear]
        else:
            return self.items[self.front:] + self.items[:self.rear]

    def is_empty(self):
        """Returns true if the queue is empty and false otherwise
        Must be O(1)"""
        if self.num_items == 0:
            return True
        return False

    def is_full(self):
        """Returns true if the queue is full and false otherwise
        Must be O(1)"""
        if self.num_items == self.capacity:
            return True
        return False

    def enqueue(self, item):
        """enqueues item, raises IndexError if Queue is full
        Must be O(1)"""
        if self.is_full():
            raise IndexError()
        self.items[self.rear] = item
        self.rear += 1
        self.rear %= self.capacity + 1
        self.num_items += 1

    def dequeue(self):
        """dequeues and returns item, raises IndexError if Queue is empty
        Must be O(1)"""

        if self.is_empty():
            raise IndexError()
        temp = self.items[self.front]
        # self.items[self.front] = None
        self.front += 1
        self.front %= self.capacity + 1
        self.num_items -= 1
        return temp
    def size(self):
       """Returns the number of items in the queue
       Must be O(1)"""
       return self.num_items

if __name__ == "__main__":
    q1 = Queue(10)
    print(q1)
    q1.enqueue(1)
    q1.enqueue(2)
    q1.enqueue(3)
    print(q1)
    q2 = Queue(10)
    q2.enqueue(1)
    q2.enqueue(2)
    q2.enqueue(3)
    print(q1==q2)
    print(q2.dequeue())
    print(q2)
    print(q1 == q2)
    print(q2.dequeue())
    print(q2.dequeue())
    q2.enqueue(4)
    q2.enqueue(5)
    q2.enqueue(6)
    q2.enqueue(7)
    q2.enqueue(8)
    q2.enqueue(1)
    q2.enqueue(2)
    q2.enqueue(3)
    print(q2.items)
    print(q2.dequeue())
    print(q2.dequeue())
    print(q2.dequeue())
    print(q2.dequeue())
    print(q2.dequeue())
    print(q2.items,q2.front,q2.rear,q2.get_items())
    print(q2)
    print(q2==q1)

Solutions

Expert Solution

It took 2 hours to complete this so please upvote me for all my efforts 
#
# binary_search_tree.py
#

import sys

class bt_node:
    data  = 0
    left  = None
    right = None

class BinarySearchTree:

    def __init__(self):
        self.tree       = None
        self.tree_list  = []
        self.tree_nodes = []

    def init_node(self, data):
        """
        Create and return a bt_node object that has been initialized
        with the given data and two None children.
        """
        new_node      = bt_node()
        new_node.data = data
        return new_node

    def insert(self, new_node):
        """
        Insert the new_node into the tree at the correct location.
        """
        if self.tree is None:
            self.tree = new_node
        else:
            cursor = self.tree
            while True:
                if new_node.data < cursor.data:
                    if cursor.left is None:
                        cursor.left = new_node
                        break
                    else:
                        cursor = cursor.left
                if new_node.data >= cursor.data:
                    if cursor.right is None:
                        cursor.right = new_node
                        break
                    else:
                        cursor = cursor.right

    def insert_data(self, data):
        """
        Insert a new node that contains the given data into the tree
        at the correct location.
        """
        new_node = self.init_node(data)
        self.insert(new_node)

    def remove(self, data):
        """
        Removes a node from the tree whose data value is the same as
        the argument.
        """
        if self.contains(data):
            cursor = self.tree
            parent = None
            while True:
                if cursor.data == data:
                    break
                elif cursor.data > data:
                    parent = cursor
                    cursor = cursor.left
                elif cursor.data < data:
                    parent = cursor
                    cursor = cursor.right
            if cursor.right and cursor.left:
                successor, successor_parent = self.find_successor(cursor)
                predecessor, predecessor_parent = self.find_predecessor(cursor)
                self.to_array()
                if len(self.tree_list) % 2 == 0:
                    if successor_parent:
                        cursor.data = successor.data
                        self.delete_node(successor, successor_parent)
                    else:
                        cursor.data = successor.data
                        self.delete_node(successor, cursor)
                else:
                    if predecessor_parent:
                        cursor.data = predecessor.data
                        self.delete_node(predecessor, predecessor_parent)
                    else:
                        cursor.data = predecessor.data
                        self.delete_node(predecessor, cursor)
            else:
                if parent:
                    self.delete_node(cursor, parent)
                else:
                    try:
                        successor, successor_parent = self.find_successor(cursor)
                    except AttributeError:
                        predecessor, predecessor_parent = self.find_predecessor(cursor)
                    if successor:
                        cursor.data = successor.data
                        self.delete_node(successor, cursor)
                    else:
                        cursor.data = predecessor.data
                        self.delete_node(predecessor, cursor)

    def delete_node(self, node, parent):
        '''
        Deletes specified node with specified parent
        Should not be called
        '''
        try:
            if parent.left == node:
                if node.left:
                    parent.left = node.left
                elif node.right:
                    parent.left = node.right
                else:
                    parent.left = None
            elif parent.right == node:
                if node.left:
                    parent.right = node.left
                elif node.right:
                    parent.right = node.right
                else:
                    parent.right = None
            else:
                if parent.left == node:
                    parent.left = None
                if parent.right == node:
                    parent.right = None
        except AttributeError:
            print sys.exc_info()
            print '    ', self.to_array()
            print '     ', node.data
            sys.exit(1)



    def find_successor(self, node):
        '''
        Finds the in-order successor of the given node
        '''
        successor_node = node.right
        successor_top  = None
        while True:
            if successor_node.left == None:
                break
            else:
                successor_top = successor_node
                successor_node = successor_node.left
        return successor_node, successor_top

    def find_predecessor(self, node):
        '''
        Finds the in-order predecessor of the given node
        '''
        predecessor_node = node.left
        predecessor_top  = None
        while True:
            if predecessor_node.right == None:
                break
            else:
                predecessor_top = predecessor_node
                predecessor_node = predecessor_node.right
        return predecessor_node, predecessor_top

    def contains(self, data):
        """
        Return True or False depending on if this tree contains a node
        with the supplied data.
        """
        if self.tree is None:
            return False
        else:
            cursor = self.tree
            while True:
                if data < cursor.data:
                    if cursor.data == data:
                        return True
                    if cursor.left is None:
                        return False
                    else:
                        cursor = cursor.left
                if data >= cursor.data:
                    if cursor.data == data:
                        return True
                    if cursor.right is None:
                        return False
                    else:
                        cursor = cursor.right

    def get_node(self, data):
        """
        If the tree contains a node with the supplied data, return
        it. Otherwise return None.
        """
        if self.contains(data):
            cursor = self.tree
            while True:
                if data < cursor.data:
                    cursor = cursor.left
                if data >= cursor.data:
                    if cursor.data == data:
                        return cursor
                    else:
                        cursor = cursor.right
        else:
            return None

    def size(self):
        """
        Return the size of this tree. If it is empty this returns 0.
        """
        if self.tree is None:
            return 0
        else:
            return len(self.to_array())

    def to_array(self):
        """
        Create and fill a list with the data contained in this
        tree. The elements of the returned list must be in the same
        order as they are found during an inorder traversal, which
        means the numbers should be in non-decreasing order.
        """
        if self.tree is None:
            return []
        else:
            self.tree_list  = []
            self.tree_nodes = []
            self.search(self.tree)
            return self.tree_list

    def search(self, node):
        if node != None:
            self.tree_list.append(node.data)
            self.tree_nodes.append(node)
            self.search(node.left)
            self.search(node.right)

binary_search_tree_testcases.py

import unittest
from binary_search_tree import BinarySearchTree

class TestBinarySearchTree(unittest.TestCase):

def __init__(self, *args, **kwargs):
unittest.TestCase.__init__(self, *args, **kwargs)

def setUp(self):
self.bst = BinarySearchTree()
self.node_5 = self.bst.init_node(-5)
self.node_4 = self.bst.init_node(-4)
self.node_3 = self.bst.init_node(-3)
self.node_2 = self.bst.init_node(-2)
self.node_1 = self.bst.init_node(-1)
self.node0 = self.bst.init_node(0)
self.node1 = self.bst.init_node(1)
self.node2 = self.bst.init_node(2)
self.node3 = self.bst.init_node(3)
self.node4 = self.bst.init_node(4)
self.node5 = self.bst.init_node(5)

self.mytree = BinarySearchTree()
self.mytree.insert_data(5)
self.mytree.insert_data(2)
self.mytree.insert_data(3)
self.mytree.insert_data(1)
self.mytree.insert_data(4)
self.mytree.insert_data(0)
self.mytree.insert_data(2.5)
self.mytree.insert_data(8)
self.mytree.insert_data(9)
self.mytree.insert_data(6)
self.mytree.insert_data(4.5)

def test_init_node(self):
node1 = self.bst.init_node(5)
node2 = self.bst.init_node(4)
assert(node1.data == 5)
assert(node1.left == None)
assert(node1.right == None)
assert(node2.data == 4)
assert(node2.left == None)
assert(node2.right == None)

def test_insert(self):
assert(self.bst.tree == None)
self.bst.insert(self.node0)
assert(self.bst.tree.data == self.node0.data)
self.bst.insert(self.node3)
assert(self.bst.tree.right.data == self.node3.data)
self.bst.insert(self.node5)
assert(self.bst.tree.right.right.data == self.node5.data)
self.bst.insert(self.node4)
assert(self.bst.tree.right.right.left.data == self.node4.data)
self.bst.insert(self.node2)
assert(self.bst.tree.right.left.data == self.node2.data)
self.bst.insert(self.node1)
assert(self.bst.tree.right.left.left.data == self.node1.data)

self.bst.insert(self.node_4)
assert(self.bst.tree.left.data == self.node_4.data)
self.bst.insert(self.node_5)
assert(self.bst.tree.left.left.data == self.node_5.data)
self.bst.insert(self.node_2)
assert(self.bst.tree.left.right.data == self.node_2.data)
self.bst.insert(self.node_3)
assert(self.bst.tree.left.right.left.data == self.node_3.data)
self.bst.insert(self.node_1)
assert(self.bst.tree.left.right.right.data == self.node_1.data)

def test_remove(self):
assert(self.mytree.contains(0) == True)
assert(self.mytree.to_array() == [5, 2, 1, 0, 3, 2.5, 4, 4.5, 8, 6, 9])
self.mytree.remove(0)
assert(self.mytree.contains(0) == False)

assert(self.mytree.to_array() == [5, 2, 1, 3, 2.5, 4, 4.5, 8, 6, 9])

assert(self.mytree.contains(4.5) == True)
self.mytree.remove(4.5)
assert(self.mytree.contains(4.5) == False)

assert(self.mytree.to_array() == [5, 2, 1, 3, 2.5, 4, 8, 6, 9])

self.mytree.insert_data(0)
assert(self.mytree.to_array() == [5, 2, 1, 0, 3, 2.5, 4, 8, 6, 9])
assert(self.mytree.contains(1) == True)
self.mytree.remove(1)
assert(self.mytree.contains(1) == False)
assert(self.mytree.contains(0) == True)
assert(self.mytree.to_array() == [5, 2, 0, 3, 2.5, 4, 8, 6, 9])

# RESET
self.setUp()
assert(self.mytree.to_array() == [5, 2, 1, 0, 3, 2.5, 4, 4.5, 8, 6, 9])
self.mytree.remove(5)
assert(self.mytree.to_array() == [6, 2, 1, 0, 3, 2.5, 4, 4.5, 8, 9] or
self.mytree.to_array() == [4.5, 2, 1, 0, 3, 2.5, 4, 8, 6, 9])
self.mytree.remove(6)
assert(self.mytree.to_array() == [4.5, 2, 1, 0, 3, 2.5, 4, 8, 9])
self.mytree.remove(4.5)
assert(self.mytree.to_array() == [4, 2, 1, 0, 3, 2.5, 8, 9])
self.mytree.remove(4)
assert(self.mytree.to_array() == [3, 2, 1, 0, 2.5, 8, 9] or
self.mytree.to_array() == [8, 2, 1, 0, 3, 2.5, 9])
self.mytree.remove(3)
assert(self.mytree.to_array() == [2.5, 2, 1, 0, 8, 9] or
self.mytree.to_array() == [8, 2, 1, 0, 2.5, 9])
self.mytree.remove(2.5)
assert(self.mytree.to_array() == [8, 2, 1, 0, 9])
self.mytree.remove(8)
assert(self.mytree.to_array() == [9, 2, 1, 0] or
self.mytree.to_array() == [2, 1, 0, 9])
self.mytree.remove(2)
assert(self.mytree.to_array() == [9, 1, 0] or
self.mytree.to_array() == [1, 0, 9])
self.mytree.remove(1)
assert(self.mytree.to_array() == [9, 0])
self.mytree.remove(0)
assert(self.mytree.to_array() == [9])

# RESET
self.setUp()
self.mytree.remove(4.5)
self.mytree.remove(4)
self.mytree.remove(2.5)
self.mytree.remove(3)
self.mytree.remove(0)
self.mytree.remove(1)
self.mytree.remove(2)
self.mytree.remove(6)
assert(self.mytree.to_array() == [5, 8, 9])
self.mytree.remove(5)
assert(self.mytree.to_array() == [8, 9])
self.mytree.remove(8)
assert(self.mytree.to_array() == [9])

def test_contains(self):
assert(self.mytree.contains(5) == True)
assert(self.mytree.contains(4) == True)
assert(self.mytree.contains(3) == True)
assert(self.mytree.contains(2) == True)
assert(self.mytree.contains(1) == True)
assert(self.mytree.contains(0) == True)
assert(self.mytree.contains(9) == True)

assert(self.mytree.contains(80) == False)
assert(self.mytree.contains(-5) == False)
assert(self.mytree.contains(-10) == False)
assert(self.mytree.contains(230) == False)
assert(self.mytree.contains(340) == False)

def test_get_node(self):
acquired_node0 = self.mytree.get_node(2)
acquired_node1 = self.mytree.get_node(8)
acquired_node2 = self.mytree.get_node(4.5)
acquired_node3 = self.mytree.get_node(45)
assert(acquired_node0.data == 2)
assert(acquired_node0.left.data == 1)
assert(acquired_node0.right.data == 3)

assert(acquired_node1.data == 8)
assert(acquired_node1.left.data == 6)
assert(acquired_node1.right.data == 9)

assert(acquired_node2.data == 4.5)
assert(acquired_node2.left == None)
assert(acquired_node2.right == None)

assert(acquired_node3 == None)

def test_to_array(self):
assert(self.bst.to_array() == [])

self.bst.insert_data(5)
self.bst.insert_data(2)
self.bst.insert_data(8)
self.bst.insert_data(6)
self.bst.insert_data(1)
self.bst.insert_data(3)
self.bst.insert_data(0)
self.bst.insert_data(4)
self.bst.insert_data(9)

assert(self.bst.to_array() == [5, 2, 1, 0, 3, 4, 8, 6, 9])
assert(self.mytree.to_array() == [5, 2, 1, 0, 3, 2.5, 4, 4.5, 8, 6, 9])

def test_size(self):
assert(self.mytree.size() == 11)
self.mytree.remove(4.5)
assert(self.mytree.size() == 10)
self.mytree.remove(4)
assert(self.mytree.size() == 9)
self.mytree.insert_data(30)
assert(self.mytree.size() == 10)

if __name__ == "__main__":
unittest.main()

venereology answered 2 years ago
Next > < Previous

Related Solutions

Binary Search Trees with Lazy Deletion Implement binary search tree class with lazy deletion that has...
Binary Search Trees with Lazy Deletion Implement binary search tree class with lazy deletion that has TreeNode as nested class in Java. Design the class, TreeNode to have following class variables: int key; // All Keys are in the range 1 to 99 TreeNode leftChild; TreeNode rightChild; boolean deleted; Your program method must have routines to do the following operations. 1. insert //Should insert a new element to a leaf node. If new element is aduplicatethen do nothing. If the...
Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree...
Prerequisite Knowledge Understand binary search tree structure Understand binary search tree operations Understand binary search tree worst case and best case time. Learning Outcomes Describe AVL tree structure Trace and implement AVL tree operations Explain and prove AVL tree performance
In MobaXterm, with the use of the binary search tree. Implement four operations of insert, in-order...
In MobaXterm, with the use of the binary search tree. Implement four operations of insert, in-order traversal, preorder traversal, and find. Please separate the code in the four parts and explain in detail what is happening. Also, if you can please basic C language. If not, then I understand. Thank you for your time. The test cases are 'm', 'd', 'g', 'r', 'p', 'b', and 'x'. Output: Enter choice (lower case is also acceptable) --- (I)nsert, (F)ind, (Q)uit: i Enter...
Implement a function to find a node in a binary search tree. Using the following class...
Implement a function to find a node in a binary search tree. Using the following class and function definition. If a node with a matching value is found, return a pointer to it. If no match is found, return nullptr. #include <iostream> class BTNode { public: int item; BTNode *left; BTNode *right; BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){} }; BTNode *root = nullptr; BTNode *find(int item) { //implement code here return nullptr; } int main() {    root = new...
Implement a function to find a node in a binary search tree. Using the following class...
Implement a function to find a node in a binary search tree. Using the following class and function definition: class BTNode { public: int item; BTNode *left; BTNode *right; BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){} }; BTNode *root = nullptr; BTNode* find(int i) { // implement } If a node with a matching value is found, return a pointer to it. If no match is found, return nullptr. #include <iostream> class BTNode { public: int item; BTNode *left; BTNode *right;...
/** * This class implements a basic Binary Search Tree that supports insert and get operations....
/** * This class implements a basic Binary Search Tree that supports insert and get operations. In * addition, the implementation supports traversing the tree in pre-, post-, and in-order. Each node * of the tree stores a key, value pair. * * @param <K> The key type for this tree. Instances of this type are used to look up key, value * pairs in the tree. * @param <V> The value type for this tree. An instance of this...
I was trying to implement a simple binary search tree using this given class of bst...
I was trying to implement a simple binary search tree using this given class of bst in c++ public: BST(); ~BST(); void insertKey(int newKey); bool hasKey(int searchKey); std::vector<int> inOrder(); int getHeight(); however; i am still required to use another class for the nodes as a pointer and i need to manage memory leak. in main we should ask for the numbers we need to insert in the binary search tree and also let the user end it with a letter...
Implement a function to remove a leaf node from a binary search tree. Using the following...
Implement a function to remove a leaf node from a binary search tree. Using the following class and function definition: class BTNode { public: int item; BTNode *left; BTNode *right; BTNode(int i, BTNode *l=nullptr, BTNode *r=nullptr):item(i),left(l),right(r){} }; BTNode *root = nullptr; BTNode * remove_leaf(int item, bool &removed) { // implement } The remove function will return the node with the item if it's present in the tree. If the node is a leaf node and is removed by the function,...
Implement a Binary tree using an array using class.
Implement a Binary tree using an array using class.
I am trying to implement a search function for a binary search tree. I am trying...
I am trying to implement a search function for a binary search tree. I am trying to get the output to print each element preceding the the target of the search. For example, in the code when I search for 19, the output should be "5-8-9-18-20-19" Please only modify the search function and also please walk me through what I did wrong. I am trying to figure this out. Here is my code: #include<iostream> using namespace std; class node {...
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT