И коммуникаций республики узбекистан

12.Работа с бинарными деревьями


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

Способ представления бинарного дерева:

• 
  A — корень дерева
  
• 
  В — корень левого поддерева
  
• 
  С — корень правого поддерева
  

Корень дерева расположен на уровне с минимальным значением.

Узел D, который находится непосредственно под узлом B, называется потомком B. Если D находится на уровне i, то B – на уровне i-1. Узел B называется предком D.

Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой.

Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.

Остальные элементы – внутренние узлы (узлы ветвления).

Число потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева.

Число ветвей, которое нужно пройти от корня к узлу x, называется длиной пути к x. Корень имеет длину пути равную 0; узел на уровне i имеет длину пути равную i.

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

13. Сбалансированные бинарные деревья

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

Пример бинарного дерева поиска
Дерево поиска с минимальной высотой как раз и называется сбалансированным, т.е. таким, в котором высота левого и правого поддеревьев отличаются не более чем на единицу.
Сбалансированное оно, видимо, потому что в таком дереве в среднем требуется наименьшее количество операций для поиска.
Чтобы дерево имело минимальную высоту, количество узлов левого и правого поддеревьев должны максимально приближаться друг к другу. Построим дерево по этому принципу: середина каждого подраздела массива становится корневым узлом, а левая и правая части — соответствующими для него поддеревьями. Т.к. массив отсортирован, то полученное дерево соответствует определению бинарного дерева поиска.

14.Направленные и неориентированные графы

Граф - это двойка , где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно (иначе говоря, ребро --- это пара вершин). Если две вершины, связанные между собой ребром, равноправны, то графы называются неориентированными: нет никакой разницы меж ду "началом" и "концом" ребра.
Теория графов применяется, чтобы решать задачи разного типа. Например, нам нужно найти путь из одного города в другой, съездить туда и обратно или узнать стоимость перевозки. Чтобы правильно решить поставленную задачу, применяют графы разных типов.
В этом уроке разберем, какие типы графов существуют и для каких задач они подходят.
Когда мы работаем с задачей, нужно понимать, с каким типом графов работаем. Выделим три основных типа:

• 
  Неориентированные
  
• 
  Направленные
  
• 
  Взвешенные
  

Разберем каждый тип подробнее.
Неориентированные графы
Неориентированными называют графы, если между их узлами нет заданных направлений. Поэтому ребро из узла в будет идентично ребру из в :

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

Снова представим, что узлы — это города. У нас есть направление из города 1 в город 2. Получается, вы можете проехать по этому пути, но не обратно в город 1, так как нет направления обратно в город 1 из города 2. При этом у граф может быть двунаправленным. Например, города 3 и 4 имеют направления в обе стороны.