Skip to content
The Chat Archive
gpt-4-0314· OpenAI WildChat-4.8M (AI2)

Assume having an application which stores the data of students in binary search tree and…

  1. 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:

    1. Add a student (write the id “from 0 to 100”, name, GPA, and department)
    2. Remove a student using id
    3. Search for student using id (if found print the student information)
    4. Print all and Department Report (all the information of students are printed sorted by id and count students per department)
  2. 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 Student class, a generic TreeNode class, 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 root
    

    Now 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.