«Коллекция данных – сбалансированное дерево поиска»
Скачать 305.47 Kb.
|
Министерство образования и науки РФ Новосибирский государственный технический университет  Лабораторная работа № 2 по дисциплине «Структуры и алгоритмы обработки данных» «Коллекция данных – сбалансированное дерево поиска» Факультет: АВТ Группа: АМ-610 Выполнили: Асанов П. Проверила: Романенко Т.А. Антонов А. Вариант 7 Новосибирск 2008
АТД «Сбалансированное двоичное дерево поиска» представляет собой модифицированную версию АТД «BST-дерево» с трудоемкостью операций O(log2n). Интерфейс АТД «Сбалансированное двоичное дерево поиска» включает следующие операции:
Для тестирования коллекции интерфейс АТД «Сбалансированное двоичное дерево поиска» включает дополнительные операции:
АТД «Рандомизированное дерево» как модификация АТД «BST-дерево». Алгоритмы операций АТД реализуются в рекурсивной форме.
Двоичное дерево поиска (Binary Search Tree - BST) представляет собой упорядоченное, иерархическое, ассоциативное множество элементов (один из которых определен как корень), между которыми существуют структурные отношения «предки-потомки». Каждый элемент ассоциативного множества состоит из данных и уникального ключевого значения, идентифицирующего данные среди прочих в множестве. Положение элемента в дереве определяется ключевым значением при сопоставлении его с другими ключами, присутствующими в дереве.
Вид структуры хранения данных: двоичное дерево поиска Тип элементов: шаблонный тип Т Параметры: размерность дерева - sz
Конструктор: Вход: нет Процесс: создание дерева с фиктивным элементом Постусловия: создано дерево размерности 0 Деструктор: Вход: нет Процесс: удаление всех узлов дерева Постусловия: дерево очищено Опрос размера дерева Вход: нет Предусловия: нет Процесс: возврат значения размерности дерева Выход: размерность дерева sz Постусловия: нет Очистка дерева Вход: нет Предусловия: дерево не пусто Процесс: удаление всех элементов дерева Выход: TRUE – дерево очищено, FALSE – дерево уже пусто Постусловия: дерево пусто (размерность 0) Проверка на пустоту Вход: нет Предусловия: нет Процесс: проверка дерева на пустоту Выход: TRUE – дерево пусто, FALSE – дерево не пусто Постусловия: нет Включение данных с заданным ключом Вход: данные заданного типа T, ключ Предусловия: объект с заданным ключом отсутствует в дереве Процесс: поиск места для вставки элемента по ключу и вставка в это место Выход: TRUE –вставка прошла успешно; FALSE – если такой ключ уже есть в дереве Постусловия: значение добавлено в дерево; увеличение размерности дерева на 1 Удаление данных с заданным ключом Вход: ключ Предусловия: есть элемент с таким ключом Процесс: проход по дереву с поиском заданного ключа и удаление элемента, содержащего этот ключ. Выход: TRUE – удаление прошло успешно; FALSE – элемент с заданным ключом отсутствует Постусловия: значение удалено из дерева; размерность дерева уменьшается на 1 Поиск данных с заданным ключом Вход: ключ Предусловия: есть элемент с таким ключом Процесс: поиск в дереве элемента с заданным ключом Выход: данные, хранящиеся в найденном элементе. Если ключ не найден или дерево пусто – выброс исключений Постусловия: нет
Итератор является средством последовательного доступа к элементам дерева для чтения/ изменения элементов. Позволяет устанавливать свое текущее положение на начальный и конечный элемент дерева. Итератор имеет два состояния: установленное (указывает на элемент дерева) и неустановленное. При выходе итератора за пределы структуры доступ к элементам прекращается до установки итератора внутрь дерева.
Вид структуры хранения данных: структура последовательного доступа к элементам дерева
Конструктор с параметрами Вход: указатель на объект дерева Процесс: создание объекта итератор и привязка к дереву Постусловия: итератор создан, но не установлен Установка на первый элемент Вход: нет Предусловия: дерево не пусто Процесс: установка итератора на элемент с минимальным ключом в дереве Выход: TRUE – установлено, FALSE – дерево пусто Постусловия: итератор переведен на первый элемент Установка на последний элемент Вход: нет Предусловия: дерево не пусто Процесс: установка итератора на элемент с максимальным ключом в дереве Выход: TRUE – установлено, FALSE – дерево пусто Постусловия: итератор переведен на последний элемент Переход к следующему элементу дерева Вход: нет Предусловия: дерево не пусто, итератор установлен, текущий элемент не фиктивный Процесс: переход к следующему по значению ключа элементу дерева Выход: TRUE – успешный переход, FALSE – при невыполнении предусловия Постусловия: итератор переведен на следующий элемент Переход к предыдущему элементу дерева Вход: нет Предусловия: дерево не пусто, итератор установлен, текущий элемент не фиктивный Процесс: переход к предыдущему по значению ключа элементу дерева Выход: TRUE – успешный переход, FALSE – при невыполнении предусловия Постусловия: итератор переведен на предыдущий элемент Проверка состояния итератора Вход: нет Предусловия: нет Процесс: проверка текущего элемента на «фиктивность» и признака установленности Выход: TRUE – итератор вне дерева, FALSE – итератор внутри дерева (установлен) Постусловия: нет Доступ к значению текущего элемента Вход: нет Предусловия: итератор внутри дерева Процесс: нет Выход: если внутри дерева - ссылка на данные элемента в дереве, иначе - исключение Постусловия: нет
Рандомизированное дерево структурно представляет собой BST-дерево, поэтому большинство методов просто наследуются от BST-дерева. Отличие состоит в реализации операций вставки и удаления в дерево, так как они имеют случайный характер. Основополагающим является то, что любой элемент может быть корнем дерева, поэтому при включении нового элемента в дерево случайным образом выбирается включение элемента в качестве листа или корня. В основе удаления лежит замена удаляемого элемента корнем его объединяемых поддеревьев. Причем объединение зависит от вероятности, показывающей, вершина правого или левого поддерева будет объединенным корнем.
Вид структуры хранения данных: двоичное дерево поиска Тип элементов: шаблонный тип Т Параметры: размерность дерева – sz количество узлов в поддереве n
Включение данных с заданным ключом Вход: данные заданного типа T, ключ Предусловия: объект с заданным ключом отсутствует в дереве Процесс: проход, аналогичный вставке в BST-дерево, но с вероятностью вставки в корень текущего поддерева на каждом шаге, равной 1/(n+1), где n – размерность текущего поддерева. С помощью поворотов дерево балансируется. Выход: TRUE - вставка прошла успешно; FALSE – если такой ключ уже есть в дереве Постусловия: значение добавлено в дерево; увеличение размерности дерева на 1 Удаление данных с заданным ключом Вход: ключ Предусловия: есть элемент с таким ключом Процесс: проход по дереву с поиском заданного ключа и при удалении элемента - объединение левого и правого для него поддеревьев. Вероятность установки корня левого поддерева в качестве корня объединенного поддерева равна n/(n+m), правого – m/(n+m); здесь n - количество узлов в левом поддереве, m – в правом. Выход: TRUE – удаление прошло успешно; FALSE – элемент с заданным ключом отсутствует Постусловия: если заданный ключ найден, то в результате дерево не содержит элемента с данным ключом
Для получения статистических оценок трудоемкостей для операций поиска, удаления и вставки была разработана тестирующая функция Testing(), которая создает BST и RND деревья большой размерности и заполняет их случайными 32-битными числами. Для данных деревьев программа генерирует поток операций в количестве повторений каждой, равном половине размерности деревьев. В качестве параметров операциям передаются сгенерированные случайные значения. В результате работы каждой операции ее трудоемкость суммируется с общей трудоемкостью для каждого типа операций, а затем, для нахождения среднего, делится на количество выполнений, то есть на size/2. Тестирование трудоемкостей операций с деревьями проводилось для двух случаев: для среднего и для худшего (вырожденного). Худший случай представляет собой полностью вырожденное в список дерево с высотой равной количеству элементов дерева (элементы добавляются в BST дерево с возрастающими ключами). Для рандомизированного дерева вырожденный случай невозможен из-за поддержания сбалансированности операциями дерева При тестировании операций поиска было задано количество промахов равное 10% В следующей таблице приведены значения средних трудоемкостей операций:
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Добавить документ в свой блог или на сайт
Похожие:
 | Конспект урока по информатике для учащихся 11 класса «Средства поиска данных в Интернете» Введение. Содержание дисциплины и порядок ее изучения. Фактографический поиск. Математические модели фактографического поиска. Информационная... |  | Реферат на тему «Сбалансированное питание это здоровье нации» Здоровье человека важный показатель его личного успеха. Одним из важнейших условий сохранения и укрепления здоровья является сбалансированное... |
