В этом видео мы обсудим корневые деревья. Корневым деревом называется дерево с выделенной вершиной. Выделенную вершину обычно называют корнем, и обычно корень дерева рисуют наверху, а соседей ниже, а соседей соседей — еще ниже и так далее. Давайте заведем еще несколько определений, связанных с корневым деревом. Если у нас есть вершина, например голубая вершина на картинке, то ее предком называется ее сосед, лежащий на пути от корня к этой вершине. Потомками вершины называются все остальные ее соседи, то есть предок у нас нарисован на нашей картинке обычно наверху от вершины, а потомки — ниже. Глубиной вершины называется длина простого пути из корня в эту вершину, например, у вершины, выделенной на картинке, глубина равна единице. Глубиной дерева называется наибольшая глубина его вершин. На этой картинке опять же у нас глубина вершин — максимум два, поэтому глубина дерева будет два (вершина глубины два выделена на этой картинке). Те же самые определения можно было дать и рекурсивно. Давайте это тоже обсудим. Пусть у нас есть некоторая вершина, и пусть у нас есть уже построенные корневые деревья "Т1, и так далее, Тk". Вершина на этой картинке нарисована сверху, а деревья нарисованы ниже, и в них выделены корни, поскольку это корневые деревья, то у них есть корень. Мы можем построить новое корневое дерево следующим образом: мы соединяем вершину "v" с корнями всех деревьев "Т1, и так далее, Тk", при этом "v" объявляем корнем. Все — корневое дерево построено рекурсивным способом. На самом деле, все предыдущие определения мы тоже можем перенести и на рекурсивное определение. Например, предком корней дерева "Т1, и так далее, Тk" мы объявим вершину "v" — просто мы скажем, что предками тех корней деревьев является новая вершина "v", а с другой стороны, потомками вершины "v" мы объявим корни деревьев "T1, и так далее, Tk". Потомки и предки для всех остальных вершин в новом дереве уже были определены в деревьях "T1, и так далее, Tk", поэтому мы сейчас доопределили понятие "предка" и "потомка" для вновь добавленных вершин. Дальше, глубина вершины "v" и всех остальных вершин. Для вершины "v" мы объявляем глубину просто равной нулю, а для всех остальных вершин уже была определена глубина в деревьях "T1, и так далее, Tk", и, исходя из этого, мы можем определить их новую глубину: новая глубина будет просто на единицу больше, чем та, что у них была в изначальных деревьях. Корневое дерево называется двоичным, если у каждой вершины не более двух потомков. Вот на картинке есть пример: разрешается, чтобы у вершины был один потомок, но надо, чтобы было их не больше двух. И, например, в деревьях принятия решений это соответствует ситуации, когда у вас в каждой вершине написан вопрос, на который не более двух вариантов ответа. Так что такие деревья встречаются, например, в случае рассмотрения деревьев принятия решений. Полным двоичным деревом глубины "n" называется двоичное дерево, в котором присутствуют все возможные вершины глубины "n", которые только можно построить, учитывая, что у нас есть ограничение, что дерево двоично. Это, в частности, значит, что у всех не листьев этого дерева, у всех не вершин степени один есть ровно два потомка. С двоичными деревьями удобно пометить ребра из каждой вершины двумя разными метками, например метки ноль и один; на самом деле, даже удобно помечать ребро, ведущее левее, нулем, а ребро, ведущее правее, единицей. Дальше каждую вершину также можно помечать и можно закодировать каждую вершину последовательностью нулей и единиц следующим образом: корень мы кодируем пустой последовательностью, а для каждой следующей вершины — мы ее кодируем кодом ее предка с приписанной меткой ребра. Например, у двух потомков корня коды будут такие: ноль и один (просто мы к пустой последовательности приписали ноль и один), а, например, у самого левого листа будет код "000", потому что мы попали в него из корня, пройдя по ребрам ноль, ноль и ноль. Длина последовательности, которой кодируется вершина, совпадает с ее глубиной, и листья при этом кодируются тогда последовательностями из нулей и единиц длины ровно n. Давайте обсудим какие-то простые параметры в двоичных деревьях. В полном двоичном дереве глубины "n" будет: два в степени k вершин глубины "k", потому что их столько же, сколько элементов в множестве (0, 1) в степени k (множестве всех последовательностей из нулей и единиц длины "k"), в частности, листьев в дереве — листья у нас находятся на глубине "n", их будет два в степени n. Это столько, сколько последовательностей длины "n". Сколько всего вершин в двоичном дереве? Надо просто просуммировать по всем глубинам: вершин глубины ноль у нас одна (это просто корень); вершин глубины 1, 2, и так далее, до два в степени n; вершин глубины "k" (два в степени k) будет такая сумма. И мы знаем, что такая сумма равняется два в степени "плюс один, минус один". А сколько будет ребер в полном двоичном дереве? Это легко посчитать — мы же знаем некоторые свойства деревьев. Ребер будет: (два в степени "n плюс 1" минус два), ребер на одно меньше, чем вершин. Если мы уже посчитали количество вершин, то количество ребер считается легко. Что мы узнали в этом уроке? Мы обсудили деревья — это связные графы без циклов, и оказывается, что они довольно часто встречаются на практике, а с другой стороны, обладают довольно многими важными и полезными свойствами. Что еще важно — деревья содержатся в каждом связном графе. В каждом связном графе можно выделить дерево и с ним как-то работать. Оказывается, что это удобно для некоторых алгоритмов.
