Какое двоичное дерево вы бы порекомендовали?

Я изучаю Haskell и в качестве упражнения создаю бинарные деревья. Сделав обычное двоичное дерево, я хочу адаптировать его к самобалансирующемуся. Так:

• Какой самый эффективный?
• Что проще всего реализовать?
• Что чаще всего используется?

Но главное, что вы рекомендуете?

Я предполагаю, что это принадлежит здесь, потому что это открыто для обсуждения.

Я бы порекомендовал вам начать либо с красно-черного дерева , либо с дерева AVL .

Красно-черное дерево быстрее вставляется, но дерево AVL имеет небольшое преимущество при поиске. Дерево AVL, вероятно, немного проще в реализации, но не настолько сильно, исходя из моего собственного опыта.

Дерево AVL гарантирует, что дерево сбалансировано после каждой вставки или удаления (ни одно поддерево не имеет коэффициента баланса, превышающего 1 / -1, в то время как красно-черное дерево обеспечивает разумную сбалансированность дерева в любое время.

Я бы рассмотрел альтернативу, если вы в порядке со случайными структурами данных: Пропускать списки .

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

Вы получите O (log N) вставок / поисков / удалений, и вам не придется иметь дело со всеми этими сложными случаями ребалансировки.

Я никогда не думал о том, чтобы реализовать их на функциональном языке, и на странице википедии их нет, поэтому это может быть непросто (по сравнению с неизменностью)

Если вы хотите, чтобы структура начала была относительно простой (как AVL-деревья, так и красно-чёрные деревья довольно неудобны), один из вариантов - это treap, который называется комбинацией «tree» и «heap».

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

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

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

Какой самый эффективный?

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

Если вы имеете в виду «время выполнения» или «использование памяти», то вам нужно сравнить фактические реализации. Затем вступают в игру язык, время выполнения, ОС и другие факторы, что затрудняет ответ на вопрос.

Что проще всего реализовать?

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

Что чаще всего используется?

Расплывчато и сложно ответить. Сначала есть "кем?" часть этого? Только на Хаскеле? А как насчет C или C ++? Во-вторых, существует проблема проприетарного программного обеспечения, когда у нас нет доступа к источнику для проведения опроса.

Но главное, что вы рекомендуете?

Я предполагаю, что это принадлежит здесь, потому что это открыто для обсуждения.

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

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

Вот список:

http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree

Есть шесть популярных из них определены. Начните с тех.

Если вас интересуют Splay-деревья, есть более простая версия, которая, как мне кажется, была впервые описана в статье Аллена и Манро. Он не имеет таких же гарантий производительности, но позволяет избежать сложностей при работе с «зигзагом» и «зигзагом».

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

Как и в случае Splay-деревьев, идея заключается в том, что объекты, к которым недавно обращались, всегда находятся рядом с корнем дерева, поэтому быстрый доступ к ним снова. Проще говоря, эти деревья поворота к корню Allen-Munroe (как я их называю - не знаю официального названия) могут быть быстрее, но они не имеют такой же амортизированной гарантии производительности.

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

Очень простое сбалансированное дерево - это дерево АА . Его инвариант проще и, следовательно, легче реализовать. Из-за своей простоты его производительность все еще хороша.

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