Дважды связанный список. Проблемы при работе с динамической памятью Стеки и очереди. Определение стека

Лекция 2

Дважды связанный список

Проблемы при работе с динамической памятью Стеки и очереди.

Очередь

Определение очереди: специальный тип списка, в котором вставка новых элементов происходит с одного конца списка, а чтение и удаление – с другого (первым пришел, первым ушел).

Методы:

INSERT – добавляет новый элемент в конец очереди;

GET – возвращает самый первый элемент из очереди и удаляет его; ISEMPTY – проверяет, не пуста ли очередь;

CLEAR – очищает очередь;

FIRST – возвращает, не удаляя, первый элемент из очереди;

Стек

Определение стека: специальный тип списка, в котором все вставки и удаления выполняются на одном конце списка (первым пришел, последним ушел).

Примеры: колода карт при игре в покер?, стопка тарелок в буфете и т. д.

Методы:

POP – возвращает верхний элемент стека и удаляет его из стека;

PUSH – вставляет элемент на вершину стека;

TOP – возвращает верхний элемент из стека, не удаляя его;

CLEAR – очищает стек;

ISEMPTY – проверяет, пуст или стек;

Циклический буфер:

Вариант списка, у которого фиксированная длина, а начало и конец зациклены. Подходит для организации очереди фиксированной длины.

Деревья

Деревья представляют собой иерархическую структуру некоторой совокупности элементов.

Дерево – это совокупность элементов, называемых узлами (один из которых определен как корень) и отношений (“родительских”), образующих иерархическую структуру узлов.

Формальное рекурсивное определение дерева: Один узел является деревом

Пусть у нас имеется узел У, а Д1, Д2, Д3 – деревья с корнями У1, У2, У3. Если сделать У родителем узлов У1, У2 и У3, то в результате получиться тоже дерево, где Д1, Д2 и Д3 будут поддеревьями.

Дерево – это направленный граф без циклов.

Термины: родители, сыновья, братья (или сестры), путь из узла У1 в узел Уn, длина пути на единицу меньше числа узлов, формирующих путь; потомок и предок (если существует путь из предка в потомок), истинный предок и истинный потомок (когда имеются предки/потомки, за исключением самого себя), лист; высота узла или дерева (длина самого длинного пути), глубина узла (длина пути от корня до этого узла), степень дерева (число непосредственных потомков).

Основные операции с деревом:

Обход дерева: прямой (R, A, B) – префиксная запись; обратный (A, B, R) – постфиксная запись; симметричный (A, R, B) – инфиксная запись (привычная);

Добавление вершин Удаление вершин.

Двоичные деревья

Упорядоченное дерево – это дерево, у которого ребра (ветви), исходящие из каждой вершины, упорядочены.

Двоичные деревья – это упорядоченные деревья степени 2.

Идеально сбалансированное двоичное дерево – дерево, число вершин в его левых и правых поддеревьях отличается не более чем на 1.

Построение идеально сбалансированного дерева. Поиск в дереве.

Удаление вершин (более сложный процесс, если удаляемая вершина содержит два потомка. Для удаления необходимо заменить ее на самый левый лист его правого поддерева или самый правый лист левого поддерева).

Анализ производительности поиска по двоичному дереву. Идеально сбалансированное дерево – поиск максимум за log₂(n) просмотров вершин.

Можно использовать для сортировки (стабильная сортировка, когда x=x_p ведет себя также как и x>x_p).

АВЛ деревья

АВЛ-дерево – это двоичное дерево, у которого высоты всех его поддеревьев отличаются не более чем на 1 (по имени Андельсон-Вельского и Ландиса, предложивших данное определение).

Даже в худшем случае за время O(log₂(n)) можно выполнить следующие операции:

1.  Найти вершину с заданным ключом.

2.  Включить вершину с заданным ключом.

3.  Исключить вершину с указанным ключом.

АВЛ дереьвья имеют высоту не более чем на 45% превышающую высоту идеально сбалансированного дерева. Включение в АВЛ-дерево.

Возможны три варианта перед включении (новая вершина добавляется в левое поддерево):

1.  Высота h левого и правого поддеревьев равны (h_l=h_r). Сбалансированность не будет нарушена.

2.  h_l<h_r Балансировка улучшиться.

3.  h_l>h_r Критерий балансировки нарушен. Дерево необходимо перестроить.

Возможные варианты несбалансированности и методы их разрешения (остальные выводятся на основании симметрии).

Алгоритм включения:

1.  Проход по дереву.

2.  Включение новой вершины

3.  Возврат с проверкой необходимости балансировки

Необходимо в каждой вершине хранить информацию о дисбалансировки. Пункт 3 можно улучшить, так как если какая-либо вершина сбалансирована, то нет и необходимости в вышестоящей балансировке.

Пример:4, 5, 7, 2, 1, 3, 6

Высота дерева примерно составляет log₂(n)+с, где с – небольшая константа.

Примерно на каждые две вставки приходится одна балансировка.

Использование АВЛ-дерева: поиск происходит чаще, чем изменение дерева.