Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 15.05.2011, 21:35   #1
CodeNOT
Форумчанин
 
Аватар для CodeNOT
 
Регистрация: 08.11.2010
Сообщений: 593
По умолчанию Красно-черное дерево

Добрый день, я не понимаю как происходит балансировка при вставке элемента в красно-черном дереве, условие балансировки я знаю: не могут идти подряд два красных узла. Пробовал алгоритм из авл дерева. но хмхм, не получилось
вот исходник
Код:

void InsertRoot(Tree &Root,int key,bool &InsertFlag)
{
        Tree rb1;
        if(Root==NULL)
        {
               Tree Element=new RB_Tree;
               Element->Left=NULL;
               Element->Right=NULL;
               Element->Data=key;
               Element->Color="RED";
               Root=Element;
               InsertFlag=true; //Ôëàã îçíà÷àåò ÷òî ýëåìåíò áûë âñòàâëåí
               cout<<"\n Ýëåìåíò äîáàâëåí ";
        }else
        {
                if(Root->Data < key)
                {
                        InsertRoot(Root->Right,key,InsertFlag);
                                if(InsertFlag)
                                {
                                        if(Root->Color=="RED")
                                        {
                                                Root->Color="BLACK";
                                        }else
                                                {
                                                        rb1=Root->Left;
                                                        if(rb1!=NULL)
                                                        {
                                                        if(rb1->Left=="RED")
                                                        {
                                                                Root->Right=rb1->Left;
                                                                rb1=Root;
                                                                Root=rb1->Right;
                                                        }
                                                        }
                                                }
                                }
                }
        }
}
в чем я "дебил"?
CodeNOT вне форума Ответить с цитированием
Старый 15.05.2011, 22:03   #2
CodeNOT
Форумчанин
 
Аватар для CodeNOT
 
Регистрация: 08.11.2010
Сообщений: 593
По умолчанию

попробовал переназначить цвета, но все равно не то получается. как именно поворотами?
вот исходник:
Код:

void InsertRoot(Tree &Root,int key)
{
        if(Root==NULL)
        {
                Tree Element=new RBTree;
                Element->Left=NULL;
                Element->Right=NULL;
                Element->Data=key;
                Element->color=1;//1=red color 0=black color
                Root=Element;
                cout<<"\n Element ADD ";
        }else
        {
                if(Root->Data < key)
                {
                        InsertRoot(Root->Right,key);
                }
                if(Root->Data > key)
                {
                        InsertRoot(Root->Left,key);
                }
                if(Root->Data == key)
                {
                        cout<<"\n Element THERE ";
                }
        }
}
void Colors(Tree &Root)
{
if(Root!=NULL)
{
        if(Root->Left!=NULL && Root->Right!=NULL)
        {
          if(Root->Left->color==1)
          {
                Root->color=0;
          }
          if(Root->Right->color==1)
          {
                Root->color=0;
          }
        }
        Colors(Root->Right);
        Colors(Root->Left);
}
CodeNOT вне форума Ответить с цитированием
Старый 16.05.2011, 11:19   #3
rustx88
Пользователь
 
Регистрация: 08.05.2011
Сообщений: 42
По умолчанию

на википедии есть готовая реализация красно-черного дерева, изучай исходники
rustx88 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Красно-черное дерево(RB-Tree) Mixim Общие вопросы C/C++ 1 26.12.2010 16:58
Красно-черные деревья Lullu Помощь студентам 0 25.04.2010 14:53
дерево С# Natok Помощь студентам 0 14.09.2009 23:42
Помогите с решением задачи или объясните, Красно-чёрные деревья тема Kambyz Паскаль, Turbo Pascal, PascalABC.NET 3 22.12.2008 16:08