Description
Part 1 – Summary and Specific Instructions
1. Implement the BST class by completing the provided skeleton code in the file
bst.py. Once completed, your implementation will include the following methods:
add(), remove()
contains(), inorder_traversal()
find_min(), find_max()
is_empty(), make_empty()
2. The BST class is constructed using instances of the provided BSTNode class.
3. We will test your implementation with different types of objects, not just integers.
We guarantee that all such objects will have correct implementation of methods
__eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__().
4. The number of objects stored in the tree will be between 0 and 900 inclusive.
5. When removing a node with two subtrees, replace it with the leftmost child
of the right subtree (i.e. the inorder successor). You do not need to recursively
continue this process. If the deleted node only has one subtree (either right or left),
replace the deleted node with the root node of that subtree.
6. The variables in BSTNode are not private. You are allowed to access and change
their values directly. You do not need to write any getter or setter methods for them.
7. RESTRICTIONS: You are NOT allowed to use ANY built-in Python data structures
and/or their methods. In case you need ‘helper’ data structures in your solution, the
skeleton code includes prewritten implementations of Queue and Stack classes,
which are in separate files and imported in bst.py and avl.py. You are allowed to
create and use objects from those classes in your implementation.
You are NOT allowed to directly access any variables of the Queue or Stack classes.
All work must be done only by using class methods.
8. Ensure that your methods meet the specified runtime requirements.
Page 4 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
add(self, value: object) -> None:
This method adds a new value to the tree. Duplicate values are allowed. If a node with
that value is already in the tree, the new value should be added to the right
subtree of that node. It must be implemented with O(N) runtime complexity.
Example #1:
test_cases = (
(1, 2, 3),
(3, 2, 1),
(1, 3, 2),
(3, 1, 2),
)
for case in test_cases:
tree = BST(case)
print(tree)
Output:
BST pre-order { 1, 2, 3 }
BST pre-order { 3, 2, 1 }
BST pre-order { 1, 3, 2 }
BST pre-order { 3, 1, 2 }
Table of Contents Page 5 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
Example #2:
test_cases = (
(10, 20, 30, 40, 50),
(10, 20, 30, 50, 40),
(30, 20, 10, 5, 1),
(30, 20, 10, 1, 5),
(5, 4, 6, 3, 7, 2, 8),
(range(0, 30, 3)),
(range(0, 31, 3)),
(range(0, 34, 3)),
(range(10, -10, -2)),
(‘A’, ‘B’, ‘C’, ‘D’, ‘E’),
(1, 1, 1, 1),
)
for case in test_cases:
tree = BST(case)
print(‘INPUT :’, case)
print(‘RESULT :’, tree)
Output:
INPUT : (10, 20, 30, 40, 50)
RESULT : BST pre-order { 10, 20, 30, 40, 50 }
INPUT : (10, 20, 30, 50, 40)
RESULT : BST pre-order { 10, 20, 30, 50, 40 }
INPUT : (30, 20, 10, 5, 1)
RESULT : BST pre-order { 30, 20, 10, 5, 1 }
INPUT : (30, 20, 10, 1, 5)
RESULT : BST pre-order { 30, 20, 10, 1, 5 }
INPUT : (5, 4, 6, 3, 7, 2, 8)
RESULT : BST pre-order { 5, 4, 3, 2, 6, 7, 8 }
INPUT : range(0, 30, 3)
RESULT : BST pre-order { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27 }
INPUT : range(0, 31, 3)
RESULT : BST pre-order { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30 }
INPUT : range(0, 34, 3)
RESULT : BST pre-order { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 }
INPUT : range(10, -10, -2)
RESULT : BST pre-order { 10, 8, 6, 4, 2, 0, -2, -4, -6, -8 }
INPUT : (‘A’, ‘B’, ‘C’, ‘D’, ‘E’)
RESULT : BST pre-order { A, B, C, D, E }
INPUT : (1, 1, 1, 1)
RESULT : BST pre-order { 1, 1, 1, 1 }
Page 6 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
Example #3:
for _ in range(100):
case = list(set(random.randrange(1, 20000) for _ in range(900)))
tree = BST()
for value in case:
bst.add(value)
if not tree.is_valid_bst():
Raise Exception(“PROBLEM WITH ADD OPERATION”)
print(‘add() stress test finished’)
Output:
add() stress test finished
Table of Contents Page 7 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
remove(self, value: object) -> bool:
This method removes a value from the tree. The method returns True if the value is
removed. Otherwise, it returns False. It must be implemented with O(N) runtime
complexity.
NOTE: See ‘Specific Instructions’ for an explanation of which node replaces the deleted
node.
Example #1:
test_cases = (
((1, 2, 3), 1),
((1, 2, 3), 2),
((1, 2, 3), 3),
((50, 40, 60, 30, 70, 20, 80, 45), 0),
((50, 40, 60, 30, 70, 20, 80, 45), 45),
((50, 40, 60, 30, 70, 20, 80, 45), 40),
((50, 40, 60, 30, 70, 20, 80, 45), 30),
)
for case, del_value in test_cases:
tree = BST(case)
print(‘INPUT :’, tree, “DELETE:”, del_value)
tree.remove(del_value)
print(‘RESULT :’, tree)
Output:
INPUT : BST pre-order { 1, 2, 3 } DEL: 1
RESULT : BST pre-order { 2, 3 }
INPUT : BST pre-order { 1, 2, 3 } DEL: 2
RESULT : BST pre-order { 1, 3 }
INPUT : BST pre-order { 1, 2, 3 } DEL: 3
RESULT : BST pre-order { 1, 2 }
INPUT : BST pre-order { 50, 40, 30, 20, 45, 60, 70, 80 } DEL: 0
RESULT : BST pre-order { 50, 40, 30, 20, 45, 60, 70, 80 }
INPUT : BST pre-order { 50, 40, 30, 20, 45, 60, 70, 80 } DEL: 45
RESULT : BST pre-order { 50, 40, 30, 20, 60, 70, 80 }
INPUT : BST pre-order { 50, 40, 30, 20, 45, 60, 70, 80 } DEL: 40
RESULT : BST pre-order { 50, 45, 30, 20, 60, 70, 80 }
INPUT : BST pre-order { 50, 40, 30, 20, 45, 60, 70, 80 } DEL: 30
RESULT : BST pre-order { 50, 40, 20, 45, 60, 70, 80 }
Page 8 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
Example #2:
test_cases = (
((50, 40, 60, 30, 70, 20, 80, 45), 20),
((50, 40, 60, 30, 70, 20, 80, 15), 40),
((50, 40, 60, 30, 70, 20, 80, 35), 20),
((50, 40, 60, 30, 70, 20, 80, 25), 40),
)
for case, del_value in test_cases:
tree= BST(tree)
print(‘INPUT :’, tree, “DELETE:”, del_value)
tree.remove(del_value)
print(‘RESULT :’, tree)
Output:
INPUT : BST pre-order { 50, 40, 30, 20, 45, 60, 70, 80 } DEL: 20
RESULT : BST pre-order { 50, 40, 30, 45, 60, 70, 80 }
INPUT : BST pre-order { 50, 40, 30, 20, 15, 60, 70, 80 } DEL: 40
RESULT : BST pre-order { 50, 30, 20, 15, 60, 70, 80 }
INPUT : BST pre-order { 50, 40, 30, 20, 35, 60, 70, 80 } DEL: 20
RESULT : BST pre-order { 50, 40, 30, 35, 60, 70, 80 }
INPUT : BST pre-order { 50, 40, 30, 20, 25, 60, 70, 80 } DEL: 40
RESULT : BST pre-order { 50, 30, 20, 25, 60, 70, 80 }
Table of Contents Page 9 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
Example #3:
case = range(-9, 16, 2)
tree = BST(case)
for del_value in case:
print(‘INPUT :’, tree, del_value)
tree.remove(del_value)
print(‘RESULT :’, tree)
Output:
INPUT : BST pre-order { -9, -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 } -9
RESULT : BST pre-order { -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { -7, -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 } -7
RESULT : BST pre-order { -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { -5, -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 } -5
RESULT : BST pre-order { -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { -3, -1, 1, 3, 5, 7, 9, 11, 13, 15 } -3
RESULT : BST pre-order { -1, 1, 3, 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { -1, 1, 3, 5, 7, 9, 11, 13, 15 } -1
RESULT : BST pre-order { 1, 3, 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { 1, 3, 5, 7, 9, 11, 13, 15 } 1
RESULT : BST pre-order { 3, 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { 3, 5, 7, 9, 11, 13, 15 } 3
RESULT : BST pre-order { 5, 7, 9, 11, 13, 15 }
INPUT : BST pre-order { 5, 7, 9, 11, 13, 15 } 5
RESULT : BST pre-order { 7, 9, 11, 13, 15 }
INPUT : BST pre-order { 7, 9, 11, 13, 15 } 7
RESULT : BST pre-order { 9, 11, 13, 15 }
INPUT : BST pre-order { 9, 11, 13, 15 } 9
RESULT : BST pre-order { 11, 13, 15 }
INPUT : BST pre-order { 11, 13, 15 } 11
RESULT : BST pre-order { 13, 15 }
INPUT : BST pre-order { 13, 15 } 13
RESULT : BST pre-order { 15 }
INPUT : BST pre-order { 15 } 15
RESULT : BST pre-order { }
Page 10 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
Example #4:
case = range(0, 34, 3)
tree = BST(case)
for _ in case[:-2]:
root_value = tree.get_root().value
print(‘INPUT :’, tree, root_value)
tree.remove(root_value)
if not tree.is_valid_bst():
raise Exception(“PROBLEM WITH REMOVE OPERATION”)
print(‘RESULT :’, tree)
Output:
INPUT : BST pre-order { 0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 } 0
RESULT : BST pre-order { 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 } 3
RESULT : BST pre-order { 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 } 6
RESULT : BST pre-order { 9, 12, 15, 18, 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 9, 12, 15, 18, 21, 24, 27, 30, 33 } 9
RESULT : BST pre-order { 12, 15, 18, 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 12, 15, 18, 21, 24, 27, 30, 33 } 12
RESULT : BST pre-order { 15, 18, 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 15, 18, 21, 24, 27, 30, 33 } 15
RESULT : BST pre-order { 18, 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 18, 21, 24, 27, 30, 33 } 18
RESULT : BST pre-order { 21, 24, 27, 30, 33 }
INPUT : BST pre-order { 21, 24, 27, 30, 33 } 21
RESULT : BST pre-order { 24, 27, 30, 33 }
INPUT : BST pre-order { 24, 27, 30, 33 } 24
RESULT : BST pre-order { 27, 30, 33 }
INPUT : BST pre-order { 27, 30, 33 } 27
RESULT : BST pre-order { 30, 33 }
Table of Contents Page 11 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
contains(self, value: object) -> bool:
This method returns True if the value is in the tree. Otherwise, it returns False. If the tree is
empty, the method should return False. It must be implemented with O(N) runtime
complexity.
Example #1:
tree = BST([10, 5, 15])
print(tree.contains(15))
print(tree.contains(-10))
print(tree.contains(15))
Output:
True
False
True
Example #2:
tree = BST()
print(tree.contains(0))
Output:
False
Page 12 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
inorder_traversal(self) -> Queue:
This method will perform an inorder traversal of the tree, and return a Queue object that
contains the values of the visited nodes, in the order they were visited. If the tree is empty,
the method returns an empty Queue. It must be implemented with O(N) runtime
complexity.
Example #1:
tree = BST([10, 20, 5, 15, 17, 7, 12])
print(tree.inorder_traversal())
Output:
QUEUE { 5, 7, 10, 12, 15, 17, 20 }
Example #2:
tree = BST([8, 10, -4, 5, -1])
print(tree.inorder_traversal())
Output:
QUEUE { -4, -1, 5, 8, 10 }
Table of Contents Page 13 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
find_min(self) -> object:
This method returns the lowest value in the tree. If the tree is empty, the method should
return None. It must be implemented with O(N) runtime complexity.
Example #1:
tree = BST([10, 20, 5, 15, 17, 7, 12])
print(tree.find_min())
Output:
5
Example #2:
tree = BST([8, 10, -4, 5, -1])
print(tree.find_min())
Output:
-4
find_max(self) -> object:
This method returns the highest value in the tree. If the tree is empty, the method should
return None. It must be implemented with O(N) runtime complexity.
Example #1:
tree = BST([10, 20, 5, 15, 17, 7, 12])
print(tree.find_max())
Output:
20
Example #2:
tree = BST([8, 10, -4, 5, -1])
print(tree.find_max())
Output:
10
Page 14 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
is_empty(self) -> bool:
This method returns True if the tree is empty. Otherwise, it returns False. It must be
implemented with O(1) runtime complexity.
Example #1:
tree = BST([10, 20, 5, 15, 17, 7, 12])
print(tree.is_empty())
Output:
False
Example #2:
tree = BST()
print(tree.is_empty())
Output:
True
make_empty(self) -> None:
This method removes all of the nodes from the tree. It must be implemented with O(1)
runtime complexity.
Example #1:
tree = BST([10, 20, 5, 15, 17, 7, 12])
tree.make_empty())
print(tree)
Output:
AVL pre-order { }
Example #2:
tree = BST()
tree.make_empty())
print(tree)
Output:
AVL pre-order { }
Table of Contents Page 15 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
Part 2 – Summary and Specific Instructions
1. Implement the AVL class (a subclass of BST) by completing the provided skeleton
code in the file avl.py.
Once completed, your implementation will include overridden versions of the
following methods:
add(), remove()
And it will inherit the following methods from BST:
contains(), inorder_traversal(), find_min(), find_max()
is_empty(), make_empty()
2. When reviewing the provided skeleton code, please note that the AVLNode class (a
subclass of BSTNode) has two important added attributes: parent (to store a pointer
to the parent of the current node) and height (to store the height of the subtree
rooted at the current node). Your implementation must correctly maintain all three
node pointers (left, right, and parent), as well as the height attribute of each
node. Your tree must use the AVLNode class.
3. We will test your implementation with different types of objects, not just integers.
We guarantee that all such objects will have correct implementation of methods
__eq__(), __lt__(), __gt__(), __ge__(), __le__(), and __str__().
4. The number of objects stored in the tree will be between 0 and 900 inclusive.
5. When removing a node with two subtrees, replace it with the leftmost child
of the right subtree (i.e. the inorder successor). You do not need to recursively
continue this process. If the deleted node only has one subtree (either right or left),
replace the deleted node with the root node of that subtree.
6. The variables in AVLNode are not private. You are allowed to access and change
their values directly. You do not need to write any getter or setter methods for them.
The AVL skeleton code includes some suggested helper methods.
7. RESTRICTIONS: You are not allowed to use ANY built-in Python data structures
and/or their methods. In case you need ‘helper’ data structures in your solution, the
skeleton code includes prewritten implementations of Queue and Stack classes,
which are in separate files and imported in bst.py and avl.py. You are allowed to
create and use objects from those classes in your implementation.
You are not allowed to directly access any variables of the Queue or Stack classes. All
work must be done only by using class methods.
8. Ensure that your methods meet the specified runtime requirements.
Page 16 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
add(self, value: object) -> None:
This method adds a new value to the tree while maintaining its AVL property. Duplicate
values are not allowed. If the value is already in the tree, the method should not change
the tree. It must be implemented with O(log N) runtime complexity.
Example #1:
test_cases = (
(1, 2, 3), #RR
(3, 2, 1), #LL
(1, 3, 2), #RL
(3, 1, 2), #LR
)
for case in test_cases:
tree = AVL(case)
print(tree)
Output:
AVL pre-order { 2, 1, 3 }
AVL pre-order { 2, 1, 3 }
AVL pre-order { 2, 1, 3 }
AVL pre-order { 2, 1, 3 }
Table of Contents Page 17 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
Example #2:
test_cases = (
(10, 20, 30, 40, 50), # RR, RR
(10, 20, 30, 50, 40), # RR, RL
(30, 20, 10, 5, 1), # LL, LL
(30, 20, 10, 1, 5), # LL, LR
(5, 4, 6, 3, 7, 2, 8), # LL, RR
(range(0, 30, 3)),
(range(0, 31, 3)),
(range(0, 34, 3)),
(range(10, -10, -2)),
(‘A’, ‘B’, ‘C’, ‘D’, ‘E’),
(1, 1, 1, 1),
)
for case in test_cases:
tree = AVL(case)
print(‘INPUT :’, case)
print(‘RESULT :’, tree)
Output:
INPUT : (10, 20, 30, 40, 50)
RESULT : AVL pre-order { 20, 10, 40, 30, 50 }
INPUT : (10, 20, 30, 50, 40)
RESULT : AVL pre-order { 20, 10, 40, 30, 50 }
INPUT : (30, 20, 10, 5, 1)
RESULT : AVL pre-order { 20, 5, 1, 10, 30 }
INPUT : (30, 20, 10, 1, 5)
RESULT : AVL pre-order { 20, 5, 1, 10, 30 }
INPUT : (5, 4, 6, 3, 7, 2, 8)
RESULT : AVL pre-order { 5, 3, 2, 4, 7, 6, 8 }
INPUT : range(0, 30, 3)
RESULT : AVL pre-order { 9, 3, 0, 6, 21, 15, 12, 18, 24, 27 }
INPUT : range(0, 31, 3)
RESULT : AVL pre-order { 9, 3, 0, 6, 21, 15, 12, 18, 27, 24, 30 }
INPUT : range(0, 34, 3)
RESULT : AVL pre-order { 21, 9, 3, 0, 6, 15, 12, 18, 27, 24, 30, 33 }
INPUT : range(10, -10, -2)
RESULT : AVL pre-order { 4, -4, -6, -8, 0, -2, 2, 8, 6, 10 }
INPUT : (‘A’, ‘B’, ‘C’, ‘D’, ‘E’)
RESULT : AVL pre-order { B, A, D, C, E }
INPUT : (1, 1, 1, 1)
RESULT : AVL pre-order { 1 }
Page 18 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
Example #3:
for _ in range(100):
case = list(set(random.randrange(1, 20000) for _ in range(900)))
tree = AVL()
for value in case:
tree.add(value)
if not tree.is_valid_avl():
raise Exception(“PROBLEM WITH ADD OPERATION”)
print(‘add() stress test finished’)
Output:
add() stress test finished
Table of Contents Page 19 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
remove(self, value: object) -> bool:
This method removes the value from the AVL tree. The method returns True if the value is
removed. Otherwise, it returns False. It must be implemented with O(log N) runtime
complexity.
NOTE: See ‘Specific Instructions’ for an explanation of which node replaces the deleted
node.
Example #1:
test_cases = (
((1, 2, 3), 1), # no AVL rotation
((1, 2, 3), 2), # no AVL rotation
((1, 2, 3), 3), # no AVL rotation
((50, 40, 60, 30, 70, 20, 80, 45), 0),
((50, 40, 60, 30, 70, 20, 80, 45), 45), # no AVL rotation
((50, 40, 60, 30, 70, 20, 80, 45), 40), # no AVL rotation
((50, 40, 60, 30, 70, 20, 80, 45), 30), # no AVL rotation
)
for case, del_value in test_cases:
tree = AVL(case)
print(‘INPUT :’, tree, “DELETE:”, del_value)
tree.remove(del_value)
print(‘RESULT :’, tree)
Output:
INPUT : AVL pre-order { 2, 1, 3 } DEL: 1
RESULT : AVL pre-order { 2, 3 }
INPUT : AVL pre-order { 2, 1, 3 } DEL: 2
RESULT : AVL pre-order { 3, 1 }
INPUT : AVL pre-order { 2, 1, 3 } DEL: 3
RESULT : AVL pre-order { 2, 1 }
INPUT : AVL pre-order { 50, 30, 20, 40, 45, 70, 60, 80 } DEL: 0
RESULT : AVL pre-order { 50, 30, 20, 40, 45, 70, 60, 80 }
INPUT : AVL pre-order { 50, 30, 20, 40, 45, 70, 60, 80 } DEL: 45
RESULT : AVL pre-order { 50, 30, 20, 40, 70, 60, 80 }
INPUT : AVL pre-order { 50, 30, 20, 40, 45, 70, 60, 80 } DEL: 40
RESULT : AVL pre-order { 50, 30, 20, 45, 70, 60, 80 }
INPUT : AVL pre-order { 50, 30, 20, 40, 45, 70, 60, 80 } DEL: 30
RESULT : AVL pre-order { 50, 40, 20, 45, 70, 60, 80 }
Page 20 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
Example #2:
test_cases = (
((50, 40, 60, 30, 70, 20, 80, 45), 20), # RR
((50, 40, 60, 30, 70, 20, 80, 15), 40), # LL
((50, 40, 60, 30, 70, 20, 80, 35), 20), # RL
((50, 40, 60, 30, 70, 20, 80, 25), 40), # LR
)
for case, del_value in test_cases:
tree = AVL(case)
print(‘INPUT :’, tree, “DELETE:”, del_value)
tree.remove(del_value)
print(‘RESULT :’, tree)
Output:
INPUT : AVL pre-order { 50, 30, 20, 40, 45, 70, 60, 80 } DEL: 20
RESULT : AVL pre-order { 50, 40, 30, 45, 70, 60, 80 }
INPUT : AVL pre-order { 50, 30, 20, 15, 40, 70, 60, 80 } DEL: 40
RESULT : AVL pre-order { 50, 20, 15, 30, 70, 60, 80 }
INPUT : AVL pre-order { 50, 30, 20, 40, 35, 70, 60, 80 } DEL: 20
RESULT : AVL pre-order { 50, 35, 30, 40, 70, 60, 80 }
INPUT : AVL pre-order { 50, 30, 20, 25, 40, 70, 60, 80 } DEL: 40
RESULT : AVL pre-order { 50, 25, 20, 30, 70, 60, 80 }
Table of Contents Page 21 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
Example #3:
case = range(-9, 16, 2)
tree = AVL(case)
for del_value in case:
print(‘INPUT :’, tree, del_value)
tree.remove(del_value)
print(‘RESULT :’, tree)
Output:
INPUT : AVL pre-order { 5, -3, -7, -9, -5, 1, -1, 3, 9, 7, 13, 11, 15 } -9
RESULT : AVL pre-order { 5, -3, -7, -5, 1, -1, 3, 9, 7, 13, 11, 15 }
INPUT : AVL pre-order { 5, -3, -7, -5, 1, -1, 3, 9, 7, 13, 11, 15 } -7
RESULT : AVL pre-order { 5, -3, -5, 1, -1, 3, 9, 7, 13, 11, 15 }
INPUT : AVL pre-order { 5, -3, -5, 1, -1, 3, 9, 7, 13, 11, 15 } -5
RESULT : AVL pre-order { 5, 1, -3, -1, 3, 9, 7, 13, 11, 15 }
INPUT : AVL pre-order { 5, 1, -3, -1, 3, 9, 7, 13, 11, 15 } -3
RESULT : AVL pre-order { 5, 1, -1, 3, 9, 7, 13, 11, 15 }
INPUT : AVL pre-order { 5, 1, -1, 3, 9, 7, 13, 11, 15 } -1
RESULT : AVL pre-order { 5, 1, 3, 9, 7, 13, 11, 15 }
INPUT : AVL pre-order { 5, 1, 3, 9, 7, 13, 11, 15 } 1
RESULT : AVL pre-order { 9, 5, 3, 7, 13, 11, 15 }
INPUT : AVL pre-order { 9, 5, 3, 7, 13, 11, 15 } 3
RESULT : AVL pre-order { 9, 5, 7, 13, 11, 15 }
INPUT : AVL pre-order { 9, 5, 7, 13, 11, 15 } 5
RESULT : AVL pre-order { 9, 7, 13, 11, 15 }
INPUT : AVL pre-order { 9, 7, 13, 11, 15 } 7
RESULT : AVL pre-order { 13, 9, 11, 15 }
INPUT : AVL pre-order { 13, 9, 11, 15 } 9
RESULT : AVL pre-order { 13, 11, 15 }
INPUT : AVL pre-order { 13, 11, 15 } 11
RESULT : AVL pre-order { 13, 15 }
INPUT : AVL pre-order { 13, 15 } 13
RESULT : AVL pre-order { 15 }
INPUT : AVL pre-order { 15 } 15
RESULT : AVL pre-order { }
Page 22 of 23
CS261 Data Structures Assignment 4: BST/AVL Tree Implementation
Example #4:
case = range(0, 34, 3)
tree = AVL(case)
for _ in case[:-2]:
root_value = tree.get_root().value
print(‘INPUT :’, tree, root_value)
tree.remove(root_value)
print(‘RESULT :’, tree)
Output:
INPUT : AVL pre-order { 21, 9, 3, 0, 6, 15, 12, 18, 27, 24, 30, 33 } 21
RESULT : AVL pre-order { 24, 9, 3, 0, 6, 15, 12, 18, 30, 27, 33 }
INPUT : AVL pre-order { 24, 9, 3, 0, 6, 15, 12, 18, 30, 27, 33 } 24
RESULT : AVL pre-order { 27, 9, 3, 0, 6, 15, 12, 18, 30, 33 }
INPUT : AVL pre-order { 27, 9, 3, 0, 6, 15, 12, 18, 30, 33 } 27
RESULT : AVL pre-order { 9, 3, 0, 6, 30, 15, 12, 18, 33 }
INPUT : AVL pre-order { 9, 3, 0, 6, 30, 15, 12, 18, 33 } 9
RESULT : AVL pre-order { 12, 3, 0, 6, 30, 15, 18, 33 }
INPUT : AVL pre-order { 12, 3, 0, 6, 30, 15, 18, 33 } 12
RESULT : AVL pre-order { 15, 3, 0, 6, 30, 18, 33 }
INPUT : AVL pre-order { 15, 3, 0, 6, 30, 18, 33 } 15
RESULT : AVL pre-order { 18, 3, 0, 6, 30, 33 }
INPUT : AVL pre-order { 18, 3, 0, 6, 30, 33 } 18
RESULT : AVL pre-order { 30, 3, 0, 6, 33 }
INPUT : AVL pre-order { 30, 3, 0, 6, 33 } 30
RESULT : AVL pre-order { 3, 0, 33, 6 }
INPUT : AVL pre-order { 3, 0, 33, 6 } 3
RESULT : AVL pre-order { 6, 0, 33 }
INPUT : AVL pre-order { 6, 0, 33 } 6
RESULT : AVL pre-order { 33, 0 }
Example #5:
for _ in range(100):
case = list(set(random.randrange(1, 20000) for _ in range(900)))
tree = AVL(case)
for value in case[::2]:
tree.remove(value)
if not tree.is_valid_avl():
raise Exception(“PROBLEM WITH REMOVE OPERATION”)
print(‘Stress test finished’)
Output:
remove() stress test finished
Table of Contents Page 23 of 23
