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

48 чел.

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

Доска

АТД таблица

операции:

  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. Следовательно,

,


 

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

58384. Публицистический стиль речи. Функциональные особенности стиля 39 KB
  Порядочность бытие начал начала облегчить афера новорожденный прирост черпать красивее позвонит квартал договор гербовый осужденный феномен партер музей.
58387. Сатирическое изображение Москвы 30–х годов в романе М.А.Булгакова «Мастер и Маргарита» 50 KB
  Цель урока: Показать сатирическое изображение московского общества; раскрыть приемы создания писателем комичных ситуаций; определить основную цель использования сатирических приемов в романе. Выявление основных сатирических приемов в романе М.