Поиск в двоичном дереве: Красно-чёрное дерево.

#include "stdafx.h"
#include <deque> 
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
//Наша структура
struct node
{
    int info; //Информационное поле
    node *l, *r;//Левая и Правая часть дерева
};
 
node * tree=NULL; //Объявляем переменную, тип которой структура Дерево
 
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a,node **t)
{
    if ((*t)==NULL) //Если дерева не существует
    {
        (*t)=new node; //Выделяем память
        (*t)->info=a; //Кладем в выделенное место аргумент a
        (*t)->l=(*t)->r=NULL; //Очищаем память для следующего роста
        return; //Заложили семечко, выходим
    }
       //Дерево есть
        if (a>(*t)->info) push(a,&(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
        else push(a,&(*t)->l); //Иначе кладем его влево
}
 
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print (node *t) 
{
    if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим
    else //Иначе
    {
   
    std::cout<<t->info<<std::endl; //И показываем элемент
    print(t->l);
    print(t->r);
    }
        
}
 
void main ()
{   
    int n; //Количество элементов
    int s;//Число, передаваемое в дерево
    int v;// Высота
    int degree; // степень графа 
    cout<<"Type number of elements  ";
    cin>>n; //Вводим количество элементов
    if (n%2!=1) {
        v = n/2;
    }
    else { 
        v = n/2 -0,5;};
        cout<<"Height of the tree = ";
        cout<<v;
        cout<<"\n";
        degree = n-1;
        cout<<"Degree of the tree =  ";
        cout<<degree;
        cout<<"\n";
 
 
    for (int i=0;i<n;++i)
    {  
    cout<<"\nType number ";
    cin>>s; //Считываем элемент за элементом
   
    push(s,&tree); //И каждый кладем в дерево
    }
    cout<<"Your tree is:\n";
    print(tree);
   system("pause");      
}

#include <iostream>
 
enum COLOR {RED, BLACK};
 
struct node
{
    node(int const rhs) : data(rhs){}
    COLOR color = RED;
    int data;
    node* left = nullptr, *right = nullptr, *parent = nullptr;
};
 
// дерево
node* root = nullptr;
 
// поиск деда
node* grandparent(node* rhs)
{
    node* ret = nullptr;
    if (rhs && rhs->parent)
    {
        ret = rhs->parent->parent;
    }
    
    return ret;
}
 
// поиск дяди
node* uncle(node* rhs)
{
    node* ret = nullptr;
    if (node const* gp = grandparent(rhs))
    {
        ret = (gp->left == rhs->parent ? gp->right : gp->left);
    }
 
    return ret;
}
 
// левый поворот
void rotate_left(node* rhs)
{
    node* pivot = rhs->right;
 
    pivot->parent = rhs->parent; 
    if (rhs->parent != nullptr) 
    {
        if (rhs->parent->left == rhs)
        {
            rhs->parent->left = pivot;
        }
        else
        {
            rhs->parent->right = pivot;
        }   
    }
    else
    {
        root = pivot;
    }
 
    rhs->right = pivot->left;
    if (pivot->left != nullptr)
    {
        pivot->left->parent = rhs;
    }
    
    rhs->parent = pivot;
    pivot->left = rhs;
}
 
// правый поворот
void rotate_right(node* rhs)
{
    node* pivot = rhs->left;
 
    pivot->parent = rhs->parent; 
    if (rhs->parent != nullptr) 
    {
        if (rhs->parent->left == rhs)
        {
            rhs->parent->left = pivot;
        }
        else
        {
            rhs->parent->right = pivot;
        }
    }
    else
    {
        root = pivot;
    }
 
    rhs->left = pivot->right;
    if (pivot->right != nullptr)
    {
        pivot->right->parent = rhs;
    }
 
    rhs->parent = pivot;
    pivot->right = rhs;
}
 
 
void push_case1(node*);
void push_case2(node*);
void push_case3(node*);
void push_case4(node*);
void push_case5(node*);
 
// вставка
void push(node*& root, int const data)
{
    node** pcur = &root;
    node* parent = nullptr;
    while(*pcur)
    {
        parent = *pcur;
        if (data < (*pcur)->data)
        {
            pcur = &(*pcur)->left;
        }
        else if (data > (*pcur)->data)
        {
            pcur = &(*pcur)->right;
        }
        else
        {
            break;
        }
    }
    if (nullptr == *pcur)
    {
        *pcur = new node(data);
        (*pcur)->parent = parent;
 
        push_case1(*pcur);
    }
}
 
void push_case1(node* rhs)
{
    if (rhs->parent == nullptr)
    {
        rhs->color = BLACK;
    }
    else
    {
        push_case2(rhs);
    }
}
 
void push_case2(node *n)
{
    if (n->parent->color == BLACK)
    {
        return; /* Tree is still valid */
    }
    else
    {
        push_case3(n);
    }
}
 
void push_case3(node *n)
{
    node *u = uncle(n), *g = nullptr;
 
    if ((u != nullptr) && (u->color == RED))
    {
        // && (n->parent->color == RED) Второе условие проверяется в insert_case2, то есть родитель уже является красным.
        n->parent->color = BLACK;
        u->color = BLACK;
        g = grandparent(n);
        g->color = RED;
        push_case1(g);
    }
    else 
    {
        push_case4(n);
    }
}
 
void push_case4(node *n)
{
    node *g = grandparent(n);
 
    if ((n == n->parent->right) && (n->parent == g->left)) 
    {
        rotate_left(n->parent);
        n = n->left;
    }
    else if ((n == n->parent->left) && (n->parent == g->right)) 
    {
        rotate_right(n->parent);
        n = n->right;
    }
    push_case5(n);
}
 
void push_case5(node *n)
{
    node *g = grandparent(n);
 
    n->parent->color = BLACK;
    g->color = RED;
    if ((n == n->parent->left) && (n->parent == g->left)) 
    {
        rotate_right(g);
    }
    else 
    { /* (n == n->parent->right) && (n->parent == g->right) */
        rotate_left(g);
    }
}
 
// поиск
node* find(int const data)
{
    node* ret = root;
    while (ret)
    {
        if (data < ret->data)
        {
            ret = ret->left;
        }
        else if (data > ret->data)
        {
            ret = ret->right;
        }
        else
        {
            break;
        }
    }
 
    return ret;
}
 
 
 
// печать дерева
void print(node* root, int indent = 0)
{
    if (root)
    {
        print(root->right, indent + 1);
        for (int i = 0; i < indent; ++i)
        {
            std::cout << ".";
        }
        std::cout << root->data << std::endl; 
        print(root->left, indent + 1);
    }
}
 
 
int main()
{
    push(root, 5);
    push(root, 6);
    push(root, 7);
    push(root, 5);
 
    print(root);
 
    if (node* found = find(5))
    {
        std::cout << "\nfound: " << found->data << std::endl;
    }
    
}