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

Материал из Вики ИТ мехмата ЮФУ
Перейти к: навигация, поиск
Строка 15: Строка 15:
  
 
''<u>Примеры</u>.''
 
''<u>Примеры</u>.''
 +
* ''Дерево папок'' на диске <br />
 +
<tt><здесь будет рисунок></tt>
 +
* Самый очевидный пример — ''генеалогическое древо''
 +
* ''Главы и пункты книги'' <br />
 +
<tt><здесь будет рисунок></tt>
 +
* ''Дерево разбора выражений''
 +
a*b + c*d
 +
<tt><здесь будет рисунок></tt>
  
 +
Теперь дадим ''рекурсивное'' определение '''дерева''':
 +
Дерево ::= корень список_поддеревьев
 +
          | ε
 +
Список поддеревьев ::= список_поддеревьев дерево
 +
                      | ε
 +
// ε означает «пусто»
  
−
Дерево как совокупность узлов, связанных ребрами (ветвями).
+
Дерево называется '''''бинарным''''' ('''''двоичным'''''), если каждая его вершина имеет не более двух потомков. <br />
−
Корень, листья дерева.
+
(Далее бинарные деревья будем сокращать как БД)
 +
Двоичное_дерево  ::= корень левое_поддерево правое_поддерево
 +
                  | ε
 +
Левое_поддерево  ::= двоичное_дерево
 +
Правое_поддерево ::= двоичное_дерево
  
−
Примеры: главы и пункты книги, дерево разбора выражений.
+
БД называется '''''идеально сбалансированным''''', если для каждого узла количество узлов в его правом поддереве отличается от количества узлов в его левом поддереве максимум на единицу.
 +
<tt><здесь будут рисунки деревьев></tt>
  
−
Рекурсивное определение дерева
+
'''''Полным''''' называют БД, у которого каждая вершина, не являющаяся листом, имеет ровно двух потомков, и все листья находятся на последнем уровне.
  
−
Бинарные деревья. Идеально сбалансированное, полное бинарное дерево.
+
 
 +
Нетрудно заметить, что количество узлов (<tt>u</tt>) и количество ребер (<tt>v</tt>) связаны простой формулой: '''<math>u = v + 1</math>'''.
 +
 
 +
Количество узлов в ''полном БД'' высчитывается по формуле <br />
 +
<math>\ 2^{n+1} - 1</math>
 +
{{Hider
 +
|title = Доказательство
 +
|content =
 +
Действительно: <br />
 +
<tt>u<sub>0</sub> = 1 = 2<sup>0</sup></tt> <br />
 +
<tt>u<sub>1</sub> = 2 = 2<sup>1</sup></tt> <br />
 +
<tt>u<sub>2</sub> = 4 = 2<sup>2</sup></tt> <br />
 +
... <br />
 +
<tt>u<sub>n</sub> = 2<sup>n</sup></tt> <br />
 +
Значит общее количество узлов в дереве глубины n: <br />
 +
<tt>u(n)</tt> = 2<sup>0</sup> + 2<sup>1</sup> + 2<sup>2</sup> + ... + 2<sup>n</sup> <br />
 +
Узнаем геометрическую прогрессию с <tt>n + 1</tt> членами. А её сумма: <br />
 +
<math>\ S_{n+1} = b_1 \frac{q^{n+1} - 1}{q - 1} = 1 \frac{2^{n+1} - 1}{2 - 1} = 2^{n + 1} - 1</math>
 +
}}
  
 
===Порядки обхода деревьев===
 
===Порядки обхода деревьев===

Версия 17:02, 29 марта 2009


Лекция 8

Деревья

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

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

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

Примеры.

  • Дерево папок на диске

<здесь будет рисунок>

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

<здесь будет рисунок>

  • Дерево разбора выражений
a*b + c*d

<здесь будет рисунок>

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

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

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

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

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

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


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

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

Доказательство  

Действительно:
u0 = 1 = 20
u1 = 2 = 21
u2 = 4 = 22
...
un = 2n
Значит общее количество узлов в дереве глубины n:
u(n) = 20 + 21 + 22 + ... + 2n
Узнаем геометрическую прогрессию с n + 1 членами. А её сумма:
<math>\ S_{n+1} = b_1 \frac{q^{n+1} - 1}{q - 1} = 1 \frac{2^{n+1} - 1}{2 - 1} = 2^{n + 1} - 1</math>

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

  • Инфиксный (левое, корень, правое)
  • Префиксный (корень, левое, правое)
  • Постфиксный (левое, правое, корень)

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

Класс TreeNode<T>

Создание идеально сбалансированного дерева.

Вывод узлов дерева в инфиксном, префиксном, постфиксном порядке.

Связь деревьев и рекурсии.

Определение глубины дерева.

Количество листов в дереве.

Поиск элемента в дереве.

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

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

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

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

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

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

Произвольные деревья

TreeNode = class
  data: integer;
  leftChild, rightSibling: TreeNode;
end;
function CreateRandomTree(n: integer; m: integer): TreeNode;  
// n - количество сыновей, m - количество уровней
begin
  Result := nil;
  if m=0 then exit;
  for var i:=1 to n do
    Result := new TreeNode(Random(100), CreateRandomTree(Random(1,5), m-1), Result)
end;
root := CreateRandomTree(3,4);
root := new TreeNode(Random(100), root, nil);
procedure PrintTree(r: TreeNode);
begin
  while r<>nil do
  begin
    write(r.data,' ');
    PrintTree(r.leftChild);
    r := r.rightSibling;
  end
end;
Источник — «http://it.mmcs.sfedu.ru/_wiki/index.php?title=Основы_программирования_—_второй_семестр_08-09;_Михалкович_С.С.;_IV_часть&oldid=1368»