Файл: отчёт_курсовая.docx

p->left = q->right;

q->right = p;

q->size = p->size;

fixsize(p);

return q;

}

RBS_Tree* rotateleft(RBS_Tree* q)

{

RBS_Tree* p = q->right;

if (!p) return q;

q->right = p->left;

p->left = q;

p->size = q->size;

fixsize(q);

return p;

}

RBS_Tree* insertroot(RBS_Tree* p, Newspaper& k)

{

if (!p) return new RBS_Tree(k);

if (k < p->key)

{

p->left = insertroot(p->left, k);

return rotateright(p);

}

else

{

p->right = insertroot(p->right, k);

return rotateleft(p);

}

}

RBS_Tree* join(RBS_Tree* p, RBS_Tree* q)

{

if (!p) return q;

if (!q) return p;

if (rand() % (p->size + q->size) < p->size)

{

p->right = join(p->right, q);

fixsize(p);

return p;

}

else

{

q->left = join(p, q->left);

fixsize(q);

return q;

}

}

RBS_Tree* remove(RBS_Tree* p, Newspaper& k)

{

if (!p) return p;

if (p->key == k)

{

RBS_Tree* q = join(p->left, p->right);

delete p;

return q;

}

else if (k < p->key)

p->left = remove(p->left, k);

else

p->right = remove(p->right, k);

return p;

}

}

Newspaper.h

#include <iostream>

using namespace std;

struct Newspaper {

string name{}; // Название газеты

int index{}; // Индекс издания

string editor{}; // ФИО редактора

int price{}; // Цена экземпляра газеты

bool operator>(Newspaper& np)

{

return name > np.name;

}

bool operator<(Newspaper& np)

{

return name < np.name;

}

bool operator==(Newspaper& np)

{

if (name == np.name && index == np.index && editor == np.editor && price == np.price)

return true;

return false;

}

bool operator>=(Newspaper& np)

{

return name >= np.name;

}

};

RBST.h

#pragma once

#include <iostream>

#include <string>

struct Newspaper {

std::string name{}; // Название газеты

int index{}; // Индекс издания

std::string editor{}; // ФИО редактора

int price{}; // Цена экземпляра газеты

bool operator>(Newspaper& np)

{

return name > np.name;

}

bool operator<(Newspaper& np)

{

return name < np.name;

}

bool operator==(Newspaper& np)

{

if (name == np.name && index == np.index && editor == np.editor && price == np.price)

return true;

return false;

}

bool operator>=(Newspaper& np)

{

return name >= np.name;

}

};

inline std::ostream& operator<<(std::ostream& out, Newspaper& np)

{

return out

<< "Newspaper name: " << np.name << '\n'

<< "Newspaper index: " << np.index << '\n'

<< "Newspaper editor: " << np.editor << '\n'

<< "Newspaper price: " << np.price << '\n';

---

}

inline std::istream& operator>>(std::istream& in, Newspaper& np)

{

std::getline(in >> std::ws, np.name);

in >> np.index;

std::getline(in >> std::ws, np.editor);

return in >> np.price;

}

struct RBS_Tree // структура дерева

{

Newspaper key;

int size;

RBS_Tree* left;

RBS_Tree* right;

RBS_Tree(Newspaper k) : key(k), left(0), right(0), size(1) {}

};

namespace RBST

{

RBS_Tree* find(RBS_Tree*, Newspaper&);

RBS_Tree* insert(RBS_Tree*, Newspaper&);

int getsize(RBS_Tree*);

RBS_Tree* insertroot(RBS_Tree*, Newspaper&);

RBS_Tree* join(RBS_Tree*, RBS_Tree*);

RBS_Tree* remove(RBS_Tree*, Newspaper&);

}

---

7. Заключение

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

8. Список использованной литературы

1. Кормен Т. и др. Алгоритмы. Построение и анализ : М. [и др.]: Вильямс, 2011.

2. Мейерс С. Эффективный и современный С++ : Вильямс, 2018

3. Седжвик Р., Моргунов А.А. Алгоритмы на C++. Анализ, структуры данных, сортировка, поиск, алгоритмы на графах: М.: Вильямс, 2011.

4. Бхаргава А. Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих : Питер, 2019

5. Прата С. Язык программирования С++. Лекции и упражнения : Диалектика, 201

---