Информатика

Константин Кориков

Тема 12

Деревья

Агенда

Как устроено дерево
Обход дерева
Двоичное дерево поиска
Ассоциативные контейнеры

Как устроено дерево

Дерево

Термины

Бинарное (двоичное) дерево

Пример дерева

Дерево каталогов файловой системы

## Свойства бинарных деревьев Максимальное число узлов на уровне `$l$` бинарного дерева равно `$2^l$`

## Свойства бинарных деревьев Максимальное число узлов в бинарном дереве высоты `$h$` равно `$2^{h+1}-1$`

## Свойства бинарных деревьев Высота бинараного дерева из `$N$` узлов лежит в диапазоне `$\log_2(N+1)-1 \leq h \leq N-1$`

## Свойства бинарных деревьев Непустое бинараное дерево из `$N$` узлов имеет `$N-1$` рёбер

## Свойства бинарных деревьев В бинарном дереве листьев на 1 больше, чем узлов второй степени

Операции

Обход дерева

Прямой обход в глубину

Узел → Левый → Правый

F, B, A, D, C, E, G, I, H

Симметричный обход в глубину

Левый → Узел → Правый

A, B, C, D, E, F, G, H, I

Обратный обход в глубину

Левый → Правый → Узел

A, C, E, D, B, H, I, G, F

Обход в ширину

Breadth-first search, BFS

F, B, G, A, D, I, C, E, H

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

## Свойство бинарного дерева поиска Пусть `$x$` представляет собой значение узла бинарного дерева поиска. Если `$y$` является значением узла в левом поддереве `$x$`, то `$y \le x$`. Если `$y$` является значением узла в правом поддереве `$x$`, то `$y \ge x$`

Свойство бинарного дерева поиска

Обход по узлам в отсортированном виде — симметричный обход в глубину

Бинарное

дерево поиска

Ассоциативные контейнеры

на деревьях