«Коллекция данных – сбалансированное дерево поиска»

Таб. 1. Средние трудоемкости операций (обычный случай) Рис. 1. Графики трудоемкостей операций (обычный случай) Размер дерева O(n/2) 1.39*O(log2n) Поиск Вставка Удаление BST RND BST RND BST RND 500 250 12.462 205.1 11.448 206.7 12.996 204.6 13.036 1000 500 13.852 376.7 11.954 384.4 13.668 392.9 13.976 2000 1000 15.242 822.5 13.755 771.1 16.268 775.7 15.489 5000 2500 17.080 2000 15.444 2020 17.952 1984 17.254 7000 3500 17.755 2746 17.023 2739 19.497 2715 18.761 Таб. 2. Средние трудоемкости операций (худший случай) Рис. 2. Графики трудоемкостей операций BST-дерева (худший случай) Рис. 3. Графики трудоемкостей операций RND-дерева (худший случай) Проанализировав полученные графики, можно сделать вывод, что трудоемкость тестируемых операций в среднем случае для BST-дерева и рандомизированного практически одинаковая и близка к оценке 1.39*O(log2n). Что касается тестирования операций для худшего случая, то здесь наблюдается значительное увеличение трудоемкостей операций BST-дерева и теперь они близки к оценке O(n/2). Это происходит из-за того, что дерево заполняется последовательностью из возрастающих ключей, что приводит к вырождению дерева в список. Но такое заполнение дерева не оказывает никакого влияния на трудоемкости операций рандомизированного дерева, что говорит о том, что по структуре оно остается близким к сбалансированному дереву. Выводы В процессе разработки АТД «Двоичное дерево поиска» и АТД «Сбалансированное дерево поиска» были запрограммированы различные операции для работы с данными произвольных типов. Также разработан итератор последовательного доступа к элементам деревьев, позволяющий также выводить и редактировать элементы структуры данных. Было проведено тестирование структуры данных в двух видах. Первый позволяет вывести содержимое дерева в удобной форме после выполнения ряда операций над деревом. Второй – тестирование трудоемкостей алгоритмов операций поиска, удаления и вставки для деревьев больших размерностей. Операции удаления и вставки для обоих деревьев в среднем случае показали результаты, очень близкие к теоретической трудоемкости 1,39*O(). В худшем случае трудоемкости алгоритмов BST – дерева приближаются к оценке O(n/2), на трудоемкости RND – дерева худший случай никак не отразился. Список используемой литературы 1.) Проектирование и реализация коллекций данных: учебно-методическое пособие, Т.А, Романенко. – Новосибирск: Изд-во НГТУ, 2005. – 112 с. 2.) Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./ Роберт Седжвик – К.: Издательство «ДиаСофт», 2001. – 688 с. Исходный код программы с комментариями: //tree.h #include "rus.h" // ---------BST---------------- template class BST; template class node { public: T data; int key; node *left; node *right; int n; //количество узлов в поддереве (для RND дерева) node() { left=right=NULL; key=-1; data=-1; n=0; } node(int _key, T _data, BST *tr) { left=right=tr->fict; key=_key; data=_data; n=1; } }; template class BST { protected: node *root; int sz; //размерность дерева public: node *fict; int np_find; int np_add; int np_del; BST(); node* BST_Add(node *t, int _key, int _data, bool &inserted); node* BST_Delete(node *t, int _key, bool &deleted); node* Del(node *t, node *t0); node* BST_Search(node *t, int _key); int GetSize(); //Опрос размера дерева bool ClearTree(); //Очистка дерева bool IsEmpty(); //Проверка дерева на пустоту T Search(int _key); //Поиск данных с заданным ключом virtual bool Add(int _key, T _data); //Включение данных с заданным ключом virtual bool Delete(int _key); //Удаление данных с заданным ключом virtual bool Show(); //Вывод дерева protected: int BST_GetSize(node *t, int sz); void BST_Show(node *t, int nbsp); void BST_ClearTree(node *t); public: class Iterator //Итератор { BST *pt; node *cur; bool set; public: Iterator(BST *T0) { if (T0==NULL) pt=NULL; else pt=T0; set=false; } bool first() { if(pt->root==pt->fict)return false; else { for(cur=pt->root;cur->left!=pt->fict;cur=cur->left); set=true; return true; } } bool last() { if(pt->root==pt->fict)return false; else { for(cur=pt->root;cur->right!=pt->fict;cur=cur->right); set=true; return true; } } bool next() { if(set==false) return false; node *t=cur; if(cur->right!=pt->fict) { node *x=cur->right; for(;x->left!=pt->fict;x=x->left); cur=x; return true; } cur=L_Parent(pt->root,cur); if(cur!=pt->fict) return true; else {cur=t; set=false; return false; } } node *L_Parent(node *t, node *x) { if(t==x)return pt->fict; if(x->keykey) { node *lp=L_Parent(t->left,x); if(lp!=pt->fict)return lp; else return t; } else return L_Parent(t->right,x); } bool prev() { if(set==false) return false; node *t=cur; if(cur->left!=pt->fict) { node *x=cur->left; for(;x->right!=pt->fict;x=x->right); cur=x; return true; } cur=R_Parent(pt->root,cur); if(cur!=pt->fict)return true; else {cur=t; set=false; return false;} } node *R_Parent(node *t, node *x) { if(t==x)return pt->fict; if(x->key > t->key) { node*rp=R_Parent(t->right,x); if(rp!=pt->fict)return rp; else return t; } else return R_Parent(t->left,x); } bool is_off() { return (set==false); } T& operator *() { if (is_off()) throw -1; else return cur->data; } }; friend class Iterator; friend class node; }; template BST::BST() //конструктор BST - дерева { sz=0; fict=new node(); root=fict; np_find=0; np_add=0; np_del=0; } template //Добавление в BST node* BST::BST_Add(node *t, int _key, int _data, bool &inserted) { np_add++; if (t==fict) { t=new node(_key, _data, this); inserted=true; } else { if(_key==t->key) { inserted=false; return t; } else { inserted=true; if(_keykey) t->left=BST_Add(t->left, _key, _data, inserted); else t->right = BST_Add(t->right, _key, _data, inserted); } } return t; } template //Добавление bool BST::Add(int _key, T _data) { bool inserted=false; if (root==fict) { np_add=0; root=new node(_key,_data,this); sz++; return true; } else { np_add=0; BST_Add(root,_key,_data,inserted); if (inserted==true) sz++; return inserted; } return false; } template //Удаление из BST node* BST::BST_Delete(node *t, int _key, bool &deleted) { np_del++; if(t==fict) { deleted=false; return t; } if(_keykey) { t->left=BST_Delete(t->left,_key,deleted); return t; } else if(_key>t->key) { t->right=BST_Delete(t->right,_key,deleted); return t; } deleted=true; if (t->left==fict && t->right==fict) { if (t==root) root=fict; delete t; return fict; } if (t->left==fict) { node *x=t->right; delete t; return x; } if (t->right==fict) { node *x=t->left; delete t; return x; } t->right=Del(t->right,t); return t; } template //установка замещающего элемента на место удаленного node* BST::Del(node *t, node *t0) { np_del++; if (t->left!=fict) { t->left=Del(t->left,t0); return t; } t0->key=t->key; t0->data=t->data; node *x=t->right; delete t; return x; } template // Удаление bool BST::Delete(int _key) { np_del=0; bool deleted=false; if (root==fict) return false; else root=BST_Delete(root, _key, deleted); if (deleted==true) sz--; return deleted; } template //Поиск в BST node* BST::BST_Search(node *t, int _key) { np_find++; if(t==fict) return t; if(_keykey) return BST_Search(t->left,_key); else if (_key>t->key) return BST_Search(t->right,_key); if (_key==t->key) return t; } template //Поиск T BST::Search(int _key) { np_find=0; if(root==fict) throw -2; node *x=BST_Search(root,_key); if(x!=fict) return x->data; else throw -1; } template //Опрос размера дерева int BST::GetSize() { return sz; } template //Очистка дерева bool BST::ClearTree() { if (IsEmpty()) return false; BST_ClearTree(root); root=fict; sz=0; return true; } template void BST::BST_ClearTree(node *t) { if(t->left!=fict) BST_ClearTree(t->left); if(t->right!=fict) BST_ClearTree(t->right); delete t; } //Проверка на пустоту template bool BST::IsEmpty() { return (root==fict); } template //Вывод bool BST::Show() { if (IsEmpty()) return false; BST_Show(root,0); return true; } template void BST::BST_Show(node *t, int nbsp) //Непосредственно вывод BST на экран { if (t==fict) return; BST_Show(t->right, nbsp+1); for (int i=0;i<2*nbsp; i++) cout<<" "; cout<<"("<key<<","<data<<")"< BST_Show(t->left, nbsp+1); } // ---------RND---------------- template class RND: public BST { protected: node* Rn(node *t) { node *x=fict; x=t->left; t->left=x->right; x->right=t; if(t->left==fict) { if(t->right==fict) t->n=1; else t->n=t->right->n+1; } else { if(t->right==fict) t->n=t->left->n+1; else t->n = t->left->n + t->right->n + 1; } if(x->left==fict) x->n=x->right->n+1; else x->n = x->left->n + x->right->n + 1; return x; } node* Ln(node *t) { node *x=fict; x=t->right; t->right=x->left; x->left=t; if(t->left==fict) { if(t->right==fict) t->n=1; else t->n=t->right->n+1; } else { if(t->right==fict) t->n=t->left->n+1; else t->n = t->left->n + t->right->n + 1; } if(x->right==fict) x->n=x->left->n+1; else x->n = x->left->n + x->right->n + 1; return x; } node *RND_Add(node *t, int _key, T _data, bool &inserted) { np_add++; if (t==fict) { t=new node(_key, _data,this); t->n=1; inserted=true; return t; } if (_key==t->key) { inserted=false; return t; } if (rand()n+1)) { t=RND_Add_Root(t,_key,_data,inserted); return t; } else { if(_keykey) t->left=RND_Add(t->left, _key, _data, inserted); else t->right = RND_Add(t->right, _key, _data, inserted); } if (inserted==true) t->n++; return t; } node *RND_Add_Root(node *t, int _key, T _data, bool &inserted) { np_add++; if (t==fict) { t=new node(_key, _data, this); t->n=1; inserted=true; return t; } if (_key==t->key) { inserted=false; return t; } if (_keykey) { t->left=RND_Add_Root(t->left, _key, _data, inserted); if (inserted==true) return Rn(t); else return t; } t->right=RND_Add_Root(t->right, _key, _data, inserted); if (inserted==true) return Ln(t); else return t; } node *RND_Delete(node *t, int _key, bool &deleted) { np_del++; if(t==fict) { deleted=false; return t; } else { if(t->key==_key) { node *x=t; t=RND_Join(t->left,t->right); delete x; deleted=true; return t; } else { if(t->key>_key) t->left=RND_Delete(t->left,_key, deleted); else t->right=RND_Delete(t->right,_key, deleted); } } if(deleted==true) t->n--; return t; } node *RND_Join(node *l, node *r) { np_del++; if(l==fict) return r; if(r==fict) return l; double rrr=(double)rand()/RAND_MAX; double nnn=(double)l->n/(l->n+r->n); if (rrr < nnn) { l->right=RND_Join(l->right,r); if(l->left==fict) l->n=l->right->n+1; else if(l->right==fict) {l->n=l->left->n+1;} else l->n=l->left->n+l->right->n+1; return l; } else { r->left=RND_Join(l,r->left); if(r->left==fict) r->n=r->right->n+1; else if(r->right==fict) {r->n=r->left->n+1;} else r->n=r->left->n+r->right->n+1; return r; } return r; } public: bool Add(int _key, T _data); bool Delete(int _key); bool Show(); void RND_Show(node *t, int nbsp); }; template //Вставка в RND bool RND::Add(int _key, T _data) { np_add=0; bool inserted=false; if (root==fict) { root=new node(_key,_data,this); root->n=1; sz++; return true; } else { root=RND_Add(root,_key,_data,inserted); if (inserted==true) sz++; return inserted; } return false; } template //Удаление из RND bool RND::Delete(int _key) { np_del=0; bool deleted=false; if (root==fict) return false; else root=RND_Delete(root, _key, deleted); if (deleted==true) sz--; return deleted; } template //Вывод RND bool RND::Show() { if (IsEmpty()) return false; RND_Show(root,0); return true; } template void RND::RND_Show(node *t, int nbsp) { if (t==fict) return; RND_Show(t->right, nbsp+1); for (int i=0;i<2*nbsp; i++) cout<<" "; cout<<"("<key<<","<data<<")"<<" ["<n<<"]"< RND_Show(t->left, nbsp+1); }

