"""This is an incomplete implentation of bst. Students are asked to implement some version of bst_find_min() or bst_find_max() or bst_sort() or some other methods. Xiannong Meng Fall 2017""" from bstiter import _BSTIterator #from bstitarray import _BSTIterator """Binar Search Tree""" class BST: def __init__( self ): """ Creates an empty binary search tree.""" self._root = None self._size = 0 def __len__( self ): """Returns the number of entries in the bst.""" return self._size def print( self ): if self._root != None: self._root.print() def __contains__( self, key ): """Determines if the map contains the given key.""" return self._bstSearch( self._root, key ) is not None def _bstFindMin( self, subtree ): """Helper method for finding the node containing the minimum key.""" pass def _bstFindMax( self, subtree ): """Helper method for finding the node containing the maximum key.""" pass def add( self, key, value ): """Adds a new entry to binary search tree.""" # Find the node containing the key, if it exists. node = self._bstSearch( self._root, key ) # If the key is already in the tree, update its value. if node is not None : node.value = value return False # Otherwise, add a new entry. else : self._root = self._bstInsert( self._root, key, value ) self._size += 1 return True def remove( self, key ): """Removes the entry associated with the given key.""" assert key in self, "Invalid key to remove." self._root = self._bstRemove( self._root, key ) self._size -= 1 def findMin( self ): """Find the minimum of this bst""" return self._bstFindMin( self._root ) def findMax( self ): """Find the maximum of this bst""" return self._bstFindMax( self._root ) def __iter__( self ): """Returns an iterator for traversing the keys in the bst. """ return _BSTIterator( self._root ) def _bstInsert( self, subtree, key, value ): """Helper method that inserts a new item, recursively.""" if subtree is None : subtree = _BSTNode( key, value ) elif key < subtree.key : subtree.left = self._bstInsert( subtree.left, key, value ) elif key > subtree.key : subtree.right = self._bstInsert( subtree.right, key, value ) return subtree def _bstSearch( self, subtree, target ): """Helper method that recursively searches the tree for a target key.""" if subtree is None : # base case, not found return None elif target < subtree.key : # target is left of the subtree root. return self._bstSearch( subtree.left, target ) elif target > subtree.key : # target is right of the subtree root. return self._bstSearch( subtree.right,target ) else : # base case, found! return subtree def _bstRemove( self, subtree, target ): """Helper method that removes an existing item recursively.""" # Search for the item in the tree. if subtree is None : # not found return subtree elif target < subtree.key : # search for the left sub-tree subtree.left = self._bstRemove( subtree.left, target ) return subtree elif target > subtree.key : # search for the right sub-tree subtree.right = self._bstRemove( subtree.right, target ) return subtree else : # We found the node containing the item, delete it. return self._bstDeleteNode( subtree ) def _bstDeleteNode( self, node ): """Delete this BST node""" if node.left is None and node.right is None : # leaf node return None elif node.left is None or node.right is None : # one child if node.left is not None : return node.left else : return node.right else : # two children, find in-order successor, replace current with it successor = self._bstFindMin( node.right ) node.key = successor.key node.value = successor.value node.right = self._bstRemove( node.right, successor.key ) return node # Storage class for the binary search tree nodes class _BSTNode : def __init__( self, key, value ): self.key = key self.value = value self.left = None self.right = None def __str__( self ): return str( self.value )