Существует множество, множество способов сбалансировать бинарные деревья поиска, каждый из которых предполагает свой набор компромиссов. Вообще говоря, сбалансированные бинарные деревья поиска попадают в одну из следующих категорий:
Деревья со сбалансированной высотой : деревья, которые пытаются сохранить разницу в высоте. между разными частями дерева несколько равны.
Деревья с балансировкой по весу : деревья, которые пытаются сохранить количество узлов в разных регионах
Случайные деревья : Деревья, которые меняют форму и пытаются таким образом сохранить низкую общую высоту.
Stati c Trees : деревья, разработанные, чтобы принимать определенную c форму, которая подходит для определенного набора запросов.
Саморегулирующиеся деревья : деревья, которые меняют свою форму в ответ на доступ, чтобы снизить затраты на поиск.
Вот краткое изложение этих различных стратегий, а также несколько примеров различных деревья каждого типа.
Деревья со сбалансированной высотой
Деревья со сбалансированной высотой интуитивно работают за счет наложения структурных ограничений, которые гарантируют, что определенные поддеревья имеют высоту, которая не может отличаться "слишком сильно," "для некоторого определения" слишком много ". Они поддерживают низкую общую высоту дерева, гарантируя, что дерево может вырасти до определенной высоты только при наличии большого количества узлов. В эту категорию попадают несколько наиболее часто используемых деревьев. Например:
деревья AVL
деревья AVL , названные в честь инициалов их изобретателей, представляют собой оригинальную структуру данных сбалансированного двоичного дерева поиска, изобретенную в 1962 году. Деревья AVL являются бинарными деревьями, которые подчиняются следующему структурному ограничению: два поддерева каждого узла могут иметь разницу в высоте не более одного. Это жесткое структурное ограничение: любое дерево AVL с высотой h имеет от F h + 2 и 2 h , где F n - n-е число Фибоначчи .
Для выполнения этого требования деревья AVL выполняют вращения дерева всякий раз, когда при вставке или удалении создается поддерево, левое и правое поддеревья которого имеют разницу в высоте ± 2.
Из-за жестких структурных ограничений деревья AVL имеют тенденцию иметь очень низкую высоту относительно количества узлов. Однако это также означает, что количество вращений, выполняемых при вставке или удалении, может быть большим, поскольку одна вставка или удаление может изменить относительную высоту поддеревьев многих узлов.
Существует несколько современных вариантов деревьев AVL . Дерево RAVL ( r elaxed AVL дерево) обобщает деревья AVL, допуская большую степень дисбаланса после удалений, уменьшая объем работы, необходимой во время каждой вставки или операция удаления. Дерево WAVL ( w eak AVL tree) обобщает понятие «разницы в высоте» до концепции, называемой «разницей в рангах», таким образом, чтобы допускать большее гибкость в структуре, гарантирующая, что каждая вставка или удаление выполняет очень небольшой средний объем работы по исправлению.
Красные / черные деревья
Красные / черные деревья - это деревья двоичного поиска в которой каждому узлу назначается цвет (красный или черный) в соответствии со строгим набором правил:
- Узел root черный.
- Ни один красный узел не имеет красного дочернего элемента .
- Любой путь, начинающийся с root дерева и уходящий от дерева, проходит через одинаковое количество черных узлов.
Это последнее правило является наиболее тонким. Это означает, что если вы начнете с узла root и пройдете влево или вправо, как хотите, в момент, когда вы сойдете с дерева, количество посещенных черных узлов всегда будет одинаковым, независимо от того, какой выбор слева / справа вы сделали.
Эти правила гарантируют, что самый глубокий листовой узел будет примерно в два раза глубже самого мелкого листового узла. Интуитивно это объясняется тем, что в крайнем случае один листовой узел может быть доступен по пути, состоящему исключительно из черных узлов, а другой лист - по пути, который чередуется с черным / красным / черным / красным / ..., поскольку красные узлы не могут есть красные дети. Более подробный анализ более убедительно показывает, что высота дерева гарантированно равна O (log n).
Вставки и удаления в красно-черном дереве выполняются путем выполнения обычных вставок или удалений, за которыми следует серия поворотов и смены цвета, чтобы гарантировать соблюдение вышеуказанных правил. В отличие от деревьев AVL, красные / черные деревья обычно мало поворачиваются и после вставки или удаления выполняют небольшую работу по «исправлению». В частности, амортизированный объем работы по исправлению, необходимой для каждой вставки или удаления, равен O (1), поэтому большинство операций вставки и удаления будут выполнять обычную операцию дерева O (log n) плюс очень небольшой объем дополнительной работы. В результате, хотя красные / черные деревья обычно выше, чем деревья AVL, они немного быстрее в рабочих процессах, которые имеют большое количество вставок и удалений.
Деревья AA
AA-деревья - это стиль деревьев со сбалансированной высотой, тесно связанных с красными / черными деревьями.
И красные / черные деревья, и деревья AA относятся к семейству многоуровневых деревьев поиска со сбалансированной высотой, называемым B-деревья . Интуитивно B-деревья - это многосторонние деревья, в которых каждый узел может хранить (примерно) ключи от b до 2b для некоторого внешнего параметра b. Они работают, выполняя вставку в листовые узлы, затем разделяя более крупные листья и «толкая» ключи выше в дереве, когда превышен предел размера.
Красное / черное дерево можно представить - и оно действительно было изобретено - моделирование B-дерева, в котором каждый узел содержит 1, 2 или 3 ключа (дерево 2-3-4 ). Идея состоит в том, что каждый черный узел в красно-черном дереве соответствует узлу в дереве 2-3-4, а каждый красный узел в красно-черном дереве представляет собой ключ, который «втягивается» в черный узел выше. Это. Деревья AA, с другой стороны, моделируются на основе B-деревьев, в которых каждый узел имеет 1 или 2 ключа ( 2-3 дерево ), с использованием аналогичного набора методов. Деревья AA также обеспечивают соблюдение правила, согласно которому «красные» узлы должны висеть слева от черного узла, в который они втянуты. Это уменьшает количество случаев, которые необходимо проверить во время вставки или удаления, но также увеличивает количество поворотов, которые могут потребоваться.
Наклоняющиеся влево красные / черные деревья
Гибрид «Между классическим красно-черным деревом и деревом АА находится левое красное / черное дерево . Эта древовидная структура, как и красное / черное дерево, кодирует дерево 2-3-4 как двоичное дерево поиска. Однако, как следует из названия, в случае, когда черный узел имеет ровно один красный дочерний элемент, этот красный дочерний элемент должен висеть слева от своего черного родителя.
Это уменьшает количество случаев, которые могут возникнуть в вставка или удаление, но, как деревья AA, увеличивает количество поворотов, которые должны быть выполнены во время редактирования дерева.
Деревья с балансировкой по весу общая высота дерева мала за счет обеспечения некоторого "хорошего" отношения между количеством узлов в левом и правом поддеревьях каждого узла. Основная идея c состоит в том, что если каждый узел разбивает оставшиеся узлы на некоторую хорошую долю (скажем, 75% / 25%), то каждый шаг вниз по дереву приводит к геометрическому уменьшению размера текущего поддерева, гарантируя, что дерево имеет логарифмический c высоту. BB [α] деревья BB [α] деревья (деревья b округлые b alance, параметр α) представляют собой бинарные деревья поиска, в которых поддеревья каждого узла имеют «вес», который всегда составляет, по крайней мере, α часть «веса» их родителя. (В деревьях BB [α] вес узла задается общим количеством узлов в его поддереве плюс один. ) По мере того как α становится все ближе и ближе к 1/2, относительные размеры левого и правого поддеревьев должны становиться все ближе и ближе друг к другу. Это означает, что необходимо проделать больше работы, чтобы сохранить форму дерева, но общая высота дерева уменьшается. По мере того, как α становится меньше, относительные размеры левого и правого поддеревьев становятся менее ограниченными, что означает, что для вставки или удаления элементов выполняется меньше работы, но высота дерева становится все больше и больше. Как и все деревья, упомянутые выше, Деревья BB [α] используют ротацию деревьев для перестановки узлов после вставки или удаления для поддержания их состояния баланса. Исходная версия деревьев BB [α] имела верхнюю границу выбора α, равную примерно 0,25, что означает, что каждый шаг в дереве будет гарантировать, что по крайней мере 25% оставшихся узлов больше не будут в текущем поисковом поддереве. Деревья-козлы отпущения Деревья-козлы отпущения представляют собой гибрид дерева со сбалансированным весом и сбалансированным по высоте. Само дерево является сбалансированным по весу деревом, в котором есть параметр α (не имеющий отношения к параметру α из деревьев BB [α]), такой что размер двух поддеревьев каждого узла составляет не более α, умноженное на размер самого узла. Здесь «размер» узла - это количество узлов в его поддереве. В отличие от вышеупомянутых типов сбалансированных деревьев, деревья козла отпущения (напрямую) не используют вращения для выполнения своей перебалансировки. Вместо этого, всякий раз, когда выполняется вставка, которая делает дерево «слишком высоким» для балансировки веса, он выполняет поиск в обратном направлении по пути вставки, чтобы найти узел, который не сбалансирован должным образом, а затем перестраивает все поддерево, чтобы оно было идеально- сбалансированный. В этом смысле, в то время как форма дерева соответствует форме дерева со сбалансированным весом, стратегия ребалансировки работает путем поиска нарушений баланса по высоте. Этот подход не гарантирует производительности O (log n) в наихудшем случае при вставке или удалении из-за затрат на оптимальную перебалансировку нарушающего поддерева. Тем не менее, он дает амортизированную O (log n) стоимость за вставку или удаление, поскольку редко требуется выполнять большое перестроение, и после того, как оно выполнено, дерево оказывается идеально сбалансированным. Фактический лог c для восстановления плохого поддерева может быть выполнен за линейное время с использованием только O (1) пространства вспомогательной памяти с помощью алгоритма Дэй-Стаута-Уоррена , который оптимально восстанавливает BST должен быть идеально сбалансирован с использованием умного набора вращений деревьев. Деревья-козлы отпущения часто используются в качестве строительных блоков в более крупных структурах данных, в которых перебалансировка через вращение невозможна. Например, деревья козлов отпущения могут быть объединены с деревьями kd , чтобы сформировать деревья динамики c kd, поскольку обычные вращения BST в дереве kd не разрешены. Случайные деревья
Рандомизированные деревья работают, выбирая случайную форму дерева при соблюдении определенных правил. Поскольку большинство случайно выбранных форм двоичного дерева поиска имеют низкую высоту (очень маловероятно, что вы получите длинную цепочку узлов), эти деревья имеют высокую вероятность сбалансированности.
Treaps
Treaps являются, как следует из названия, гибридом между двоичным деревом поиска и двоичной кучей (или, точнее, между двоичным деревом поиска и декартовым деревом ). Каждый узел в treap аннотируется равномерно-случайным весом (скажем, случайным 32-битным целым числом или случайным действительным числом от 0 до 1), и узлы расположены так, что
- узлы образуют двоичное дерево поиска относительно ключей в treap, и
- вес каждого узла меньше или равен весам его дочерних элементов.
Эти два свойства однозначно определяют форма трепа; фактически, для любого набора (отдельных) ключей и весов существует ровно один треап, содержащий эти ключи и веса.
Полезная перспектива для понимания treaps - это представить запуск рандомизированной быстрой сортировки для ключей, хранящихся в дереве. В первом раунде быстрой сортировки мы выбираем случайную точку поворота (представьте, что выбираете ключ с наименьшим весом), затем меняем порядок элементов так, чтобы меньшие элементы go слева от точки поворота (в левое поддерево) и более крупные элементы go справа от оси (в правое поддерево). Затем мы рекурсивно сортируем эти элементы (рекурсивно строим остальную часть дерева). В результате, согласно тому же анализу, который показывает, что ожидаемая общая стоимость рандомизированной быстрой сортировки составляет O (n log n), ожидаемая глубина любого узла в treap составляет O (log n).
Вставки и удаления в treap могут быть выполнены с помощью очень простых вращений дерева. Вставка выполняется обычным способом с последующим вращением узла вместе с его родителем до тех пор, пока его вес не превысит вес его родителя. Удаление может быть выполнено путем вращения узла с его дочерним элементом с меньшим весом до тех пор, пока узел не станет листом, а затем удалением узла.
Zip Trees
Zip tree являются альтернатива treaps, которые требуют меньше случайных битов на узел. Как и treaps, каждому узлу назначается случайный вес, но на этот раз из geometri c распределения , а не равномерного распределения. Правило состоит в том, что вес каждого узла должен быть больше веса его дочерних узлов, за исключением того, что если в рангах находится ie, связанный узел должен быть его правым дочерним элементом. Эти правила, как и treaps, сохраняются за счет выполнения поворотов всякий раз, когда узел вставляется или удаляется, или выполнения эквивалентной операции, называемой zipping или unzip , которая имитирует вращения без их фактического выполнения *. 1217 *
Zip-деревья были изобретены как способ кодирования skiplist как рандомизированного двоичного дерева поиска. Они, как правило, немного выше ожидаемых, чем treaps, но из-за использования geometri c, а не однородных случайных величин, требуется меньше случайных битов на узел (treaps нужно примерно O (log n) бит на узел; zip-деревьям нужно примерно O (log log n) бит на узел.)
Stati c Trees
Stati c деревья двоичного поиска - это деревья двоичного поиска, которые не допускают вставки или удаления вообще. Обычно они используются в случаях, когда вероятности доступа каждого узла известны или могут быть оценены заранее.
Статически оптимальные BST
Статически оптимальные BST - это двоичный поиск деревья, специально построенные для минимизации ожидаемых затрат на поиск в дереве, предполагая, что вероятности доступа каждого узла известны заранее. Например, если вы создавали BST для хранения контактной информации в телефоне и знали, какие люди с наибольшей вероятностью будут искать, вы можете структурировать BST, чтобы разместить обычно называемых людей в дереве выше, а тех, которые реже -позвали людей вниз по дереву.
Дон Кнут нашел алгоритм времени O (n 2 ) для построения оптимального двоичного дерева поиска с учетом вероятностей доступа каждого узла. Алгоритм представляет собой умное решение для программирования Dynami c, которое работает на следующих выводах. Во-первых, какой-то узел - мы не сразу уверены, какой - должен go на root. И при любом выборе узла root мы затем построим оптимальные бинарные деревья поиска для левого и правого поддеревьев root, которые соответствуют элементам меньше и больше, чем root, соответственно. Это означает, что есть только O (n 2 ) возможных подзадач для рассмотрения, соответствующих каждому последовательному поддиапазону элементов для сохранения в дереве. Наивно, что для определения решения любой из этих подзадач потребуется время O (n), потому что в каждом поддиапазоне есть O (n) узлов, которые можно попробовать как root. Тем не менее, Кнут показал, что существует некая хитрая структура того, как работают эти варианты поворота, которая позволяет общей сложности оценки работать до O (n 2 ).
Позднее было доказано, что стоимость поиск в таком дереве - O (1 + H), где H - энтропия Шеннона вероятностного распределения ключей. Эта величина H варьируется от нуля (все обращения к одному ключу) до журнала n (все ключи имеют равные шансы быть найденными) в зависимости от того, насколько искажено распределение. *
Деревья с уравновешенным весом , иногда ошибочно называемые деревья со сбалансированным весом , представляют собой тип дерева состояния c, построенного в соответствии с простым правилом. Узел root выбирается так, чтобы сумма вероятностей доступа левого и правого поддеревьев была как можно ближе, и эти поддеревья рекурсивно строились таким же образом.
В приведенном выше правиле говорится: веса левого и правого поддеревьев, насколько это возможно », и поэтому неудивительно, что деревья, построенные таким образом, сбалансированы по весу относительно полной вероятностной массы каждого поддерева. В частности, вы можете доказать, что каждое поддерево имеет не более 2/3 вероятностной массы его родительского дерева. Приложив немного больше математики, вы можете доказать, что стоимость поиска в этих деревьях составляет O (1 + H) с постоянным коэффициентом ожидаемой стоимости поиска оптимальных деревьев Кнута.
Наивно, это потребовало бы time O (n 2 ) работают для построения дерева с уравновешенным весом: вы можете попробовать каждый узел в качестве потенциального дерева root и рекурсивно построить деревья с уравновешенным весом для левого и правого поддеревьев. Тем не менее, можно ускорить это время построения до O (n log n) для набора несортированных ключей, отсортировав ключи и используя умный двоичный поиск, чтобы найти оптимальные root. Более поздняя работа показала, что это может быть улучшено еще больше к времени построения O (n) из набора отсортированных ключей с помощью очень умного двустороннего экспоненциального поиска.
Самонастраивающиеся деревья
Самонастраивающиеся деревья пытаются добиться хорошего времени выполнения другим способом - динамически реструктурируя себя в ответ на запросы. Приспосабливаясь к сделанным из них запросам, они часто могут, практически или теоретически, превосходить стандартные сбалансированные деревья в тех случаях, когда для выполняемых запросов есть какая-то хорошая структура.
Splay Trees
Splay-деревья - самые известные из самонастраивающихся деревьев поиска. Расширяемое дерево - это обычное двоичное дерево поиска с одним поворотом - всякий раз, когда узел вставляется, удаляется или просматривается, этот узел перемещается в root с помощью процесса, называемого раскрытие . Операция расширения выполняется путем многократного просмотра узла, его родителя и его прародителя, а затем принятия решения о серии вращений, которые перемещают root ближе к root. Случаи называются зигзаг , зигзаг и зигзаг и их довольно просто реализовать.
Помимо этого правила, расширьте деревья не накладывают никаких ограничений на их форму. Это означает, что растущие деревья могут стать очень несбалансированными в обычном понимании. Однако операция расширения обладает некоторыми удивительными свойствами, которые делают дерево развертывания невероятно быстрым в смысле амортизированного . В частности:
- Амортизированная стоимость поиска элемента равна O (log n).
- Амортизированная стоимость поиска элемента равна O (1 + H), где H - энтропия Шеннона распределения доступов по узлам. Другими словами, деревья splay могут использоваться в качестве замены деревьев stati c.
- Амортизированная стоимость поиска элемента равна O (log t), где t - количество различных элементов, которые были доступ с момента последнего поиска запрошенного элемента. Другими словами, если в каждый момент времени в дереве есть набор «горячих» элементов, стоимость поиска зависит только от количества горячих элементов, а не от количества элементов в дереве.
- Амортизированная стоимость поиска элемента равна O (log Δ), где Δ - это разность рангов между запрошенным элементом и последним запрошенным элементом. То есть, если вы представите себе, что в дереве хранится отсортированный массив элементов, стоимость поиска зависит только от того, на сколько шагов в массиве вы находитесь от последнего запрошенного элемента, а не от общего количества элементов.
Предполагается, но не доказано, что деревья splay являются динамически оптимальными в том смысле, что ни один другой самонастраивающийся BST не может превзойти дерево splay в любой достаточно длинной последовательности доступа.
Однако накладные расходы на выполнение поворотов на операцию в сочетании с тем фактом, что деревья расширения не работают с параллелизмом, а их гарантии имеют только амортизированное значение, означает, что деревья расширения не являются обычно используется как «стандартная» реализация BST.
Tan go Trees
Tan go tree - это двоичное дерево поиска, которое состоит из нескольких различных красных / черные деревья свисают друг с друга и меняются при каждом доступе. Деревья Tan go стремятся к эффективности совсем иначе, чем другие деревья здесь: они построены таким образом, чтобы гарантировать, что стоимость любой последовательности операций над деревом Tan go составляет не более O (log log n · c*), где c* - наилучшая возможная стоимость выполнения этой последовательности операций с любой сбалансированной структурой BST.
В частности, дерево tan go работает следующим образом: представление ссылочного двоичного дерева (фактически нигде не построенного) с содержимым дерева в виде листьев. У каждого узла в дереве есть предпочтительный дочерний элемент, что заставляет дерево разделять края на пути, называемые «предпочтительными путями». В дереве Tan go каждый из этих путей хранится как красное / черное дерево, причем нежелательные края используются для связывания каждого красного / черного дерева с дочерним красным / черным деревом. При поиске предпочтительные дочерние элементы в ссылочном дереве изменяются таким образом, что искомый ключ находится на предпочтительном пути вниз от root, а красные / черные деревья реструктурируются, чтобы соответствовать полученным путям.
Используя растянутые деревья вместо красных / черных деревьев в коричневом go дереве, мы получаем дерево мультисплея , которое также выполняет свои операции за время O (log log n · c*), но также гарантирует амортизированное время O (log n) на поиск, а также несколько других хороших свойств (например, стоимость последовательного поиска каждого элемента в дереве мультиэкрана составляет O (n)).
Больше для изучения
Есть много других красивых структур данных, которые у меня не было времени включить сюда во всех деталях. Вот пример других, заслуживающих внимания:
B-деревья широко используются в базах данных и файловых системах, а также в качестве источников вдохновения. для и строительных блоков в других структурах данных. Красное / черное дерево и дерево AA разработаны как кодировки определенных c B-деревьев как двоичных деревьев поиска.
Skiplists являются альтернативой сбалансированным BST, которые работают путем запуска нескольких иерархических связанных списков через коллекцию элементов. Исходная структура данных skiplist была рандомизирована и гарантировала O (log n) операций с ожидаемым временем (эта структура, адаптированная в BST, дает zip-дерево). Более поздняя работа произвела детерминированных c специалистов, которые работают, моделируя 2-3-4 дерева, делая их по существу идентичными красно-черным деревьям, за исключением совершенно другого представления.
Структура рабочего набора Iacono использует набор сбалансированных BST для хранения элементов таким образом, чтобы гарантировать, что поиск недавно запрошенных элементов выполняется быстрее, чем поиск более старых элементов. Это строительный блок в унифицированной структуре Iacono , благодаря чему поиск предметов, близких к недавно запрошенным (в техническом смысле), намного быстрее, чем обычно.
Geometri c Greedy , чье настоящее имя слишком красочно для переполнения стека, представляет собой тип BST, который, как предполагается, «настолько хорош, насколько это возможно» для двоичных файлов. деревья поиска. Это самонастраивающееся дерево, которое смотрит на прошлые шаблоны доступа для реструктуризации дерева, чтобы минимизировать количество узлов, затрагиваемых при поиске. Будет ли это на самом деле оптимальным BST, еще неизвестно.
Деревья поиска по пальцам - это BST, реструктурированные вокруг общей точки доступа, называемой finger , при этом запросы к элементам рядом с пальцем выполняются намного быстрее, чем запросы к элементам, находящимся дальше от пальца.
Надеюсь, это поможет!