SHARE
TWEET

Untitled

a guest Nov 14th, 2017 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. """Lab 9: Binary Search Trees
  2.  
  3. === CSC148 Fall 2016 ===
  4. Diane Horton and David Liu
  5. Department of Computer Science,
  6. University of Toronto
  7.  
  8. === Module Description ===
  9. This module contains a few BinarySearchTree methods that you should implement
  10. recursively. Make sure you understand the *BST Property*; it will play an
  11. important role in several of these methods.
  12. """
  13.  
  14.  
  15. class BinarySearchTree:
  16.     """Binary Search Tree class.
  17.  
  18.    This class represents a binary tree satisfying the Binary Search Tree
  19.    property: for every node, its value is >= all items stored in its left
  20.    subtree, and < all items stored in its right subtree.
  21.  
  22.    === Private Attributes ===
  23.    @type _root: object
  24.        The item stored at the root of the tree, or None if the tree is empty.
  25.    @type _left: BinarySearchTree | None
  26.        The left subtree, or None if the tree is empty
  27.    @type _right: BinarySearchTree | None
  28.        The right subtree, or None if the tree is empty
  29.  
  30.    === Representation Invariants ===
  31.     - If _root is None, then so are _left and _right.
  32.       This represents an empty BST.
  33.     - If _root is not None, then _left and _right are BinarySearchTrees.
  34.     - (BST Property) All items in _left are <= _root,
  35.       and all items in _right are >= _root.
  36.    """
  37.     def __init__(self, root):
  38.         """Initialize a new BST with the given root value.
  39.  
  40.        If <root> is None, the tree is empty, and the subtrees are None.
  41.        If <root> is not None, the subtrees are empty.
  42.  
  43.        @type self: BinarySearchTree
  44.        @type root: object
  45.            A value for the root of the BST. If None, the BST is empty.
  46.        @rtype: None
  47.        """
  48.         if root is None:
  49.             self._root = None
  50.             self._left = None
  51.             self._right = None
  52.         else:
  53.             self._root = root
  54.             self._left = BinarySearchTree(None)
  55.             self._right = BinarySearchTree(None)
  56.  
  57.     def is_empty(self):
  58.         """Return True if this BST is empty.
  59.  
  60.        @type self: BinarySearchTree
  61.        @rtype: bool
  62.  
  63.        >>> bst = BinarySearchTree(None)
  64.        >>> bst.is_empty()
  65.        True
  66.        >>> bst = BinarySearchTree(10)
  67.        >>> bst.is_empty()
  68.        False
  69.        """
  70.         return self._root is None
  71.  
  72.     def print_bst(self, depth=0):
  73.         """Print all of the items in this BST, using indentation to show depth.
  74.  
  75.        @type self: BinarySearchTree
  76.        @type depth: int
  77.        @rtype: None
  78.        """
  79.         if self.is_empty():
  80.             pass
  81.         else:
  82.             print(depth * '  ' + str(self._root))
  83.             self._left.print_bst(depth + 1)
  84.             self._right.print_bst(depth + 1)
  85.  
  86.     def __contains__(self, item):
  87.         """Return True if <item> is in this BST.
  88.  
  89.        @type self: BinarySearchTree
  90.        @type item: object
  91.        @rtype: bool
  92.  
  93.        >>> bst = BinarySearchTree(3)
  94.        >>> bst._left = BinarySearchTree(2)
  95.        >>> bst._right = BinarySearchTree(5)
  96.        >>> 3 in bst
  97.        True
  98.        >>> 5 in bst
  99.        True
  100.        >>> 2 in bst
  101.        True
  102.        >>> 4 in bst
  103.        False
  104.        """
  105.         if self.is_empty():
  106.             return False
  107.         elif item == self._root:
  108.             return True
  109.         elif item < self._root:
  110.             return item in self._left   # or, self._left.__contains__(item)
  111.         else:
  112.             return item in self._right  # or, self._right.__contains__(item)
  113.  
  114.     # ------------------------------------------------------------------------
  115.     # Lab 9 Task 1
  116.     # ------------------------------------------------------------------------
  117.     def height(self):
  118.         """Return the height of this BST.
  119.  
  120.        @type self: BinarySearchTree
  121.        @rtype: int
  122.  
  123.        >>> BinarySearchTree(None).height()
  124.        0
  125.        >>> bst = BinarySearchTree(7)
  126.        >>> bst.height()
  127.        1
  128.        >>> bst._left = BinarySearchTree(5)
  129.        >>> bst.height()
  130.        2
  131.        >>> bst._right = BinarySearchTree(9)
  132.        >>> bst.height()
  133.        2
  134.        """
  135.         if self.is_empty():
  136.             return 0
  137.         else:
  138.             return 1 + max(self._left.height(), self._right.height())
  139.  
  140.     def items(self):
  141.         """Return all of the items in the BST in sorted order.
  142.  
  143.        @type self: BinarySearchTree
  144.        @rtype: list
  145.  
  146.        >>> BinarySearchTree(None).items()
  147.        []
  148.        >>> bst = BinarySearchTree(7)
  149.        >>> left = BinarySearchTree(3)
  150.        >>> left._left = BinarySearchTree(2)
  151.        >>> left._right = BinarySearchTree(5)
  152.        >>> right = BinarySearchTree(11)
  153.        >>> right._left = BinarySearchTree(9)
  154.        >>> right._right = BinarySearchTree(13)
  155.        >>> bst._left = left
  156.        >>> bst._right = right
  157.        >>> bst.items()
  158.        [2, 3, 5, 7, 9, 11, 13]
  159.        """
  160.         if self.is_empty():
  161.             return []
  162.         else:
  163.             return self._left.items() + [self._root] + self._right.items()
  164.  
  165.     def smaller(self, item):
  166.         """Return the items in this BST strictly less than <item>.
  167.  
  168.        The items are returned in sorted order.
  169.  
  170.        @type item: object
  171.        @rtype: list
  172.  
  173.        >>> bst = BinarySearchTree(7)
  174.        >>> left = BinarySearchTree(3)
  175.        >>> left._left = BinarySearchTree(2)
  176.        >>> left._right = BinarySearchTree(5)
  177.        >>> right = BinarySearchTree(11)
  178.        >>> right._left = BinarySearchTree(9)
  179.        >>> right._right = BinarySearchTree(13)
  180.        >>> bst._left = left
  181.        >>> bst._right = right
  182.        >>> bst.smaller(6)
  183.        [2, 3, 5]
  184.        >>> bst.smaller(13)
  185.        [2, 3, 5, 7, 9, 11]
  186.        """
  187.         if self.is_empty():
  188.             return []
  189.         elif self._root >= item:
  190.             return self._left.smaller(item)
  191.         else:
  192.             return self._left.smaller(item) + [self._root] +\
  193.                    self._right.smaller(item)
  194.  
  195.     # ------------------------------------------------------------------------
  196.     # Lab 9 Task 2
  197.     # ------------------------------------------------------------------------
  198.     def insert(self, item):
  199.         """Insert <item> into this BST, maintaining the BST property.
  200.  
  201.        Do not change positions of any other items.
  202.  
  203.        @type self: BinarySearchTree
  204.        @type item: object
  205.        @rtype: None
  206.  
  207.        >>> bst = BinarySearchTree(10)
  208.        >>> bst.insert(3)
  209.        >>> bst.insert(20)
  210.        >>> bst._root
  211.        10
  212.        >>> bst._left._root
  213.        3
  214.        >>> bst._right._root
  215.        20
  216.        """
  217.         if self.is_empty():
  218.             self._root = item
  219.             self._left = BinarySearchTree(None)
  220.             self._right = BinarySearchTree(None)
  221.         elif self._root >= item:
  222.             self._left.insert(item)
  223.         else:
  224.             self._right.insert(item)
  225.  
  226.     # ------------------------------------------------------------------------
  227.     # Lab 9 Task 3
  228.     # ------------------------------------------------------------------------
  229.     def rotate_right(self):
  230.         """Rotate the BST clockwise, i.e. make the left subtree the root.
  231.  
  232.        @type self: BinarySearchTree
  233.        @rtype: object
  234.  
  235.        >>> bst = BinarySearchTree(7)
  236.        >>> left = BinarySearchTree(3)
  237.        >>> right = BinarySearchTree(11)
  238.        >>> left._left = BinarySearchTree(2)
  239.        >>> left._right = BinarySearchTree(5)
  240.        >>> bst._left = left
  241.        >>> bst._right = right
  242.        >>> bst.print_bst()
  243.        7
  244.          3
  245.            2
  246.            5
  247.          11
  248.        >>> bst.rotate_right()
  249.        >>> bst.print_bst()
  250.        3
  251.          2
  252.          7
  253.            5
  254.            11
  255.        >>> bst.rotate_right()
  256.        >>> bst.print_bst()
  257.        2
  258.          3
  259.            7
  260.              5
  261.              11
  262.        """
  263.         new_root = BinarySearchTree(self._left._root)
  264.         new_root._left = self._left._left
  265.         new_root._right = BinarySearchTree(self._root)
  266.         new_root._right._left = self._left._right
  267.         new_root._right._right = self._right
  268.  
  269.         self._root = new_root._root
  270.         self._left = new_root._left
  271.         self._right = new_root._right
  272.  
  273.     def rotate_left(self):
  274.         """Rotate the BST counter-clockwise, i.e. make the right subtree the root.
  275.  
  276.        @type self: BinarySearchTree
  277.        @rtype: object
  278.  
  279.        >>> bst = BinarySearchTree(7)
  280.        >>> left = BinarySearchTree(3)
  281.        >>> left._left = BinarySearchTree(2)
  282.        >>> left._right = BinarySearchTree(5)
  283.        >>> right = BinarySearchTree(11)
  284.        >>> right._left = BinarySearchTree(9)
  285.        >>> right._right = BinarySearchTree(13)
  286.        >>> bst._left = left
  287.        >>> bst._right = right
  288.        >>> bst.print_bst()
  289.        7
  290.          3
  291.            2
  292.            5
  293.          11
  294.            9
  295.            13
  296.        >>> bst.rotate_left()
  297.        >>> bst.print_bst()
  298.        11
  299.          7
  300.            3
  301.              2
  302.              5
  303.            9
  304.          13
  305.        >>> bst.rotate_left()
  306.        >>> bst.print_bst()
  307.        13
  308.          11
  309.            7
  310.              3
  311.                2
  312.                5
  313.              9
  314.        """
  315.         new_root = BinarySearchTree(self._right._root)
  316.         new_root._right = self._right._right
  317.         new_root._left = BinarySearchTree(self._root)
  318.         new_root._left._left = self._left
  319.         new_root._left._right = self._right._left
  320.  
  321.         self._root = new_root._root
  322.         self._left = new_root._left
  323.         self._right = new_root._right
  324.  
  325.     # ------------------------------------------------------------------------
  326.     # Implementation of deletion - we'll cover this on Friday
  327.     # ------------------------------------------------------------------------
  328.     def delete(self, item):
  329.         """Remove *one* occurrence of item from this BST.
  330.  
  331.        Do nothing if <item> is not in the BST.
  332.  
  333.        @type self: BinarySearchTree
  334.        @type item: object
  335.        @rtype: None
  336.  
  337.        >>> bst = BinarySearchTree(7)
  338.        >>> left = BinarySearchTree(3)
  339.        >>> left._left = BinarySearchTree(2)
  340.        >>> left._right = BinarySearchTree(5)
  341.        >>> right = BinarySearchTree(11)
  342.        >>> right._left = BinarySearchTree(9)
  343.        >>> right._right = BinarySearchTree(13)
  344.        >>> bst._left = left
  345.        >>> bst._right = right
  346.        >>> bst.items()
  347.        [2, 3, 5, 7, 9, 11, 13]
  348.        >>> bst.delete(13)
  349.        >>> bst.items()
  350.        [2, 3, 5, 7, 9, 11]
  351.        >>> bst.delete(9)
  352.        >>> bst.items()
  353.        [2, 3, 5, 7, 11]
  354.        >>> bst.delete(2)
  355.        >>> bst.items()
  356.        [3, 5, 7, 11]
  357.        >>> bst.delete(5)
  358.        >>> bst.items()
  359.        [3, 7, 11]
  360.        >>> bst.delete(7)
  361.        >>> bst.items()
  362.        [3, 11]
  363.        """
  364.         if self.is_empty():
  365.             pass
  366.         elif self._root == item:
  367.             self.delete_root()
  368.         elif item < self._root:
  369.             self._left.delete(item)
  370.         else:
  371.             self._right.delete(item)
  372.  
  373.     def delete_root(self):
  374.         """Remove the root of this tree.
  375.  
  376.        Precondition: this tree is *non-empty*.
  377.  
  378.        @type self: BinarySearchTree
  379.        @rtype: None
  380.        """
  381.         if self._left.is_empty() and self._right.is_empty():
  382.             self._root = None
  383.             self._left = None
  384.             self._right = None
  385.         elif self._left.is_empty():
  386.             self._root = self._right.extract_min()
  387.         else:
  388.             self._root = self._left.extract_max()
  389.  
  390.     def extract_max(self):
  391.         """Remove and return the maximum item stored in this tree.
  392.  
  393.        Precondition: this tree is *non-empty*.
  394.  
  395.        @type self: BinarySearchTree
  396.        @rtype: object
  397.        """
  398.         if self._right.is_empty():
  399.             temp = self._root
  400.             # Copy left subtree to self, because root node is removed.
  401.             # Note that self = self._left does NOT work!
  402.             self._root, self._left, self._right =\
  403.                 self._left._root, self._left._left, self._left._right
  404.             return temp
  405.         else:
  406.             return self._right.extract_max()
  407.  
  408.     def extract_min(self):
  409.         """Remove and return the minimum item stored in this tree.
  410.  
  411.        Precondition: this tree is *non-empty*.
  412.  
  413.        @type self: BinarySearchTree
  414.        @rtype: object
  415.        """
  416.         if self._left.is_empty():
  417.             temp = self._root
  418.             self._root, self._left, self._right =\
  419.                 self._right._root, self._right._left, self._right._right
  420.             return temp
  421.         else:
  422.             return self._left.extract_min()
  423.  
  424. if __name__ == '__main__':
  425.     import python_ta
  426.     python_ta.check_all(config='pylintrc.txt')
RAW Paste Data
Top