Двоичные Б-деревья (ДБД) m=1 - презентация, доклад, проект скачать

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

Содержание ▲

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

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

Слайд 1

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

Двоичные Б-деревья (ДБД) m=1 Б-деревья первого порядка не имеет смысла использовать для представления больших множеств данных, требующих вторичной памяти. Кроме неэффективного обращения к внешнему носителю, приблизительно половина страниц будут содержать только один элемент. Поэтому забудем о внешней памяти и вновь займемся построением деревьев поиска, находящихся в оперативной памяти.

Слайд 2

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

Определение. Двоичное Б-дерево состоит из страниц с одним или двумя элементами, страница содержит две или три ссылки на поддеревья. Определение. Двоичное Б-дерево состоит из страниц с одним или двумя элементами, страница содержит две или три ссылки на поддеревья. Пример: или Так как имеем дело с оперативной памятью, то необходимо её эффективно использовать. Поэтому представление страницы в виде массива уже не подходит. Решение – динамическое размещение на основе списочной структуры. Страница - список из одного или двух элементов.

Слайд 3

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

Так как каждая страница может иметь не более трех потомков (содержать не более трех ссылок), то попытаемся объединить ссылки на потомков и ссылки внутри страницы (вертикальные и горизонтальные). Так как каждая страница может иметь не более трех потомков (содержать не более трех ссылок), то попытаемся объединить ссылки на потомков и ссылки внутри страницы (вертикальные и горизонтальные). Тогда страницы Б-дерева теряют свою целостность. Элементы начинают играть роль вершин в двоичном дереве.

Слайд 4

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

Однако, Необходимо делать различия между горизонтальными и вертикальными ссылками; Необходимо следить, чтобы все листья были на одном уровне. Введем логические переменные HR и VR – горизонтальный и вертикальный рост дерева. Показатель баланса Bal = 0 или 1 Bal помещаем в структуру дерева, переменные HR и VR – глобальные.

Слайд 5

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

Рассмотрим добавление вершины в ДБД. Рассмотрим добавление вершины в ДБД. Различают 4 возможных ситуации, возникающие при росте левых и правых поддеревьев

Слайд 6

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

Слайд 7

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

Алгоритм построения ДБД VR=1 HR=1 B2INSERT(D, Vertex *&p) IF ( p=NULL ) <память по адресу p> , p-->Data = D, p-->Left = p-->Right = NULL, p-->Bal = 0, VR = 1 ELSE IF ( p-->Data > D) B2INSERT(D, p-->Left) IF ( VR=1 ) IF (p-->Bal=0) q=p-->Left, p-->Left=q-->Right, q-->Right=p, p=q, q-->Bal=1, VR=0, HR=1 ELSE p-->Bal=0, VR=1, HR=0 FI ELSE HR=0 FI

Слайд 8

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

ELSE IF (p-->Data<D) B2INSERT(D, p-->Right) ELSE IF (p-->Data<D) B2INSERT(D, p-->Right) IF (VR=1) p-->Bal=1, HR=1, VR=0 ELSE IF (HR=1) IF(p-->Bal=1) q=p-->Right, p-->Bal=0, q-->Bal=0, p-->Right=q-->Left, q-->Left=p, p=q, VR=1, HR=0 ELSE HR=0 FI FI FI FI FI

Слайд 9

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

К У Р А П О В Е Л Н И Т

Слайд 10

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

К У Р А П О В Е Л Н И Т Очевидно, что двоичные Б-деревья представляют собой альтернативу критерию АВЛ-сбалансированности.

Слайд 11

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

Отметим некоторые отличия: Отметим некоторые отличия: АВЛ-деревья – подмножество всех двоичных деревьев. Следовательно, класс ДБД шире, а их длина пути поиска в среднем хуже, чем у АВЛ-деревьев. Высота двоичного Б-дерева: h ≤ При m=1: h ≤ Длина пути ДБД может в два раза превышать высоту: L ≤ 2* Для сравнения, в плохом АВЛ-дереве: L ≤ 1,44*

Слайд 12

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

Однако, при построении ДБД реже приходится переставлять вершины (повороты выполняются лишь в двух случаях). Однако, при построении ДБД реже приходится переставлять вершины (повороты выполняются лишь в двух случаях). Поэтому ДБД предпочтительней, когда чаще добавляются вершины, АВЛ-деревья предпочтительнее, когда чаще производится поиск элементов. Кроме того, существует зависимость от особенностей реализации, поэтому вопрос о применении того или иного типа деревьев следует решать индивидуально для каждой конкретной задачи.