В дереве AVL требуется постоянное количество одиночных и двойных поворотов каждый раз, когда мы перебалансируем при вставке и удалении, поскольку нам нужно только проверить путь от точки вставки или удаления до корня.
Если бы у нас было несбалансированное дерево, нам пришлось бы проверять, сбалансированы ли все возможные узлы, поэтому перебалансировка несбалансированного дерева стоила бы O(n). Это верно?
Требуется время O (n), чтобы перебалансировать несбалансированное дерево, но не по той причине, о которой вы упомянули. В дереве AVL вставки и удаления могут потребовать (log n) поворотов, если дерево было максимально несбалансированным до того, как элемент был вставлен. Потенциально это может потребовать O(n log n) времени для перебалансировки дерева, поскольку вы можете выполнить O(log n) работы для каждого из n узлов.
Однако, используя другие алгоритмы, вы можете перебалансировать дерево за время O(n). Одним из простых вариантов является неупорядоченный обход дерева для получения элементов в отсортированном порядке, а затем восстановление оптимального BST из этих элементов путем рекурсивного построения дерева снизу вверх. Кроме того, вы можете использовать Day-Stout-Warren. алгоритм, который уравновешивает любое дерево за O(n) времени и O(1) пространства.
Надеюсь это поможет!