| Реферат на тему «Сбалансированное питание это здоровье нации» Здоровье человека важный показатель его личного успеха. Одним из важнейших условий сохранения и укрепления здоровья является сбалансированное... | | Коллекция/модуль поиска |
| В базе данных Исакова О. Н. Основы поиска патентов в базе данных Европейского патентного ведомства: Препринт 03 – Новосибирск: гпнтб со ран, 2003.... | | Программа дисциплины Технологии поиска, анализа данных и распространения информации в Интернет Значение проекта Семантическая Паутина для расширения возмож-ностей смыслового поиска информации в сети Интернет |
| Урока информатики по теме «Табличные базы данных». (Открытый урок.) Данный урок «База данных. Системы управления базами данных» является первым уроком по теме «Технологии хранения, поиска и сортировки... | | Коллекция обивочных тканей Данная коллекция станет украшением любой модели кроватей. Ткань относится к категории мебельного атласа отличается не только богатым... |
| Определитесь с инструментами поиска Для обнаружения в текстах фрагментов, аналогичных заданному, используются инструменты линейного поиска информации. К таким инструментам... | | Коллекция игр Играющие садятся в круг, ведущий объявляет, что все участники игры, начиная с первого, должны назвать по одному растению, причем... |
| Коллекция 038 Белгород Это пример платной текущей распечатки бдкр, вместо контактных данных указаны только номера коллекций и | | Коллекция 614 Тюмень Это пример платной текущей распечатки бдкр по комнатным растениям, вместо контактных данных указаны только |
| Коллекция 589 Мордовия, Саранск Это пример платной текущей распечатки бдкр по садовым овощным растениям, вместо контактных данных указаны | | Программа по формированию навыков безопасного поведения на дорогах... Сейба, дынное дерево, шоколадное дерево, пальмы, фикусы, гевея, кувшинка Виктория регия |
| Литература по химии. Азбука веб-поиска для химиков. Методика поиска... Химия и жизнь: научно-популярный журнал. Электронная версия научно-популярного журнала. Архив содержаний номеров. Доступ к полной... | | Тематика контента (источников, баз(ы) данных Архив (acs legacy Archives) 25-ти журналов коллекция ретроспективных выпусков журналов с 1879 по 1995гг. Реферативные источники |
