Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Data_Structure / лекц07.ppt
Скачиваний:
43
Добавлен:
03.03.2016
Размер:
199.17 Кб
Скачать

Деревья

1

Дерево- это совокупность элементов (узлов), один из которых определен как корень, и отношений, образующих иерархическую структуру узлов.

Визуально дерево- связный граф без циклов.

2

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

В- «сын» А,

A

 

«Отец» E,F,G

 

поддерево

B

C

D

E F G H I

E, F, G – «сыновья» В

J

K

 

 

A – корень дерева;

 

C, E, F, G, Н, J, K -листья.

3

Степень вершины дерева – число ее непосредственных потомков.

Степень дерева – максимальная степень всех вершин.

Сильно ветвящееся дерево- дерево

со степенью больше 2.

4

Сбалансированность дерева влияет на время поиска.

Дерево называется идеально сбалансированным, если число вершин в его левых и правых поддеревьях отличается не более чем на 1.

5

Дерево называется

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

6

Идеально сбалансированное дерево

7

Сбалансированное дерево

8

Двоичные деревья

Любой узел, кроме листьев, может иметь не более двух порожденных узлов.

9

Отображение дерева в ОП

 

A

Указа

 

Указа

 

 

А

B

C

тель

тель

на В

 

на С

Левый узел

Правый узел

10

Соседние файлы в папке Data_Structure