Я знаю, что удаление узла в дереве AVL требует временной сложности O (logn). При этом удаление дерева AVL с n узлами заняло бы O (n logn). Однако мне интересно, если моя цель состоит в том, чтобы иметь отсортированный элемент дерева AVL, чтобы я мог удалить все элементы в O (n) вместо O (n logn). Возможно, путем реализации элемента удаления, который будет принимать O (1).
Я не смог найти способ сделать это в O (n). Это потому, что мы не можем или я что-то упустил?