CptS 215 Data Analytics Systems and Algorithms

CptS 215 Data Analytics Systems and Algorithms. Define a field self.graph within AVLTree class. Initialize it to None within the constructor method.

Washington State University

Srini Badri (Instructor)

Gina Sprint (Original Author)

PA4 AVL Trees (100 pts)

Due:

Learner Objectives

At the conclusion of this programming assignment, participants should be able to:

• Implement AVT Trees
• Visualize Trees

Prerequisites

Before starting this programming assignment, participants should be able to:

• Write object-oriented code in Python
• Work with trees
• Work with lists

Acknowledgments

Content used in this assignment is based upon information in the following sources:

• Data Structures: Abstraction and Design Using Java by Koffman and Wolfgang

Overview and Requirements

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

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

Program Details

Delete operations:

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

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

Similar to the Binary Search Tree implementation, the delete(key) method would need a remove(node) method to remove the node containing the key. This method would be similar in implementation to BST’s remove(node) method except that it would also need to ensure the tree is balanced (similar to _put() method).

So, to support the re-balancing operation, implement update_balance_delete(node) method that would recursively update the balance factor of the parent node and call rebalance(node) method if needed.

Finally, make sure update_balance_delete(node) method is called from within remove(node) method during node removal operation.

Here is the pseudo-code (not actual code) for update_balance_delete(node) method:

def update_balance_delete(self, node):

if node has parent:

update parent’s balance factor

if node’s parent is unbalanced (balance factor < 1 or balance factor > 1:

rebalance

recursively call this method on node’s parent’s parent

elif base condition is met (node’s parent’s balance factor != 0):

return

else:

call this method recursively on parent if needed

Note: update_balance_delete(node) method is needed since the update_balance(node) method is designed for rebalance during insertion (put) operations.

Test

Test your implementation by adding and removing the following items in the order shown: Data Analytics Systems and Algorithms

In [ ]:

mytree[9]=“CptS_450”

mytree[8]=“CptS_415”

mytree[7]=“CptS_315”

mytree[6]=“CptS_215”

mytree[5]=“CptS_132”

mytree[4]=“CptS_131”

mytree[3]=“CptS_122”

mytree[2]=“CptS_121”

mytree[1]=“CptS_115”

mytree.level_order_traversal()

mytree.delete(5)

mytree.delete(6)

mytree.level_order_traversal()

Below is the expected output from the above test code:

Level order traversal output – original tree:
{6:CptS_215(1)}
{4:CptS_131(1)}{8:CptS_415(0)}
{2:CptS_121(0)}{5:CptS_132(0)}
{1:CptS_115(0)}{3:CptS_122(0)}

{7:CptS_315(0)}{9:CptS_450(0)}

Level order traversal output – after delete operations:
{7:CptS_315(1)}
{2:CptS_121(-1)}{8:CptS_415(-1)}
{1:CptS_115(0)}{4:CptS_131(1)}

{3:CptS_122(0)}

{9:CptS_450(0)}

Tree Visualization

Visualize the tree using Python pydot module.

• Define a field self.graph within AVLTree class. Initialize it to 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.graph field to a new graph object using Graph() constructor method. It should also add root node to the graph plot and call visualize_helper(node) with root node as agrument. Finally, the visuallize(file) should render and save the tree visualization to a .png, .jpeg or .pdf file.
• The visualize(node) method should recursively add tree nodes and their parent-child relationships (edges) to self.graph for visualization.

Data Analytics Systems and Algorithms

Note: You may use the provided level_order_traversal() and level_order_helper() methods as templates for defining visualize(file) and visualize_helper(node) methods.

Here is a sample of the expected original tree: 

Here is a sample view of the expected updated tree after delete operations shown in the Test code: 

Submitting Assignments

1. Use the Blackboard tool https://learn.wsu.edu to submit your assignment. You will submit your code to the corresponding programming assignment under the “Content” tab. You must upload your solutions as <your last name>_pa4.zip by the due date and time.
2. Your .zip file should contain your .py files and your .txt files used to test your program.

Grading Guidelines

This assignment is worth 100 points bonus. Your assignment will be evaluated based on a successful compilation and adherence to the program requirements. We will grade according to the following criteria:

Standard (100 points):

• 50 pts for correct delete(key), remove(node) and update_balance_delete(node) implementations
• 10 pts for correct test result output
• 30 pts for correct visualize(file) and visuallize_helper(node) implementations
• 5 pts for generating and including the correct tree visualization plots (.png, .jpg or .pdf) files
• 5 pts for adherence to proper programming style and comments established for the class