Определение критерия сбалансированности для всех узлов дерева




Цели работы

Освоение технологии реализации ассоциативных нелинейных коллекций на примере АТД «Двоичное дерево поиска».

 

Задание

Спроектировать, реализовать и протестировать АТД «BST -дерево» для коллекции, содержащей данные произвольного типа. Тип коллекции задаётся клиентской программой.

Двоичное дерево поиска (Binary Search Tree – BST) представляет упорядоченное, иерархическое, ассоциативное множество элементов, между которыми существуют структурные отношения «предки – потомки».

Интерфейс АТД «BST -дерево» включает следующие операции:

● опрос размера дерева (количества узлов),

● очистка дерева (удаление всех узлов),

● проверка дерева на пустоту,

● поиск данных с заданным ключом,

● включение в дерево нового узла с заданным ключом и данными,

● удаление из дерева узла с заданным ключом,

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

● дополнительная операция, заданная в варианте задания.

Для тестирования коллекции интерфейс АТД «BST – дерево» включает дополнительные операции:

● вывод структуры дерева на экран.

 

Алгоритмы основных операций АТД (вставки, удаления и поиска) реализуются в рекурсивной форме.

Схема операции обхода: L t → t→ R t .

Дополнительная операция: определение критерия сбалансированности для всех узлов дерева (критерий сбалансированности узла = высота правого поддерева – высота левого поддерева).

 


Описание АТД «Дерево»

Разработанный абстрактный тип данных представляет собой ассоциативную структуру, в которой каждый экземпляр данных хранится в связке с ключом — уникальным идентификатором этих данных, встречающийся в списке единожды.

Доступ к данным осуществляется по значению ключа.

Данные:

Параметры:

Структура данных:

Бинарное дерево

Операции:

 

Конструктор

Вход: нет

Предусловия: нет

Процесс: создание пустой коллекции

Выход: нет

Постусловия: создана коллекция с пустой вершиной

 

Деструктор

Вход: нет

Предусловия: нет

Процесс: удаление коллекции

Выход: нет

Постусловия: коллекция удалена

 

Получение размера коллекции

Вход: нет

Предусловия: нет

Процесс: обход дерева с подсчетом

Выход: текущий размер коллекции s

Постусловия: нет

 

Очистка коллекции

Вход: нет

Предусловия: нет

Процесс: удаление всех значений коллекции

Выход: нет

Постусловия: коллекция пуста

 

Проверка коллекции на пустоту

Вход: нет

Предусловия: нет

Процесс: проверка размера дерева на пустоту

Выход: возврат булевского значения

Постусловия: нет

 

Вставка значения в коллекцию

Вход: ключ T и значение V

Предусловия: ключ T не встречается в дереве

Процесс: вставка узла с ключом T и значением V в коллекцию

Выход: false, если элемент не был вставлен, true, если элемент был вставлен

Постусловия: в коллекцию добавлено значение V с ключом T

 

Получение доступа к элементу

Вход: ключ элемента T

Предусловия: нет

Процесс: рекурсивный поиск элемента с ключом T

Выход: получение элемента с ключом T или возврат NULL

Постусловия: нет

 

Удаление значения

Вход: узел remove_node, булевская переменная-признак успешного удаления

Предусловия: коллекция содержит узел remove_node

Процесс: удаление узла remove_node

Выход:true, если узел был удален, false, если узел не был удален

Постусловия: из коллекции удалён узел remove_node

 

Вывод коллекции на экран

Вход: служебная переменная сдвига, необходимая для вывода структуры дерева на экран

Предусловия: нет

Процесс: вывод коллекции на экран

Выход: нет

Постусловия: коллекция выведена на экран

 

Демонстрация порядка обхода L-T-R

Вход: нет

Предусловия: нет

Процесс: обход элементов коллекции в порядке l-t-r

Выход: нет

Постусловия: ключи коллекции выведены на экран в порядке l-t-r

 

Определение критерия сбалансированности для всех узлов дерева

Вход: узел root

Предусловия: коллекция содержит узел root

Процесс: разность максимальной и минимальный глубины <= 1

