“Красно черное” дерево.

Рубрика: C++, Дата: 7 April, 2013, Автор:
Tags:

Здорова господа! Сейчас мы с вами поговорим о такой фигне как “красно черное” дерево. Посмотрите видео: [youtube]http://www.youtube.com/watch?v=vDHFF4wjWYU[/youtube]

“Красно черное” дерево это дерево представленное на видео. Как видно оно так красиво и равномерно как то заполняется. Да помучился я с этим деревом. Честно признаюсь не понял алгоритм как оно строится. Там какой то запутанный алгоритм, в википедии прочитал и взял оттуда код, я под видео сделал но не доделал, лень как то стало. Гамно программа. Да и подумать хорошенько ну она я думаю мне не пригодиться так просто сделать ну либо делать ее это много времени забирает, сложная вообщем задачка. Кину я код который у меня получился он хоть на половину рабочий.

Файл RedTree1.h:

//ob69vlenie dvoichnogo dereva
#ifndef REDTREE1_H
#define REDTREE1_H
#include "string"
using std::string;

struct TreeNode1
{
	int data;
	string color;
	TreeNode1 *leftPtr;
	TreeNode1 *rightPtr;
	TreeNode1 *parentPtr;//ykazuvaet na roditel6ckii yzel
	//konctryktor preobrazovani9
	TreeNode1(int a, TreeNode1* b=0)
	:data(a),leftPtr(0),rightPtr(0),parentPtr(b),color("R"){};
};

class RedTree1
{
	TreeNode1 *rootPtr;
	void insertNodeHelper(TreeNode1 **ptr, const int &value, TreeNode1* p);
	void outputTreeHelper(TreeNode1*, int);
	//dedywka
	TreeNode1* grandparent(TreeNode1 *n);
	//d9d9
	TreeNode1* uncle(TreeNode1 *n);

	//clychai
	//ecli koren6
	void insert_case1(TreeNode1 *n);
	//ecli predok chornui
	void insert_case2(TreeNode1 *n);
	//ecli roditel6 i d9d9 kracnue to oni mogyt but6 perekrawenu v chornui
	void insert_case3(TreeNode1 *n);
	//ecli roditel6 kracnui no d9d9 chornui
	void insert_case4(TreeNode1 *n);
	void insert_case5(TreeNode1 *n);
	void rotate_right(TreeNode1* g);
	void rotate_left(TreeNode1* g);
public:
	//konctryktor po ymolchaniyu
	RedTree1();

	//dobavlenie yzla
	void insertNode(const int&);

	//vuvod na pechat6
	void outputTree();
};

#endif

Файл RedTree1.cpp:

//opredelenie klacca RedTree1
#include <cstdlib>
using std::exit;

#include "RedTree1.h"

//konctryktor po ymolchaniyu
RedTree1::RedTree1()
{
	rootPtr=0;
}

//dobavlenie yzla
void RedTree1::insertNode(const int& value)
{
	insertNodeHelper(&rootPtr,value,rootPtr);
}

//dobavit6 element v dvoichnoe derevo
void RedTree1::insertNodeHelper(TreeNode1 **ptr, const int &value, TreeNode1* p)
{
	//ecli derevo pyctoe
	if(*ptr==0)
	{
		//cout <<rootPtr<<' '<<*ptr<<endl;//exit(1);
		//cout <<"derevo pyctoe dobavl9em koren6"<<endl;
		*ptr=new TreeNode1(value,p);

		//exit(1);
		insert_case1(*ptr);
		//cout <<"mu v tekywem ne kornevom yzle"<<endl;exit(1);
	}
	else //podderevo ne pycto
	{
		//vctavl9emue dannue men6we, chem dannue v tekywem yzle
		if(value<(*ptr)->data)
			insertNodeHelper(&((*ptr)->leftPtr),value,*ptr);
		else
		{
			//vctavl9emue dannue bol6we, chem dannue v tekywem yzle
			if(value>(*ptr)->data)
				insertNodeHelper(&((*ptr)->rightPtr),value,*ptr);
			else//dyblikatu znachenii dannux ignoriryyutc9
			{
				cout <<value<<" dup"<<endl;
				//insertNodeHelper(&((*ptr)->rightPtr),value);//razrewaet dyblirovanie
			}
		}//kones else
	}//kones else
}

