Где можно узнать производительность AA-tree?
Конкретно о производительности алгоритма, (средний, худший случай). Где можно узнать это?
Ответы (1 шт):
Насколько я помню, AA-tree отличается от красно-чёрных деревьев упрощением балансировок и уменьшением количества разных случаев. Значит, время работы такое же, как у RB - O(logN) для всех трёх базовых операций в среднем и худшем случае.
Вот и английская Вика подтверждает:
Performance The performance of an AA tree is equivalent to the performance of a red-black tree. While an AA tree makes more rotations than a red-black tree, the simpler algorithms tend to be faster, and all of this balances out to result in similar performance. A red-black tree is more consistent in its performance than an AA tree, but an AA tree tends to be flatter, which results in slightly faster search times.