30503

Алгоритмы поиска. Использование деревьев в задачах поиска: бинарные, сбалансированные, красно-черные деревья поиска

Доклад

Математика и математический анализ

TN TN Θlog N. Число сравнений ключей при поиске Лучший С = Olog N Худший С = ON. Средний С = 2 ln N ≈ 139 log2 N если ключи появляются в случайном порядке VLдерево Г. Дополнительно Асимптотические оценки времени поиска Алгоритм Структура данных Удачный поиск в среднем Неудачный поиск в среднем Вставка в среднем Удачный поиск в худшем случае Вставка в худшем случае Последовательный поиск в неупорядоченном массиве N 2 N 1 N 1 Последовательный поиск в упорядоченном массиве N 2 N 2 N 2 N N Бинарный поиск в упорядоченном...

Русский

2013-08-24

126.38 KB

49 чел.

Алгоритмы поиска. Использование деревьев в задачах поиска: бинарные, сбалансированные, красно-черные деревья поиска.

Доска

АТД таблица

операции:

  1.  Поиск.
  2.  Вставка.
  3.  Удаление.

Поиск в линейных структурах

  1.  Последовательный
  2.  Бинарный и интерполяционный

Поиск в древовидных структурах

  1.  Бинарное дерево
  2.  AVL-дерево
  3.  Красно-черное дерево

Вырожденные деревья поиска

 

Деревья Фибоначчи порядка 2, 3, 4, 5 и 6 – пример наихудшего случая AVL-дерева (имеют наибольшее количество узлов для заданной высоты)

Добавление ключей 6, 2, 4, 1, 7, 3, 5 в красно-черное дерево

Выступление

АТД таблица — совокупность элементов, каждый из которых идентифицируется ключом (ключами).

Доступ к элементам — по ключу.

Основные операции:

  1.  Поиск элемента с заданным ключом.
  2.  Вставка элемента с заданным ключом.
  3.  Удаление элемента с заданным ключом.

 

Классификация таблиц

  1.  Место хранения: внутренние и внешние.
  2.  Отношения связи между элементами: линейные и нелинейные.
  3.  Упорядоченность элементов: упорядоченные и неупорядоченные

ПОИСК В ЛИНЕЙНЫХ ТАБЛИЦАХ

Линейная таблица элементов T1, T2, …, TN 

с ключами K1, K2, …, KN,

N ≥ 1 — количество элементов таблицы,

ключ поиска x.

Найти позицию i элемента Ti: x  Ki.

Последовательный поиск

Алгоритм последовательного поиска (sequential search) в неупорядоченной таблице

При успешном поиске в худшем случае N и порядка N/2 в среднем.

Бинарный и интерполяционный поиск

Алгоритм бинарного или двоичного поиска (binary search). Дж. Мочли в 1946 г., 1960 г. Д. Г. Лехмер - Асимптотически оптимальный алгоритм – осуществляет поиск в упорядоченных линейных таблицах (сначала необходимо провести операцию сортировки).

T(N)  

T(N)  Θ(log N).

1957 г. В. В. Петерсон

Алгоритм интерполяционного поиска

l  (r  l)/2 – точка разделения в бинарном поиске

l  (x  Kl)(r  l)/(Kr  Kl), - точка разделения в интерполяционном поиске (более общий случай)

где Kl  T[l].key, Kr  T[r].key.

ПОИСК В ДРЕВОВИДНЫХ ТАБЛИЦАХ

Бинарное дерево

Бинарное дерево поиска (BST — binary search tree), бинарное дерево, организованное таким образом, что ключ в любом узле больше ключей во всех узлах левого поддерева этого узла, и меньше ключей во всех узлах правого поддерева этого узла.

Число сравнений ключей при поиске

Лучший С = O(log N),

Худший С = O(N).

Средний С = 2 lN ≈ 1,39 log2 N, если ключи появляются в случайном порядке,

AVL-дерево

Г. М. Адельсон-Вельский, Е. М. Ландис, 1962 г.

Критерий сбалансированности:

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

Баланс узла Bal  Hr  Hl.

Для АВЛ-деревьев Bal  [1, 1].

Красно-черное дерево

Бинарное дерево поиска назовем красно-черным деревом (симметричным ББ-деревом), если:

  1.  Каждый узел — либо красный, либо черный.
  2.  Два красных узла не могут следовать последовательно друг за другом.
  3.  Все листья находятся на одном уровне.

В красно-черных деревьях все пути от корня к внешним узлам содержат одинаковое количество черных узлов.

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


Дополнительно

Асимптотические оценки времени поиска

Алгоритм  Структура данных

Удачный поиск
в среднем

Неудачный поиск
в среднем

Вставка
в среднем

Удачный поиск
в худшем случае

Вставка
в худшем случае

