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

Бинарное дерево – набор вершин, который либо пуст, либо делится на 3 непересекающиеся части: корень, лев. и прав. двоичное поддерево.

Основное назначение двоичных деревьев заключается в повышении эффективности поиска.

Пример:

Д ерево с порядком на детях – для каждой его вершины множество детей упорядочено. Это всегда полное дерево. Его структура не зависит от содержимого.

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

Вершина корневого дерева называется листом если она не имеет детей(потомков).

Вершина корневого дерева называется внутренней если у нее есть дети(потомки), кроме корня.

Высотой дерева называется максимальная длина ветки

Упорядоченное дерево – это дерево с корнем (один узел назначен корнем), в котором определён порядок следования дочерних узлов каждого узла.

Полным k-ичным деревом называется дерево, в котором все листья имеют одинаковую глубину, все внутренние вершины имеют потомков.

Представление графов с помощью матриц смежности, списков смежных вершин, списков ребер и матриц инцидентности. Области применения этих представлений.

Пусть задано множество точек V (множество вершин) и множество связей между этими точками R (множество рёбер). Графом G =G(V,R) называется пара множества G(V,R), то есть граф задаётся множеством вершин и рёбер.

Если для ребра выполняется равенство (a,b)=(d,a) (то есть эта пара является неупорядоченной), то такое ребро называется неориентированным, если (a,b)(b,a), (т.е. пара упорядочена), то такое ребро называется ориентированным или дугой.

Две вершины соединённые ребром называются смежными. Два ребра называются смежными, если они имеют общую вершину. Ребро инцидентно двум смежным вершинам, и наоборот вершина инцидентна смежным рёбрам.

Граф, в котором все рёбра не ориентированы называется неориентированным. Граф, в котором все рёбра ориентированы называется ориентированным. Граф, в котором имеются как ориентированные, так и неориентированные рёбра называется смешанным.

Мультиграф – граф, в котором задано не одно, а несколько множеств между вершинами. Мультиграф отличается от обычного тем, что между его вершинами может быть несколько одинаковых рёбер называемых кратными рёбрами.

Вершина, не имеющая смежных вершин, называется изолированной.

Ребро, соединяющее вершину саму с собой, называется петлёй.

Граф с конечным числом вершин и рёбер называется конечным, с бесконечным числом – бесконечным. Граф, состоящий только из изолированных вершин называется нуль-графом.

Граф называется полным, если любые его две вершины смежны.

Степенью вершины называется число рёбер инцидентных ей.

Два графа G и G* изоморфны, если существует взаимооднозначное соответствие между множествами их вершин V и V* такое, что две вершины в одном графе  , когда соответствующие им вершины соединены ребром в другом графе(знак соответствия ).

Однородный граф – граф у которого все вершины имеют одинаковую степень.

Последовательность рёбер – конечная или бесконечная вида (X[1],X[2]), …, (X[k-1],X[k]), (X[k],X[k+1]) такая, что каждые два соседних ребра имеют общую концевую точку называется маршрутом .

Маршрут, не содержащий одинаковых рёбер называется цепью, маршрут не содержащий одинаковых вершин называется простой цепью.

Цепь в которой начальная и конечная вершины совпадают называется циклом. Простая цепь с таким свойством называется простым циклом.

В ориентированном графе существует ориентированный маршрут, ориентированная цепь и ориентированный цикл(контур) в которых все рёбра проходят в направлении их ориентации.

Граф называется связным, если для любой пары его вершин существует соединяющая их цепь.

Связный подграф графа G называется его связной компонентой. Множество вершин связной компонентной называется областью связности графа.

Числом вершинной связности æ(G) (каппа) называется наименьшее число вершин удаление которых приводит к несвязному графу.

Числом рёберной связности λ(G) (каппа) называется наименьшее число рёбер удаление которых приводит к несвязному графу.

Вершина VG называется точкой сочленения или разделяющей вершиной, если граф G* без этой вершины имеет больше связных компонентов, чем граф G.

Ребро графа называется мостом, если его удаление увеличивает число связных компонент графа.

Критерий планарности Мак-Лейна:

Пусть G – граф, а G* - его часть не содержащая петель и голых вершин. Граф G планарен если G* - пусто или существует система разрезов (множество рёбер лишающие данный граф связности), состоящая из æ+1 рёбер, где æ – хромотическое число. Причём данные рёбра линейно независимы и каждое ребро  ровно двум разрезам.

Грань – плоскость, образованная рёбрами графа, по отношению к которой граф лежит в одной плоскости.

Эйлерова характеристика: граф планарен если |V| - |E| + K = 2

V – количество вершин E – количество рёбер K – количество граней

Свободной раскраской рёбер графа называют придание рёбрам цветов так, что множество рёбер E разбивается на попарно пересекающиеся подмножества, каждое из которых имеет свой цвет

Г рафическое представление. Например, возьмем простой граф, показанный на рисунке.

Таблица ребер. В памяти хранится список ребер, в каждом элементе указано, какие вершины связаны, и, возможно, дополнительная информация, например, вес ребра. Если граф ориентированный, то каждая запись описывает направленную связь.

• Удобная структура для хранения в БД.

• Если с вершиной не связано ни одно ребро, то она не попадет в таблицу. Это можно исправить, если добавить в БД таблицу вершин. Либо, можно добавить в граф фиктивные ребра-петли, соединяющие вершину саму с собой.

