🗊Презентация Двоичные деревья

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Двоичные деревья, слайд №1Двоичные деревья, слайд №2Двоичные деревья, слайд №3Двоичные деревья, слайд №4Двоичные деревья, слайд №5Двоичные деревья, слайд №6Двоичные деревья, слайд №7Двоичные деревья, слайд №8Двоичные деревья, слайд №9Двоичные деревья, слайд №10Двоичные деревья, слайд №11Двоичные деревья, слайд №12Двоичные деревья, слайд №13Двоичные деревья, слайд №14Двоичные деревья, слайд №15Двоичные деревья, слайд №16Двоичные деревья, слайд №17Двоичные деревья, слайд №18Двоичные деревья, слайд №19Двоичные деревья, слайд №20Двоичные деревья, слайд №21Двоичные деревья, слайд №22Двоичные деревья, слайд №23Двоичные деревья, слайд №24Двоичные деревья, слайд №25Двоичные деревья, слайд №26Двоичные деревья, слайд №27Двоичные деревья, слайд №28Двоичные деревья, слайд №29Двоичные деревья, слайд №30Двоичные деревья, слайд №31Двоичные деревья, слайд №32Двоичные деревья, слайд №33Двоичные деревья, слайд №34Двоичные деревья, слайд №35Двоичные деревья, слайд №36Двоичные деревья, слайд №37Двоичные деревья, слайд №38
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Двоичные деревья. Доклад-сообщение содержит 38 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


3.8. ДВОИЧНЫЕ ДЕРЕВЬЯ 3.8.1. Основные определения
Описание слайда:
3.8. ДВОИЧНЫЕ ДЕРЕВЬЯ 3.8.1. Основные определения

Слайд 2


Определение (рекурсивное) 1. Одиночная вершина есть двоичное дерево. 2. Двоичное дерево – это вершина (V), соединенная с (возможно, пустыми) левым (ТL) и правым (ТR) двоичными деревьями.
Описание слайда:
Определение (рекурсивное) 1. Одиночная вершина есть двоичное дерево. 2. Двоичное дерево – это вершина (V), соединенная с (возможно, пустыми) левым (ТL) и правым (ТR) двоичными деревьями.

Слайд 3


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

Слайд 4


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

Слайд 5


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

Слайд 6


3.8.2. Некоторые свойства деревьев Свойство 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. Некоторые свойства деревьев Свойство 1: Максимальное число вершин в двоичном дереве высоты h равно nmax(h)= 2h – 1 Доказательство: на первом уровне 1 = 2º вершин на втором уровне 2 = 2¹ вершин на третьем уровне 4 = 2² вершин на h уровне 2h-1 вершин nmax = 1 + 2 + ... + 2h-1 = 2h — 1

Слайд 7


Свойство 2: Свойство 2: Минимально возможная высота двоичного дерева с n вершинами равна hmin(n) = log(n+1) Доказательство: Из свойства 1 имеем h = log (nmax + 1)
Описание слайда:
Свойство 2: Свойство 2: Минимально возможная высота двоичного дерева с n вершинами равна hmin(n) = log(n+1) Доказательство: Из свойства 1 имеем h = log (nmax + 1)

Слайд 8


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

Слайд 9


Пример
Описание слайда:
Пример

Слайд 10


Свойство 3: Свойство 3: Высота ИСД с n вершинами минимальна. hисд(n) = hmin(n) = log(n+1)
Описание слайда:
Свойство 3: Свойство 3: Высота ИСД с n вершинами минимальна. hисд(n) = hmin(n) = log(n+1)

Слайд 11


3.8.3. Представление деревьев в памяти компьютера Каждая вершина содержит данные и указатели на вершину слева и справа. В качестве заголовка для дерева используем переменную Root, указывающую на корень.
Описание слайда:
3.8.3. Представление деревьев в памяти компьютера Каждая вершина содержит данные и указатели на вершину слева и справа. В качестве заголовка для дерева используем переменную Root, указывающую на корень.

Слайд 12


Структура вершины дерева struct Vertex { int Data; Vertex * Left; Vertex * Right; } ; Vertex * Root;
Описание слайда:
Структура вершины дерева struct Vertex { int Data; Vertex * Left; Vertex * Right; } ; Vertex * Root;

Слайд 13


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

Слайд 14


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

Слайд 15


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

Слайд 16


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

Слайд 17


Пример. Обходы дерева Корень, левое, правое. Левое, корень, правое. Левое, правое, корень.
Описание слайда:
Пример. Обходы дерева Корень, левое, правое. Левое, корень, правое. Левое, правое, корень.

