Overview and Requirements

AVL Trees provide a balanced binary tree for efficient storage,retreival and deletion of data. We learnt about implementing AVLTrees in the class. We will expand on the implementation bysupporting delete operations. We will also practice visualizing thetree using Graphviz and Python's pydot module.

Note: for this assignment, do not use Jupyter Notebookto code your solution. Use standard Python script (.py) files.

Program Details

Delete operations:

delete(data), remove(node) & update_balance_delete(node)methods:

Write a program that implements and tests an AVL treedelete(data) method. This method accepts a data to remove. If thedata is in the tree, the method finds the node with the data,removes the node, re-balances the tree, and returns True. If thedata is not in the tree, False is returned.

Similar to the Binary Search Tree implementation, thedelete(data) method would need a remove(node) method to remove thenode containing the data. This method would be similar inimplementation to BST's remove(node) method except that it wouldalso need to ensure the tree is balanced (similar to _put()method).

To support the re-balancing operation, implementupdate_balance_delete(node) method that would recursively updatethe balance factor of the parent node. Once the node with imbalanceis identified, the method would perform appropriate sub-treerotations. You can refer to the update_balance_insert(node) methodas a templace to implement the update_balance_delete(node)method.

Finally, make sure update_balance_delete(node) method is calledfrom from the remove(node) method during node removaloperation.

Test

Test your implementation by adding and removing the followingitems in the order shown:

In [ ]:

mytree = AVLTree()mytree.put(131)mytree.put(121)mytree.put(122)mytree.put(132)mytree.put(115)mytree.put(415)mytree.put(321)mytree.put(315)mytree.put(111)print("pre-order traversal:", end = " ")mytree.pre_order_traversal()print("level-order traversal:", end = " ")mytree.level_order_traversal()# no AVL delete implemented!!# del mytree[122]# print("pre-order traversal after delete:", end = " ")# mytree.pre_order_traversal()# print("level-order traversal after delete:", end = " ")# mytree.level_order_traversal()

Tree Visualization

Visualize the tree using Python pydot module.

• Define a field self.graph within AVLTree class. Initialize itto None within the constructor method
• Define methods visualize(file) and visualize_helper(node)methods within AVLTree class.
• The visualize(file) method should initialize the self.graphfield to a new graph object using Graph() constructor method. Itshould also add root node to the graph plot and callvisualize_helper(node) with root node as agrument. Finally, thevisuallize(file) should render and save the tree visualization to a.png, .jpeg or .pdf file.
• The visualize(node) method should recursively add tree nodesand their parent-child relationships (edges) to self.graph forvisualization.

Note: You may use the providedlevel_order_traversal() and level_order_helper() methods astemplates for defining visualize(file) and visualize_helper(node)methods.

Sample of original tree:

Sample of Final tree

Note: You may use the provided level_order_traversal() and level_order_helper0) methods as templates for defining visualize(file) and visualize_helper (node) methods. Here is a sample of the expected original tree: 111 115 121 122 132 131 315 321 415