Двоичные деревья - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

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

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

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

Словарь 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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

Пример

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 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

Описание слайда:

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

Слайд 18

Описание слайда:

Слайд 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

Описание слайда:

Пример: Пример: Мама мыла раму, Маша ела кашу.

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

B 9 2 4 1 7 E F A D C 3 5 8 6

Слайд 32

Описание слайда:

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

Слайд 33

Описание слайда:

Обозначения: Root - корень, D – данные, Обозначения: Root - корень, D – данные, p - указатель на указатель Добавить (данные D в дерево с корнем Root) p=&Root DO(*p!=NULL) // поиск элемента IF (DData) 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

Слайд 37

Описание слайда:

Средняя высота дерева: Средняя высота дерева: 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)

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

Похожие презентации