Блог

Я изучаю деревья AVL. Деревья AVL — это бинарные деревья поиска, которые балансируют себя посредством поворотов. Поскольку они сбалансированы, время запроса равно O (log n). Но порядок, в котором добавляются записи, также важен, чтобы избежать наихудшего случая O (log n) поворотов за вставку.

Каково асимптотическое время выполнения:

(a) добавление n записей с последовательными ключами в дереве AVL (время для вставки всех, а не каждого из них)

б) поиск ключа, которого нет в дереве.

Насколько я понимаю, эта высота равна O (log N), поэтому вставка в дерево AVL имеет наихудший случай O (log N). Поиск Авл дерево является абсолютно неизменным часов по британскому летнему времени, и поэтому тоже требует времени, пропорционального длине дерева, что делает o(зарегистрируйте N).

Правильно ли это?

Для вставки в AVL требуется не более одного оборота, а не O (log n) оборотов (два, если считать двойные обороты по отдельности). Асимптотически порядок вставки не имеет значения, поскольку вращение занимает постоянное время.

а) при n вставке стоимость = n * (стоимость поиска подходящего места для вставки фактическое создание и вставка узла вращение, если необходимо) = n * (O (log n) O (1) O (1)) = O (n log n)

б) поиск элемента равен O (log n), поскольку дерево сбалансировано

c) для удаления одного элемента требуется не более O (log n) оборотов, поэтому сложность удаления также равна O (log n)