• Приводится краткий обзор 10 алгоритмов, которые не рассматривались в книге. Вы узнаете, для чего нужны эти алгоритмы.
• Я порекомендую книги, которые стоит читать дальше в зависимости от того, какие темы представляют интерес для вас.
Деревья
Вернемся к примеру с бинарным поиском. Когда пользователь вводит свое имя на сайте Facebook, сайт должен проверить содержимое большого массива, чтобы узнать, существует ли пользователь с таким именем. Мы выяснили, что для нахождения значения в массиве быстрее всего воспользоваться бинарным поиском. Однако здесь возникает проблема: каждый раз, когда на сайте регистрируется новый пользователь, придется заново сортировать массив, потому что бинарный поиск работает только с отсортированными массивами. Насколько удобнее было бы вставить пользователя в правильную ячейку массива, чтобы потом его не пришлось сортировать заново! Именно эта идея заложена в основу структуры данных бинарного дерева поиска.
Бинарное дерево поиска выглядит так:
Для каждого узла все узлы левого поддерева содержат меньшие значения, а все узлы правого поддерева — большие значения.
Предположим, вы ищете узел Maggie. Поиск начинается с корневого узла.
Строка Maggie идет после David, поэтому идем направо.
Строка Maggie предшествует Manning, поэтому идем налево.
Мы нашли узел Maggie! В целом процедура поиска напоминает бинарный поиск. Поиск элемента в бинарном дереве поиска в среднем выполняется за время O(log n), а в худшем случае — за время O(n). Поиск в отсортированном массиве выполняется за время O(log n) в худшем случае — казалось бы, отсортированный массив эффективнее. Однако бинарное дерево поиска в среднем работает намного быстрее при удалении и вставке элементов.
У бинарных деревьев поиска есть и свои недостатки: во-первых, они не поддерживают произвольный доступ. Вы не сможете потребовать: «Выдайте мне i-й элемент этого дерева». Кроме того, в таблице приведено среднее время выполнения операций; оно зависит от сбалансированности дерева. Допустим, ваше дерево не сбалансировано, как на следующем рисунке.
Видите, как дерево перекошено вправо? Эффективность такого дерева оставляет желать лучшего, потому что это дерево не сбалансировано. Существуют специальные бинарные деревья поиска, способные к самобалансировке (как, например, красно-черные деревья).
Где же используются бинарные деревья поиска? B-деревья, особая разновидность бинарных деревьев, обычно используются для хранения информации в базах данных.
Если вас интересуют базы данных или более сложные структуры данных, поищите информацию по следующим темам:
• в-деревья;
• красно-черные деревья;
• кучи;
• скошенные (splay) деревья.
Инвертированные индексы
Перед вами сильно упрощенное объяснение того, как работает поисковая система. Допустим, имеются три веб-страницы с простым содержимым.
Построим хеш-таблицу для этого содержимого.
Ключами хеш-таблицы являются слова, а значения указывают, на каких страницах встречается каждое слово. Теперь предположим, что пользователь ищет слово hi. Посмотрим, на каких страницах это слово встречается.
Ага, слово встречается на страницах А и B. Выведем эти страницы в результатах поиска. Или предположим, что пользователь ищет слово there. Вы знаете, что это слово встречается на страницах A и C. Несложно, верно? Это очень полезная структура данных: хеш-таблица, связывающая слова с местами, в которых эти слова встречаются. Такая структура данных, называемая инвертированным индексом, часто используется для построения поисковых систем. Если вас интересует область поиска, эта тема станет хорошей отправной точкой для дальнейшего изучения.