Последовательный поиск в неупорядоченном массиве

N/2

N

1

N

1

Последовательный поиск в упорядоченном массиве

N/2

N/2

N/2

N

N

Бинарный поиск
в упорядоченном
массиве

log N

log N

N/2

log N

N

Поиск в бинарном
дереве поиска

log N

log N

log N

N

N

Поиск в сбалансированном дереве

log N

log N

log N

log N

log N

Поиск в рандомизированном дереве

log N

log N

log N

N

N

Хеширование

1

1

1

N

1

Расчет среднего времени поиска в бинарном дереве

.

, при С1  1.

.

,

.

.

HN  1  1/2   1/3 … 1/N:

Доказательство по индукции.

При N  1 проверка тривиальна.

.

Учитывая формулу Эйлера

HN  lnN  γ  1/(12N), где γ  0,57721…

CN  2[ln N  γ]  3.

CN  2 ln 2 logN  1,386 logN,

Теорема (Адельсон-Вельский, Ландис). Высота h сбалансированного дерева с N узлами оценивается следующим соотношением:

log2(N  1) ≤ h ≤ 1,4404 log2(N  2)  0,328.

Доказательство.

1. N  1 ≤ 2h.

2. При каком минимальном значении N дерево будет иметь высоту h?

Пусть Th — АВЛ-дерево с минимальным количеством узлов и высотой h. Тогда левое поддерево – Th-1, а правое — Th-2.

Т.о., минимальное количество узлов среди всех сбалансированных деревьев будут иметь д. Ф. порядка h  1. Следовательно,

,


 

А также другие работы, которые могут Вас заинтересовать

72400. Манипулирование объектами. Разбитая табличка с письменами 3.89 MB
  Сначала создайте табличку — прямоугольник с текстурной заливкой. Для этого нарисуйте объект инструментом Rectangle (Прямоугольник), после чего примените к нему текстурную заливку, выбрав в группе Fill (Заливка) инструмент Texture Fill (Текстурная заливка).
72401. Настройка параметров системы Сorel Draw 8.17 MB
  CorelDRAW предоставляет пользователю широкие возможности, но зато и требует много ресурсов, в частности оперативной и дисковой памяти. Частично об этой проблеме стоит задуматься уже на этапе установки, когда вы решаете, на какой диск устанавливать программу, а на каком будет находиться папка для хранения временных файлов.
72402. Работа с фигурным текстом. Колючая надпись 337.5 KB
  Все это делалось для того, чтобы можно было воспользоваться инструментом Artistic Media (Художественные средства) в режиме Sprayer (Распылитель). Этот инструмент позволяет разбрасывать фигуры из специальных наборов одним движением кисти.
72403. CorelDRAW. Работа с линзами. Футуристичный автомобиль 548.5 KB
  Этот пример демонстрирует возможности линз, — чрезвычайно прост и оригинален. При этом получаемый результат действительно хорош с визуальной точки зрения и применим в профессиональном дизайне.
72404. Работа с макросами в CORELDRAW. Формирование календаря 2.16 MB
  Задание. Создайте изображение настенного календаря для вывода на печать. Создайте новый документ Файл - Новый (File - New). В меню Средства (Инструменты) - Visual Basiс - выбрать Воспроизвести (Tools - Visual Basiс - Play):...
72405. CorelDraw. Работа с растровыми объектами. Завернутый уголок 1.39 MB
  Существует растровый фильтр Page Curl (Завернутый угол страницы): Bitmaps > 3D Effects > Page Curl (Точечная графика > Трехмерные эффекты > Завернутый угол страницы). Где вы сможете выбрать место сворачивания уголка (слева, справа, снизу, сверху), направление...
72406. Повышение эффективности работы гальванической линии завода «ВЗЭП» г. Витебск 1.51 MB
  Обзор современных решений программ автоматического управления автооператорами гальванической линии; систематизация собранного материала для выполнения дипломного проекта, выбор физической среды реализации; изучение существующего программного обеспечения для проектирования выбранной системы; построение алгоритма управляющей программы. Определение протокола связи с модулями автооператоров, построение диаграммы состояний, вариантов использования...
72407. Форматирование таблицы, работа с формулами 1.08 MB
  Цель работы: ознакомиться со способами форматирования данных внутри ячеек, видами выравнивания и ориентации текста, прорисовки границ и выделения цветом. Изучить различные виды адресации ячеек, правила написания формул, работу Мастера функций и назначение кнопочек ленточной вкладки Формула.
72408. Работа с текстовыми данными 180.5 KB
  Цель работы: изучить основные сведения по работе с текстовыми данными, научиться обрабатывать текст. Уметь связывать данные в разных таблицах, освоить работу логических функций. Изучить пользовательские форматы данных. Научиться использовать средство Условное форматирование для выделения диапазона данных.