Бинарные деревья

Бинарное дерево представляет собой структуру, в которой каждый узел (или вершина) имеет не более двух узлов-потомков и в точности одного родителя. Самый верхний узел дерева является единственным узлом без родителей; он называется корневым узлом. Бинарное дерево
с N узлами имеет не меньше [log₂N + 1] уровней (при максимально плотной упаковке узлов).
Если уровни дерева занумеровать, считая что корень лежит на уровне 1, то на уровне с номером К лежит 2^К-1 узел. У полного бинарного дерева с j уровнями (занумерованными от 1 до j) все листья лежат на уровне с номером j, и у каждого узла на уровнях с первого по j — 1
в точности два непосредственных потомка. В полном бинарном дереве с j уровнями 2^j — 1 узел.
*-Нравится статья? Кликни по рекламе! :)

Бинарные деревья поиска обычно применяются для реализации множеств и ассоциативных массивов. И применяются для быстрого поиска информации. Например в статье Двоичный (бинарный) поиск элемента в массиве мы искали во встроенной в Python структуре данных, типа list, а могли реализовать бинарное дерево. Двоичные деревья, как и связные списки, являются рекурсивными структурами.
Различные реализации одного и того же бинарного дерева

Существуют следующие разновидности бинарных деревьев:

• полное(расширенное) бинарное дерево - каждый узел, за исключением листьев, имеет по 2 дочерних узла;
• идеальное бинарное дерево - это полное бинарное дерево, в котором все листья находятся на одной высоте;
• сбалансированное бинарное дерево - это бинарное дерево, в котором высота 2-х поддеревьев для каждого узла отличается не более чем на 1. Глубина такого дерева вычисляется как двоичный логарифм log(n), где n - общее число узлов;
• вырожденное дерево - дерево, в котором каждый узел имеет всего один дочерний узел, фактически это связный список;
• бинарное поисковое дерево (BST) - бинарное дерево, в котором для каждого узла выполняется условие: все узлы в левом поддереве меньше, и все узлы в правом поддереве больше данного узла.

Вычисление путей
Путь - это расстояние от корня дерева до какого либо узла. Если число листьев полного бинарного дерева обозначить как S, а число остальных узлов обозначить как N, то справедлива формула:

S = N +1

Если путь от корневого узла до листа обозначить как внешний путь, а путь от корневого узла до НЕлиста обозначить как внутренний путь, тогда сумма всех внешних путей для дерева, изображенного на рисунке, примере полного дерева, ниже:

E=3+3+2+3+4+4+3+3=25,

а сумма внутренних путей будет равна:

I=2+1+0+2+3+1+2=11.

и тогда будет справедлива формула:

E=I+2n, где n - число узлов.

Пример расширенного дерева

Можно сформулировать следующие задачи:

1. сконструировать бинарное дерево таким образом, чтобы сумма путей была минимальной, так как это сокращает время вычислений для различных алгоритмов.
2. сконструировать полное расширенное бинарное дерево таким образом, чтобы сумма произведений путей от корневого узла до листьев на значение листового узла была минимальной.

Давид Хаффман (David Huffman) предложил алгоритм для решения этой проблемы, в котором на каждом шаге выбираются и складываются два наименьших листа, как показано в листинге 1, что приводит к дереву, изображенному на рисунке ниже.

Листинг 1. Пример алгоритма Хаффмана

2 3 5 7 11 13 17 19 23 29 31 37 41
    5 5 7 11 13 17 19 23 29 31 37 41
     10 7 11 13 17 19 23 29 31 37 41
       17    24 17 19 23 29 31 37 41
             24 34 19 23 29 31 37 41
             24 34    42 29 31 37 41
                      42 53 65 37 41
                      42 53 65    78
                         95 65    78
                         95      143
                                 238

Бинарное дерево, построенное по алгоритму Хаффмана

  Более полную статью, по кодам Хаффмана читай в моей более ранней статье.

Реализация:
До этого, в своих статьях я показывал силу функционального программирования Python.
Теперь, пришло время, показать ООП в действии, создав новую структуру данных Tree, состоящую из других структур, типа Node.
Сразу скажу, что код взят с сайта IBM с минимальными изменениями и дополнениями. С моей точки зрения данный класс является недееспособным с точки зрения добавления элементов,по причине того, что мы сами должны строить дерево, помня структуру у себя в голове, а ведь мы можем и ошибиться. И позже я напишу так, как мне кажется верным, где добавление элемента является рекурсивным проходом по дереву и поиску подходящего места. А пока, разберем, что есть:

class node:
    def __init__(self, data = None, left = None, right = None):
        self.data   = data
        self.left   = left
        self.right  = right

    def __str__(self):
        return 'Node ['+str(self.data)+']'

#/* класс, описывающий само дерево */  
class Tree:
    def __init__(self):
        self.root = None #корень дерева

