main.cpp

#include <iostream>
#include <vector>
#include <chrono> // Do pomiaru czasu
#include <cmath>

#define N 1000

struct Node {
    int value;
    Node *left;
    Node *right;

    Node(int val) :
            value(val),
            left(nullptr),
            right(nullptr) {}
};

int height(Node* node) {
    if (node == nullptr)
        return 0;
    return std::max(height(node->left), height(node->right)) + 1;
}
int countNodes(Node* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

void createBackbone(Node* root) {
    Node* prev = nullptr;
    Node* curr = root;

    while (curr != nullptr) {
        if (curr->left != nullptr) {
            // Rotate right to eliminate left child
            Node* temp = curr->left;
            curr->left = temp->right;
            temp->right = curr;
            curr = temp;
            if (prev != nullptr) prev->right = temp;
            else root = temp;
        }
        else {
            prev = curr;
            curr = curr->right;
        }
    }
}

int balanceFactor(Node* node) {
    if (node == nullptr)
        return 0;
    return std::abs(height(node->left) - height(node->right));
}

Node* leftRotate(Node* node) {
    Node* newRoot = node->right;
    node->right = newRoot->left;
    newRoot->left = node;
    return newRoot;
}

Node* rightRotate(Node* node) {
    Node* newRoot = node->left;
    node->left = newRoot->right;
    newRoot->right = node;
    return newRoot;
}

void compress(Node* grand, int m)
{
    Node* tmp = grand->right;

    for (int i = 0; i < m; i++) {
        Node* oldTmp = tmp;
        tmp = tmp->right;
        grand->right = tmp;
        oldTmp->right = tmp->left;
        tmp->left = oldTmp;
        grand = tmp;
        tmp = tmp->right;
    }
}

Node* balanceTree(Node* root) {
    if (root == nullptr)
        return nullptr;

    int leftHeight = height(root->left);
    int rightHeight = height(root->right);

    if (leftHeight - rightHeight > 1) {
        if (height(root->left->left) >= height(root->left->right))
            root = rightRotate(root);
        else {
            root->left = leftRotate(root->left);
            root = rightRotate(root);
        }
    }
    else if (rightHeight - leftHeight > 1) {
        if (height(root->right->right) >= height(root->right->left))
            root = leftRotate(root);
        else {
            root->right = rightRotate(root->right);
            root = leftRotate(root);
        }
    }

    return root;
}

Node* dsw_balance(Node* root) {
    if (root == nullptr) return nullptr;
    Node* grand = new Node(0);
    grand->right = root;
    createBackbone(root); //gdyby drzewo nie bylo zdegenerowane, nalezy na poczatku sprowadzic je do winorosli
    int n = countNodes(root);
    int h = floor(log2(n + 1));
    int m = pow(2, h) - 1;

    compress(grand, n - m);
    for (m = m / 2; m > 0; m /= 2) {
        compress(grand, m);
    }

    return grand->right;
}


void addNode(Node *root, int n) {
    if (root->value > n) {
        if (root-> left != nullptr)
            addNode(root->left, n);
        else
            root->left = new Node(n);
    }
    else {
        if (root->right != nullptr)
            addNode(root->right, n);
        else
            root->right = new Node(n);
    }
}

void inorderPrint(Node *root) {
    if (root != nullptr) {
        inorderPrint(root->left);
        std::cout << root->value << " -> ";
        inorderPrint(root->right);
    }
}

void preorderPrint(Node *root) {
    if (root != nullptr) {
        std::cout << root->value << " -> ";
        preorderPrint(root->left);
        preorderPrint(root->right);
    }
}
void postorderPrint(Node *root) {
    if (root != nullptr) {
        postorderPrint(root->left);
        postorderPrint(root->right);
        std::cout << root->value << " -> ";
    }
}

Node* deleteNode(Node* root, int val) {
    if (root == nullptr)
        return root;

    if (val < root->value)
        root->left = deleteNode(root->left, val);
    else if (val > root->value)
        root->right = deleteNode(root->right, val);
    else {
        if (root->left == nullptr) {
            Node* temp = root->right;
            delete root;
            return temp;
        }
        else if (root->right == nullptr) {
            Node* temp = root->left;
            delete root;
            return temp;
        }
        Node* temp = root->right;
        while (temp->left != nullptr)
            temp = temp->left;
        root->value = temp->value;
        root->right = deleteNode(root->right, temp->value);
    }
    return root;
}

void postOrderDelete(Node *root) {
    if (root != nullptr) {
        postOrderDelete(root->left);
        postOrderDelete(root->right);
        std::cout << "Deleting node: " << root->value << "\n";
        delete root;
    }
}

int findMax(Node *root) {
    if (root == nullptr){
        std::cout << "The tree is empty.\n";
        return -1;
    }
    std::cout << "Search path (from the root to the maximum element): ";
    while (root->right != nullptr) {
        std::cout << root->value << " -> ";
        root = root->right;
    }
    return root->value;
}

int findMin(Node *root) {
    if (root == nullptr) {
        std::cout << "The tree is empty.\n";
        return -1;
    }
    std::cout << "Search path (from the root to the minimum element): ";
    while (root->left != nullptr) {
        std::cout << root->value << " -> ";
        root = root->left;
    }
    return root->value;
}

Node* buildAVL(std::vector<int>& sortedArray, int start, int end) {
    if (start > end)
        return nullptr;

    int mid = (start + end) / 2; // assumes the list is sorted (sort it beforehand otherwise)
    Node* root = new Node(sortedArray[mid]);
    root->left = buildAVL(sortedArray, start, mid - 1);
    root->right = buildAVL(sortedArray, mid + 1, end);

    return root;
}

int main() {

    int option_generate;
    std::cout << "Choose an option:\n";
    std::cout << "1. Generate the trees automatically\n";
    std::cout << "2. Enter a list of numbers\n";
    std::cin >> option_generate;
    int n;
    std::vector<int> numbers;
    if (option_generate == 2) {
        std::cout << "Enter the number of elements: ";
        std::cin >> n;
        std::cout << "Enter " << n << " numbers:\n";
        numbers.resize(n);
        for (int i = 0; i < n; ++i) {
            std::cin >> numbers[i];
        }
        std::sort(numbers.begin(), numbers.end());
    } else {
        std::cout << "Enter the number of elements: ";
        std::cin >> n;
        numbers.resize(n);
        for (int i = 0; i < n; ++i) {
            numbers[i] = i + 1;
        }
    }
    // BUILDING A DEGENERATE BST
//    int *n;
//    n = new int[N];
//    for(int i=0; i < N; ++i)
//        n[i] = i+1;

    std::cout<<"Building the (degenerate) BST: ";
    Node *bstRoot = new Node(numbers[0]);
    auto start = std::chrono::steady_clock::now();
    for (int i = 1; i < n; ++i) {
        addNode(bstRoot, numbers[i]);
    }
    auto end = std::chrono::steady_clock::now();
    std::cout << "BST created. Operation time: " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " microseconds" << std::endl;



//    // BUILDING THE AVL TREE BY BINARY HALVING
//    std::vector<int> sortedArray;
//    for (int i = 1; i <= n; ++i) {
//        sortedArray.push_back(i);
//    }
    std::cout<<"Building the AVL tree by binary halving: ";
    start = std::chrono::steady_clock::now();
    Node* avlRoot = buildAVL(numbers, 0, numbers.size() - 1);
    end = std::chrono::steady_clock::now();
    std::cout << "AVL tree created. Operation time: " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " microseconds" << std::endl;


    // MENU LOOP
    int option;
    do {
        std::cout << "\nMenu:\n";
        std::cout << "1. Find the smallest and largest element in the tree\n";
        std::cout << "2. Delete a tree element with a given key\n";
        std::cout << "3. Print all tree elements in-order and pre-order\n";
        std::cout << "4. Delete the whole tree node by node (post-order)\n";
        std::cout << "5. Balance the tree\n";
        std::cout << "0. Exit\n";
        std::cout << "Choose an option: ";
        std::cin >> option;

        switch (option) {
            case 1:
            {
                auto start = std::chrono::steady_clock::now();
                std::cout << "Drzewo BST:\n";
                std::cout << "Maksymalny element: " << findMax(bstRoot) << std::endl;
//                std::cout << "Minimalny element: " << findMin(bstRoot) << std::endl;
                auto end = std::chrono::steady_clock::now();
                std::cout << "Czas operacji dla drzewa BST: " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " microseconds" << std::endl;

                start = std::chrono::steady_clock::now();
                std::cout << "Drzewo AVL:\n";
                std::cout << "Maksymalny element: " << findMax(avlRoot) << std::endl;
//                std::cout << "Minimalny element: " << findMin(avlRoot) << std::endl;
                end = std::chrono::steady_clock::now();
                std::cout << "Czas operacji dla drzewa AVL: " << std::chrono::duration_cast<std::chrono::microseconds>(end - start).count() << " microseconds" << std::endl;
            }
                break;
            case 2:
            {
                int numToDelete;
                std::cout << "Podaj liczbe wezlow do usuniecia: ";
                std::cin >> numToDelete;
                std::cout << "Podaj wartosci kluczy do usuniecia:\n";

                auto startBST = std::chrono::steady_clock::now();
                for (int i = 0; i < numToDelete; ++i) {
                    int key;
                    std::cout << "Wartosc klucza " << i + 1 << ": ";
                    std::cin >> key;
                    bstRoot = deleteNode(bstRoot, key);
                }
                auto endBST = std::chrono::steady_clock::now();
                std::cout << "Czas operacji usuwania dla drzewa BST: " << std::chrono::duration_cast<std::chrono::microseconds>(endBST - startBST).count() << " microseconds" << std::endl;

                auto startAVL = std::chrono::steady_clock::now();
                for (int i = 0; i < numToDelete; ++i) {
                    int key;
                    std::cout << "Wartosc klucza " << i + 1 << ": ";
                    std::cin >> key;
                    avlRoot = deleteNode(avlRoot, key);
                }
                auto endAVL = std::chrono::steady_clock::now();
                std::cout << "Czas operacji usuwania dla drzewa AVL: " << std::chrono::duration_cast<std::chrono::microseconds>(endAVL - startAVL).count() << " microseconds" << std::endl;
            }
                break;
            case 3:
            {
                auto startBST = std::chrono::steady_clock::now();
                std::cout << "Drzewo BST (In-order): ";
                inorderPrint(bstRoot);
                std::cout << std::endl;
//                std::cout << "Drzewo BST (Pre-order): ";
//                preorderPrint(bstRoot);
//                std::cout << std::endl;
                auto endBST = std::chrono::steady_clock::now();
                std::cout << "Czas operacji dla wypisywania elementow dla drzewa BST: " << std::chrono::duration_cast<std::chrono::microseconds>(endBST - startBST).count() << " microseconds" << std::endl;

                auto startAVL = std::chrono::steady_clock::now();
                std::cout << "Drzewo AVL (In-order): ";
                inorderPrint(avlRoot);
                std::cout << std::endl;
//                std::cout << "Drzewo AVL (Pre-order): ";
//                preorderPrint(avlRoot);
//                std::cout << std::endl;
                auto endAVL = std::chrono::steady_clock::now();
                std::cout << "Czas operacji dla wypisywania elementow dla drzewa AVL: " << std::chrono::duration_cast<std::chrono::microseconds>(endAVL - startAVL).count() << " microseconds" << std::endl;
            }
                break;
            case 4:
            {
                auto startBST = std::chrono::steady_clock::now();
                postOrderDelete(bstRoot);
                std::cout << "Drzewo BST zostalo usuniete.\n";
                auto endBST = std::chrono::steady_clock::now();
                std::cout << "Czas operacji usuwania drzewa BST: " << std::chrono::duration_cast<std::chrono::microseconds>(endBST - startBST).count() << " microseconds" << std::endl;

                auto startAVL = std::chrono::steady_clock::now();
                postOrderDelete(avlRoot);
                std::cout << "Drzewo AVL zostalo usuniete.\n";
                auto endAVL = std::chrono::steady_clock::now();
                std::cout << "Czas operacji usuwania drzewa AVL: " << std::chrono::duration_cast<std::chrono::microseconds>(endAVL - startAVL).count() << " microseconds" << std::endl;
            }
                break;
            case 5:
            {
                auto startBST = std::chrono::steady_clock::now();
                std::cout << "Wywoluje rownowazenie drzewa BST...\n";
                bstRoot = dsw_balance(bstRoot);
                std::cout << "Drzewo BST zostalo zrownowazone.\n";
                auto endBST = std::chrono::steady_clock::now();
                std::cout << "Czas operacji rownowazenia drzewa BST: " << std::chrono::duration_cast<std::chrono::microseconds>(endBST - startBST).count() << " microseconds" << std::endl;

//                auto startAVL = std::chrono::steady_clock::now();
//                std::cout << "Wywoluje rownowazenie drzewa AVL...\n";
//                avlRoot = balanceTree(avlRoot);
//                std::cout << "Drzewo AVL zostalo zrownowazone.\n";
//                auto endAVL = std::chrono::steady_clock::now();
//                std::cout << "Czas operacji rownowazenia drzewa AVL: " << std::chrono::duration_cast<std::chrono::microseconds>(endAVL - startAVL).count() << " microseconds" << std::endl;
            }
                break;
            case 0:
                std::cout << "Koniec programu.\n";
                break;
            default:
                std::cout << "Niepoprawna opcja. Sprobuj ponownie.\n";
                break;
        }
    } while (option != 0);

//    delete[] n;
    return 0;
}