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

Сентябрь 7, 2022

Главная
Алгебра
Двоичные деревья

Содержание

2. Определение (рекурсивное) 1. Одиночная вершина есть двоичное дерево. 2. Двоичное дерево – это вершина (V), соединенная
3. Пример двоичного дерева Кружочками обозначены вершины дерева, стрелками - связи между вершинами.
4. Высота дерева (h) определяется как число вершин в самой длинной ветви дерева. Начальная вершина называется корнем.
5. Словарь tree [три] – дерево root [рут] – корень vertex [вётэкс] – вершина right [райт] –
6. Свойство 1: Максимальное число вершин в двоичном дереве высоты h равно nmax(h)= 2h – 1 Доказательство:
7. Свойство 2: Минимально возможная высота двоичного дерева с n вершинами равна hmin(n) = ⎡log(n+1)⎤ Доказательство: Из
8. Определение Двоичное дерево называют идеально сбалансированным (ИСД), если для каждой его вершины размеры левого и правого
9. Пример
10. Свойство 3: Высота ИСД с n вершинами минимальна. hисд(n) = hmin(n) = ⎡log(n+1)⎤
11. Каждая вершина содержит данные и указатели на вершину слева и справа. В качестве заголовка для дерева
12. Структура вершины дерева struct Vertex { int Data; Vertex * Left; Vertex * Right; } ;
13. Графическое представление
14. Существует много работ, которые можно выполнять с деревьями. Например, посадка, подкормка, подстрижка, полив, окучивание и т.п.
15. Основные операции с деревьями Определение. Обход дерева – выполнение некоторой операции с каждой его вершиной. Существуют
16. Обходы легко программируются с помощью рекурсивных процедур. Пример. Процедура обхода дерева сверху вниз. void Obhod1 (
17. Пример. Обходы дерева Корень, левое, правое. Левое, корень, правое. Левое, правое, корень. (↓): 1 2 4
18. (↓): 1 3 2 4 5 6 (→): 1 2 3 6 5 4 (↑): 2
19. 3.9. Деревья поиска Двоичные деревья часто используются для представления данных, среди которых идет поиск элементов по
20. Определение. Двоичное дерево называется деревом поиска, если ключ в каждой его вершине больше ключей в левом
21. 3.9.1. Поиск вершины с ключом Х Начиная с корневой вершины дерева, сравниваем ключ поиска с данными
22. Поиск вершины с ключом Х Алгоритм на псевдокоде p := Root DO (p != NULL) IF
23. Трудоемкость поиска по дереву Максимальное количество сравнений при поиске: Cmax =2h Идеально сбалансированное дерево: Cmax= 2
24. Построение ИСДП из элементов массива А = (a1, a2 ,…, an): Отсортировать массив по возрастанию. Построить
25. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
26. Построение ИСДП Алгоритм на псевдокоде Vertex* ISDP (L,R) IF (L>R) return NULL; ELSE m := ⎡(L+R)/2⎤
27. В реальности количество элементов данных заранее неизвестно и они поступают последовательно в произвольном порядке. Требуется строить
28. Случайные деревья поиска. Все преимущества деревьев реализуются именно тогда, когда меняется их структура в ходе выполнения
29. Пример: Мама мыла раму, Маша ела кашу. слово частота Мама 1 Ела 1 Мыла 1 Раму
30. Построение СДП Идея: построение выполняется путем добавления новых вершин в дерево. Если дерево пустое, то создать
31. B 9 2 4 1 7 E F A D C 3 5 8 6
32. При создании новой вершины нужно изменить значение указателя на неё, поэтому нам нужен указатель на указатель
33. Обозначения: Root - корень, D – данные, p - указатель на указатель Добавить (данные D в
34. Хотя назначение этого алгоритма - поиск с включением, его можно использовать и для сортировки. Если мы
35. 5’ 1’ 2’ 4 3 2” 1” 6 5” 7 1’ 1” 2’ 2” 3 4
36. Случайное дерево быстро строится, но его недостаток: оно может слишком вытянуться, в худшем случае выродиться в
39. Скачать презентацию

Слайд 2

Определение (рекурсивное)
1. Одиночная вершина есть двоичное дерево.
2. Двоичное дерево – это вершина (V),

соединенная с (возможно, пустыми) левым (ТL) и правым (ТR) двоичными деревьями.

Слайд 3

Пример двоичного дерева
Кружочками обозначены вершины дерева, стрелками - связи между

вершинами.

Слайд 4

Высота дерева (h) определяется как число вершин в самой длинной

ветви дерева.

Начальная вершина называется корнем.

Оконечные вершины, не имеющие поддеревьев, называются листьями.

Ребра ориентированы по направлению от корня к листьям. Путь от корня к листу называется ветвью.

Под длиной ветви будем понимать число входящих в неё вершин.

Размер дерева – число входящих в него вершин.

Каждая вершина дерева может содержать какую-либо информацию.

Слайд 5

Словарь
tree [три] – дерево
root [рут] – корень
vertex [вётэкс] – вершина
right [райт]

– правый
left [лэфт] – левый

Слайд 6

Свойство 1:
Максимальное число вершин в двоичном дереве высоты h равно
nmax(h)=

2h – 1
Доказательство:
на первом уровне 1 = 2º вершин
на втором уровне 2 = 2¹ вершин
на третьем уровне 4 = 2² вершин
на h уровне 2h-1 вершин
nmax = 1 + 2 + ... + 2h-1 = 2h — 1

3.8.2. Некоторые свойства деревьев

Слайд 7

Свойство 2:
Минимально возможная высота двоичного дерева с n

вершинами равна
hmin(n) = ⎡log(n+1)⎤
Доказательство:
Из свойства 1 имеем h = log (nmax + 1)

Слайд 8

Определение
Двоичное дерево называют идеально сбалансированным (ИСД), если для каждой его

вершины размеры левого и правого поддеревьев отличаются не более чем на 1.
ИСД сбалансировано по количеству вершин.

Слайд 9

Пример

Слайд 10

Свойство 3:
Высота ИСД с n вершинами минимальна.
hисд(n)

= hmin(n) = ⎡log(n+1)⎤

Слайд 11

Каждая вершина содержит данные и указатели на вершину слева и

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

3.8.3. Представление деревьев в памяти компьютера

Слайд 12

Структура вершины дерева
struct Vertex
{ int Data;
Vertex * Left;

Vertex * Right;
} ;
Vertex * Root;

Слайд 13

Графическое представление

Слайд 14

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

полив, окучивание и т.п.
Распространенная задача – выполнение некоторой определенной операции с каждой вершиной дерева.
Для этого необходимо «посетить» все вершины дерева, или, как обычно говорят, сделать обход дерева.

3.8.4. Основные операции с деревьями

Слайд 15

Основные операции с деревьями
Определение. Обход дерева – выполнение некоторой операции с

каждой его вершиной.
Существуют
три основных порядка обхода дерева:
1. Сверху вниз (↓): корень, левое поддерево,
правое поддерево.
2. Слева направо (→): левое поддерево, корень,
правое поддерево.
3. Снизу вверх (↑): левое поддерево, правое
поддерево, корень.

Слайд 16

Обходы легко программируются с помощью рекурсивных процедур.
Пример. Процедура обхода дерева сверху

вниз.
void Obhod1 ( Vertex *p )
IF ( p!=NULL )
< печать (p->Data) >
Obhod1 ( p->Left )
Obhod1 ( p->Right )
FI
Вызов процедуры: Obhod1 (Root)
Чтобы изменить порядок обхода, нужно
поменять местами операторы внутри функции.

Слайд 17

Пример. Обходы дерева
Корень, левое, правое.
Левое, корень, правое.
Левое, правое, корень.
(↓): 1 2

4 5 3 6
(→): 4 2 5 1 3 6
(↑): 4 5 2 6 3 1

Максимальная глубина рекурсии при обходе = h

Слайд 18

(↓): 1 3 2 4 5 6
(→): 1 2 3 6

5 4
(↑): 2 6 5 4 3 1

(↓): 1 2 3 5 6 4
(→): 3 6 5 2 4 1
(↑): 6 5 3 4 2 1

Слайд 19

3.9. Деревья поиска
Двоичные деревья часто используются для представления данных, среди которых

идет поиск элементов по уникальному ключу.
Будем считать, что:
часть данных в каждой вершине является ключом поиска;
для всех ключей определены операции сравнения (<,>,=);
в дереве нет элементов с одинаковыми ключами.

Слайд 20

Определение. Двоичное дерево называется деревом поиска, если ключ в каждой его

вершине больше ключей в левом поддереве и меньше ключей в правом поддереве.
Пример. Двоичное дерево поиска.

Слайд 21

3.9.1. Поиск вершины с ключом Х
Начиная с корневой вершины дерева, сравниваем

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

Слайд 22

Поиск вершины с ключом Х Алгоритм на псевдокоде
p := Root
DO (p !=

NULL)
IF (X < p->Data) p := p->Left
ELSE IF (X > p->Data) p := p->Right
ELSE OD
FI
FI
OD
IF (p != NULL) <вершина найдена по адресу р>
ELSE <вершины нет дереве>
FI

Слайд 23

Трудоемкость поиска по дереву
Максимальное количество сравнений при поиске: Cmax =2h
Идеально

сбалансированное дерево:
Cmax= 2 ⎡log(n+1)⎤
Будем считать, что все вершины ищутся одинаково часто. Тогда идеально сбалансированное дерево поиска (ИСДП) обеспечивает минимальное среднее время поиска:
Т = О(log2n)

Слайд 24

Построение ИСДП
из элементов массива А = (a1, a2 ,…, an):
Отсортировать

массив по возрастанию.
Построить ИСДП, пользуясь свойством:
Если дерево идеально сбалансировано,
то все его поддеревья тоже идеально
сбалансированы.
Идея построения ИСДП: В качестве корня возьмем средний элемент упорядоченного массива, из меньших элементов строим левое поддерево, из больших – правое поддерево.

Слайд 25

1 2 3 4 5 6 7 8 9 10 11

12 13 14 15

Слайд 26

Построение ИСДП
Алгоритм на псевдокоде
Vertex* ISDP (L,R)
IF (L>R) return NULL;
ELSE

m := ⎡(L+R)/2⎤
<выделение памяти по адресу р>
p->Data := A[m]
p->Left := ISDP (L, m-1)
p->Right := ISDP (m+1, R)
return p
FI

Слайд 27

В реальности количество элементов данных заранее неизвестно и они поступают последовательно

в произвольном порядке.
Требуется строить деревья поиска путем добавления новых вершин, так же необходимо предусмотреть удаление вершин.
Все операции могут чередоваться с поиском и должны выполняться как можно быстрее.
Решение этих задач мы будем рассматривать в дальнейшем.

Слайд 28

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

структура в ходе выполнения программы.
Рассмотрим случай, когда дерево только растет.
Пример – построение словаря частот встречаемости слов в тексте.
Каждое слово надо искать в дереве. Если его нет, то слово добавляется с частотой, равной 1. Если слово найдено в дереве, то увеличиваем частоту на 1.
Эту задачу часто называют поиском по дереву с включением.
Форма дерева определяется случайным порядком поступления элементов.

Слайд 29

Пример:
Мама мыла раму, Маша ела кашу.
слово частота
Мама 1
Ела 1
Мыла 1
Раму

Маша 1

Кашу 1

Слайд 30

Построение СДП
Идея: построение выполняется путем добавления новых вершин в дерево.
Если

дерево пустое, то создать вершину (распределить память) и записать в неё данные. Указатели Left и Right обнуляются.
Если дерево не пустое, то вершина добавляется к левому или правому поддереву в зависимости от соотношения с данными текущей вершины.

Слайд 31

B 9 2 4 1 7 E F A D C

3 5 8 6

Слайд 32

При создании новой вершины нужно изменить значение указателя на неё,

поэтому нам нужен указатель на указатель (двойная косвенность): Vertex**p; Обращение к данным (*p)->Data;

Root

NULL

Root

P=&Root

Слайд 33

Обозначения: Root - корень, D – данные,
p - указатель

на указатель
Добавить (данные D в дерево с корнем Root)
p=&Root
DO(*p!=NULL) // поиск элемента
IF (D<(*p)->Data) p=&((*p)->Left)
ELSE IF (D>(*p)->Data) p=&((*p)->Right)
ELSE OD {данные уже есть в дереве}
FI
FI
OD
IF (*p=NULL)
память(*p), (*p)->Data=D;
(*p)->Left=NULL; (*p)->Right=NULL;
FI

Слайд 34

Хотя назначение этого алгоритма - поиск с включением, его можно использовать

и для сортировки.
Если мы хотим сортировать данные
с помощью двоичного дерева, то
одинаковые элементы нужно добавлять
вправо для сохранения устойчивости сортировки.

Слайд 35

5’ 1’ 2’ 4 3 2” 1” 6 5” 7
1’ 1”

2’ 2” 3 4 5’ 5” 6 7

Слайд 36

Случайное дерево быстро строится, но его недостаток: оно может слишком вытянуться,

в худшем случае выродиться в список.
1 2 3 4 5
5 1 2 4 3

Максимальная высота дерева: hmax = n

Слайд 37

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

Содержание

Определение (рекурсивное)1. Одиночная вершина есть двоичное дерево.2. Двоичное дерево – это вершина (V),

Пример двоичного дерева Кружочками обозначены вершины дерева, стрелками - связи между

Высота дерева (h) определяется как число вершин в самой длинной

Словарьtree [три] – деревоroot [рут] – кореньvertex [вётэкс] – вершинаright [райт]

Свойство 1: Максимальное число вершин в двоичном дереве высоты h равно nmax(h)=

Свойство 2: Минимально возможная высота двоичного дерева с n

Определение Двоичное дерево называют идеально сбалансированным (ИСД), если для каждой его

Пример

Свойство 3: Высота ИСД с n вершинами минимальна. hисд(n)

Каждая вершина содержит данные и указатели на вершину слева и

Структура вершины дерева struct Vertex { int Data; Vertex * Left;

Графическое представление

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

Основные операции с деревьямиОпределение. Обход дерева – выполнение некоторой операции с

Обходы легко программируются с помощью рекурсивных процедур.Пример. Процедура обхода дерева сверху

Пример. Обходы дереваКорень, левое, правое.Левое, корень, правое.Левое, правое, корень.(↓): 1 2

(↓): 1 3 2 4 5 6(→): 1 2 3 6

3.9. Деревья поискаДвоичные деревья часто используются для представления данных, среди которых