Двоичное дерево

Двоичное дерево

 jupiter notebook

1) пустая структура — это двоичное дерево;

2) двоичное дерево — это корень и два связанных с ним отдельных двоичных дерева (левое и правое поддеревья).

Приминение:

• поиск в большом массиве данных;
• сортировка данных;
• вычисление арифметических выражений;
• оптимальное кодирование данных (метод сжатия Хаффмана)

Опишем дерево из примера с помощью словаря Python:

In [60]:

tree = {
    'val': 6,
    'right':{
        'val': 8,
        'right': { 'val': 9, 'right': {}, 'left': {} },
        'left': { 'val': 7, 'right': {}, 'left': {} } },
    'left':{
        'val': 3,
        'right': { 'val': 4, 'right': {}, 'left': {} },
        'left': { 'val': 1, 'right': {}, 'left': {} } } }

Обход и вывод дерева

Обойти дерево — это значит «посетить» все узлы по одному разу. Существуют несколько способов обхода двоичного дерева. Например: "правый — корень — левый" (симметричный обход):

• обойти правое поддерево
• посетить корень
• обойти левое поддерево

Как видим, это рекурсивные алгоритм. Он должн заканчиваться без повторного вызова, когда текущий корень — пустое дерево. При выводе элементов, обход будем сочетать с выводом отступа '\t' - n раз:

In [61]:

def OutTree(x,n):
    if x:
        OutTree( x['right'], n+1 )
        print( '\t'*n,x['val'] )
        OutTree( x['left'], n+1 )
OutTree(tree,0)

       9
   8
       7
6
       4
   3
       1

Деревья поиска

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

Дерево сбалансировано - когда для каждой его вершины высота левого и правого поддеревьев различается не более чем на единицу. Если при линейном поиске в массиве за одно сравнение отсекается 1 элемент, здесь — сразу примерно половина оставшихся. Алгоритм поиска имеет асимптотическую сложность 
$O(lo{g}_{2}N)$

In [24]:

def FindInTree(x,y,n): # x - элемент, y - дерево, n - кол-во шагов
    if y:
        if x==y['val']:

          print('Элемент',x,'найден за',n, 

                n>4 and 'шагов' or 

                n>1 and 'шага' or'шаг')

        elif x<y['val']: FindInTree(x,y['left'],n+1)
        else: FindInTree(x,y['right'],n+1)
    else:

      print('Элемент',x,'не найден. Проверено за',n, 

                n>4 and 'шагов' or 

                n>1 and 'шага' or'шаг')

FindInTree( 8, tree, 0)
FindInTree( 5, tree, 0)
FindInTree( 4, tree, 0)

Элемент 8 найден за 1 шаг
Элемент 5 не найден. Проверено за 3 шага
Элемент 4 найден за 2 шага

Вычисление арифметических выражений

Сначала выражение, записанное в линейном виде (в одну строку), нужно "разобрать" и построить соответствующее ему дерево. Затем в результате прохода по этому дереву от листьев к корню вычисляется результат. Пример: 40 - 2 3 - 4 5 В корень дерева нужно поместить последнюю из операций с наименьшим приоритетом.

Алгоритм построения дерева:

• найти последнюю выполняемую операцию
• if операций нет:
• создать узел-лист (число)
• return
• поместить найденную операцию в корень дерева
• построить левое поддерево
• построить правое поддерево

Программа получения дерева Tree из строки s:

In [145]:

def prt(x): # Функция определения приоритета:
             # "число" - 3; "+-" - 1 или "*/" - 2
    return (x in '+-') and 1 or (x in '*/') and 2 or 3

def last(s): # Функция определения последней операции (минимального приоретета)
             # В какой позиции строки s она находиться
    minPtr=3; k=3
    for i in range(len(s)):
        if prt(s[i])<=minPtr:
            minPtr=prt(s[i])
            k=i
    return k

def makeTree(s):
    y={}
    if any(s):
        k = last(s)
        y['val'] = s[k]
        y['left'] = makeTree( s[ :k] )
        y['right'] = makeTree( s[k+1: ] )
    return y
s = '40 - 2 * 3 - 4 * 5'.split()
Tree = makeTree(s)
OutTree(Tree,0)

   
         5
    *
         4
-
         3
     *
         2
     -
         40

Теперь вычислим выражение по дереву. Если в корне нахо- дится знак операции, её нужно применить к результатам вычисления поддеревьев:

• n1 = значение левого поддерева
• n2 = значение правого поддерева
• результат = операция (n1, n2)

In [147]:

def calcTree(x):
    if x['left']:
        n1 = calcTree(x['left'])
        n2 = calcTree(x['right'])
        op = x['val']
        return op=="+"and n1+n2 or op=="-"and n1-n2 or op=="*"and n1*n2 or n1//n2
    else: return int(x['val'])
calcTree(Tree)

Out[147]:

14