Assume having an application which stores the data of students in binary search tree and…
- User
Assume having an application which stores the data of students in binary search tree and AVL trees, where each student has an id, a name, department and a GPA. In case of BST and AVL the key of the tree is the id, there are four functions as follows:
- Add a student (write the id “from 0 to 100”, name, GPA, and department)
- Remove a student using id
- Search for student using id (if found print the student information)
- Print all and Department Report (all the information of students are printed sorted by id and count students per department)
- Assistant
Here's an example of how we can implement a program that incorporates binary search trees and AVL trees to store student data. We'll be using Python as our programming language, but the logic can apply to other languages as well.
First, let's define a
Studentclass, a genericTreeNodeclass, and functions for BST and AVL:class Student: def __init__(self, id, name, department, GPA): self.id = id self.name = name self.department = department self.GPA = GPA def __str__(self): return f"ID: {self.id}, Name: {self.name}, Department: {self.department}, GPA: {self.GPA}" class TreeNode: def __init__(self, student, left=None, right=None, height=1): self.student = student self.left = left self.right = right self.height = height def add_student_bst(root, student): ... def remove_student_bst(root, id): ... def search_student_bst(root, id): ... def print_all_bst(root): ... def add_student_avl(root, student): ... def remove_student_avl(root, id): ... def search_student_avl(root, id): ... def print_all_avl(root): ...Now let's implement the BST functions:
def add_student_bst(root, student): if root is None: return TreeNode(student) if student.id < root.student.id: root.left = add_student_bst(root.left, student) else: root.right = add_student_bst(root.right, student) return root def remove_student_bst(root, id): if root is None: return None if id < root.student.id: root.left = remove_student_bst(root.left, id) elif id > root.student.id: root.right = remove_student_bst(root.right, id) else: if root.left is None: return root.right elif root.right is None: return root.left temp = find_min(root.right) root.student = temp.student root.right = remove_student_bst(root.right, temp.student.id) return root def find_min(root): current = root while current.left: current = current.left return current def search_student_bst(root, id): if root is None or root.student.id == id: return root if id < root.student.id: return search_student_bst(root.left, id) return search_student_bst(root.right, id) def print_all_bst(root): if root: print_all_bst(root.left) print(root.student) print_all_bst(root.right)Now let's implement the AVL tree functions. The main difference between BST and AVL is in the addition and removal part, which should be balanced:
def add_student_avl(root, student): ... # call the helper function to balance the tree after inserting student here ... return root def remove_student_avl(root, id): ... # call the helper function to balance the tree after removing the student here ... return root def search_student_avl(root, id): # since AVL is also a binary search tree, we can reuse the BST search function. return search_student_bst(root, id) def print_all_avl(root): # since AVL is also a binary search tree, we can reuse the BST print_all function. return print_all_bst(root) #helper functions for balancing AVL trees def height(root): return root.height if root else 0 def balance_factor(root): return height(root.left) - height(root.right) def update_height(root): root.height = 1 + max(height(root.left), height(root.right)) def rotate_left(root): # perform a left rotation ... def rotate_right(root): # perform a right rotation ... def balance(root): # balance the tree ... return rootNow we can use this implementation to create a menu-based application, where the user can interact with the trees by adding, removing, and searching for students, or printing all the records.
Note that in the actual implementation, you should also handle edge cases, user input validation, and wrong inputs.