Выход: возврат булевово значения – признак сбалансированности

Постусловия: нет


Поиск для заданного ключа предыдущего по значению ключа в дереве

Вход: ключ k

Предусловия: нет

Процесс: поиск предущего по значению ключа в дереве для заданного ключа

Выход: возврат указателя на элемент или NULL

Постусловия: нет

 

4.Клиентское описание класса BSTree:

BSTNode(T new_key, V new_val): L(0), R(0) //конструктор

~BSTNode() //деструктор

bool IsEmpty() //проверка коллекции на пустоту

size_t size() //Получение размера коллекции

void clear() //очистка коллекции

get(T find_key) //получения значения элемента по ключу

bool insert(BSTNode<T, V>* new_node) //вставка в коллекцию

void print_tree(int indent) // Вывод коллекции на экран

void print_ltr() // Демонстрация порядка обохода L-T-R

bool isBalanced (BSTNode<T, V>*) // Определение критерия сбалансированности для всех узлов дерева

BSTNode<T, V>* find_previous_by_key(T);

remove(BSTNode<T, V>* remove_node, bool &deleted) // Удаление значения из коллекции по ключу

 

Выводы

В результате проделанной работы был создан абстрактный тип данных — двоичное дерево поиска. Работоспособность класса была проверена с помощью созданной программы-меню, дающей доступ ко всем методам созданного класса.


Приложение А

Исходный код класса


Файл BST.h

#ifndef BST_H

#define BST_H

#include <iostream>

#include <iomanip>

#include <algorithm>

using namespace std;

 

 

template<typename T = int, typename V = char>

class BSTNode

{

protected:

T key;

V val;

BSTNode<T, V>* r_max();

BSTNode<T, V>* r_parent(BSTNode<T, V>*);

 

public:

BSTNode(T, V);

~BSTNode();

BSTNode<T, V>* L;

BSTNode<T, V>* R;

V value();

T k();

size_t size();

 

void clear();

bool is_empty();

void empty_node();

BSTNode<T, V>* get(T);

bool insert(BSTNode<T, V>*);

BSTNode<T, V>* remove(BSTNode<T, V>*, bool&);

BSTNode<T, V>* remove(T, bool&);

BSTNode<T, V>* del(BSTNode<T, V>*);

void print_ltr();

void print_tree(int = 0);

BSTNode<T, V>* find_node(T);

int maxDepth(BSTNode<T, V>*);

int minDepth(BSTNode<T, V>*);

bool isBalanced(BSTNode<T, V>*);

};

 

//---------------------------------------------------------------------------//

 

template<typename T, typename V> // Constructor

BSTNode<T, V>::BSTNode(T new_key, V new_val): L(0), R(0)

{

this->key = new_key;

this->val = new_val;

}

 

template<typename T, typename V> // Destructor

BSTNode<T, V>::~BSTNode()

{

delete this->L;

delete this->R;

}

 

template<typename T, typename V> // value()

V BSTNode<T, V>::value() {

return this->val;

}

 

template<typename T, typename V> // k()

T BSTNode<T, V>::k() {

return this->key;

}

 

template<typename T, typename V> // size()

size_t BSTNode<T, V>::size() {

size_t s = 1;

if (this->L) s += L->size();

if (this->R) s += R->size();

return s;

}

 

template<typename T, typename V> // print_ltr()

void BSTNode<T, V>::print_ltr() {

cout << "(";

if (this->L) this->L->print_ltr();

cout << this->key << ':' << this->val;

if (this->R) this->R->print_ltr();

cout << ")";

}

 

template<typename T, typename V> // print_tree()

void BSTNode<T, V>::print_tree(int indent) {

if (this->R) {

this->R->print_tree(indent + 1);

}

if (indent) {

cout << std::setfill('\t') << std::setw(indent + 1) << ' ';

}

if (!this->is_empty()) {

cout << this->key << ':' << this->val << endl << ' ';

}

if (this->L) {

this->L->print_tree(indent + 1);

}

}

 

template<typename T, typename V> // clear()

void BSTNode<T, V>::clear() {

this->~BSTNode();

this->R = this->L = 0;

this->val = 0;

this->key = 0;

}

 

