Answer the question
In order to leave comments, you need to log in
How to implement red-black tree in C++?
Need help with red-black tree
How to bring these parts of the code into one, it is necessary that after each new element is entered, the maximum element of the tree and its color are displayed.
Here is the code.
#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);
}
Answer the question
In order to leave comments, you need to log in
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question