Краткие итоги

Ключевые термины

Циклический (кольцевой) список – это структура данных, представляющая собой последовательность элементов, последний элемент которой содержит указатель на первый элемент списка, а первый (в случае двунаправленного списка) – на последний.

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

Дек с ограниченным входом – это дек, из конца которого можно только извлекать элементы;

Дек с ограниченным выходом – это дек, в конец которого можно только добавлять элементы.

Красно-черное дерево (Red-Black-Tree, RB-Tree) – это бинарное дерево со следующими свойствами:

· каждая вершина должна быть окрашена либо в черный, либо в красный цвет;

· корень дерева должен быть черным;

· листья дерева должны быть черными и объявляться как NIL-вершины;

· каждый красный узел должен иметь черного предка;

· на всех ветвях дерева, ведущих от его корня к листьям, число черных вершин одинаково.

Черная высота дерева – это количество черных вершин на ветви красно-черного дерева от корня до листа.

1.Особенности указателей в языке С++ позволяют строить динамические структуры памяти на основе статически объявленных переменных или на смеси статических и динамических переменных.

2.Циклический (кольцевой) список является структурой данных, представляющей собой последовательность элементов, последний элемент которой содержит указатель на первый элемент списка, а первый (в случае двунаправленного списка) – на последний.

3.Основными операциями с циклическим списком являются: создание списка; печать (просмотр) списка; вставка элемента в список; удаление элемента из списка; поиск элемента в списке; проверка пустоты списка; удаление списка.

4.Дек является структурой данных, представляющей собой последовательность элементов, в которой можно добавлять и удалять в произвольном порядке элементы с двух сторон. Первый и последний элементы дека соответствуют входу и выходу дека.

5.Частные случаи дека – это ограниченные деки.

6.Основными операциями с деком являются: создание дека; печать (просмотр) дека; добавление элемента в левый конец дека; добавление элемента в правый конец дека; извлечение элемента из левого конца дека; извлечение элемента из правого конца дека; проверка пустоты дека; очистка дека.

7.Красно-черные деревья являются одним из способов балансировки деревьев, что определяется свойствами данной структуры.

8.Над красно-черными деревьями можно выполнять все те же основные операции, что и над бинарными деревьями.

9.При вставке/удалении элемента необходима поддержка баланса дерева через проверку и перекрашивание узлов при необходимости.