template<typename T, typename V> // is_empty()

bool BSTNode<T, V>::is_empty() {

return!this->R &&!this->L &&!this->val;

}

 

template<typename T, typename V> // get()

BSTNode<T, V>* BSTNode<T, V>::get(T find_key) {

if (this->key == find_key) return this;

else if (find_key < this->key) {

if (this->L) return this->L->get(find_key);

}

else {

if (this->R) return this->R->get(find_key);

}

return 0;

}

 

template<typename T, typename V> // insert()

bool BSTNode<T, V>::insert(BSTNode<T, V>* new_node) {

if (new_node->key == this->key) return false;

 

if (new_node->key < this->key) {

if (this->L) this->L->insert(new_node);

else this->L = new_node;

}

else {

if (this->R) this->R->insert(new_node);

else this->R = new_node;

}

return true;

}

 

template<typename T, typename V> // find_node()

BSTNode<T, V>* BSTNode<T, V>::find_node(T find_key) {

BSTNode<T, V>* elem = this->get(find_key);

if (!elem) return 0;

else return elem;

}

 

template<typename T, typename V> // r_max()

BSTNode<T, V>* BSTNode<T, V>::r_max() {

if (this->R) return this->R->r_max();

else return this;

}

 

template<typename T, typename V> // remove()

BSTNode<T, V>* BSTNode<T, V>::remove(T remove_node, bool &deleted) {

BSTNode<T, V>* elem = this->get(remove_node);

if (!elem) {

deleted = false;

return this;

}

return this->remove(elem, deleted);

}

 

template<typename T, typename V> // remove()

BSTNode<T, V>* BSTNode<T, V>::remove(BSTNode<T, V>* remove_node, bool &deleted) {

if (!remove_node) {

deleted = false;

return this;

}

if (remove_node->key < this->key) {

bool del = false;

if (!this->L) return 0;

this->L = this->L->remove(remove_node, del);

deleted = del;

return this;

}

else if (remove_node->key > this->key) {

bool del = false;

if (!this->R) return 0;

this->R = this->R->remove(remove_node, del);

deleted = del;

return this;

}

deleted = true;

if (!this->L &&!this->R) {

this->empty_node();

return 0;

}

if (!this->L) {

BSTNode<T, V>* right = this->R;

this->empty_node();

return right;

}

if (!this->R) {

BSTNode<T, V>* left = this->L;

this->empty_node();

return left;

}

this->R = this->R->del(remove_node);

return this;

}

 

template<typename T, typename V> // del()

BSTNode<T, V>* BSTNode<T, V>::del(BSTNode<T, V>* remove_node) {

if (this->L) {

BSTNode<T, V>* old = this->L;

this->L = this->L->del(remove_node);

delete old;

return this;

}

remove_node->key = this->key;

remove_node->val = this->val;

 

BSTNode<T, V>* right = this->R;

this->empty_node();

return right;

}

 

template<typename T, typename V> // empty_node()

void BSTNode<T, V>::empty_node() {

this->val = 0;

this->L = this->R = 0;

}

 

template<typename T, typename V> // r_parent()

BSTNode<T, V>* BSTNode<T, V>::r_parent(BSTNode<T, V>* elem) {

if (this == elem) return 0;

if (elem->key > this->key) {

if (this->R) {

BSTNode<T, V>* rp = this->R->r_parent(elem);

if (rp) return rp;

else return this;

}

else {

return 0;

}

}

else return this->L->r_parent(elem);

}

 

template<typename T, typename V> // maxDepth()

int BSTNode<T, V>::maxDepth(BSTNode<T, V>* root){

if (!root) {

return 0;

}

return 1 + max(maxDepth(root->L), maxDepth(root->R));

}

 

template<typename T, typename V> // minDepth()

int BSTNode<T, V>::minDepth(BSTNode<T, V>* root) {

if (!root) {

return 0;

}

return 1 + min(minDepth(root->L), minDepth(root->R));

}

 

template<typename T, typename V> // isBalanced()

