Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

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

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


Присылайте нам Донат :), напишите за что прислали )


Ответ
 
Опции темы
Старый 18.05.2019, 00:07   #1
Константин01
 
Регистрация: 11.05.2019
Сообщений: 7
Репутация: 10
По умолчанию Реализация декартова дерева (treap)

Здравствуйте, изучаю C++, написал реализацию декартова дерева, но код не работает (сложно сказать в чем именно ошибка). Прошу проверить и указать в чем причина неправильной работы.

Код:

#include <iostream>
#include <cstdlib>

using namespace std;

class Treap
{
public:

	int x, y;
	Treap *left;
	Treap *right;

	Treap()
	{
		left = NULL;
		right = NULL;
	}
};


struct TreapPair
{
	Treap *T1;
	Treap *T2; 
};


Treap* merge(Treap *L, Treap *R)
{
	if (L == NULL)
	{
		return R;
	}
	if (R == NULL)
	{
		return L;
	}
	else if (L->y > R->y)
	{
		L->right = merge(L->right, R);
		return L;
	}
	else
	{
		R->left = merge(L, R->left);
		return R;
	}
} 


TreapPair* split(Treap *T, int x)
{
	TreapPair *TP = new TreapPair;

	if (T == NULL)
	{
		TP->T1 = NULL;
    TP->T2 = NULL;
		return TP;
	}
	else
	{
		if (x > T->x)
		{
			TP = split(T->right, x);
			T->right = TP->T1;
			return TP;
		}
		else
		{
			TP = split(T->left, x);
			T->left = TP->T2;
			return TP;
		}
	}
}

Treap* newTreap(int x)
{
	Treap* temp = new Treap;
	temp->x = x;
	temp->y = rand()%100;
	temp->left = temp->right = NULL;
	return temp;
}

Treap* insert(Treap *T, int x)
{
	TreapPair* TP = new TreapPair;

	if (T == NULL)
	{
		T = newTreap(x);
	}
	else
	{
		Treap *new_T = newTreap(x);
		TP = split(T, x);
		TP->T1 = merge(TP->T1, new_T);
		T = merge(TP->T1, TP->T2);
		return T; 
	}
}

bool find(Treap *T, int x)
{
	if (T->x == x)
	{
		return true;
	}
	if (T == NULL)
	{
		return false;
	}
	else
	{
		if (T->x > x)
		{
			return find(T->left, x);
		}
		else
		{
			return find(T->right, x);
		}
	}
}

int main()
{
	Treap T;
	return 0;
}

Константин01 вне форума   Ответить с цитированием
Ответ

Опции темы

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Реализация бинарного дерева на C# NastyaShuvalova C# (си шарп) 0 25.02.2014 19:24
Реализация дерева +XML mdekalka Общие вопросы .NET 0 30.11.2012 02:04
Реализация дерева на HTML mimm HTML и CSS 3 19.10.2012 08:52
Реализация Б-дерева VB Army Помощь студентам 3 19.06.2011 14:47


06:09.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.

RusProfile.ru


Справочник российских юридических лиц и организаций.
Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru