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

Материал из Вики ИТ мехмата ЮФУ
Версия от 16:26, 4 апреля 2009; Juliet (обсуждение | вклад) (Бинарные деревья поиска)

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


Лекция 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

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

<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;

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

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

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

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

Пример БДП:
Пример бинарного дерева поиска

Обойдем наше БДП с помощью инфиксного обхода:

10 15 17 27 28 32 45 50 59 64 67 71 77 80 89

Значит, при инфиксном обходе БДП получаем отсортированную последовательность данных.
Т.о. в каждый момент времени БДП хранит отсортированные данные.

Каково же количество действий при обходе БДП?
Поскольку при обходе мы проходим по каждому ребру дважды (один раз — вниз, на рекурсивном спуске, и один раз — вверх, на рекурсивном возврате), то мы тратим количество действий, в два раза превышающее количество ребер.
Т.к. количество ребер на 1 меньше количества вершин, то всего тратится <math>2(n - 1)</math> действий, где <math>n</math> — количество вершин (для сравнения: в массиве обход занимает <math>n</math> действий.

<xh4>Алгоритм добавления элемента к БДП</xh4> <xh4></xh4> <xh4></xh4>

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

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

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

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