//naxojdenie naxojdenie dedywki i d9di
TreeNode1* RedTree1::grandparent(TreeNode1 *n)
{
        if ((n != NULL) && (n->parentPtr != NULL))
                return n->parentPtr->parentPtr;
        else
                return NULL;
}

TreeNode1* RedTree1::uncle(TreeNode1 *n)
{
        TreeNode1 *g = grandparent(n);
        if (g == NULL)
                return NULL; // No grandparent means no uncle
        if (n->parentPtr == g->leftPtr)
                return g->rightPtr;
        else
                return g->leftPtr;
}
//clychai
//ecli koren6
void RedTree1::insert_case1(TreeNode1 *n)
{
        if (n->parentPtr == NULL)
                n->color = "B";
        else
                insert_case2(n);
}
//ecli predok chornui
void RedTree1::insert_case2(TreeNode1 *n)
{
        if (n->parentPtr->color == "B")
                return; /* Tree is still valid */
        else
                insert_case3(n);
                //cout <<"Tretii clychai"<<endl;
}
//ecli roditel6 i d9d9 kracnue to oni mogyt but6 perekrawenu v chornui
void RedTree1::insert_case3(TreeNode1 *n)
{
        TreeNode1 *u = uncle(n), *g;

        if ((u != NULL) && (u->color == "R") && (n->parentPtr->color == "R")) {
                n->parentPtr->color = "B";
                u->color = "B";
                g = grandparent(n);
                g->color = "R";
                insert_case1(g);
        } else {
                insert_case4(n);
                //cout <<"insert_case4(n)"<<endl;
        }
}
//ecli roditel6 kracnui, no d9d9 chornui
void RedTree1::insert_case4(TreeNode1 *n)
{
        TreeNode1 *g = grandparent(n);

        if ((n == n->parentPtr->rightPtr) && (n->parentPtr == g->leftPtr)) {
                rotate_left(n->parentPtr);
               // cout <<"rotate_left(n->parentPtr)"<<endl;
                n = n->leftPtr;
        } else if ((n == n->parentPtr->leftPtr) && (n->parentPtr == g->rightPtr)) {
                rotate_right(n->parentPtr);
               // cout <<"rotate_right(n->parentPtr)"<<endl;
                n = n->rightPtr;
               // cout <<n->data<<' '<<n->parentPtr->data<<endl;exit(1);
        }
        insert_case5(n);
        //cout <<"insert_case5(n)"<<endl;
}

void RedTree1::insert_case5(TreeNode1 *n)
{
        TreeNode1 *g = grandparent(n);

        n->parentPtr->color = "B";
        g->color = "R";
        //exit(1);
        if ((n == n->parentPtr->leftPtr) && (n->parentPtr == g->leftPtr)) {
                rotate_right(g);
               // cout <<"1rotate_right(g)"<<endl;
        } else { /* (n == n->parent->right) and (n->parent == g->right) */
                rotate_left(g);
                //cout <<"2rotate_left(g)"<<endl;
        }
        cout <<"konec"<<endl;
}

