Map на “красно черных” деревьях.

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

Перепрограммируйте Map из параграфа 13.9[8], используя более подходящие типы данных (например “красно черные” деревья.).

Да что ж это за “красно чорные” деревья? Первый раз слышу.

Для решения этой задачи нам понадобиться класс “красно черного” дерева. Посмотреть, что это такое вы можете по ссылке: http://www.kselax.ru/2013/04/krasno-chernoe-derevo/

Ну что ж господа как видите не получилось у меня создать “красно черное” дерево, так что будем делать на обычных деревьях ссылка: http://www.kselax.ru/2013/04/obychnoe-dvoichnoe-derevo/

Да токо посмотрел, чтобы сделать данную задачу на двоичном дереве, мне нужно все дерево переписать почти. Дерево ж ведь у меня содержит одно данное, а мне нужно добавить и число которое будет содержать второе. Нужно сделать так, чтобы в  узле дерева хранилось две единицы данных. ППц неохота.

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

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

Ну что же дорешал я кое как от сам код дерева файл Tree1.h:

//ob69vlenie dvoichnogo dereva
#ifndef TREE1_H
#define TREE1_H
#include <string>
using std::string;

struct TreeNode1
{
	int data;
	string val;
	TreeNode1 *leftPtr;
	TreeNode1 *rightPtr;
	//konctryktor preobrazovani9
	TreeNode1(int a,string s=""):data(a),val(s),leftPtr(0),rightPtr(0){};
};

class Tree1
{
	TreeNode1 *rootPtr;
	void insertNodeHelper(string&,TreeNode1 **ptr, const int &value);
	void outputTreeHelper(TreeNode1*, int);
	TreeNode1* searchListHelper(TreeNode1* ptr,string &value1)const;
	void deleteNodeHelper(TreeNode1**ptr, string &value);
public:
	//konctryktor po ymolchaniyu
	Tree1();
	
	//dobavlenie yzla
	void insertNode(string&, const int&);
	
	//vuvod na pechat6
	void outputTree();
	
	//poick elementa v dereve
	bool binaryTreeSearch(string& value1, int *&value);
	
	//ydalenie elementa
	void deleteNode(string &value);
	
	//vozvrachaet ykazatel6 na krainii levui element
	TreeNode1* zamHelper(TreeNode1*ptr);
};

#endif

Файл Tree1.cpp:

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

#include "Tree1.h"

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

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

//dobavit6 element v dvoichnoe derevo
void Tree1::insertNodeHelper(string& s, TreeNode1 **ptr, const int &value)
{
	//podderevo pycto; cozdat6 novui TreeNode, coderjawii value
	if(*ptr==0)
		*ptr=new TreeNode1(value, s);
	else //podderevo ne pycto
	{
		//vctavl9emue dannue men6we, chem dannue v tekywem yzle
		if(value<(*ptr)->data)
			insertNodeHelper(s,&((*ptr)->leftPtr),value);
		else
		{
			//vctavl9emue dannue bol6we, chem dannue v tekywem yzle
			if(value>(*ptr)->data)
				insertNodeHelper(s,&((*ptr)->rightPtr),value);
			else//dyblikatu znachenii dannux ignoriryyutc9
			{
				cout <<value<<" dup"<<endl;
				insertNodeHelper(s,&((*ptr)->rightPtr),value);//razrewaet dyblirovanie
			}
		}//kones else
	}//kones else
}

//vovod dvoichnogo dereva na pechat6
void Tree1::outputTree()
{
	outputTreeHelper(rootPtr,0);
}

//vuvod dereva
void Tree1::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->val<<' '<<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);
		}
	}
}