Похожие:

	Конспект урока по информатике для учащихся 11 класса «Средства поиска данных в Интернете» Введение. Содержание дисциплины и порядок ее изучения. Фактографический поиск. Математические модели фактографического поиска. Информационная...		Реферат на тему «Сбалансированное питание это здоровье нации» Здоровье человека важный показатель его личного успеха. Одним из важнейших условий сохранения и укрепления здоровья является сбалансированное...
	Реферат на тему «Сбалансированное питание это здоровье нации» Здоровье человека важный показатель его личного успеха. Одним из важнейших условий сохранения и укрепления здоровья является сбалансированное...		Коллекция/модуль поиска
	В базе данных Исакова О. Н. Основы поиска патентов в базе данных Европейского патентного ведомства: Препринт 03 – Новосибирск: гпнтб со ран, 2003....		Программа дисциплины Технологии поиска, анализа данных и распространения информации в Интернет Значение проекта Семантическая Паутина для расширения возмож-ностей смыслового поиска информации в сети Интернет
	Урока информатики по теме «Табличные базы данных». (Открытый урок.) Данный урок «База данных. Системы управления базами данных» является первым уроком по теме «Технологии хранения, поиска и сортировки...		Коллекция обивочных тканей Данная коллекция станет украшением любой модели кроватей. Ткань относится к категории мебельного атласа отличается не только богатым...
	Определитесь с инструментами поиска Для обнаружения в текстах фрагментов, аналогичных заданному, используются инструменты линейного поиска информации. К таким инструментам...		Коллекция игр Играющие садятся в круг, ведущий объявляет, что все участники игры, начиная с первого, должны назвать по одному растению, причем...
	Коллекция 038 Белгород Это пример платной текущей распечатки бдкр, вместо контактных данных указаны только номера коллекций и		Коллекция 614 Тюмень Это пример платной текущей распечатки бдкр по комнатным растениям, вместо контактных данных указаны только
	Коллекция 589 Мордовия, Саранск Это пример платной текущей распечатки бдкр по садовым овощным растениям, вместо контактных данных указаны		Программа по формированию навыков безопасного поведения на дорогах... Сейба, дынное дерево, шоколадное дерево, пальмы, фикусы, гевея, кувшинка Виктория регия
	Литература по химии. Азбука веб-поиска для химиков. Методика поиска... Химия и жизнь: научно-популярный журнал. Электронная версия научно-популярного журнала. Архив содержаний номеров. Доступ к полной...		Тематика контента (источников, баз(ы) данных Архив (acs legacy Archives) 25-ти журналов коллекция ретроспективных выпусков журналов с 1879 по 1995гг. Реферативные источники