//povorot dereva
void RedTree1::rotate_right(TreeNode1* p)//roditel6
{

	//koren6 dereva
	if(p->parentPtr==0)
	{
		cout <<"mu v kornevom yzle dodelai"<<endl;
		if(p->leftPtr==0||p->rightPtr==0)
		{
			cout <<"odin potomok"<<endl;
		}
		else if(p->leftPtr!=0&&p->rightPtr!=0)
		{
			cout <<"dva potomka"<<endl;
		}
		//xz mb i ne nyjno
		exit(1);
	}
	//ne koren6
	else if(p->parentPtr!=0)
	{
		//odin potomok
		if(p->leftPtr==0||p->rightPtr==0)
		{
			//cout <<p->leftPtr->data<<endl;
			//if(p->data==60)exit(1);
			p->leftPtr->parentPtr=p->parentPtr;//Np=Gp;
			p->parentPtr->rightPtr=p->leftPtr;//Gr=N;

			p->leftPtr->rightPtr=p;//Nr=P;
			p->parentPtr=p->leftPtr;//Pp=Pl;
			p->leftPtr=0;//Pl=0;
			//cout <<p->parentPtr->data<<endl;

			//if(p->data==60)exit(1);

		}
		//dva potomka
		else if(p->leftPtr!=0&&p->rightPtr!=0)
		{
			outputTree();cout <<endl<<endl;
			cout <<" sdfsdfsa dva potomka"<<endl;
			cout <<p->data<<' '<<p->leftPtr->data<<' '<<p->rightPtr->data<<endl;
			p->leftPtr->parentPtr=p->parentPtr;//Np=Gp; 30.parentPtr(15)
			p->leftPtr->rightPtr->parentPtr=p;// 60.parentPtr(70)
			p->parentPtr->rightPtr=p->leftPtr;//Gr=N; 15.rightPtr(30)

			TreeNode1* Nr=p->leftPtr->rightPtr;//prava9 vetka N
			p->leftPtr->rightPtr=p;// 30.rightPtr(70)
			p->parentPtr=p->leftPtr;//
			p->leftPtr=Nr;
			cout <<p->parentPtr->data<<endl;
			//insert_case1(p->parentPtr->parentPtr);
			outputTree();
			//cout <<p->leftPtr->leftPtr->parentPtr->data<<endl;exit(1);

			/*//p->leftPtr->rightPtr
			p->leftPtr->rightPtr=p;//Nr=P;
			p->parentPtr=p->leftPtr;//Pp=Pl;
			//p->leftPtr=0;//Pl=0;
			p->leftPtr=p->leftPtr->leftPtr;//Pl=Nl*/
		}
	}	
}
//povorot dereva cleva
void RedTree1::rotate_left(TreeNode1* g)
{

	cout <<"rotate_left "<<g->data<<endl;
	//kornevoi yzel
	if(g->parentPtr==0)
	{
		cout <<"koren6"<<endl;
		//odin potomok
		if(g->leftPtr==0||g->rightPtr==0)
		{
			rootPtr=g->rightPtr;

			g->rightPtr->parentPtr=g->parentPtr;//Pp=Gg
			g->parentPtr=g->rightPtr;//Gp=Gr

			g->rightPtr->leftPtr=g;
			g->rightPtr=0;
		}
		//dva potomka
		else if(g->leftPtr!=0&&g->rightPtr!=0)
		{
			cout <<"kdsafj;alskjdfl;as "<<endl;
			outputTree();cout <<endl<<endl;
			rootPtr=g->rightPtr;//koren6 klacca

			g->parentPtr=g->rightPtr;//15.parentPtr(30)
			if(g->rightPtr->leftPtr!=0)
				g->rightPtr->leftPtr->parentPtr=g;//20.parentPtr(15)
			g->rightPtr->parentPtr=0;//koren6 zla
			TreeNode1* temp=g->rightPtr->leftPtr;
			g->rightPtr->leftPtr=g;//30.leftPtr(15)
			g->rightPtr=temp;//15.rightPtr(20)
			outputTree();

			//if(g->data==15)exit(1);
		}
	}
	//obuchnui yzel
	else //ecli ne G ne koren6
	{
		cout <<"ne koren6"<<endl;
		//odin potomok
		if(g->rightPtr==0||g->leftPtr==0)
		{
			outputTree();
			//ecli yzel cprava, to mu cprava (kyda ykazuvaet roditel6)
			if(g->parentPtr==g->parentPtr->rightPtr)
			{
				g->parentPtr->rightPtr=g->leftPtr;
			}
			else //levui potomok roditel6ckogo yzla
			{
				g->parentPtr->leftPtr=g->rightPtr;

		//exit(1);
				g->rightPtr->parentPtr=g->parentPtr;//Pp=Gg
				g->parentPtr=g->rightPtr;//Gp=Gr
				//ok

				g->rightPtr->leftPtr=g;
				g->rightPtr=0;
				g->parentPtr->rightPtr->parentPtr=g->parentPtr;
				//exit(1);
			}
		}
		//dva potomka
		else if(g->rightPtr!=0||g->leftPtr!=0)
		{
			cout <<"left dva potomka"<<endl;
			//mb bydet clychai xz. kod nyjno
			exit(1);
		}		
	}	
}

