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

Версия 16:15, 4 апреля 2009

Лекция 8

Деревья

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

Количество уровней называется глубиной дерева.
Каждая вершина нижнего уровня соединяется ровно с одной вершиной предыдущего уровня.

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

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

Примеры.

• Дерево папок на диске
  
• Самый очевидный пример — генеалогическое древо
  
• Главы и пункты книги
  
• Дерево разбора выражений

a*b + c*d

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

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

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

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

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

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

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

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

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

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

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

• Инфиксный

Д₁ К Д₂ Д₁ К Д₃ К ... К Д_n

и

БД: Левое_поддерево Корень Правое_поддерево

• Префиксный

К Д₁ Д₂ Д₁ Д₃ ... Д_n

и

БД: Корень Левое_поддерево Правое_поддерево

+ * a b c — префиксная запись выражения

Примечание. Для вычисления выражений, записанных в префиксной форме, применяется рекурсивный алгоритм.

• Постфиксный

Д₁ Д₂ Д₁ Д₃ ... Д_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> Пусть у нас есть такое бинарное дерево:

Вызовем процедуру InfixPrintTree(root).
Заметим, что её дерево рекурсивных вызовов совпадет с нашим деревом:

Да и, вообще говоря, с ним совпадет дерево рекурсивных вызовов любой из процедур InfixPrintTree, PrefixPrintTree или PostfixPrintTree.

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

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

Лекция 9

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

<xh4>Поиск элемента в бинарном дереве</xh4>

function Find(root: TreeNode<integer>; k: integer): TreeNode<integer>;
begin
  if root = nil then
  begin
    Result := nil;
    exit;
  end;

  if root.data = k then  // если нашли элемент, то возвращаем его и прекращаем поиск
  begin                  
    Result := root;
    exit;              
  end;

  // ищем элемент в левом поддереве
  Result := Find(root.left, k);

  // если не нашли в левом поддереве, то ищем в правом
  if Result = nil then             
    Result := Find(root.right, k);
end;

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

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

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

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

Пример БДП:

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

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

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

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