bool BSTNode<T, V>::isBalanced(BSTNode<T, V>* root){

return (maxDepth(root) - minDepth(root) <= 1);

}

#endif // BST_H

 

Исходный код меню

Файл Menu.cpp

#include "stdafx.h"

#include <iostream>

#include "bst.h"

 

using namespace std;

// Вариант 7

 

int main() {

int choice = -1;

BSTNode<int, char>* root = 0, *node = 0;

int new_key;

char new_val;

bool inserted;

bool removed;

 

while (true) {

cout << endl << setfill('=') << setw(18) << " BST " << setw(15) << ' ' << endl;

cout << "Available actions:" << endl;

cout << "1 - create sample tree," << endl << "2 - print tree (L->t->R)," << endl << "3 - print tree (structure)," << endl;

cout << "4 - insert node (key, value)," << endl << "5 - remove node (key)," << endl << "6 - clear tree," << endl;

cout << "7 - find node by existing key," << endl << "8 - check if tree is empty," << endl;

cout << "9 - check if tree is balanced," << endl;

cout << "0 - exit." << endl << "Choice: ";

cin >> choice;

cout << endl;

 

new_key = 0;

new_val = 0;

inserted = false;

removed = false;

node = 0;

 

switch (choice) {

case 1:

if (root) delete root;

root = new BSTNode<int, char>(7, 'b');

root->insert(new BSTNode<int, char>(6, 'e'));

root->insert(new BSTNode<int, char>(10, 'f'));

root->insert(new BSTNode<int, char>(4, 'g'));

root->insert(new BSTNode<int, char>(16, 'j'));

root->insert(new BSTNode<int, char>(8, 'i'));

root->insert(new BSTNode<int, char>(12, 'c'));

root->insert(new BSTNode<int, char>(2, 'd'));

root->insert(new BSTNode<int, char>(18, 'k'));

root->insert(new BSTNode<int, char>(20, 'm'));

cout << root->size() << " node(s) in tree." << endl;

break;

 

case 2:

if (root) {

cout << "Tree:" << endl;

root->print_ltr();

}

else cout << "Empty tree.";

cout << endl;

break;

 

case 3:

if (root) {

cout << "Tree structure:" << endl;

root->print_tree();

}

else cout << "Empty tree.";

cout << endl;

break;

 

case 4:

cout << "Enter node key: "; cin >> new_key;

cout << "Enter node value: "; cin >> new_val;

if (root) {

inserted = root->insert(new BSTNode<int, char>(new_key, new_val));

}

else {

root = new BSTNode<int, char>(new_key, new_val);

inserted = true;

}

if (inserted) cout << "Success!" << endl;

else cout << "Failed to insert node, key exists." << endl;

break;

 

case 5:

if (root) {

cout << "Enter key to remove: "; cin >> new_key;

node = root->get(new_key);

if (node) {

root = root->remove(node, removed);

if (removed) {

cout << "Removed node " << new_key << ":" << node->value() << endl;

}

else cout << "Cannot remove." << endl;

}

else {

cout << "Key " << new_key << " not found in tree. Cannot remove." << endl;

}

}

else {

cout << "Empty tree." << endl;

}

break;

 

case 6:

if (root) {

root->clear();

root = 0;

}

cout << "Tree cleared." << endl;

break;

 

case 7:

if (root) {

cout << "Enter key: "; cin >> new_key;

node = root->find_node(new_key);

if (node) {

cout << "Node: " << node->k() << ":" << node->value() << endl;

}

else {

cout << "Key not found." << endl;

}

}

else {

cout << "Empty tree." << endl;

}

break;

 

case 8:

if (!root || root->is_empty()) cout << "Tree is empty." << endl;

else cout << "Tree is not empty, " << root->size() << " nodes." << endl;

break;

 

case 9:

if (root) {

if (root->isBalanced(root)) {

cout << "Tree is balanced" << endl;

}

else {

cout << "Tree is not balanced" << endl;

}

}

else {

cout << "Empty tree." << endl;

}

break;

 

case 0:

return 0;

break;

 

default:

cout << "Incorrect command. Try again." << endl;

}

}

return 0;

}



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2018-02-24 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: