Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


Слоёные списки

Поиск:
Слоёные списки - это связные списки, которые позволяют вам пропустить (skip) ненужные элементы, прыгнув сразу к нужному. Это позволяет преодолеть ограничения последовательного поиска, являющегося основным источником неэффективного поиска в списках. В то же время вставка и удаление остаются сравнительно эффективными. Оценка среднего времени поиска в таких списках есть O(lg n). Для наихудшего случая оценкой является O(n), но худший случай крайне маловероятен.

Эта структура очень удобна и сочетает простоту несбалансированного бинарного дерева с хорошими показателями AVL-tree.

Теория

user posted image
Рис. 3.8: Устройство слоёного списка

Эта простая идея может быть расширена - мы можем добавить нужное число уровней. Внизу на рис. 3.8 мы видим второй уровень, который позволяет двигаться еще быстрее первого. При поиске элемента мы двигаемся по этому уровню, пока не дойдем до нужного отрезка списка. Затем мы еще уменьшаем интервал неопределенности, двигаясь по ссылкам 1-го уровня. Лишь после этого мы проходим по ссылкам 0-го уровня.

Вставляя узел, мы должны будем определить количество исходящих от него ссылок. Эта проблема легче всего решается с использованием случайного механизма: при добавлении нового узла мы "бросаем монету", чтобы определить, нужно ли добавлять еще уровень. Например, мы можем добавлять очередные уровни до тех пор, пока выпадает "решка". Если реализован только один уровень, мы имеем дело фактически с обычным списком и время поиска есть O(n). Однако, если имеется достаточное число уровней, слоёный список можно считать деревом с корнем на высшем уровне, а для дерева время поиска есть O(lg n).

Поскольку реализация слоёных списков включает в себя случайный процесс, для времени поиска в них устанавливаются вероятностные границы. При обычных условиях эти границы довольно узки. Например, когда мы ищем элемент в списке из 1000 узлов, вероятность того, что время поиска окажется в 5 раз больше среднего, можно оценить как 1/1,000,000,000,000,000,000.





Файлы:
s_fig38.gif

Просмотров: 2672

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную