Сложность обхода по порядку в двоичном дереве поиска (с использованием итераторов)?

Question

Сложность обхода по порядку в двоичном дереве поиска (с использованием итераторов)?

Связанный вопрос: Сложность времени обхода дерева InOrder двоичного дерева O (N)?, однако он основан на обходе через рекурсию (то есть в пространстве O (log N)), в то время как итераторы допускают использование только пространства O (1).

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

Если map реализованы в виде списка пропусков, тогда результат будет очевиден
Однако они часто реализуются как красно-черные деревья (или, по крайней мере, как двоичные деревья поиска)

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

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

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

       3
2       2
1   1   1   1
1 2 1 3 1 2 1 4

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

Сумма составляет 28, для общего числа узлов 15: таким образом, стоимость в среднем меньше 2 на узел, что (если оно выдержит) было бы хорошей амортизированной стоимостью. Так:

Во время обхода в порядке, действительно ли увеличение итератора O (1) для сбалансированного (и полного) бинарного дерева поиска?
Может ли результат быть расширен, чтобы охватить неполные деревья двоичного поиска?

9

algorithm c++complexity-theory

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Да, амортизированная стоимость действительно O(1) за итерацию, для любого дерева.

Доказательство основано на том, сколько раз вы «посещаете» каждый узел.

Листья посещаются только один раз.
Ни один листочек не посещают максимум 3 раза:

при переходе от родителя к самому узлу.
когда возвращаешься из левого поддерева
когда возвращаешься из правильного поддерева

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

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

Худший случай за шаг O(h), который O(logn) в сбалансированном дереве, но может быть O(n) в некоторых случаях.

Постскриптум Я понятия не имею, как красно-черные деревья реализованы в C ++, но если ваша структура данных дерева содержит parent поле от каждого узла, он может заменить рекурсивный стек и разрешить O(1) потребление пространства. (Это, конечно, «обман», потому что хранение n такие поля O(n) сам).

9