• API
• FAQ
• Tools
• Archive
daily pastebin goal
38%
SHARE
TWEET

# Untitled

a guest Nov 14th, 2017 95 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top