30503

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

Доклад

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

Дополнительно Асимптотические оценки времени поиска Алгоритм Структура данных Удачный поиск в среднем Неудачный поиск в среднем Вставка в среднем Удачный поиск в худшем случае Вставка в худшем случае Последовательный поиск в неупорядоченном массиве N 2 N 1 N 1 Последовательный поиск в упорядоченном массиве N 2 N 2 N 2 N N Бинарный поиск в упорядоченном...

Русский

2017-09-27

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

,


 

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

31338. Культ Великой Матери богов Кибелы в греко-римской древности (К проблеме религиозного синкретизма в античности) 5.81 MB
  Археологические свидетельства безусловно важны но немы что с одной стороны предоставляет ученым широкий простор для построения различных гипотез а с другой стороны затрудняет их обоснование. Следует подчеркнуть что они очень неравномерно представлены по главным периодам античной истории наибольший объем литературных материалов приходится на римский период причем особый интерес к культу наблюдается на стыке старой и новой эпох и во времена поздней империи. Необходимо подчеркнуть что культовое обращение к Кибеле Пиндара в точности...
31339. СОЦИАЛЬНО-ПОЛИТИЧЕСКИЙ МИФ: ТЕОРЕТИКО-МЕТОДОЛОГИЧЕСКИЕ ПРОБЛЕМЫ 4.36 MB
  Отношение политического мифа к политической идеологии Миф в системе политической науки. Почитание предков и становление политической мифологии лидерства Мифологема Русская земля: целеполагание и пространственные рамки политического процесса Мифология отличного порядка. Общественное насилие над властью: мифология политического самоопределения социума Эволюция групповой идентичности крестьянства...
31340. ИНДОЕВРОПЕЙСКИЕ МИФОТРАДИЦИИ (НА МАТЕРИАЛАХ САКРАЛЬНЫХ ГЕНЕАЛОГИЙ) 2.04 MB
  Современная наука установила факт существования общеиндоевропейского языка праиндоевропейского этноса в виде племени или соплеменности праиндоевропейской культуры как реальности эпохи неолита....
31341. ПРОБЛЕМЫ ЛИНГВИСТИЧЕСКОЙ РЕКОНСТРУКЦИИ ГЕРМАНСКОЙ КОСМОГОНИИ 864.88 KB
  В синхронии основным методом семантической реконструкции является изучение контекста слова. Под контекстом имеется в виду не только непосредственное окружение слова, но и его дальние связи в пределах более крупных единств, например, строф, то есть объектом исследования оказываются как контактное, так и дистантное расположение лексем.
31342. ЛЕКСИКА КУХОННОЙ УТВАРИ И ПОСУДЫ В ОРЛОВСКИХ ГОВОРАХ 3.84 MB
  Комплексное исследование лексики кухонной утвари и посуды позволит предпринятому нами исследованию заполнить пустующую нишу в системе последовательных изысканий в области изучения различных тематических групп в орловских говорах: агентивной лексики Т. Наиболее изученной является эта область лексики в сибирских и северновеликорусских говорах. В разное время обращались к её описанию в томских говорах Ф.
31343. АНТИЧНЫЙ МИФ ОБ АТЛАНТЕ И АТЛАНТИДЕ: ОПЫТ ФОЛЬКЛОРИСТИЧЕСКОГО РАССМОТРЕНИЯ 2.61 MB
  Образ Атланта в античном мифе и эпосе - это ярчайший пример олицетворения в ми-фо-поэтической форме догреческой неведической культуры и культа, с которыми ведические греки вели ожесточенную борьбу, и от которых в то же время они заимствовали множество их достижений
31344. КУЛЬТ АРЕСА В РЕЛИГИОЗНЫХ ПРЕДСТАВЛЕНИЯХ СКИФСКИХ ПЛЕМЕН СЕВЕРНОГО ПРИЧЕРНОМОРЬЯ (V-III вв. до н.э.) 3.56 MB
  Неудивительно что у скифов главным занятием которых была война совершенно особое место занимал культ бога войны Ареса. С точки зрения марксистской концепции религии перед нами яркое подтверждение того что религиозные верования вызревают и принимают различные формы под воздействием определенных социальных условий достигнутой обществом степени развития. Здесь же отметим что важнейшие аспекты скифского военного культа остаются недостаточно разработанными. Считается что до нас не дошло ни одного скифского мифа связанного с Аресом.
31345. ГЕНЕЗИС И ЭВОЛЮЦИЯ СОЛЯРНЫХ АСПЕКТОВ МИФОЛОГИИ АПОЛЛОНА 9.61 MB
  Лосев писал что широкая публика а значительной мере также и наука отождествляет Аполлона и Солнце1. Цель предлагаемой им реконструкции состоит в том чтобы дать правдоподобное объяснение известному и довольно странному факту: по сравнению с восточными религиозными системами в Греции в историческую эпоху культ Солнца как и других астральных божеств был очень мало развит. Рапп объясняет это тем что известный нам греческий Гелиос был последним звеном цепи развития мифологических представлений и именно поэтому сохранил в своей мифологии...