Эффективность вращения дерева AVL

Question

Какова эффективность Big O вращения дерева AVL?

Например, при вставке: - O (logN) для поиска позиции - O (1) для вставки -? для балансировки (если она должна быть перебалансирована)

Я думал, что это будет O (logN), но я нашел сайт, который утверждает, что это O (1) - если я не неправильно его прочитал - http://users.informatik.uni -halle.de / ~ jopsi / dinf504 / chap4.shtml

(Будет ли то же самое для 2-3 деревьев?)

Заранее спасибо за помощь

Answer 1

Сложность O (log n), как вы говорите. Я полагаю, что в этой статье они означают постоянное время для каждой операции перебалансировки, то есть каждого оборота, в то время как вы должны сделать O (log n) оборотов. Как бы то ни было, сложность, как вы говорите, логарифмическая.