Сохранение бинарного дерева при вставке элементов в порядок

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

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

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

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

В качестве примера предположим, что у меня было следующее дерево:

       4
      / \
     /   \
    2     6
   / \   / \
  1   3 5   7

Есть ли простой способ поддерживать баланс при вставке нового элемента, если я знаю, что элемент будет больше 7?

Ответ 1

Если вы действительно заинтересованы в этом, используя BST (который, я думаю, не самый лучший вариант, как вы можете прочитать в моем другом ответе), вы можете сделать это следующим образом:

Иметь нормальный BST. Это означает, что поиск - это O (log N), если нам удастся сохранить глубину во время вставок.

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

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

Например, в первом дереве ниже поддерево 4 не является совершенным, но поддерево 5 (дерево с только одним node является идеальным по определению). Итак, мы добавляем 6 в качестве родительского элемента 5, что означает, что теперь 4 является родительским для 6, а 5 - левым дочерним элементом 6.

Если мы попытаемся добавить еще один node, то поддерево 4 все еще не является совершенным, и ни один из них не является 6. И 6 является самым правым node, поэтому мы добавляем 7 в качестве правильного ребенка от 6.

     4             4             4
    / \           / \           / \
   /   \         /   \         /   \
  2     5 -->   2     6 -->   2     6
 / \           / \   /       / \   / \
1   3         1   3 5       1   3 5   7

Если мы используем этот алгоритм, поддерево левого дочернего элемента корня всегда будет совершенным, а поддерево правого ребенка никогда не будет иметь большую высоту, чем у левой. Из-за этого высота всего дерева всегда будет O (log N), и так будет время поиска. Вставка также займет время O (log N).

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

По сравнению с решением на основе массива из моего другого ответа временная сложность поиска одинакова, но этот BST имеет худшее время вставки.

Ответ 2

В соответствии с требованиями, которые вы описываете, вам вообще не нужно дерево. Выбранный динамический массив - это все, что вам нужно.

При вставке всегда вставляйте в конец (O (1) амортизируется).

При поиске используйте обычный двоичный поиск (O (log N)).

Это предполагает, что вам не нужны какие-либо другие операции, или что вы не возражаете, они будут O (N).

Ответ 3

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

Я не уверен, что бинарное дерево лучше всего подходит для быстрой вставки, когда вы его описываете. Но могут быть и другие структуры данных, которые хорошо справляются с используемым случаем, который вы описываете: "Хотя я никогда не использовал его, skip-list приходит мой разум. Поскольку вы всегда вставляете элементы, которые больше, чем все элементы уже в коллекции, должно быть довольно легко обновить указатели.