Первая страница / Теория / Деревья /

Деревья последовательного поиска

Голосование: 17, 3

Введение: последовательный поиск

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

Стандартный поиск 1 Стандартный поиск 2

Однако, можно принимать во внимание, что результаты двух последовательных операций поиска могут находиться достаточно близко. Если начинать поиск из элемента, в котором закончилась предыдущая операция поиска, то часто результата можно достичь быстрее.

Последовательный поиск 1 Последовательный поиск 2

Поиск, основанный на таких соображениях, будем называть «последовательным поиском». В англоязычной литературе принят термин “finger search”, так как указатель на последний результат поиска часто называют “finger”(палец).

Подобно тому, как в обычных структурах поиска достигают оценки времени работы O(logN), в структурах, поддерживающих последовательный поиск, достигают оценки O(logD) в худшем случае, где D — расстояние между последовательными целями в отсортированном списке элементов.

Обзор простейших структур данных, поддерживающих последовательный поиск

Рассмотрим некоторые хорошо известные структуры данных, которые можно модифицировать для поддержки последовательного поиска.

2-3 дерево

Это расширение функциональности обычного 2-3 дерева описано в [6]. К узлам обычного 2-3 дерева добавлены дополнительные ссылки. Они указывают на соседние вершины того же уровня. Быстродействие структуры данных достигло оценки O(logD), однако она затрачивает много дополнительной памяти для обеспечения функциональности.

2-3 дерево Брауна-Тарьяна

Список пропусков

В этой структуре данных ([5]) необходимые межуровневые ссылки уже содержатся как составная часть.

Список пропусков

Операции вставки и удаления

Каждая из операций вставки и удаления может быть рассмотрена как две последовательные подоперации — нахождения места модификации структуры и собственно модификация. Первая из этих подопераций может быть оптимизирована за счет применения последовательного поиска. Вторая же в некоторых структурах данных тоже может занимать значительное время. Например, в вышеупомянутом списке пропусков эта операция занимает O(logN) в лучшем случае.

Дерево последовательного поиска с константным временем вставки

В работе [2] продемонстрировано дерево поиска, модификация которого для операции вставки происходит за O(1). За счет того, что вершине дерева позволяется изменять степень в широких пределах, при вставке вершины в дерево можно расщепить не более одного узла.

Константное время вставки

Для определения необходимости расщепления используется счетчик модификаций, хранящийся в каждом листе дерева (для вершины K будем обозначать значение этого счетчика CK). Вставка реализуется следующим образом:

  1. CB = CB + 1.
  2. CN = CB.
  3. Найти такое D, что CN mod 2D = 2D−1.
  4. Если степень предка на уровне D (на иллюстрации это вершина V) больше 2ΔD, то расщепить этого предка. Здесь ΔD — минимальное число потомков узла на уровне D.

Однако удаление элемента в этой структуре занимает уже O(log logN).

Структура для последовательного поиска с O(logN) дополнительной памяти

Поиски структур данных, близких к оптимальным как по времени выполнения операций, так и по дополнительной занимаемой памяти привели в 2003 году к созданию структуры данных [1], поддерживающей последовательный поиск за время O(logD), занимающей O(logN) дополнительной памяти и надстраиваемой над любым уже построенным деревом поиска из семейства B-деревьев. О ней и пойдет речь далее.

Определения, обозначения, соглашения

Будем считать, что дерево, над которым мы надстраиваем структуру данных, не содержит одинаковых элементов. Дадим следующие определения:

  • af — вершина дерева, с которой начинается поиск (собственно finger).
  • a — ключ, являющийся целью нашего поиска.
  • a+ — вершина дерева с минимальным ключом, не меньшим a. Если такового нет, используется значение +∞.
  • a — вершина дерева с максимальным ключом, не большим a. Если такового нет, используется значение −∞.
  • x++ — вершина, следующая за x в порядке увеличения ключа.
  • x−− — вершина, предшествующая x в порядке увеличения ключа.
  • depth(x) — глубина вершины x в дереве. Глубина корня равна 1.

Принцип работы структуры данных для простоты вначале будет объяснен на полном двоичном дереве поиска, так как в нем, как и в B-деревьях, все листья расположены на одном уровне.

  • Правый ствол вершины x — список вершин, определяемый следующим образом:
    • если у вершины x нет правого потомка, то он состоит из x.
    • иначе он образован присоединением правого ствола правого потомка к списку, состоящему из вершины x.
  • Левый ствол вершины x определен аналогично.
  • Основание ствола — это его самая нижняя вершина.
  • Правый изогнутый ствол вершины x — список вершин, состоящий из вершины x и левого ствола ее правого потомка при наличии такового. Левый потомок в этом случае называется изгибом правого изогнутого ствола.
  • Левый изогнутый ствол и его изгиб определяется аналогично.
Стволы в дереве
  • Если вершина x лежит на правом изогнутом стволе вершины y, то y называется левым родителем x.
  • Аналогично, если вершина z лежит на левом изогнутом стволе вершины y, то y называется правым родителем z.
  • Если вершина y является левым родителем вершины x и правым родителем вершины z, причем depth(x) = depth(z), то z является левым соседом x, а x является правым соседом z.
Родители и соседи

Инкрементальный обход. Деамортизация оценок времени работы одной итерации инкрементального обхода

Прежде, чем приступить к рассказу о реализации последовательного поиска, рассмотрим его упрощенную версию — инкрементальный обход. Инкрементальный обход — это обход всех вершин дерева в порядке возрастания их ключей. Так как мы хотим добиться оценки O(logD) для последовательного поиска, то при инкрементальном обходе мы должны обеспечить время работы одной итерации O(1) в худшем случае.

Рассмотрим время работы одной итерации. При наивной реализации алгоритма амортизированное время работы одной итерации составляет O(1). Действительно, каждое ребро дерева проходится ровно два раза в течение всего обхода, а ребер в дереве, как известно, O(N). Следовательно, каждая итерация требует в среднем O(1) времени. Однако, в худшем случае время одной итерации достигает O(logN).

По этой причине, при разработке структур данных часто задаются вопросом деамортизации оценок времени работы, то есть, стремятся сделать оценки времени в худшем случае равными амортизированным оценкам за счет некоторого перераспределения выполняемых операций. Попробуем и мы произвести деамортизацию алгоритма инкрементального поиска.

Во-первых, заметим, что существует два различных положения x++ относительно x: x++ является либо основанием правого изогнутого ствола вершины x, либо (если правое поддерево отсутствует) ее правым родителем.

Следующий элемент

Для обработки второго случая будем хранить для текущей рассматриваемой вершины стек правых родителей. Устроен он так: на вершине стека хранится текущая вершина, и каждый элемент является правым родителем предыдущего.

Стек правых родителей

Для обработки первого случая необходимо перейти в основание правого изогнутого ствола текущей вершины, попутно сложив их в стек правых родителей. Сделать это без подготовки за O(1) невозможно.

Переход к следующему элементу

Однако, можно заметить, что мы проходим «около» необходимых вершин, когда поднимаемся по их левым соседям. Мы можем поддерживать еще один стек, хранящий те вершины, которые потом будут добавлены к стеку правых родителей. Элементы в этот стек будут добавляться в тот момент, когда мы будем покидать их левых соседей. Обработка же первого случая осуществляется просто присоединением содержимого этого стека к стеку правых родителей. За O(1) это легко осуществить, если вместо стеков применять деки.

Опишем далее структуру данных, которая реализует вышеописанные мысли на практике.

«Рука»

Рассмотрим упрощенный вариант, предназначенный для поиска в направлении увеличения значения ключа. Будем использовать для описания структур данных семантику языка Java. В этом языке все объекты расположены в динамической памяти, а переменные соответствующих типов являются указателями на эти объекты. Пусть Deque<Type> — это дек, содержащий элементы типа Type, Node — узел дерева. Тогда опишем следующую структуру данных:

class HandElement {
    Node node;
    Deque<HandElement> spine;
    HandElement(Node node) {
        this.node = node;
        spine = new Deque<HandElement>();
    }
}

Основная структура данных называется «рука» (“hand”) и является деком таких элементов.

Deque<HandElement> hand;

Считаем, что элементы дека нумеруются с единицы. «Рука» обладает следующими свойствами:

  1. Первый элемент «руки» содержит текущую вершину. Вершина каждого последующего элемента «руки» является правым родителем вершины предыдущего элемента.
  2. Пусть индекс элемента руки равен j. Тогда в hand[j].spine хранится правый изогнутый ствол вершины hand[j].node без самой этой вершины длиной depth(hand[j].node) - depth(hand[j + 1].node) - 1. Под первым индексом в этом стволе хранится его изгиб.

На иллюстрации ниже продемонстрированы примеры «руки» для двух разных вершин.

Руки

Из определения «руки» вытекает, что число элементов, содержащихся во всей структуре, равно высоте дерева. Это означает, что для B-дерева или полного двоичного дерева «рука» занимает O(logN) дополнительной памяти.

Можно показать, что для любой вершины соответствующую «руку» можно построить за время O(logN). В том числе это можно сделать и для минимального элемента дерева, с которого начинается инкрементальный обход.

Заметим, что теперь можно легко получить доступ к правому соседу, не используя дополнительных связей. Действительно, рассмотрим для вершины префикс правого изогнутого ствола ее правого родителя. Левый потомок основания этого префикса и является правым соседом вершины, как нетрудно убедиться, за исключением случая пустого префикса. В последнем случае текущая вершина является непосредственным левым ребенком своего правого родителя, и правый сосед этой вершины — это правый потомок ее правого родителя.

Приведем код алгоритма модификации «руки» для одной итерации инкрементального обхода. Процедура возвращает true, если мы перешли на следующую вершину дерева, и false, если закончили обход дерева.

boolean increment() {
    HandElement finger = hand.removeFirst();
    if (hand.isEmpty()) {
        hand = finger.spine;
    } else {
        HandElement parent = hand.first();
        if (parent.spine.isEmpty()) {
            parent.spine.addFirst(new HandElement(parent.node.right));
        } else {
            parent.spine.addFirst(new HandElement(parent.spine.first().node.left));
        }
        hand = Deque.concat(hand, finger.spine);
    }
    return !hand.isEmpty();
}

Вкратце поясним, что выполняет этот код. Вначале мы удаляем верхний элемент (соответствующий текущей вершине, далее будем отождествлять элемент «руки» и вершину, ссылка на которую в нем хранится). Если у него нет правого родителя, то переходим к основанию правого изогнутого ствола текущей вершины. Заметим, что для этого основания сам правый ствол будет являться «рукой», поэтому просто присваиваем «руке» значение этого ствола.

Если же у текущей вершины есть правый родитель, то добавим своего правого соседа в соответствующий стек. Рассмотренные выше два случая напрямую реализуются в коде. Далее присоединяем префикс правого изогнутого ствола текущей вершины к руке. Если он непустой, то его основание окажется на вершине «руки». Если он пуст, то на вершине «руки» окажется правый родитель текущей вершины. Таким образом, мы разобрали оба возможных случая нахождения следующего элемента.

В качестве примера продемонстрируем содержимое «руки» для первых 9 итераций инкрементального поиска на полном двоичном дереве поиска из 15 элементов.

9 состояний 'руки'

Последовательный поиск, движение вправо

С помощью «руки» возможно выполнять последовательный поиск за время O(logD). Для описанной упрощенной модификации этот поиск происходит в направлении увеличения ключа. Как и в случае инкрементального обхода, рассмотрим, какие возможны случаи расположения цели поиска a относительно текущей вершины af.

Где цель поиска?

Рассмотрим два случая: a ∈ (afy] и a ∈ (y, +∞), где y — правый родитель af, z — правый сосед af.

В первом случае цель либо находится в правом поддереве af, либо является его правым родителем. Вызовем процедуру инкремента, затем будем удалять из «руки» элементы до тех пор, пока ключ вершины, на которую указывает следующий элемент, не окажется больше a. Как только мы нашли такой элемент, начинаем из первой вершины «руки» обычный поиск по дереву, одновременно достраивая «руку». Время работы для этого случая O(logH), где H — высота поддерева, в котором находится цель поиска. Оценивая D ≥ 2H−1, получаем оценку на время работы O(logD).

Теперь рассмотрим второй случай. Будем удалять по одному элементу из «руки» до тех пор, пока ключ вершины, на которую указывает следующий элемент, не окажется больше, чем a. Одновременно будем производить добавление правых соседей удаляемых элементов в соответствующие стеки.

Рассмотрим «руку», получившуюся в результате этих действий. Пусть верхним элементом «руки» сделался некоторый элемент w. Чтобы свойства «руки» выполнялись, необходимо дополнить ее левым стволом z. После этого искомая вершина находится в правом поддереве вершины w, то есть, далее можно выполнять алгоритм, соответствующий первому случаю.

Время работы во втором случае складывается из трех составляющих: нахождения w, достраивания «руки» и поиск из w. Первые два этапа в совокупности можно оценить через расстояние от af до w: T1 = O(log D(afw)). Последний этап оценивается с помощью первого случая как T2 = O(log D(wa)). Пользуясь неравенством log u + log v < 2 log (u+v), получаем, что и для этого случая оценка времени работы равна O(log D(afa)) = O(log D).

Обобщение на произвольное направление поиска

Теперь обобщим нашу структуру данных на случай последовательного поиска в обоих направлениях.

Дополним элемент «руки» еще одним полем — ссылкой на другой элемент такого же типа, после чего тип элемента будет записан так:

class HandElement {
    Node node;
    Deque<HandElement> spine;
    HandElement cross;
    HandElement(Node node) {
        this.node = node;
        spine = new Deque<HandElement>();
    }
}

В измененной структуре данных теперь будут присутствовать «левая рука» и «правая рука». «Правая рука» определена аналогично старой «руке», «левая рука» — симметрично, для чего необходимо поменять местами понятия «левый» и «правый».

Deque<HandElement> rightHand, leftHand;

Очевидно, что каждый из предков вершины, на которой построены обе «руки», находится либо в правой руке, либо в левой. Пара «рук» подчиняется следующему дополнительному правилу:

Если обходить элементы, начиная с корня, по указателям cross, учитывая, что cross = null обозначает, что надо переходить на вышележащий элемент в текущей «руке», то такой обход соответствует пути от корня к вершине, на которой построены «руки». Если путь закончился в «левой руке», то текущая вершина является левым ребенком своего родителя, иначе — правым.

Принципы модификации описанных выше алгоритмов для пары «рук» подробно освещены в [1], и мы не будем здесь их описывать. Упомянем только, что все они сохраняют свои асимптотические оценки по времени работы и занимаемой памяти. По симметрии, версии этих алгоритмов, работающие в направлении уменьшения ключей, также будут корректно работать с соответствующими оценками по времени работы и памяти.

Случаи несуществующего элемента

Возможны ситуации, когда происходит поиск элемента, которого нет в дереве. Для устранения неопределенностей будем использовать следующие правила: при поиске значения a в направлении увеличения ключа поиск должен останавливаться на элементе a+, а при поиске в направлении уменьшения ключа — на элементе a. При удалении элемента считаем, что указатель должен быть передвинут на a+. Данные ограничения легко реализовать соответствующим выбором неравенств в условиях поиска.

Обобщение на B-деревья

До сих пор мы рассматривали структуру данных, работающую как надстройка над полным двоичным деревом поиска. Однако, данные далеко не всегда можно расположить в полном двоичном дереве, да и операции добавления и удаления элементов неприменимы к такому дереву. Чтобы получить динамическую структуру данных, произведем обобщение построенной структуры данных на B-деревья.

Будем использовать для обобщения следующую нотацию. Пусть ключи в вершине дерева обозначаются xj, где 1 ≤ j < k, а потомки вершины обозначаются x[j], где 1 ≤ j ≤ k. Введем следующие обозначения:

  • xj[L] = x[j] — левый j-тый потомок, где 1 ≤ j < k.
  • xj[R] = x[j + 1] — правый j-тый потомок, где 1 ≤ j < k.

Тогда можно будет определить все ранее введенные типы стволов для данного узла с помощью этих индексов. Например, будет иметь смысл j-тый правый изогнутый ствол вершины x.

Инкрементальный поиск на B-деревьях

Рассмотрим, как обобщаются вышеописанные алгоритмы для случая B-деревьев, на примере инкрементального поиска.

