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

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

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 27.04.2012, 17:37   #1
Даsha
 
Регистрация: 20.02.2011
Сообщений: 9
По умолчанию красно-черные деревья

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


Код:
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <iostream.h>
#include <string.h>
#include <stdarg.h>

typedef int nodeColor;
struct Node{
	Node *left;
	Node *right;
	Node *parent;
	nodeColor color;
	int data;
	};
struct tree{
		struct Node *root;
	};
Node sentinel;
Node* NIL = &sentinel;
Node *root = NIL;

void Make_RBTree(struct Node*,int);
void Insert_Node(struct Node*,int);
void Insert_Fixup(struct Node,Node *);
void Rotate_Left(struct Node*,Node *);
void Rotate_Right(struct Node*,Node *);
void Printf_Node(struct Node*, int);


void main(void)
{
	int n;
	Make_RBTree(root,n);

}
void Make_RBTree(struct Node* root,int n)
{
	int data;
	while (n>0)
	{
		cout <<"Vvedite znachenie";
		cin >>data;
		Insert_Node(root,data);
		n--;
	}
}

void Insert_Node(struct Node* root,int data)
{
	Node **current, *parent, *new_node;
	current=root;
	parent=NIL;
	while(*current!=NIL);
	{
		parent=(*current);
		current=data < (*current)->data ? &((*current)->left) : &((*current)->right);
	}
	new_node=new Node();
	new_node->data=data;
	new_node->parent=parent;
	new_node->left=NIL;
	new_node->right=NIL;
	new_node->color=RED;
	if(parent!=NIL)
	{
		if(data<parent->data)
			parent->left=new_node;
		else
			parent->right=new_node;
	}
	else (*current)=new_node;
	Insert_Fixup(*root,new_node);
}

void Insert_Fixup(struct Node* root,Node* new_node)
{
	Node* current=new_node;
	while(current!= root && current->parent->color==RED)
	{
		if(current->parent==current->parent->parent->left)
		{
			Node *ptr=current->parent->parent->right;
			if(ptr->color==RED)
			{
				current->parent->color=BLACK;
				ptr->color=BLACK;
				current->parent->parent->color=RED;
				current=current->parent->parent;
			}
			else
			{
				if(current==current->parent->right)
				{
					current=current->parent;
					Rotate_Left(root,current);
				}
				current->parent->color=BLACK;
				current->parent->parent->color=RED;
				Rotate_Right(root,current->parent->parent);
			}
		}
		else
		{
			Node *ptr=current->parent->parent->left;
			if(ptr->color==RED)
			{
				current->parent->color=BLACK;
				ptr->color=BLACK;
				current->parent->parent->color=RED;
				current=current->parent->parent;
			{
			else
			{
				if(current==current->parent->left)
				{
					current=current->parent;
					Rotate_Right(root,current);
				}
				current->parent->color=BLACK;
				current->parent->parent->color=RED;
				Rotate_Left(root,Current->parent->parent);
			}
		}
	}
	root->color=BLACK;
}

void Rotate_Left(struct Node* root,Node *current)
{
	Node *ptr=current->right;
	current->right=ptr->left;
	if(ptr->left!=NIL)
		ptr->left->parent=current;
	if(ptr!=NIL)
		ptr->parent=current->parent;
	if(current->parent!=NIL)
	{
		if(current==current->parent->left)
			current->parent->left=ptr;
		else
			current->parent->right=ptr;
	}
	else
	{
		(*root)=ptr;
	}
	ptr->left=current;
	if(current!=NIL)
		current->parent=ptr;
}

void Rotate_Right(struct Node* root,Node *current)
{
	Node *ptr=current->left;
	current->left=ptr->right;
	if(ptr->right!=NIL)
		ptr->right->parent=current;
	if(ptr!=NIL)
		ptr->parent=current->parent;
	if(current->parent!=NIL)
	{
		if(current==current->parent->right)
			current->parent->right=ptr;
		else
			current->parent->left=ptr;
	}
	else
	{
		(*root)=ptr;
	}
	ptr->right=current;
	if(current!=NIL)
		current->parent=ptr;
}

void Print_Node(struct Node* root, int l)
{
	int i;
	if(root!=NIL)
	{
		Printf_Node(Node->right,l+1);
		for(i=0;i<l,i++)
		count <<  "     ";
		if(root_>color==RED)
			SetConcoleTextAttribute(hStd,FOREGROUND_RED);
		cprintf("%4ld",root->data);
		SetConsoleTextAttribute(hStd,atr);
		Print_Node(Node->left,l+1);
	}
	else
		cout << endl;
}
Даsha вне форума Ответить с цитированием
Ответ


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



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