Народ, при вставке в красно-черное дерево, сложность балансировки в худшем

Question

supapro.cxx

Александр

Народ, при вставке в красно-черное дерево, сложность балансировки в худшем

случае логарифмическая?

#c #embedded #programming #russian

0

06.06.2022

1 ответов

7 просмотров

Bulat Ziganshin · Accepted Answer

в википедии это глубоко закопано, но всё же есть: Все рекурсивные вызовы функции хвостовые и преобразуются в циклы, так что алгоритм требует памяти O(1). В алгоритме выше, все случаи связаны по очереди, кроме случая 3, где может произойти возврат к случаю 1, который применяется к предку узла: это единственный случай когда последовательная реализация будет эффективным циклом (после одного вращения в случае 3). Так же, хвостовая рекурсия никогда не происходит на дочерних узлах, поэтому цикл хвостовой рекурсии может двигаться только от дочерних узлов к их последовательным родителям. Произойдет не более, чем O(log n) циклических возвратов к случаю 1 (где n — общее количество узлов в дереве до удаления). Если в случае 2 произойдет вращение (единственно возможное в цикле случаев 1-3), тогда отец узла N становится красным после вращения и мы выходим из цикла. Таким образом будет произведено не более одного вращения в течение этого цикла. После выхода из цикла произойдет не более двух дополнительных поворотов. А в целом произойдет не более трех поворотов дерева.

170 похожих чатов

Народ, при вставке в красно-черное дерево, сложность балансировки в худшем

1 ответов

Похожие вопросы