## Topo

#include <iostream>

using namespace std;

typedef struct leader* lref;
typedef struct trailer* tref;


struct leader{
    int key; // Key value
    int count; // Count leader before it, leader before it in topo
    lref next; // To next leader
    tref trailer; // Trailer will manage leader which stay behind current leader
};

struct trailer{
    lref id; // To leader which stay behind current leader

    tref next; // The next trailer of current leader
};

vector<lref> allNodes;

lref addList(lref& head, lref& tail, int w, int &z)
{
    lref h;

    h = head;

    tail->key = w;

    while(h->key != w) // Sequential Search to return q or p
    {
        h = h->next;
    }
    if(h == tail)
    { // need create new tail to be guard
        tail = new leader;

        h->next = tail;
        z++;
        h->count = 0;
        h->trailer = nullptr;
        //allNodes.push_back(h); // Easy  to delete node
    }
    
    return h;
}   


void update(lref& p, lref& q)
{
    tref t = new trailer;
    t->id = q;
    t->next = p->trailer;
    p->trailer = t;
    q->count++;
}

void topoSort(lref& head , lref& tail, int& z)
{
    lref p = head;
    lref q = p;
    head = nullptr; // head : list of node have count = 0

    while(p != tail)
    {
        q = p;
        p = p->next;
        --z;
        if(q->count == 0)
        {
            q->next = head;
            head = q;
        }
    }

    q = head;
    while(q)
    {
        cout << q->key << " ";
        tref t = q->trailer;
        q = q->next;
        while(t)
        {
            p = t->id;
            p->count--;
            if(p->count == 0)
            {
                p->next = q;
                q = p;
            }
            t = t->next;
        }
    }
}

void deleteTrailers(tref t) {
    while (t != NULL) {
        tref temp = t;
        t = t->next;
        delete temp;
    }
}

void deleteLeaders(lref head) {
    while (head != NULL) {
        lref temp = head;
        head = head->next;
        deleteTrailers(temp->trailer); // Giải phóng danh sách các trailer
        delete temp;
    }
}

int main()
{
    lref head, tail, p , q;
    int z, x, y;

    z = 0;
    head = new leader;
    tail = head;

    while(cin >> x >> y)
    {
        p = addList(head,tail, x , z);
        q = addList(head,tail, y , z);

        update(p, q);
    }
    lref head_tmp = head;

    topoSort(head, tail, z);
    if(z)
    {
        cout << "Error List!\n";
    }

    deleteLeaders(head_tmp);

}

## Radix Sort (Ứng dụng Hash)
+ Xác định số lớn nhất để xem lặp lại bao nhiêu lần
+ Mỗi lần lặp sẽ lặp sẽ tạo các leader theo thứ tự theo thứ tự tăng dần, leader sẽ chứa các trailer mà có kí số bằng đại diện đó
+ Giống với sắp xếp Topo nhưng các leader được sắp tăng dần
+ Mỗi lần duyệt kí số sẽ nối trailer của leader trước nối trailer sau rồi xoá các leader(Coi ví dụ trong tập nhé mf)

#include <iostream>
#include <fstream>
#include <math.h>
#include "multi-link-list.h"
#include "radix-sort.h"

struct TRAILER //node quản lý các số dữ liệu thực sự
{
    int number;
    TRAILER* next;
};

struct TLIST //danh sách các trailer
{
    TRAILER* head;
};

struct LEADER //node quản lý các chữ số dùng để so sánh được sắp xếp thứ tự tăng dần của digit
{
    int digit;
    LEADER* next;
    TRAILER* trailerHead;
    TRAILER* trailerTail;
};

struct LLIST //danh sách các leader
{
    LEADER* head;
};
#include <iostream>
#include "multi-link-list.h"
TRAILER* createTrailer(int number)
{
    TRAILER* trailer = new TRAILER;
    if (!trailer)
    {
        std::cerr << "Cannot allocate memory\n";
        return nullptr;
    }
    trailer->next = nullptr;
    trailer->number = number;
    return trailer;
}

LEADER* createLeader(int digit)
{
    LEADER* leader = new LEADER;
    if (!leader)
    {
        std::cerr << "Cannot allocate memory\n";
        return nullptr;
    }
    leader->digit = digit;
    leader->next = nullptr;
    leader->trailerHead = nullptr;
    leader->trailerTail = nullptr;
    return leader;
}

void addHeadTrailer(TLIST& tlist, int number)
{
    TRAILER* newTrailer = createTrailer(number); 
    if (!newTrailer)
        return;

    if (tlist.head)
        newTrailer->next = tlist.head;
    tlist.head = newTrailer;
}

void delTrailer(TLIST& tlist)
{
    for (TRAILER* trailer = tlist.head; trailer; trailer = trailer->next)
        delete trailer;
    tlist.head = nullptr;
}

void delLeader(LLIST& llist)
{
    for (LEADER* leader = llist.head; leader; leader = leader->next)
        delete leader;
    llist.head = nullptr;
}

