Как реализовать красно-черное дерево в С++?

Question

[Vic_ks]

Нужна помощь с красно-черным деревом
Как свести эти части кода в одно целое, нужно чтобы после ввода каждого нового элемента, выводился максимальный элемент дерева и его цвет.
Вот код.

#include <iostream.>
using namespace std;
 
struct node // структура для представления узлов дерева
{
    int key;
    unsigned char height;
    node* left;
    node* right;
    node(int k) { key = k; left = right = 0; height = 1; }
};
 
unsigned char height(node* p)
{
    return p ? p->height : 0;
}
 
int bfactor(node* p)
{
    return height(p->right) - height(p->left);
}
 
void fixheight(node* p)
{
    unsigned char hl = height(p->left);
    unsigned char hr = height(p->right);
    p->height = (hl>hr ? hl : hr) + 1;
}
 
node* rotateright(node* p) // правый поворот вокруг p
{
    node* q = p->left;
    p->left = q->right;
    q->right = p;
    fixheight(p);
    fixheight(q);
    return q;
}
 
node* rotateleft(node* q) // левый поворот вокруг q
{
    node* p = q->right;
    q->right = p->left;
    p->left = q;
    fixheight(q);
    fixheight(p);
    return p;
}
 
node* balance(node* p) // балансировка узла p
{
    fixheight(p);
    if (bfactor(p) == 2)
    {
        if (bfactor(p->right) < 0)
            p->right = rotateright(p->right);
        return rotateleft(p);
    }
    if (bfactor(p) == -2)
    {
        if (bfactor(p->left) > 0)
            p->left = rotateleft(p->left);
        return rotateright(p);
    }
    return p; // балансировка не нужна
}
 
node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
{
    if (!p) return new node(k);
    if (k<p->key)
        p->left = insert(p->left, k);
    else
        p->right = insert(p->right, k);
    return balance(p);
}

Заранее спасибо!

Comments

[krka92]

Можно где-то хранить ссылку на узел с максимальным ключом. При вставке значения больше чем сохраненное - менять. И по ссылке у уже отбалансированного узла получать цвет