Введение в деревья

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

Дерево и его свойства

Определение - Дерево - это связный ациклический неориентированный граф. Между каждой парой вершин в $ G $ существует уникальный путь. Дерево с N числом вершин содержит $ (N-1) $ число ребер. Вершина, которая имеет 0 градусов, называется корнем дерева. Вершина, имеющая 1 градус, называется листовым узлом дерева, а степень внутреннего узла составляет не менее 2.

Пример . Ниже приведен пример дерева.

дерево

Центры и Би-Центры Дерева

Центр дерева - это вершина с минимальным эксцентриситетом. Эксцентриситет вершины $ X $ в дереве $ G $ - это максимальное расстояние между вершиной $ X $ и любой другой вершиной дерева. Максимальный эксцентриситет - диаметр дерева. Если у дерева есть только один центр, оно называется Центральным деревом, а если у дерева всего несколько центров, оно называется Би-центральным деревом. Каждое дерево является либо центральным, либо двухцентральным.

Алгоритм нахождения центров и бицентров дерева

Шаг 1 - Удалите все вершины степени 1 из данного дерева, а также удалите их падающие ребра.

Шаг 2 - Повторяйте шаг 1, пока не останется одна вершина или две вершины, соединенные ребром. Если осталась одна вершина, то это центр дерева, а если осталось две вершины, соединенные ребром, то это бицентр дерева.

Проблема 1

Узнайте центр / би-центр следующего дерева -

Дерево 1

Решение

Сначала мы удалим все вершины степени 1, а также удалим их инцидентные ребра и получим следующее дерево:

Tree1 Solution

Опять же, мы удалим все вершины степени 1, а также удалим их инцидентные ребра и получим следующее дерево:

Решение Tree 1 Удаление вершины

Наконец, мы получили одну вершину «c» и остановили алгоритм. Поскольку существует одна вершина, у этого дерева есть один центр 'c', и дерево является центральным деревом.

Проблема 2

Узнайте центр / би-центр следующего дерева -

Дерево2

Решение

Сначала мы удалим все вершины степени 1, а также удалим их инцидентные ребра и получим следующее дерево:

Tree 2 Solution

Опять же, мы удалим все вершины степени 1, а также удалим их инцидентные ребра и получим следующее дерево:

Решение Tree 2 Удаление вершины

Наконец, у нас осталось две вершины 'c' и 'd', поэтому мы останавливаем алгоритм. Поскольку оставлены две вершины, соединенные ребром, это дерево имеет двухцентровый «cd», а дерево является двухцентровым.

Маркированные деревья

Определение - помеченное дерево - это дерево, вершинам которого присваиваются уникальные номера от 1 до n. Мы можем посчитать такие деревья для малых значений n вручную, чтобы предположить общую формулу. Число помеченных деревьев из n вершин равно $ n ^ {n-2} $. Два помеченных дерева изоморфны, если их графы изоморфны, а соответствующие точки двух деревьев имеют одинаковые метки.

пример

Помеченное дерево с двумя вершинамиТри возможных помеченных дерева с тремя вершинами

Немеченые деревья

Определение - немеченое дерево - это дерево, вершинам которого не назначены никакие числа. Число помеченных деревьев с n числом вершин равно $ \ frac {(2n)!} {(N + 1)! N! } $ (n- е каталонское число)

пример

Немеченое деревоНемеченое дерево с тремя вершинамиДва возможных немеченых дерева с четырьмя вершинами

Укорененное дерево

Корневое дерево $ G $ - это связный ациклический граф со специальным узлом, который называется корнем дерева, и каждое ребро прямо или косвенно происходит от корня. Упорядоченное корневое дерево - это корневое дерево, в котором упорядочены дочерние элементы каждой внутренней вершины. Если каждая внутренняя вершина корневого дерева имеет не более m дочерних элементов, она называется m-арным деревом. Если каждая внутренняя вершина корневого дерева имеет ровно m детей, она называется полным m-арным деревом. Если $ m = 2 $, корневое дерево называется бинарным деревом.

Укорененное дерево

Двоичное дерево поиска

Двоичное дерево поиска - это двоичное дерево, которое удовлетворяет следующему свойству:

  • $ X $ в левом поддереве вершины $ V, Value (X) \ le Value (V) $
  • $ Y $ в правом поддереве вершины $ V, Value (Y) \ ge Value (V) $

Таким образом, значение всех вершин левого поддерева внутреннего узла $ V $ меньше или равно $ V $, а значение всех вершин правого поддерева внутреннего узла $ V $ больше или равно $ V $. Количество ссылок от корневого узла к самому глубокому узлу является высотой дерева двоичного поиска.

пример

Двоичное дерево поиска

Алгоритм поиска ключа в BST

BST_Search(x, k) 
if ( x = NIL or k = Value[x] ) 
   return x; 
if ( k < Value[x]) 
   return BST_Search (left[x], k); 
else  
   return BST_Search (right[x], k)  

Сложность бинарного дерева поиска

Средний случай Худший случай
Космическая сложность На) На)
Сложность поиска O (log n) На)
Сложность вставки O (log n) На)
Сложность удаления O (log n) На)