Сложный анализ упражнений на деревьях RB - PullRequest
Новая
       86

Сложный анализ упражнений на деревьях RB

0 голосов
/ 18 мая 2018 
BLACK_PATH(T,x)
 if x==NIL 
    then return TRUE
 if COLOR(x)==BLACK
    then return BLACK_PATH(T,left(x)) || BLACK_PATH(T,right(x))
 return FALSE

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

T (n) <= 2T (2n / 3) + O (1) </p>

Используя дерево рекурсии, я получаю T (n) = O (n).Это правильно?

1 Ответ

0 голосов
/ 18 мая 2018

Сложность этого метода линейна (O(n)) в худшем случае в отношении количества элементов в дереве.

Использование основной теоремы в терминах общего числа узлов здесьсложно, потому что не учитывает свойства красного черного дерева.Хотя в целом для куч, как правило, верно, что каждое поддерево дерева с n узлами имеет максимум 2n/3 узлов, также верно, что для красных черных деревьев каждое поддерево имеет максимум n/2 black узлы.Это связано с тем, что красно-черные деревья сбалансированы по отношению к черным узлам (каждый путь вниз к конечному узлу от произвольного узла имеет одинаковое количество черных узлов).

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

Таким образом, вместо использованияT(n)<=2T(2n/3)+O(1) Вы должны использовать T(m)<=T(m/2)+O(1), где m - это количество черных узлов, которые дают вам O(m), и, поскольку, как уже говорилось, O(m)==O(n), у нас есть O(n).

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

...