//poick elementa v dereve
bool Tree1::binaryTreeSearch(string& value1, int*& value)
{
	TreeNode1* ptr=searchListHelper(rootPtr, value1);
	if(ptr==0)
		return false;
		
	value=&ptr->data;
	return true;
}
//pick help fynkci9
TreeNode1* Tree1::searchListHelper(TreeNode1* ptr,string &value1)const
{
	TreeNode1* serch=0;
	if(ptr!=0)
	{
		if(ptr->val==value1)
		{
		//	cout <<"Nawli ptr->data= "<<ptr->data<<" ptr= "<<ptr<<endl;
			 serch=ptr;
		}
		else
		{
			if(serch==0)
				serch=searchListHelper(ptr->leftPtr,value1);
			if(serch==0)
				serch=searchListHelper(ptr->rightPtr,value1);
		}
		//cout <<"ptr= "<<ptr<<"value= "<<value<<"ptr->data= "<<ptr->data<<endl;
	}
	
	return serch;
}

//fynkci9 ydaleni9 elementa
void Tree1::deleteNode(string &value)
{
	if(rootPtr!=0)
	deleteNodeHelper(&rootPtr, value);//prinimaet ykazatel6 na ykazatel6
}
//vcpomogatel6na9 fynkci9 ydaleni9
void Tree1::deleteNodeHelper(TreeNode1**ptr, string &value)
{
	//poisk elementa dl9 ydaleni9
	//cout <<"ptr= "<<ptr<<" value= "<<value<<" ptr->data= "<<(*ptr)->data<<endl;
	//при разыменовании указателя на указатель мы получаем просто указатель(*) на который указывал указатель на указатель(**) ( просто получаем память адресс указателя собственный )
	if(ptr!=0)
	{
		if((*ptr)->val==value)
		{
			cout <<"ELEMENT NAIDEN (*ptr)->data= "<<(*ptr)->data<<endl;
			// net potomok
			if((*ptr)->leftPtr==0&&(*ptr)->rightPtr==0)
			{
				cout <<"Net potomkov"<<endl;
				TreeNode1* prom=*ptr;
				delete prom;//ydalenie lista
				//scout <<"ptr= "<<ptr<<" *ptr= "<<*ptr<<endl;
				*ptr=0;
			}
			//odin potomok
			else if(((*ptr)->leftPtr!=0&&(*ptr)->rightPtr==0)||
			    ((*ptr)->leftPtr==0&&(*ptr)->rightPtr!=0))
			{
				cout <<"Ect6 odin potomok "<<endl;
				cout <<"(*ptr)->data= "<<(*ptr)->data<<endl;
				TreeNode1* prom;
				if((*ptr)->leftPtr!=0)
					prom=(*ptr)->leftPtr;
				else
					prom=(*ptr)->rightPtr;
				cout <<"prom= "<<prom->data<<endl;
				delete *ptr;//osvobojdenie pam9ti na kotoryyu on ykazuvaet
				*ptr=prom;
			}
			//yzel imee dva potomka
			else if((*ptr)->leftPtr!=0&&(*ptr)->rightPtr!=0)
			{
				//naxodim men6wee makcimal6noe
				TreeNode1* zam;
				zam=zamHelper( (*ptr)->leftPtr );
				//element r9dom bez prava (rightPtr=0)
				cout <<"NAXODIM MEN6WEE MAKCIMAL6NOE ZNACHENIE"<<endl;
				if(zam->rightPtr!=0)
				{	
					if((zam->rightPtr)->leftPtr==0)
					{
						cout <<"ZAM NE IMEET POTOMKOV"<<endl;
						//ydal9em element
						cout <<(*ptr)->data<<' '<<zam->rightPtr->data<<endl;
						//ydal9ema9 oblact6
						TreeNode1* prom=*ptr;
						//zamen9em danue
						//obnovl9em vetki zamen9emogo elementa
						zam->rightPtr->rightPtr=(*ptr)->rightPtr;
						zam->rightPtr->leftPtr=(*ptr)->leftPtr;
						*ptr=zam->rightPtr;
						//obnyl9em ykazatel6 na poclednii element
						zam->rightPtr=0;
						delete prom;
					}
					else if((zam->rightPtr)->leftPtr!=0)
					{
						cout <<"ECT6 POTOMOK CPRAVA"<<endl;
						//1. coxran9em yk na yzel kotorui doljen but6 ydalen vo
						// vremennoi peremennoi
						TreeNode1* prom=*ptr;
						//2. yctanovit6 ykazatel6 v roditel6ckom po otnoweniyu k ydal9emomy
						*ptr=zam->rightPtr;
						//3. yctanovit6 ykazatel6 v roditel6ckom po otnoweniyu k 
						//zamechayuchemy, na levogo potomka zamechayuchego yzla
						zam->rightPtr=zam->rightPtr->leftPtr;
						cout <<zam->rightPtr->data<<endl;
						(*ptr)->leftPtr=prom->leftPtr;
						//4. yctanovit6 ykazatel6 na pravoe podderevo v zamechayuchem yzle na
						//pravoe podderevo ydal9emogo yzla
						(*ptr)->rightPtr=prom->rightPtr;
						//5. ydalit6 yzel na kotorui ykazuvaet vremennui ykazatel6
						delete prom;	
					}
				}
				else
				{
					cout <<"Srazy cleva"<<endl;
					cout <<"zam->data= "<<zam->data<<endl;
					//ydal9ema9 oblact6
					TreeNode1* prom=*ptr;
					//zamen9em dannue
					//obnovl9em vetki zamen9emogo elementa
					zam->rightPtr=(*ptr)->rightPtr;
					*ptr=zam;
					delete prom;
					
				}
				
			}//konec yzel imeet dva potomka
		}//konec poicka elementa
		else
		{
			if((*ptr)->leftPtr!=0)
				deleteNodeHelper(&((*ptr)->leftPtr),value);
			if((*ptr)->rightPtr!=0)
				deleteNodeHelper(&(*ptr)->rightPtr,value);
		}
		//cout <<"ptr= "<<ptr<<" ptr->data= "<<ptr->data<<endl;
	}
}
//vozvrachaet ykazatel6 na krainii levui element
TreeNode1* Tree1::zamHelper(TreeNode1*ptr)
{
	TreeNode1 *search=ptr;
	//cout <<"zPtr->data= "<<ptr->data<<endl;
	if(ptr->rightPtr!=0)
	{
		if((ptr->rightPtr)->rightPtr!=0)
		{
			cout <<"REK VUZOV"<<endl;	
			search=zamHelper(ptr->rightPtr);
		}
	}
	
	return search;
}