Слайд 18


Двоичные деревья, слайд №18
Описание слайда:

Слайд 19


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

Слайд 20


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

Слайд 21


3.9.1. Поиск вершины с ключом Х Начиная с корневой вершины дерева, сравниваем ключ поиска с данными в текущей вершине. Если ключ поиска меньше, то переходим в левое поддерево, если ключ поиска больше, то переходим в правое поддерево. Действуем аналогично, пока не будет найден элемент с заданным ключом или листовая вершина дерева. Если достигнута листовая вершина, то искомого элемента нет в дереве.
Описание слайда:
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
Описание слайда:
Поиск вершины с ключом Х Алгоритм на псевдокоде 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)
Описание слайда:
Трудоемкость поиска по дереву Трудоемкость поиска по дереву Максимальное количество сравнений при поиске: Cmax =2h Идеально сбалансированное дерево: Cmax= 2 log(n+1) Будем считать, что все вершины ищутся одинаково часто. Тогда идеально сбалансированное дерево поиска (ИСДП) обеспечивает минимальное среднее время поиска: Т = О(log2n)

Слайд 24


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

Слайд 25


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Описание слайда:
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
Описание слайда:
Построение ИСДП Построение ИСДП Алгоритм на псевдокоде 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. Эту задачу часто называют поиском по дереву с включением. Форма дерева определяется случайным порядком поступления элементов.
Описание слайда:
Случайные деревья поиска. Все преимущества деревьев реализуются именно тогда, когда меняется их структура в ходе выполнения программы. Рассмотрим случай, когда дерево только растет. Пример – построение словаря частот встречаемости слов в тексте. Каждое слово надо искать в дереве. Если его нет, то слово добавляется с частотой, равной 1. Если слово найдено в дереве, то увеличиваем частоту на 1. Эту задачу часто называют поиском по дереву с включением. Форма дерева определяется случайным порядком поступления элементов.

Слайд 29


Пример: Пример: Мама мыла раму, Маша ела кашу.
Описание слайда:
Пример: Пример: Мама мыла раму, Маша ела кашу.

Слайд 30


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

Слайд 31


B 9 2 4 1 7 E F A D C 3 5 8 6
Описание слайда:
B 9 2 4 1 7 E F A D C 3 5 8 6

Слайд 32


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

Слайд 33


Обозначения: Root - корень, D – данные, Обозначения: 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
Описание слайда:
Обозначения: Root - корень, D – данные, Обозначения: 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
Описание слайда:
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
Описание слайда:
Случайное дерево быстро строится, но его недостаток: оно может слишком вытянуться, в худшем случае выродиться в список. Случайное дерево быстро строится, но его недостаток: оно может слишком вытянуться, в худшем случае выродиться в список. 1 2 3 4 5 5 1 2 4 3

Слайд 37


Средняя высота дерева: Средняя высота дерева: hср. = hср.(СДП) = = = 3,86 hср.(ИСДП) = = =3,28 Н. Вирт доказал: hср.(ИСДП) = log(n) при n->∞ hср.(СДП) = 2*ln(n) при n->∞ = = 2*ln2 = 1,386 т. е. средняя высота СДП хуже ИСДП на 39%
Описание слайда:
Средняя высота дерева: Средняя высота дерева: hср. = hср.(СДП) = = = 3,86 hср.(ИСДП) = = =3,28 Н. Вирт доказал: hср.(ИСДП) = log(n) при n->∞ hср.(СДП) = 2*ln(n) при n->∞ = = 2*ln2 = 1,386 т. е. средняя высота СДП хуже ИСДП на 39%

Слайд 38


Рекурсивная процедура добавления в случайное дерево поиска Добавить рекурсивно (D, Vertex*&p) IF (p=NULL) память (p), p->Data=D, p->Left=NULL, p->Right=NULL ELSE IF (D< p->Data) Добавить рекурсивно(D, p->Left) ELSE IF (D> p->Data) Добавить рекурсивно(D, p->Right) ELSE <Вершина есть в дереве> FI Вызов процедуры: Добавить рекурсивно (D, root)
Описание слайда:
Рекурсивная процедура добавления в случайное дерево поиска Добавить рекурсивно (D, Vertex*&p) IF (p=NULL) память (p), p->Data=D, p->Left=NULL, p->Right=NULL ELSE IF (D< p->Data) Добавить рекурсивно(D, p->Left) ELSE IF (D> p->Data) Добавить рекурсивно(D, p->Right) ELSE <Вершина есть в дереве> FI Вызов процедуры: Добавить рекурсивно (D, root)

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию