Наилучшая временная сложность, чтобы проверить, является ли двоичное дерево 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) время невозможно прочитать весь ввод.