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

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

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

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 17.05.2019, 23:07   #1
Константин01
Пользователь
 
Регистрация: 11.05.2019
Сообщений: 21
По умолчанию Реализация декартова дерева (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 вне форума Ответить с цитированием
Ответ


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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Реализация бинарного дерева на 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