LEADER* getLeader(LLIST& llist, int digit)
{
    if (!llist.head) //leader list chưa có phần tử nào -> tạo phần tử đầu tiên
    {
        LEADER* newLeader = createLeader(digit);
        if (!newLeader)
            return nullptr;
        llist.head = newLeader;
        return llist.head;
    }

    //tìm leader với digit đã cho
    LEADER* fakeHead = createLeader(-1); //tạo một head giả trỏ đến head thật sự
    fakeHead->next = llist.head;
    LEADER* leader = fakeHead;
    while (leader->next && (leader->next)->digit < digit) //tìm phần tử cuối cùng 
                                                          //hoặc phần tử tiếp theo có digit lớn hơn hoặc bằng digit đã cho
            leader = leader->next;
    //nếu phần tử tiếp theo là nullptr hoặc có digit lớn hơn 
    //-> không tồn tại leader với digit đã cho
    //-> tạo leader mới
    if (!leader->next || (leader->next)->digit > digit)
    {
        LEADER* newLeader = createLeader(digit);
        newLeader->next = leader->next;
        if (leader == fakeHead)
            llist.head = newLeader;
        else
            leader->next = newLeader;
        return newLeader;
    }

    //trường hợp còn lại: phần tử tiếp theo có digit bằng với digit cho trước 
    //-> đã tồn tại leader với digit cho trước
    //-> trả về leader tiếp theo 
    return leader->next;
}

int main()
{
    TLIST tlist = {nullptr};
    std::ifstream f = openFile("input.txt");
    int k, n;
    f >> k >> n;
    for (int i = 0; i < n; i++) //tạo danh sách liên kết gồm các trailer
    {
        int number; 
        f >> number;
        addHeadTrailer(tlist, number);
    }
    radixSort(tlist, k);

    for (TRAILER* trailer = tlist.head; trailer; trailer=trailer->next)
        std::cout << trailer->number << " ";
    delTrailer(tlist);
    return 0;
}

std::ifstream openFile(const char path[])
{   
    std::ifstream f;
    f.open(path);
    if (!f) 
    {
        std::cerr << "Cannot open file!\n";
        exit(-1);
    }
    return f;
}

int getDigit(int number, int k, int i) //chia các chữ số thành các phần gồm k chữ số
                                       //lấy đoạn thứ i (i từ 0) từ phải qua trái
{
    return (number / (int)pow(10, k * i)) % (int)pow(10, k);
}

void radixSort(TLIST& tlist, int k)
{
    if (!tlist.head)
        return;

    int max = tlist.head->number;
    for (TRAILER* trailer = tlist.head; trailer; trailer = trailer->next) 
        if (max < trailer->number)
            max = trailer->number; //tìm số lớn nhất trong trailer list
    int times = ceil(ceil(log10(max)) / k); //tính toán số lần thực hiện vòng for 
                                            //sử dụng số lớn nhất để tính toán
                                            //công thức: số số chữ số chia số khoảng chia yêu cần (làm tròn lên)
    
    for (int i = 0; i < times; i++)
    {
        LLIST llist = {nullptr};
        TRAILER* trailer = tlist.head;
        do
        {
            int digit = getDigit(trailer->number, k, i);
            LEADER* leader = getLeader(llist, digit); //trả về leader giữ digit 
                                                      //nếu chưa tồn tại, tạo mới rồi trả về
            
            //addTail trailer để giữ tính stable của radix sort
            TRAILER* curTrailer = trailer; //lưu lại trailer hiện tại
            trailer = trailer->next;

            ////nếu leader đang xét chưa có trailer -> thêm vào và cập nhật trailerHead và trailerTail
            if (!leader->trailerHead)
            {
                leader->trailerHead = leader->trailerTail = curTrailer;
                curTrailer->next = nullptr;
                continue;
            }
            ////nếu leader đã có trailer
            curTrailer->next = nullptr;
            leader->trailerTail = (leader->trailerTail)->next = curTrailer;
        } while (trailer);

        //sau khi hoàn thành đưa các trailer vào đúng leader có digit theo thứ tự tăng dần
        //-> nối các trailer lại với nhau
        tlist.head = (llist.head)->trailerHead;
        for (LEADER* leader = llist.head; leader->next; leader = leader->next)
            (leader->trailerTail)->next = (leader->next)->trailerHead;
        delLeader(llist); //sau khi nối thì xóa hệ thống leader
    }
}

## Priority queue
### Heap
+ Insert, Extract -> siftUp
+ Remove -> siftDown
+ i = 0, j = 2*i + 1

#include <iostream>
using namespace std;

struct p_queue{
    int key;
    int priority; // do uu tien
};


void sift(p_queue* a, int l, int r)
{
    int i = l;
    int j = 2*i + 1;


    while(j < r)
    {
        if(j < r - 1)
        {
            if(a[j].priority > a[j+1].priority)
            {
                ++j;
            }
        }
        if(a[i].priority <= a[j].priority)
            break;

        swap(a[i], a[j]);
        i = j;
        j = i*2 + 1;
        
    }
}

void sift_up(p_queue* a, int index)
{
    int i = (index - 1)/2;
    int j = index;
    while(i)
    {
        if(a[j].priority < a[i].priority)
        {
            swap(a[j], a[i]);
        }
        else{
            break;
        }
        j = i;
        i = (j - 1) / 2;
    }
    
}