# /* функция для добавления узла в дерево */
    def newNode(self, data):
        return node(data,None,None)

Дальше, все функции расширяют класс Tree.


Высота бинарного дерева
Для определения высоты дерева потребуется пройти от корня сначала по левому поддереву, потом по правому, сравнить две этих высоты и выбрать максимальное значение. И не забыть к получившемуся значению прибавить единицу (корневой элемент). Мы реализуем её в привычном уже нам рекурсивном виде.

# /* функция для вычисления высоты дерева */
    def height(self,node):
      if node==None:
          return 0
      else:
        lheight = self.height(node.left)
        rheight = self.height(node.right)
    
        if lheight > rheight:
            return(lheight+1)
        else:
          return(rheight+1)

«Зеркальное» отражение бинарного дерева
Когда два дерева являются зеркальным отражением друг друга, то говорится, что они симметричны. Для получения «зеркальной» копии дерева сначала выполняется проверка на наличие у корня дерева дочерних узлов, и если эти узлы есть, то они меняются местами. Потом эти же действия рекурсивно повторяются для левого и правого дочерних узлов. Если существует только один дочерний узел, тогда можно переходить на один уровень ниже по дереву и продолжать.

#    /* функция для зеркального отражения дерева */
    def mirrorTree(self, node):
      if  node.left and node.right:
        node.left,node.right=node.right,node.left
        self.mirrorTree(node.right)
        self.mirrorTree(node.left)
      else:
        if node.left==None and node.right:
            return self.mirrorTree(node.right)
        if node.right==None and node.left:
            return self.mirrorTree(node.left)

Проверка наличия узла в бинарном дереве
Нужно только учесть, что данная функция не работает для зеркального отображения дерева!

#    /* функция для проверки наличия узла */
    def lookup(self, node, target):
        if node == None:return 0
        else:
            if target == node.data: return 1
            else:
                if target < node.data: return self.lookup(node.left, target)
                else: return self.lookup(node.right, target)

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

# /* функция для вычисления ширины дерева */
    def getMaxWidth(self,root):
      maxWdth = 0
      i = 1
      width = 0 ;
      h = self.height(root)
      while( i< h):
        width =   self.getWidth(root, i)
        if(width > maxWdth):
            maxWdth  = width;
        i +=1    
      return maxWdth;

    def getWidth(self, root, level):
      if root == None:
        return 0
      if level == 1: 
        return 1
      elif level > 1:
          return self.getWidth(root.left, level-1) +  self.getWidth(root.right, level-1)

Распечатка дерева:

# /* функция для распечатки элементов на определенном уровне дерева */
    def printGivenLevel(self, root, level):
      if root == None:
        return
      if level == 1:
        print ("%d " % root.data)
      elif level > 1:
          self.printGivenLevel(root.left, level-1);
          self.printGivenLevel(root.right, level-1);


# /* функция для распечатки дерева */
    def printLevelOrder(self, root):
      h = self.height(self.root)
      i=1
      while(i<=h):
        self.printGivenLevel(self.root, i)
        i +=1

Сравнение бинарных деревьев
Вынесите её за пределы класса только)

def sameTree(a, b):
    if a==None and b==None: return 1
    elif a and b:
        return(
                a.data == b.data and
                sameTree(a.left, b.left) and
                sameTree(a.right, b.right)
                )
    return 0

Количество узлов в бинарном дереве
Вычислить количество узлов в бинарном дереве также можно с помощью рекурсии.
Хотя с точки зрения производительности и принципов ООП, правильнее встроить счетчик в сам объект.

def size(node):
    if node==None:return 0;
    return(size(node.left) + 1 + size(node.right));

Немножко о производительности
Я протестировал наш класс на поиск. К сожалению, данная его реализация проиграла бинарному поиску по списку, описанному ранее. Я тестировал, запуская в 100000 цикле поиска элемента со значением 5 и результат нашего класса
400003 function calls (100003 primitive calls) in 3.481 seconds
против
200003 function calls in 1.791 seconds
Я считаю, что причина в рекурсивном исполнении данного метода + реализации на Python, а не Си)

Вывод:
Организация данных с помощью бинарных деревьев часто позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов, присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени. Максимальное число шагов при поиске по дереву равно высоте данного дерева, т.е. количеству уровней в иерархической структуре дерева.
Вот и все, в заключение хочу сказать, что если какие то вопросы не раскрыты, не понятны или не оптимальны, просьба не стесняться и писать в комментариях!)
Используемая литература:

1. Дж. Макконнелл - Основы современных алгоритмов.
2. Структуры данных: бинарные деревья. Часть 1
3. Работа со структурами данных в языках Си и Python: Часть 6. Двоичные деревья
4. Может быть полезным Обходы бинарных деревьев