//
// Created by grtsinry43 on 5/8/25.
//

#include "problem2.h"

#include <iostream>
#include <string>
using namespace std;

struct Student {
    int id;        // 学号
    int score;     // 成绩
    Student(int id, int score) : id(id), score(score) {}
};

struct TreeNode {
    Student data;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(Student data) : data(data), left(nullptr), right(nullptr) {}
};

class BST {
private:
    TreeNode* root;

    TreeNode* insert(TreeNode* node, Student data) {
        if (!node) return new TreeNode(data);
        if (data.id < node->data.id)
            node->left = insert(node->left, data);
        else if (data.id > node->data.id)
            node->right = insert(node->right, data);
        return node;
    }

    TreeNode* findMin(TreeNode* node) {
        while (node && node->left) node = node->left;
        return node;
    }

    TreeNode* remove(TreeNode* node, int id) {
        if (!node) return nullptr;
        if (id < node->data.id)
            node->left = remove(node->left, id);
        else if (id > node->data.id)
            node->right = remove(node->right, id);
        else {
            if (!node->left) {
                TreeNode* temp = node->right;
                delete node;
                return temp;
            } else if (!node->right) {
                TreeNode* temp = node->left;
                delete node;
                return temp;
            }
            TreeNode* temp = findMin(node->right);
            node->data = temp->data;
            node->right = remove(node->right, temp->data.id);
        }
        return node;
    }

    TreeNode* search(TreeNode* node, int id) {
        if (!node || node->data.id == id) return node;
        if (id < node->data.id)
            return search(node->left, id);
        return search(node->right, id);
    }

    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        cout << "ID: " << node->data.id << ", Score: " << node->data.score << endl;
        inorder(node->right);
    }

public:
    BST() : root(nullptr) {}

    void insert(Student data) {
        root = insert(root, data);
    }

    void remove(int id) {
        root = remove(root, id);
    }

    void search(int id) {
        TreeNode* result = search(root, id);
        if (result)
            cout << "Found - ID: " << result->data.id << ", Score: " << result->data.score << endl;
        else
            cout << "Student with ID " << id << " not found." << endl;
    }

    void display() {
        inorder(root);
    }
};

int problem_2() {
    BST bst;

    // 插入学生成绩
    bst.insert(Student(101, 85));
    bst.insert(Student(102, 90));
    bst.insert(Student(103, 78));
    bst.insert(Student(104, 88));

    cout << "All students:\n";
    bst.display();

    // 查找学生成绩
    cout << "\nSearching for student with ID 102:\n";
    bst.search(102);

    // 删除学生信息
    cout << "\nRemoving student with ID 103:\n";
    bst.remove(103);

    cout << "\nAll students after removal:\n";
    bst.display();

    return 0;
}