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

,


 

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

25979. Холодная пластическая деформация 169 KB
  Основными механизмами сдвиговой пластической деформации кристаллических тел являются скольжение и двойникование. Скольжение - это такое перемещение одной части кристалла относительно другой, при котором кристаллическое строение обеих частей остается неизменным
25980. Аудиторская проверка финансовых вложений 43 KB
  Как и при проверке других активов аудитор исходит из предпосылок: полноты все финансовые вложения отражены в бухгалтерском учете и бухгалтерской отчетности не существует неучтенных финансовых вложений: в бухгалтерском учете и отчетности отражены все приобретенные организацией ценные бумаги и выданные займы; сальдо и обороты по счетам синтетического учета финансовых вложений совпадают с сальдо и оборотами по счетам аналитического учета; сальдо и обороты по счетам в полном объеме перенесены из регистров бухгалтерского учета в Главную книгу и...
25981. АУДИТ УЧЕТА ФИНАНСОВЫХ РЕЗУЛЬТАТОВ И ИХ ИСПОЛЬЗОВАНИЯ 35.5 KB
  Выручка от продукции реализованной на сторону отражается прежде всего на счете 90. Кроме того на данном счете отражается себестоимость реализованной продукции которая включает в себя: себестоимость готовой продукции и полуфабрикатов собственного производства; себестоимость работ и услуг промышленного характера; стоимость покупных изделий; стоимость строительномонтажных и проектноизыскательских работ; стоимость товаров; расходы по перевозке грузов; транспортноэкспедиционные расходы на погрузочноразгрузочные работы; услуги связи; зарплата...
25982. Аудит учета финансовых вложений 40.5 KB
  Законодательные и нормативные документыПри учете и аудите финансовых вложений необходимо руководствоваться следующими законодательнонормативными документами:1. Положение по бухгалтерскому учету Учет финансовых вложений ПБУ 19 02 утвержденное приказом Минфина России от 10. Методические указания по инвентаризации имущества и финансовых обязательств приказ Минфина России от 13 июня 1995 г.
25983. Философия Гераклита. Принципы диалектики. Диалектика и метафизика 25.3 KB
  Принципы диалектики. Согласно его рассуждениям мудрый тот кто не дает названия предметамони меняются Основные принципы диалектики. Гегель расширил понимание диалектики вывел ее из рамки движения мыслиувидел столкновение и объединение противоположностей в самой действительности в истории в культуре. В современных вариантах диалектики практически отсутствует понимания ее как о развитии.
25984. Философия и жизнь Сократа 19.09 KB
  Философия и жизнь Сократа О жизни и деятельности Сократа одного из величайших философов Древней Греции можно узнать лишь по произведениям его современников и учеников в первую очередь Платона потому что сам Сократ письменных источников после себя не оставил. Платон же познакомился с Сократом за восемь лет до гибели последнего когда Сократу было уже за шестьдесят и встреча эта произвела революцию в душе будущего знаменитого философа. Платон же написал и Апологию Сократа из которой можно узнать о некоторых аспектах сократовской...
25985. Платон. Сущность философского идеализма 18.03 KB
  Выделить в творчестве Платона какойлибо аспект и систематически изложить его довольно сложно так как приходится реконструировать мысли Платона из отдельных высказываний которые настолько динамичны что в процессе эволюции мысли порой превращаются в свою противоположность.Систематическое широкое использование математического материала имеет место у Платона начиная с диалога Менон где Платон подводит к основному выводу с помощью геометрического доказательства. Значительно в большей мере чем в гносеологии влияние математики...
25986. Философия Аристотеля, ученого-энциклопедиста 38.02 KB
  Проблема человека Познание человека – центральная проблема философии. Стремление человека познавать свою собственную природу является одним из главных стимулов развития философии мысли. В современной науке насчитывается более 800 дисциплин изучающих человека. – неделимый соединяет в себе черты: 1 ОБЩЕЧЕЛОВЕЧЕСКИЕ присущие всем людям как членам человеческого рода вида homo sapiens; 2 СОЦИАЛЬНОТИПИЧЕСКИЕ свойственные ему как представителю конкретного общества определенной культуры народа социальной группы; 3 ИНДИВИДУАЛЬНЫЕ...
25987. Философия эллинизма 20.28 KB
  Жизнь и деятельность ВойноЯсенецкого. ВойноЯсенецкого Валентин Феликсович ВойноЯсенецкий родился в 1877 г. Его отец провизор Феликс Станиславович ВойноЯсенецкий происходил из известного с 16 века обедневшего дворянского рода. Отец ВойноЯсенецкого был католиком мать Мария Дмитриевна Кудрина православной.