Основы программирования — второй семестр 08-09; Михалкович С.С.; IV часть

Материал из Вики ИТ мехмата ЮФУ
Версия от 11:59, 4 апреля 2009; Bravit (обсуждение | вклад) (Реализация бинарного дерева: исправление некорректных обходов дерева)

Перейти к: навигация, поиск


Лекция 8

Деревья

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

Единственная вершина на уровне 0 называется корнем дерева.
Она не имеет вершин-предков.

Вершины, не имеющие потомков, называют листьями дерева, а совокупность всех листьев образует крону дерева.

Примеры.

  • Дерево папок на диске
    Дерево папок.png
  • Самый очевидный пример — генеалогическое древо
    Генеалогическое-дерево.gif
  • Главы и пункты книги
    Содержание книги.jpg
  • Дерево разбора выражений
a*b + c*d

Дерево выражения2.png

Теперь дадим рекурсивное определение дерева:

Дерево ::= корень список_поддеревьев
         | ε 
Список поддеревьев ::= список_поддеревьев дерево
                     | ε
// ε означает «пусто»

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

Двоичное_дерево  ::= корень левое_поддерево правое_поддерево
                  | ε
Левое_поддерево  ::= двоичное_дерево
Правое_поддерево ::= двоичное_дерево

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

Полным называют БД, у которого каждая вершина, не являющаяся листом, имеет ровно двух потомков, и все листья находятся на последнем уровне.


Количество узлов (u) и количество ребер (v) в произвольном дереве связаны простой формулой: <math>u = v + 1</math>.

Количество узлов в полном БД высчитывается по формуле
<math>\ 2^{n+1} - 1</math>, где n — глубина дерева.

Порядки обхода деревьев

Требуется составить алгоритм, обходящий все узлы дерева в некотором порядке.
Существует несколько вариантов обходов, каждый из которых описывается рекурсивным алгоритмом.

Рассмотрим эти алгоритмы для обычного и бинарного деревьев:
Дерево     Бинарное дерево разбора выражений


  • Инфиксный
Д1 К Д2 Д1 К Д3 К ... К Дn
и
БД: Левое_поддерево Корень Правое_поддерево
  • Префиксный
К Д1 Д2 Д1 Д3 ... Дn
и
БД: Корень Левое_поддерево Правое_поддерево
+ * a b cпрефиксная запись выражения
Примечание. Для вычисления выражений, записанных в префиксной форме, применяется рекурсивный алгоритм.
  • Постфиксный
Д1 Д2 Д1 Д3 ... Дn К
и
БД: Левое_поддерево Правое_поддерево Корень
a b * с +обратная польская бесскобочная запись выражения

Реализация бинарного дерева

type
  TreeNode<T> = class
    data: T;
    left, right: TreeNode<T>;
  
    constructor (d: T; l, r: TreeNode<T>);
    begin
      data := d;
      left := l;
      right := r;
    end;
  end;

<xh4>Создание идеально-сбалансированного бинарного дерева</xh4>

type
  IntFunc = function: integer;

/// Возвращает идеально-сбалансированное дерево из n узлов
/// (Значения полей data определяются функцией GenerateInt)
function CreateTree(n: integer; GenerateInt: IntFunc): TreeNode<integer>;
begin
  if n <= 0 then
    Result := nil
  else
    Result := new TreeNode<integer>(
      GenerateInt(), 
      CreateTree((n-1) div 2, GenerateInt), 
      CreateTree(n - ((n-1) div 2) - 1, GenerateInt));
end;

function ReadInt: integer;
begin
  read(Result);
end;

function RandomInt: integer;
begin
  Result := Random(1, 99);
end;

<xh4> Обходы БД </xh4>

  • Инфиксный
procedure InfixPrintTree(root: TreeNode<integer>);
begin
  if root = nil then
    exit;
  
  InfixPrintTree(root.left);
  write(root.data, ' ');
  InfixPrintTree(root.right);
end;

Заметим, что кроме вывода root.data, над ним можно совершать еще массу действий (например, уменьшать на 1, или выводить его квадрат).
Поэтому есть смысл передавать в процедуру обхода выполняемое действие. Для этого определим процедурный тип и внесем в процедуру соответствующие изменения:

type
  IntAction = procedure (var data: integer);

procedure InfixTraverseTree(root: TreeNode<integer>; Action: IntAction);
begin
  if root = nil then
    exit;
  
  InfixTraverseTree(root.left, Action);
  Action(root.data);
  InfixTraverseTree(root.right, Action);
end;
  • Префиксный
procedure PrefixTraverseTree(root: TreeNode<integer>; Action: IntAction);
begin
  if root = nil then
    exit;
  
  Action(root.data);
  PrefixTraverseTree(root.left, Action);
  PrefixTraverseTree(root.right, Action);
end;
  • Постфиксный
procedure PostfixTraverseTree(root: TreeNode<integer>; Action: IntAction);
begin
  if root = nil then
    exit;
  
  PostfixTraverseTree(root.left, Action);
  PostfixTraverseTree(root.right, Action);
  Action(root.data);
end;

Замечание. Видим, что процедуры отличаются только моментом вызова Action. Поэтому можем избежать дублирования кода, написав процедуру, которой в качестве параметра также передается порядок обхода:

type
  /// Порядок обхода
  TraversalOrder = (Infix, Prefix, Postfix);

procedure TraverseTree(root: TreeNode<integer>; Action: IntAction; order: TraversalOrder := Infix);
begin
  if root = nil then
    exit;
  
  if order = Prefix then    // если префиксный порядок обхода, 
    Action(root.data);      // то сначала обрабатываем корень

  TraverseTree(root.left, Action, order);

  if order = Infix then     // если инфиксный, то корень надо обработать
    Action(root.data);      // после левого поддерева, но перед правым

  TraverseTree(root.right, Action, order);

  if order = Postfix then   // и если порядок постфиксный,
    Action(root.data);      // то корень обрабатывается последним
end;

<xh4> Связь деревьев и рекурсии </xh4> Пусть у нас есть такое бинарное дерево:
RecurTree.png
Вызовем процедуру InfixPrintTree(root).
Заметим, что её дерево рекурсивных вызовов совпадет с нашим деревом:
TraverseTree.png
Да и, вообще говоря, с ним совпадет дерево рекурсивных вызовов любой из процедур InfixPrintTree, PrefixPrintTree или PostfixPrintTree.

Сделаем несколько замечаний:

  • Форма дерева рекурсивных вызовов не зависит от порядка обхода.
  • В каждый момент времени глубина рекурсии совпадает с текущей глубиной дерева.
  • Стрелочки вниз соответствуют рекурсивному спуску, а стрелочки вверх — рекурсивному возврату.
  • Все алгоритмы на деревьях наиболее компактно записываются в рекурсивной форме.

Лекция 9

Задачи на бинарные деревья

Поиск элемента в дереве. Ну и где? )

Бинарные деревья поиска

Определение БДП.

Добавление в БДП. Инвариантность БДП относительно операции добавления.

Оценка количества операций при добавлении. Худший случай.

Сортировка деревом. Асимптотическая сложность алгоритма.

Поиск элемента в БДП.