И файл main.cpp:

//Map na dvoichnom dereve
#include <iostream>
using std::cout;
using std::endl;
#include <cstdlib>
using std::exit;
#include <string>
using std::string;

#include "Tree1.cpp"

class Map
{
	Tree1* d;//ykazatel6 na derevo
public:
	//konctryktor po ymolchaniyu
	Map(){d=new Tree1;}
	//
	int& operator[](string i)
	{
		//d->outputTree();
		int val=5;
		int* v=&val;
		//cout <<"i= "<<i<<endl;exit(1);
		if(!d->binaryTreeSearch(i,v))
		{
			d->insertNode(i,val);
			if(d->binaryTreeSearch(i,v))
			{
				//cout <<"mu tyt"<<endl;exit(1);
				return *v;
			}
		}
		else
			return *v;
	}
};

int main()
{
	Map m;
	m["hellow"]=4;//m.operator["hellow"]
	cout <<"m[hellow]= "<<m["hellow"]<<endl;
	m["hellow"]=7;
	cout <<"m[hellow]= "<<m["hellow"]<<endl;
	m["print"]=15;
	cout <<m["print"]<<endl;	
	
	return 0;
}

Как видно я создал все без шаблонов и всего навсего один оператор взятие индекса перегрузил, я думаю достаточно неохота на всяком гамне распылятся.

[youtube]http://www.youtube.com/watch?v=zBuYnveRJ1A#![/youtube]

rss