М атрица смежности. Это двумерный массив, размером NxN, где N-количество вершин. Если между вершинами i и j существует ребро, то элемент в строке i и столбце j равен 1. Если граф взвешенный, то этот элемент может содержать вес ребра, или указатель на структуру данных, описывающую ребро. Если граф не ориентированный, то массив симметричен относительно главной диагонали.

Просто добавлять и удалять ребра, просто выяснить, связаны ли две вершины

• Сложно добавить вершину, т.к. придется перераспределять память для массива

• Неэффективно используются ресурсы, если много вершин и мало ребер. Для решения этой проблемы можно применить разреженный массив

С вязный список вершин. В памяти формируется связный список или массив, содержащий вершины. Каждой вершине соответствует связный список ребер с узлами для всех вершин, связанных с данной.

Просто добавлять и вершины и ребра. Просто выяснить, связаны ли вершины

• Неэффективно используются ресурсы, если много ребер.

Матрица инцидентности. Это двумерный массив, размером NxM, где N - количество вершин. M – количество ребер. Ребра как и вершины пронумерованы. Если между вершинами i и j существует ребро k, то элементы [i,k], и [j,k] имеют значение 1. Если граф взвешенный, то в них может содержатся вес ребра. Если граф ориентированный, элемент [i,k] равен -1, а [j,k] равен 1.

С ложно добавить вершину, т.к. нужно перераспределять память для массива

• Сложно добавить ребро по той же причине

• Сложно удалить вершину. Для этого нужно пройти по всему массиву, чтобы убрать соответствующие единицы.

Алгоритмы обхода графов. Общий принцип обхода такой. Пусть есть набор, организованный как очередь или стек. Вначале, в него помещается произвольная вершина графа. Затем до тех пор, пока набор не опустеет, выполняются следующие действия

1. берется очередная не пройденная вершина из набора

2. э та вершина отмечается как пройденная

3. в набор добавляются все вершины, смежные с данной, и не пройденные

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

При поиске в ширину, до перехода к следующему узлу сначала должны быть перебраны все возможности для данного узла.

Обход в ширину. В качестве набора используется очередь.

Обход в глубину. В качестве набора используется стек.

.

АТД «Таблица символов», способы реализации. Алгоритм бинарного поиска.

Структура данных элементов с ключами, которая поддерживает 2 базовые операции: вставка нового элемента, возврат элемента с заданным ключом, а также – удаление указанного элемента, выбор k-го по величине элемента в таблице символов, сортировка таблицы по ключам, объединение двух таблиц.

Способы реализации

1) Индексированный по ключам массив. Значения ключей – целые положительные числа, меньшие зарезервированного значения M, и они используются в качестве индексов массива. Ключи должны попадать в достаточно узкий диапазон.

2) Дерево бинарного поиска (Binaric Search Tree – BST) – бинарное* дерево, с каждым из внутренних узлов которого связан ключ, причем ключ в любом узле больше (или равен) ключам во всех узлах левого поддерева и меньше (или равен) ключам во всех узлах правого поддерева.

Бинарный поиск. Суть бинарного поиска в том, что набор элементов необходимо разделить на две части, определить к какой из двух частей принадлежит ключ поиска, а затем искать в этой части.

3) Дерево типа «красно-черное» – это дерево бинарного поиска, в котором каждый узел помечен либо как красный, либо как черный с наложением ограничения: никакие 2 красных узла не могут появиться друг за другом в любом пути от листа к корню.

4 ) Бинарное рандомизованное дерево. При создании дерева есть два способа: элементы вставляются в случайном порядке или при последовательной вставке в дерево, состоящее из N узлов, вероятность появления нового узла в корне равна 1/(N+1); в противном случае рекурсивно используется метод вставки в соответствующее поддерево.

5) Список пропусков – связанный список, где каждый узел содержит разное количество связей, и i-е связи в узлах реализуют односвязные списки, пропускающие узлы, что содержат менее i связей.

Также «Таблицу символов» можно реализовывать в виде упорядоченного/неупорядоченного массива или списка, и каждая из реализаций имеет преимущества и недостатки во времени выполнения операций и требуемых объемах памяти.

Разновидностью BST-дерева является 2-3-4-дерево – либо пустое дерево, либо дерево, содержащее 3 типа узлов:

2-узлы, с одним ключом, левой связью к дереву с меньшими ключами и правой связью – с большими;

3-узлы, с двумя ключами, левой связью к дереву с меньшими ключами и правой связью – с большими, и средней связью к дереву, значения ключей которого находятся между значениями ключей данного узла;

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

Другим видом реализации АТД «Таблица символов» является Алгоритм поиска в BST-дереве: начинаем с корня дерева; если дерево пусто, имеет место промах при поиске; если ключ поиска равен ключу в корне, то имеет место попадание при поиске: в противном случае рекурсивно выполняется поиск в соответствующем поддереве.

Время работы базовых операций	Худший случай			Средний случай
	вставка	поиск	выбор	вставка	попадание при поиске	промах при поиске
массив, индексированный по ключам	1	1	M	1	1	1
упорядоченный массив	N	N	1	N/2	N/2	N/2
упорядоченный список	N	N	N	N/2	N/2	N/2
неупорядоченный массив	1	N	NlgN	1	N/2	N
неупорядоченный список	1	N	NlgN	1	N/2	N
бинарный поиск	N	lgN	1	N/2	lgN	lgN
дерево бинарного поиска	N	N	N	lgN	lgN	lgN
дерево типа «красно-черное»	lgN	lgN	lgN	lgN	lgN	lgN
рандомизованное дерево	N	N	N	lgN	lgN	lgN

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