наилучшая временная сложность, чтобы проверить, является ли двоичное дерево avl-деревом (сбалансировано по высоте)

Question

Итак, меня спросили в интервью, возможно ли, чтобы проверка, является ли дерево avl-деревом, могла бы быть: T (n) = O (log (n))

и не знал ответа, после поиска в Google лучшие алгоритмы, которые я видел, были O (n) ("https://www.geeksforgeeks.org/how-to-determine-if-a-binary-tree-is-balanced/")

это сделать алгоритм с O (log (n))?

Answer 1

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

Обратите внимание, что за O(log n) время невозможно прочитать весь ввод.