void Insert(p_queue*& a, int x, int priority, int& len)
{
    p_queue* b = new p_queue[len + 1];
    memcpy(b, a, len*sizeof(p_queue));
    b[len].key = x;
    b[len].priority = priority;

    delete[]a;

    a = b;

    int l = (len + 1) / 2 - 1;

    sift_up(b, len);
    ++len;

}

void Remove(p_queue*& a, int val, int& len)
{

    int index = 0;

    for(int i = 0 ; i < len; ++i)
    {
        if(a[i].key == val)
        {
            index = i;
            swap(a[index], a[len-1]);
            break;
        }
    }
    
    if(index == len)
        return;
    p_queue* b = new p_queue[len - 1];
    memcpy(b, a, (len - 1)*sizeof(p_queue));

    delete[] a;

    a = b;
    --len;

    sift(a, index, len);
}

int Extract(p_queue* a, int& len)
{
    if(len == 0)
    {
        return -1;
    }
    int val = a[0].key;

    swap(a[0], a[len-1]);
    --len;
    sift(a, 0, len);
    return val;
}


int main()
{
    p_queue *a = nullptr;
    int list[] = {1, 4, 5, 3, 2 ,7 ,6};
    int priority[] = {1, 2, 3, 4, 5 ,6 ,7};

    int n = 7;
    int l = n / 2 - 1;
    a = new p_queue[n];

    for(int i = 0 ; i < n ; ++i)
    {
        a[i].key = list[i];
        a[i].priority = priority[i];
    }

    while(l--)
    {
        sift(a,l,n);
    }

    for(int i = 0 ; i < n; ++i)
    {
        cout << a[i].key << "-" << a[i].priority << endl;
    }
    cout << "After insert \n";
    Insert(a, 10, 2, n);

    cout << n << endl;
    for(int i = 0 ; i < n; ++i)
    {
        cout << a[i].key << "-" << a[i].priority << endl;
    }

    cout << "After remove \n";
    Remove(a, 4, n);

    cout << n << endl;
    for(int i = 0 ; i < n; ++i)
    {
        cout << a[i].key << "-" << a[i].priority << endl;
    }

    cout << "Pop : " << Extract(a, n) << endl;
    for(int i = 0 ; i < n; ++i)
    {
        cout << a[i].key << "-" << a[i].priority << endl;
    }
}

### List

#include <iostream>
using namespace std;

struct PQNode{
    PQNode* next; 
    int key;
    int priority;

    PQNode(int key, int priority) : key(key), priority(priority), next(nullptr) {}

};

bool isEmpty(PQNode* head) {
        return head == nullptr;
    }