Пусть элемент «руки» хранит вместе с указателем на вершину дерева еще и индекс ключа внутри этой вершины. Будем записывать такой указатель как xj. Тогда список spine первого элемента «руки» является суффиксом j-того правого изогнутого ствола x, который одновременно является суффиксом (j+1)-того левого ствола x.

Инкремент для B-деревьев

Если рассматриваемый ключ не является последним в текущей вершине, то при инкременте из xj необходимо сначала добавить в «руки» новый элемент с ключом xj+1, а затем присоединить список spine элемента с ключом xj.

Вставка и удаление в B-деревьях

Распространив преимущества последовательного поиска на B-деревья, мы получаем возможность таких модификаций структур, как вставка и удаление элементов, т.е. структура становится динамической.

В B-деревьях существует три основных операции модификации: разделение узла, слияние узлов и отделение корня. Нетрудно показать (см. [1]), что каждая из этих модификаций сопровождается константным изменением структуры «рук». Операции вставки и удаления реализуются через эти три операции и требуют амортизированно O(1) времени для стандартной реализации B-деревьев. Следовательно, каждая из этих операций производит O(1) модификаций структуры «рук».

Как замечено там же, поддержка слияния и разделения деревьев тоже не требует никаких дополнительных изменений в принципе работы «рук», так как эти операции реализуются через все те же основные модификации.

Можно отметить особо то, что деамортизация операций вставки и удаления основного дерева также приведет к деамортизации этих операций с добавленной возможностью последовательного поиска. Так, используя «руки» совместно с деревом из [2], можно получить константное в худшем случае время вставки.

Абстрактные вычислители. Оптимальные и достигнутые оценки на время последовательного поиска

Сделаем небольшой экскурс в теорию. Задачи поиска, в том числе и последовательного, могут выполняться на разных вычислительных устройствах, обладающих различной специализацией. Среди их многообразия можно выделить два основных класса, или абстрактных вычислителя: Pointer Machine и Random Access Memory Machine.

Pointer Machine — это вычислитель, оперирующий с вершинами и ребрами — указателями на вершины. Позволяется проводить тесты на равенство и отношение порядка. Отсутствует арифметика, в том числе и арифметика указателей. Подобный класс вычислителей является одним из наиболее общих классов.

RAM Machine умеет выполнять более широкий класс операций, в частности, арифметику (в том числе указателей) и битовые операции.

Большая часть рассмотренных структур данных использует только возможности Pointer Machine. Следовательно, они могут применяться на широком классе устройств. Для Pointer Machine оценка O(logD) для последовательного поиска является оптимальной.

Структуры данных, предназначенные для RAM Machine, очевидно, более узкоспециализированные, но это позволяет добиться лучших оценок для времени работы.

Оптимальной оценкой для последовательного поиска на RAM Machine является

O(sqrt(log D / log log D))

Эта оценка была достигнута в 2000 году в работе [3]. В [4] авторы добились математического ожидания времени работы O(log logD) для широкого класса вероятностных распределений.

Заключение

Совершенствование методов последовательного поиска является одним из перспективных направлений дискретной математики. Улучшения, достигнутые в этой области, находят свое применение в разработке баз данных, вычислительной геометрии ([7], см. также прим. 1) и смежных областей.

Литература

  1. G. Blelloch, B. Maggs, S. Maverick – Space-Efficient Finger Search on Degree-Balanced Search Trees (2003).
  2. G. Brodal – Finger Search Trees with Constant Insertion Time (1997).
  3. A. Anderson, M. Thorup – Tight Worst-Case Bounds on Dynamic Searching and Priority Queues (2000).
  4. A. Kapolis et al. – Improved Bounds for Finger Search on a RAM (2003).
  5. W. Pugh. – A skip list cookbook (1990).
  6. M. Brown, R. Tarjan – Design and analysis of a data structure for representing sorted lists (1980).
  7. R. E. Tarjan and C. J. Van Wyk. An O(n log log n)-time algorithm for triangulating a simple polygon (1998).

Примечания

  1. Данный источник был упомянут в [1], однако нам не удалось получить доступ к этой статье.

Максим Буздалов


Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий