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

,


 

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

29230. Личность и общество в системе культуры: инкультурация, социализация, аккультурация, маргинальность 42.5 KB
  существовавший к тому времени термин €œсоциализация€ не охватывал процессов усвоения когнитивных познавательных аспектов культуры знаний верований ценностей и т. Оно подвергалось критике ввиду неопределенности его значения; кроме того оно по сути дублировало гораздо более широко использовавшийся термин €œсоциализация€ а его происхождение было прямо связано с не вполне правомерной попыткой противопоставления общества и культуры. СОЦИАЛИЗАЦИЯ процесс усвоения и активного воспроизводства индивидом социокультурного опыта социальных...
29231. Анимизм, фетишизм, тотемизм, магия как базовые формы культуры 37.5 KB
  Отсюда магические обряды размножения тотема ритуальное поедание его мяса в обычных условиях запрещенного рассказывание мифов пляски маскированных танцоров подражающих тотему. magéia колдовство чародейство волшебство обряды связанные с верой в способность человека сверхъестественным путём воздействовать на людей животных явления природы а также на воображаемых духов и богов. Магические обряды распространённые у всех народов мира чрезвычайно разнообразны. Широко были распространены магические обряды при начале пахоты сева...
29232. СЛОВО об АНТИЧНОСТИ 40.5 KB
  Три вещи связывали древних с их землей: храмы могилы и предки. Слово родина у древних было прилагательным и сочеталось со словом земля то была отцовская земля это слово доходило до сердца. Слово свобода к примеру имело для древних тот же глубинный смысл что и ответственность . Свобода теперь имеет моральный смысл у древних же совершенно политический Древние которых все их государственное устройство заставляло быть рационалистами были одухотворены поэзией.
29233. Синкретизм первобытной культуры 62 KB
  Синкретизм первобытной культуры. Синкретизм – основное качество культуры характеризующее процесс перехода от биологической формы бытия животных к социокультурной форме существования человека разумного. Синкретизм этого первого исторического состояния культуры естествен и закономерен так как на начальном уровне целостность системы проявляется в её аморфности нерасчленённости. С этим отождествлением связан и характерный для первобытной культуры тотемизм с языка индейского племени оджибве – его род – вера в первопредка которым может быть...
29234. Проблема «Восток-Запад» в культуре 38.5 KB
  Отличия Западной и Восточной культуры: 1. Для западной культуры характерен ускоренный прогресс науки и техники быстрое изменение предметного мира. На Западе сформировалась сильная рационалистическая традиция которая проявлялась во всех видах культуры.
29235. Культура и глобальные проблемы современности 36 KB
  Одно из самых напряженных противоречий политической и духовной жизни человечества обнаружившееся в конце ХХ столетия и обозначившее рубеж между завершавшимся вторым и рождавшимся третьим тысячелетиями – столкновение процессов и движений получивших название глобализма и антиглобализма. Вообще говоря само противостояние позиций обозначенных этими новыми понятиями отнюдь не ново – оно пронизывает всю историю человечества. Речь идет о едином для всего человечества техникотехнологическом уровне производства о...
29236. Николай Яковлевич Данилевский (1822-1885) 44.5 KB
  В наше время особенно актуальна мысль Данилевского о том что необходимым условием расцвета культуры является политическая независимость. Отрицая существование единой мировой культуры Данилевский выделял 10 культурноисторических типов египетский китайский ассировавилонский индийский иранский и др. Арнольд Джозеф Тойнби 1889 1975 английский историк и социолог автор 12томного Исследования истории 1934 1961 труда в котором он стремился осмыслить развитие человечества в духе круговорота цивилизаций употребляя этот термин в...
29237. Первобытность и цивилизация 48 KB
  Кочевой образ жизни оказывался на периферии культуры. Новый хозяйственный и административный уклад принципиально меняет содержание духовной культуры: нравственная нейтральность этическая невменяемость Г. Все восточные культуры единообразны не однообразны пластичны жизнестойки. Восточные культуры способны создавать величайшие культурные ценности при сравнительно низком развитии индивидуального я и вообще самодеятельнотворческого начала.
29238. Индо-буддистский тип культуры 30.5 KB
  это учение было изложено в четырех сборниках: Ригведа Книга гимнов Яджурведа Книга жертв Самаведа Книга песен Артхарваведа Книга жрецов .