//vovod dvoichnogo dereva na pechat6
void RedTree1::outputTree()
{
	outputTreeHelper(rootPtr,0);
}
//vuvod dereva
void RedTree1::outputTreeHelper(TreeNode1*ptr, int totalSpaces) 
{
	//cout <<ptr->data<<' '<<totalSpaces<<endl;
	// poka ykazatel6 na tekychii yzel ne nylevoi
	if(ptr!=0)
	{
		if(ptr->rightPtr!=0)
		{
			// rekyrcivno vuzvat6 fynkciyu c pravum poddrerevom tekywego yzla
			// i totalSpacec+5

				outputTreeHelper(ptr->rightPtr,totalSpaces+5);
		}
		//vocpol6zovatc9 operatorom for dl9 vuvoda probelov
		for(int i=0;i<totalSpaces;i++)
			cout <<' ';
		//vuvecti znachenie v tekywem yzle
		cout <<ptr->color<<'|'<<ptr->data<<endl;

		//yctanovit6 ykazatel6 tekywego yzla na levoe podderevo tekychego yzla
		//yctanovit6 znachenie totalSpaces na 5
		if(ptr->leftPtr!=0)
		{
			outputTreeHelper(ptr->leftPtr,totalSpaces+5);
		}
	}
}

И файл test1.cpp:

//dvoichnoe derevo
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::rand;
using std::srand;
using std::exit;
#include <ctime>
using std::time;

#include "RedTree1.cpp"

int main()
{
	RedTree1 d;

	//zapoln9em derevo
	srand(time(0));
	/*for(int i=0;i<10;i++)
	{
		d.insertNode(1+rand()%50);
	}*/

	d.insertNode(10);
	d.insertNode(85);
	d.insertNode(15);
	d.insertNode(70);
	d.insertNode(20);
	d.insertNode(60);
	cout <<"30"<<endl;
	d.insertNode(30);
	cout <<"50"<<endl;
	d.insertNode(50);
	d.insertNode(65);
	d.insertNode(80);
	d.insertNode(90);
	d.insertNode(40);
	d.insertNode(5);
	d.insertNode(55);

	cout <<endl<<endl;
	d.outputTree();

	return 0;
}

Как видно из этого кода можно конечно построить, но у меня сил не хватило, да и безсмыслено это все я просто посмотрел времени много уходит на постройку этого дерева. Обычное двоичное и то много забирает, а это еще больше. Короче плюнул на все. Ну что касается кода, то фунция поворот влево ошибку бывает выбрасывает, где то чо то не то с указателями. Да вы сами когда запустите увидите.

Ну что еще сказать? Добавлю наверно алгоритм по которому строится дерево.

Свойство дерева:

  1. Узел либо красный, либо чёрный.
  2. Корень — чёрный. (В других определениях это правило иногда опускается. Это правило слабо влияет на анализ, так как корень всегда может быть изменен с красного на чёрный, но не обязательно наоборот).
  3. Все листья(NIL) — черные.
  4. Оба потомка каждого красного узла — черные.
  5. Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число черных узлов.

Да хотел было я создать статью по этому дереву да понял, что это информация специфическая поэтому не стал заморачиваться. 🙂 . Мб кода не будь и доделаю если понадобиться.

[youtube]http://www.youtube.com/watch?v=mD-h2lLby84[/youtube]

rss