// Method to insert an object into the queue
void Insert(PQNode*& head, int key, int priority) {
    PQNode* newNode = new PQNode(key, priority); // Create a new node
    // If the queue is empty or the new node has higher priority than the head
    if (isEmpty(head) || head->priority > priority) {
        newNode->next = head; // Insert the new node at the beginning
        head = newNode;
    } else {
        // Find the correct position to insert the new node
        PQNode* current = head;
        while (current->next != nullptr && current->next->priority <= priority) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

// Method to extract (remove) the highest priority object from the queue
PQNode* Extract(PQNode*& head) {
    if (isEmpty(head)) {
        return nullptr; // Return null if the queue is empty
    }
    PQNode* temp = head; // Store the head node
    head = head->next; // Move the head to the next node
    return temp; // Return the original head node
}

// Method to remove an object with a specific ID from the queue
bool Remove(PQNode*& head, int val) {
    if (isEmpty(head)) {
        return false; // Return false if the queue is empty
    }
    if (head->key == val) {
        // Remove the head node if it matches the ID
        PQNode* temp = head;
        head = head->next;
        delete temp;
        return true;
    }
    // Search for the node with the given ID
    PQNode* current = head;
    while (current->next != nullptr && current->next->key != val) {
        current = current->next;
    }
    if (current->next == nullptr) {
        return false; // Return false if the ID is not found
    }
    // Remove the found node
    PQNode* temp = current->next;
    current->next = temp->next;
    delete temp;
    return true;
}

// Method to change the priority of an object with a specific ID
bool changePriority(PQNode*& head,int val, int newPriority) {
    if (Remove(head, val)) {
        // If the object is successfully removed, re-insert it with the new priority
        Insert(head, val, newPriority);
        return true;
    }
    return false; // Return false if the object with the specified ID is not found
}

void printQueue(PQNode* a)
{
    PQNode* p = a;
    while(p)
    {
        cout << p->key << " - " << p->priority << endl;
        p = p->next;
    }

}

int main()
{
    PQNode *a;

    int list[] = {1, 4, 5, 3, 2 ,7 ,6};
    int priority[] = {1, 2, 3, 4, 5 ,6 ,7};

    int n = 7;

    for(int i = 0 ; i < n; ++i)
    {
        Insert(a, list[i], priority[i]);
    }
    printQueue(a);
    cout << "After insert 10 : " << endl;
    Insert(a, 10, 2);
    printQueue(a);
    Remove(a, 4);
    printQueue(a);
}

## BST

+ Sử dụng dummyHead để gán hai node ý tưởng để khử đệ qui

#include <bits/stdc++.h>
using namespace std;


template<typename T>
class Stack {
private:
    struct StackNode {
        T data;
        StackNode* next;

        StackNode(T data) : data(data), next(nullptr) {}
    };

    StackNode* topNode;

public:
    Stack() : topNode(nullptr) {}

    ~Stack() {
        while (!isEmpty()) {
            pop();
        }
    }

    void push(T data) {
        StackNode* newNode = new StackNode(data);
        newNode->next = topNode;
        topNode = newNode;
    }

    void pop() {
        if (isEmpty()) {
            return;
        }
        StackNode* temp = topNode;
        topNode = topNode->next;
        delete temp;
    }

    T top() {
        if (!isEmpty()) {
            return topNode->data;
        }
        return nullptr; // Handle this appropriately in your code
    }

    bool isEmpty() {
        return topNode == nullptr;
    }
};


struct NODE{ // AVL
    int key;
    NODE* pLeft;
    NODE* pRight;
    int height;
};


struct BSTNODE{
    int key;
    BSTNODE* pLeft;
    BSTNODE* pRight;

};

BSTNODE* createNode(int data){
    BSTNODE* pNode = new BSTNODE;
    pNode->key = data;
    pNode->pLeft = NULL;
    pNode->pRight = NULL;

    return pNode;
}

NODE* createNodeAVL(int data){
    NODE* pNode = new NODE;
    pNode->key = data;
    pNode->height = 0;
    pNode->pLeft = nullptr;
    pNode->pRight = nullptr;

    return pNode;
}

void Insert(BSTNODE* &pRoot, int x){
    if (pRoot == NULL)
        pRoot = createNode(x);
    else if (x < pRoot->key)
        Insert(pRoot->pLeft, x);
    else if (x > pRoot->key)
        Insert(pRoot->pRight, x);
}

void Insert(BSTNODE*& dummyHead, BSTNODE*& root, int x)
{
    if(root == nullptr)
    {
        root = createNode(x);
        return;
    }
    BSTNODE* p1 = root; // p2 is parent of p1
    BSTNODE* p2 = dummyHead;
    while(p1 != nullptr)
    {
        if(p1->key == x)
            return;
        p2 = p1;
        if(p1->key > x)
        {
            p1 = p1->pLeft;
        }
        else{
            p1 = p1->pRight;
        }
    }
    p1 = createNode(x);

    if(p2->key > x)
    {
        p2->pLeft = p1; 
    }
    else
    {
        p2->pRight = p1;
    }
}

int Height(BSTNODE* pRoot){
    if (pRoot == NULL)
        return -1;

    return max(Height(pRoot->pLeft), Height(pRoot->pRight)) + 1;
}

void printTree(BSTNODE* r, int indent = 0) 
{
    if (r != nullptr) {
        if (r->pRight) {
            printTree(r->pRight, indent + 5);
        }
        if (indent > 0) {
            cout << setw(indent) << " ";
        }
        cout << "[" << r->key << "]" << endl;
        if (r->pLeft) {
            printTree(r->pLeft, indent + 5);
        }
    }
}

void printTree(NODE* r, int indent = 0) 
{
    if (r != nullptr) {
        if (r->pRight) {
            printTree(r->pRight, indent + 5);
        }
        if (indent > 0) {
            cout << setw(indent) << " ";
        }
        cout << "[" << r->key << "]" << endl;
        if (r->pLeft) {
            printTree(r->pLeft, indent + 5);
        }
    }
}
void createTree(BSTNODE*& dummy, BSTNODE*& root, int a[], int n)
{
    if(n <= 0)
        return;


    for(int i = 0 ; i < n; ++i)
    {
        Insert(dummy, root, a[i]);
    }
}

// 6. Level-order Traversal:
void LevelOrder(BSTNODE* pRoot){
    if (pRoot == NULL)
        return;

    queue<BSTNODE*> Q;
    Q.push(pRoot);
    while (!Q.empty()){
        BSTNODE* p = Q.front();
        Q.pop();

        cout << p->key << " ";
        if (p->pLeft != NULL)
            Q.push(p->pLeft);
        if (p->pRight != NULL)
            Q.push(p->pRight);
    }
}

// BSTNODE* Search(BSTNODE* pRoot, int x){
//     if (pRoot == NULL)
//         return NULL;

//     if (x == pRoot->key)
//         return pRoot;
//     else if (x < pRoot->key)
//         return Search(pRoot->pLeft, x);
//     else
//         return Search(pRoot->pRight, x);
// }

BSTNODE* Search(BSTNODE* root, int x)
{
    if(root == nullptr)
        return root;

    BSTNODE* p1 = root;
    while(p1 != nullptr)
    {
        if(p1->key == x)
            return p1;
        if(p1->key > x)
        {
            p1 = p1->pLeft;
        }
        else{
            p1 = p1->pRight;

        }
    }
    return nullptr;
}

BSTNODE* findRightMostNode(BSTNODE* pRoot){
    // pRoot must be not null
    if (pRoot->pRight == NULL)
        return pRoot;
    return findRightMostNode(pRoot->pRight);
}

void Del(BSTNODE*& root, int x)
{
    if(root == nullptr)
        return;
    
    if(root->key < x)
        Del(root->pRight, x);
    else if (root->key > x)
        Del(root->pLeft, x);
    else
    {
        if(root->pLeft == nullptr && root->pRight == nullptr) // no child
        {
            delete root;
            root = nullptr;
        }
        else if (root->pLeft == nullptr || root->pRight == nullptr)
        {
            if(root->pLeft == nullptr)
            {
                BSTNODE* tmp = root->pRight;
                delete root;
                root = tmp;
            }
            else
            {
                BSTNODE* tmp = root->pLeft;

                delete root;
                root = tmp;
            }
        }
        else
        {
            BSTNODE* rightMost = findRightMostNode(root->pLeft);
            root->key = rightMost->key;
            Del(root->pLeft, rightMost->key);
        }
    }
}

void DeleteNode(BSTNODE*& root, int x) { # Non-recursive
    BSTNODE* parent = nullptr;
    BSTNODE* current = root;

    // Tìm node cần xoá
    while (current != nullptr && current->key != x) {
        parent = current;
        if (x < current->key) {
            current = current->pLeft;
        } else {
            current = current->pRight;
        }
    }

    // Nếu không tìm thấy node cần xoá
    if (current == nullptr) {
        return;
    }

    // Nếu node có hai con
    if (current->pLeft != nullptr && current->pRight != nullptr) {
        BSTNODE* successor = current->pRight;
        BSTNODE* successorParent = current;

        // Tìm node kế cận (node có giá trị nhỏ nhất trong cây con phải của current)
        while (successor->pLeft != nullptr) {
            successorParent = successor;
            successor = successor->pLeft;
        }

        // Copy giá trị của successor vào current
        current->key = successor->key;

        // Di chuyển current và parent đến node kế cận để xoá
        current = successor;
        parent = successorParent;
    }

    // Node có một hoặc không có con
    BSTNODE* child = (current->pLeft != nullptr) ? current->pLeft : current->pRight;

    // Xác định node cần xoá là con trái hay con phải của parent
    if (parent == nullptr) {
        root = child;
    } else if (parent->pLeft == current) {
        parent->pLeft = child;
    } else {
        parent->pRight = child;
    }

    // Xoá node
    delete current;
}

## AVL

int getHeight(NODE* root)
{
    if(root == nullptr)
        return 0;
    return max(getHeight(root->pLeft), getHeight(root->pRight)) + 1;
}


void UpdateHeight(NODE*& p){
    if (p == nullptr) return;

    p->height = max(getHeight(p->pLeft), getHeight(p->pRight)) + 1;
}



NODE* LeftRotation(NODE* pRoot){
    NODE* child = pRoot->pRight;
    pRoot->pRight = child->pLeft;
    child->pLeft = pRoot;

    UpdateHeight(pRoot);
    UpdateHeight(child);

    return child;
}

NODE* RightRotation(NODE* pRoot){
    NODE* child = pRoot->pLeft;
    pRoot->pLeft = child->pRight;
    child->pRight = pRoot;

    UpdateHeight(pRoot);
    UpdateHeight(child);

    return child;
}

int BalanceFactor(NODE* p){
    if (p == NULL) return 0;
    return getHeight(p->pLeft) - getHeight(p->pRight);
}

void Balance(NODE*& pRoot){
    if (pRoot == NULL) 
        return;

    UpdateHeight(pRoot);
    int balanceFactor = BalanceFactor(pRoot);

    if (abs(balanceFactor) <= 1) 
        return;

    // Left Left
    if (balanceFactor > 1 && BalanceFactor(pRoot->pLeft) >= 0){
        pRoot = RightRotation(pRoot);
    }

    // Right Right
    else if (balanceFactor < -1 && BalanceFactor(pRoot->pRight) < 0){
        pRoot = LeftRotation(pRoot);
    }

    // Left Right
    else if (balanceFactor > 1 && BalanceFactor(pRoot->pLeft) < 0){
        pRoot->pLeft = LeftRotation(pRoot->pLeft);
        pRoot = RightRotation(pRoot);
    }

    // Right Left
    else if(balanceFactor < -1 && BalanceFactor(pRoot->pRight) >= 0){
        pRoot->pRight = RightRotation(pRoot->pRight);
        pRoot = LeftRotation(pRoot);
    }
}

void Insert(NODE* &pRoot, int x){
    if (pRoot == nullptr){
        pRoot = createNodeAVL(x);
        return;
    }

    if (x < pRoot->key){
        Insert(pRoot->pLeft, x);
        UpdateHeight(pRoot->pLeft);
    }
    else if (x > pRoot->key){
        Insert(pRoot->pRight, x);
        UpdateHeight(pRoot->pRight);
    }
    else
        return;
    
    Balance(pRoot);
}

void RemoveRightmost(NODE*& pRoot, NODE*& tmp){
    if (pRoot->pRight != NULL){
        RemoveRightmost(pRoot->pRight, tmp);
    }
    else{
        tmp->key = pRoot->key;
        tmp = pRoot;
        pRoot = pRoot->pLeft;
        delete tmp;
    }

    Balance(pRoot);
}

void Remove(NODE* &pRoot, int x){
    if (pRoot == NULL)
        return;
    
    if (x < pRoot->key)
        Remove(pRoot->pLeft, x);
    else if (x > pRoot->key)
        Remove(pRoot->pRight, x);
    else{
        // FOUND
        NODE* tmp = pRoot;
        if (pRoot->pLeft == NULL){
            pRoot = pRoot->pRight;
            delete tmp;
        }
        else if (pRoot->pRight == NULL){
            pRoot = pRoot->pLeft;
            delete tmp;
        }
        else
            RemoveRightmost(pRoot->pLeft, tmp);
    }

    Balance(pRoot);
}


void balanceTree(NODE*& node) {
    if (node == nullptr) {
        return;
    }

    // Balance the left subtree
    balanceTree(node->pLeft);

    // Balance the right subtree
    balanceTree(node->pRight);

    // Get the balance factor of this node to check whether
    // this node became unbalanced
    int balance = BalanceFactor(node);

    // If this node becomes unbalanced, then there are 4 cases

    // Left Left Case
    if (balance > 1 && BalanceFactor(node->pLeft) >= 0) {
        node = RightRotation(node);
    }

    // Left Right Case
    if (balance > 1 && BalanceFactor(node->pLeft) < 0) {
        node->pLeft = LeftRotation(node->pLeft);
        node = RightRotation(node);
    }

    // Right Right Case
    if (balance < -1 && BalanceFactor(node->pRight) <= 0) {
        node = LeftRotation(node);
    }

    // Right Left Case
    if (balance < -1 && BalanceFactor(node->pRight) > 0) {
        node->pRight = RightRotation(node->pRight);
        node = LeftRotation(node);
    }

    // Return the node pointer
}

void InsertNonRecursive(NODE*& root, int x) {
    Stack<NODE**> path;
    // Find the position to insert the new node
    NODE** p = &root;
    while (*p != nullptr) {

        path.push(p); // Store the path for later balancing
        if (x < (*p)->key) {
            p =&((*p)->pLeft);
        } else if (x > (*p)->key) {
            p =&((*p)->pRight);

        } else { // Element already exists
            return;
        }
    }

    // Create new node
    *p = createNodeAVL(x);

    // Traverse back up the tree and balance each node
    while (!path.isEmpty()) {
        p = path.top();
        path.pop();
        if(abs(BalanceFactor(*p)) > 1)
        {
            UpdateHeight(*p);
            Balance(*p);
            break; // Dung lai khi gap nut mat can bang
        }
    }
    UpdateHeight(root);
}


void RemoveNonRecursive(NODE*& root, int x) {
    Stack<NODE*> path;
    NODE* p = root;

    NODE* parent = nullptr;

    // Tìm node cần xoá
    while (p != nullptr && (p)->key != x) {
        path.push(p); // Store the path for later balancing

        parent = p;
        if (x < (p)->key) {
            p = ((p)->pLeft);
        } else if (x > p->key){
            p = ((p)->pRight);
        }
        else
            break;
    }

    // Nếu không tìm thấy node cần xoá
    if (p == nullptr) {
        return;
    }
    // Nếu node có hai con
    if (p->pLeft != nullptr && p->pRight != nullptr) {
        NODE* successor = p->pRight;
        NODE* successorParent = p;

        // Tìm node kế cận (node có giá trị nhỏ nhất trong cây con phải của current)
        while (successor->pLeft != nullptr) {
            path.push(successorParent);
            successorParent = successor;
            successor = successor->pLeft;
        }

        // Copy giá trị của successor vào current
        p->key = successor->key;

        // Di chuyển current và parent đến node kế cận để xoá
        p = successor;
        parent = successorParent;
    }

    // Node có một hoặc không có con
    NODE* child = (p->pLeft != nullptr) ? p->pLeft : p->pRight;

    // Xác định node cần xoá là con trái hay con phải của parent
    if (parent == nullptr) {
        root = child;
    } else if (parent->pLeft == p) {
        parent->pLeft = child;
    } else {
        parent->pRight = child;
    }

    // Xoá node
    delete p;

    // Traverse back up the tree and balance each node
    while (!path.isEmpty()) {
        p = path.top();
        path.pop();
        if(abs(BalanceFactor(p)) >= 1)
        {
            UpdateHeight(p);
            Balance(p);
        }

    }
}


int main()
{
    int a[] = {3,2,4,5,6,7,2,3,5};
    int n = sizeof(a)/sizeof(a[0]);
    BSTNODE* dummyHead = new BSTNODE;
    BSTNODE* root = nullptr;
    dummyHead->pRight = root;
    createTree(dummyHead, root, a, n);
    //LevelOrder(root);
    // printTree(root);
    // BSTNODE* node = Search(root, 7);
    // cout << node->key << endl;

    // DeleteNode(root, 3);
    // printTree(root);

    // DeleteNode(root, 2);
    // printTree(root);


    // AVL Tree

    NODE* AVL_root = nullptr;

    for(int i = 0; i < n ; ++i)
    {
        InsertNonRecursive(AVL_root, a[i]);
        //printTree(AVL_root, a[i]);
    }

    printTree(AVL_root);
    cout <<"-------------------------\n";
    InsertNonRecursive(AVL_root,8);
    printTree(AVL_root);
    cout <<"-------------------------\n";
    RemoveNonRecursive(AVL_root,5);
    printTree(AVL_root);

    cout <<"-------------------------\n";
    RemoveNonRecursive(AVL_root,4);
    printTree(AVL_root);

    cout <<"-------------------------\n";
    RemoveNonRecursive(AVL_root,6);
    printTree(AVL_root);

}

## Đỏ đen

#include <iostream>
using namespace std;

struct RBNode{
    int key;
    bool color; //Black = 0
    RBNode* parent;
    RBNode* left;
    RBNode* right;
};

RBNode* nil;

RBNode* getNode(int key, int color, RBNode* nil)
{
    RBNode* p = new RBNode;
    p->key = key;
    p->color = color;
    p->left = p->right = p->parent = nil;
    return p;
}

void leftRotate(RBNode*& root, RBNode* x)
{
    RBNode* y = x->right;
    x->right = y->left;
    if (y->left != nil)
    {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if(x->parent == nil)
    {
        root = y;
    }
    else
    {
        if(x->parent->left == x)
        {
            x->parent->left = y;
        }
        else 
            x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

void rightRotate(RBNode*& root, RBNode* x)
{
    RBNode* y = x->left;
    x->left = y->right;
    if (y->right != nil)
    {
        y->right->parent = x;
    }
    y->parent = x->parent;
    if(x->parent == nil)
    {
        root = y;
    }
    else
    {
        if(x->parent->left == x)
        {
            x->parent->left = y;
        }
        else 
            x->parent->right = y;
    }
    y->right = x;
    x->parent = y;
}

void insertLeftAdjust(RBNode* &pRoot, RBNode* ref) { // parent in left side
    RBNode* p = ref->parent->parent->right;

    if (p->color == true) { //case 1
        ref->parent->color = false;

        p->color = false;

        ref->parent->parent->color = true;

        ref = ref->parent->parent;
    } else {
        //Case 2 or case 3
        if (ref == ref->parent->right) {
            ref = ref->parent;

            leftRotate(pRoot, ref);
        }
        //case 3 
        ref->parent->color = false;

        ref->parent->parent->color = true;

        rightRotate(pRoot, ref->parent->parent);
    }
}

void insertRightAdjust(RBNode* &pRoot, RBNode* ref) {
    RBNode* p = ref->parent->parent->left;

    if (p->color == true) {
        ref->parent->color = false;

        p->color = false;

        ref->parent->parent->color = true;

        ref = ref->parent->parent;
    } else {
        if (ref == ref->parent->left) {
            ref = ref->parent;

            rightRotate(pRoot, ref);
        }

        ref->parent->color = false;

        ref->parent->parent->color = true;

        leftRotate(pRoot, ref->parent->parent);
    }
}

void inserFixedUp(RBNode*  &pRoot, RBNode* ref) {
    while (ref->parent->color == true) {
        if (ref->parent == ref->parent->parent->left) {
            insertLeftAdjust(pRoot, ref);
        } else {
            insertRightAdjust(pRoot, ref);
        }
    }

    pRoot->color = false;
}

void BST_Insert(RBNode*& root, RBNode* x)
{
    RBNode* y = nil;
    RBNode* z = root;
    while(z != nil)
    {
        y = z;
        if(x->key < z->key)
            z = z->left;
        else if(x->key > z->key)
            z = z->right;
        else
            return;
    }
    x->parent = y;
    if(y == nil)
        root = x;
    else
    {
        if(x->key < y->key)
            y->left = x;
        else 
            y->right = x;
    }
}

void insert(RBNode*& root, int key)
{
    RBNode* x = getNode(key, true, nil);
    BST_Insert(root, x);
    inserFixedUp(root, x);
}

RBNode* createTree(int a[], int n) {
    RBNode* pRoot = nil;

    for (int i = 0; i < n; i++) {
        insert(pRoot, a[i]);
    }

    return pRoot;
}

RBNode* lookUp(RBNode* pRoot, int key) {
    RBNode* ans = pRoot;

    while (ans != nil) {
        if (ans->key == key) {
            return ans;
        }

        if (ans->key > key) {
            ans = ans->left;
        } else {
            ans = ans->right;
        }
    }

    return nil;
}

int blackHeight(RBNode* pRoot) {
    if (pRoot == nil) {
        return 1;
    }

    int leftBlackHeight = blackHeight(pRoot->left);
    int rightBlackHeight = blackHeight(pRoot->right);

    if (leftBlackHeight != rightBlackHeight) {
        return 0;
    }

    if (pRoot->color == false) {
        leftBlackHeight++;
    }

    return leftBlackHeight;
}


void removeLeftAdjust(RBNode* pRoot, RBNode* ref) {
    RBNode* p = ref->parent->right;

    if (p->color == true) {
        p->color = false;

        ref->parent->color = true;

        leftRotate(pRoot, ref->parent);

        p = ref->parent->right;
    }

    if (p->right->color == false && p->left->color == false) {
        p->color = true;

        ref = ref->parent;
    } else {
        if (p->right->color == false) {
            p->left->color = false;
            p->color = true;
            
            rightRotate(pRoot, p);
            p = ref->parent->right;
        }

        p->color = ref->parent->color;

        ref->parent->color = false;

        p->right->color = false;

        leftRotate(pRoot, ref->parent);

        ref = pRoot;
    }
}

void removeRightAdjust(RBNode* pRoot, RBNode* ref) {
    RBNode* p = ref->parent->left;

    if (p->color == true) {
        p->color = false;

        ref->parent->color = true;

        rightRotate(pRoot, ref->parent);

        p = ref->parent->left;
    }

    if (p->left->color == false && p->right->color == false) {
        p->color = true;

        ref = ref->parent;
    } else {
        if (p->left->color == false) {
            p->right->color = false;
            p->color = true;

            leftRotate(pRoot, p);
            p = ref->parent->left;
        }

        p->color = ref->parent->color;

        ref->parent->color = false;

        p->left->color = false;

        rightRotate(pRoot, ref->parent);

        ref = pRoot;
    }
}

void removeFixedUp(RBNode* pRoot, RBNode* ref) {
    while ((ref->color == false) && (ref != pRoot)) {
        if (ref == ref->parent->left) {
            removeLeftAdjust(pRoot, ref);
        } else {
            removeRightAdjust(pRoot, ref);
        }
    }

    ref->color = false;
}

RBNode* minimum(RBNode* pRoot, RBNode* ref) {
    while (ref->left != nil) {
        ref = ref->left;
    }

    return ref;
}

RBNode* maximum(RBNode* pRoot, RBNode* ref) {
    while (ref->right != nil) {
        ref = ref->right;
    }

    return ref;
}

RBNode* treeSuccessor(RBNode* pRoot, RBNode* ref) {
    if (ref->right != nil) {
        return minimum(pRoot, ref->right);
    }

    RBNode* y = ref->parent;

    while (y != nil && ref == y->right) {
        ref = y;
        y = y->parent;
    }

    return y;
}

//return 0 if key does not appear in tree, therefore cannot remove
//return 1 if successfully remove
int remove(RBNode* pRoot, int key) {
    RBNode* pFind = lookUp(pRoot, key);

    if (pFind == nil) {
        return 0;
    }

    RBNode* y;
    if (pFind->left == nil || pFind->right == nil) {
        y = pFind;
    } else {
        y = treeSuccessor(pRoot, pFind);
    }
    
    RBNode* x;
    if (y->left != nil) {
        x = y->left;
    } else {
        x = y->right;
    }

    if (x != nil) {
        x->parent = y->parent;
    }

    if (y->parent == nil) {
        pRoot = x;
    } else if (y == y->parent->left) {
        y->parent->left = x;
    } else {
        y->parent->right = x;
    }

    if (y != pFind) {
        pFind->key = y->key;
    }

    if (y->color == false) {
        removeFixedUp(pRoot, x);
    }

    delete y;
}


int main(){
    nil = new RBNode;
    nil->color = false;
    nil->left = nil->right = nil->parent = nil;
    RBNode* root = nil;

}

## Graph

Prim(G, root) {
    for (each vertex v in V) {
        v.dist = INF;
        v.parent = NIL;
    }
    root.dist = 0; VT = ∅;
    createQueue(Q, V);
    while (!isEmpty(Q)){
        v* = extractQueue(Q);
        add v* to VT;
        for (each v in Q that is adjacent to v*)
        if (G[v*][v] < v.dist) {
            v.dist = G[v*][v];
            v.parent = v*;
            updateQueue(Q, v);
        }
    }
}

void Prim(Graph g, int root)
{
    int len = g.getV();
    prim* lst = new prim[len];
    for(int i = 0 ; i < len ; ++i)
    {
        lst[i].priority = i + 1;
        lst[i].dist = INFINITY;
        lst[i].parent = nullptr;
    }
    lst[root].dist = 0;
    p_queue* Q = nullptr;
    createQueue(Q, lst, len);

    while(Q->len > 0)
    {
        prim v_star = Extract(Q,Q->len);

        // DUyet ma tran trong so de lay ra cac dinh ke cua v_star roi thuc hien nhu ma gia
    }
}

Dijkstra(G(V, E), source) {
    for (each vertex v ! V) {
    v.dist = ";
    v.parent = NIL;
    }
    source.dist = 0; VT = #;
    createQueue(Q, V);
    while (!isEmpty(Q)) {
        v* = extractQueue(Q);
        add v* to VT;
        for (each v ! Q that is adjacent to v*)
            if (v*.dist + G[v*][v] < v.dist) {
            v.parent = v*;
            v.dist = v*.dist + G[v*][v];
            updateQueue(Q, v);
            }
    }
}