Реферат: Структуры данных
заменить одну заданную вершину на другую;
удалить вершину;
вставить новую вершину.
При построении алгоритмов, реализующих эти равно как и другие операции над деревьями надо учитывать, что в дереве возможны самые разнообразные последователльности промотра вершин. Было бы полхо если результат операции зависел бы от порядка обхода дерева. Основные направления обхода: сверху-вниз, снизу-вверх, справа-налево, слева-направо.
Определение.
Дерево называется K-ичным если все внутренние вершины в нем имеют степень исхода K.
Соответсвенно дерево называется единичным или линейным, если степень исхода его внутренних вершин равна 1; в двоичном или бинарном дереве она соответсвенно равна 2.
Перечисление бинарных деревьев.
Попробуем подсчитать число двоичных деревьев, имеющих n вершин. Обознаячим b(i) - число бинарных деревьев из i вершин. Тогда следуя рекурсивному определению дерева, можно написать
b(n)=b(0)b(n-1) +b(1)b(n-2) +b(2)b(n-3) +...+b(n-1)b(0)
Нетрудно подсчитать что b(1)=1, b(2)=2, b(3)=b(0)b(2) + b(1)b(1) + b(2)b(0) , полагая b(0)=1, получаем, что b(3)=2+1+2=5. Соответственно b(4)=5+2+2+5=14, b(5)=14+5+4+5+14=42.
В общем случае b(n)=C(n, 2n) / (n+1) = (2*n!) / (n! * n!)
Определение.
Дерево называется совершенным (или полностью сбалансированным) если любой путь в нем от корня к листу не более чем на единицу отличается от длины самого длинного пути в этом дереве.
Следствие.
Совершенное дерево из n вершин имеет минимальную высоту среди всех деревьев, имеющих n вершин.
Подсчитаем высоту совершенного бинарного дерева из n вершин. Пусть в нем i ярусов. (Ярусом назовем множество вершин равно отстоящих от корня дерева.) Тогда число вершин в дереве можно выразить следующим соотношением:
1 + 2 + 2^2 +...+ 2^i = n.
Отсюдаполучаем2^i -1=n, i=log2 (n+1) - 1. Или в приближенно log n. Отметим, что число совершенных деревьев составляет лишь малую часть общего числа деревьев. Например, при n=4 их всего 4.
Совершенные деревья интересны, например, тем что сложность доступа от корню к любому листу практически одна и та же. Здесь под сложностью доступа мы понимаем длину пути от корня к листу.
3.4. Стек
Стеком называется линейное дерево. В отличии от деревьев для операций со стеком есть ограничения. Доступ в стеке возможен только к корню дерева, которое в случае стека называется окном стека. Поэтому чтобы посмотреть элемент или изъять его или добавить новый - все это можно сделать только через корень. Примеры стека: подносы в столовой, патроны в обойме.
Основные операции: добавить элемент в стек, изъять элемент.
3.5. Очередь
Очередь - это линейное дерево, но в отличие от стека добавить элемент в очередь можно только в корень дерева, который в случае очереди называется хвостом или концом очереди, а изъять элемент из очереди можно только со стороны листа, который называется головой очереди.
Пример: банальная очередь в магазине, в столовой. Основные операции изъять элемент, добавить элемент.
3.6. Таблица
Упорядоченное множество пар (ключ,тело).
Примеры:
функция может быть представлена как пара (аргумент, результат),
таблица с записями о людях. В такой таблице ФИО - ключ, данные о человеке - тело. Мы здесь не будем подробно останавливаться на таблицах, так как им будет посвящено особое место в курсе.
4. Структура данных хранения (СДХ)
В Pascal можно выделить две базовые структуры хранения: вектор из записей и список. С идей списка мы уже сталкивались когда рассматривали динамические структуры данных. Когда мы не можем фиксировать заранее число компонентов в структуре. Однако, как мы увидим позднее связывание статических элемнтов памяти посредством ссылок в цепочки позволяет динамически упралять не только числом компонентов, но и структурой в целом. Например, когда мы заранее не знаем степень вершин в графе.