Более эффективное время выполнения в схеме - AVL

Question

Так у меня в принципе есть функция avl?который запускается в O (n ^ 2), это так, потому что каждый раз, когда я повторяюсь, я вызываю высоту, которая является функцией O (n) (где n - количество узлов в дереве).* Моя проблема в том, что я хочу сделать AVL?бегать в O (N) время.Мне дали подсказку: «Вы должны попытаться ограничить вызов своей функции высоты в течение постоянного времени, независимо от того, к какому размеру BST вы применяете. Таким образом, вы можете получить время выполнения O (n) для всех».... Я не уверен, как заставить мой рост работать в постоянном времени, ты.Любое предложение, чтобы сделать мой avl?работать в O (n), а не O (n ^ 2)?

Answer 1

Если вам не разрешено хранить высоту в дереве, вы можете избежать ее пересчета, имея рабочую функцию, которая сообщает вам высоту дерева и , если это дерево AVL.Затем каждый узел рассматривается ровно один раз, и у вас есть алгоритм O (n).Затем вызовите работника из оболочки, которая забывает часть высоты результата работника.Разумеется, вам следует сократить путь, поэтому, если определенное поддерево определено как нарушающее условие балансировки, не пытайтесь проверять больше поддеревьев, верните #f и поддельную высоту.

Answer 2

Другим вариантом будет сохранение высоты в каждом узле, где значение представляет высоту поддерева, укорененного в этом узле. Очевидно, что при таком подходе возвращение высоты поддерева было бы операцией O (1).

Это означает, что все операции, которые изменяют дерево (вставка, удаление и т. Д.), Должны поддерживать высоту в актуальном состоянии всякий раз, когда в дереве происходят структурные изменения.