Эффективный псевдокод, который проверяет, является ли данный BST допустимым деревом AVL

Question

Мне нужно написать алгоритм (в псевдокоде), который проверяет, является ли данное дерево BST допустимым деревом AVL. При этом мне нужно присвоить каждому узлу ранг (в деревьях AVL ранг означает высоту узла), поэтому результатом будет правильное дерево AVL.

Я подумал о простом алгоритме, который вычисляет на каждом шаге высоту узла и высоту его двух сыновей (если сыновья равны нулю, то высота равна -1), а затем проверяет, равна ли разница между высотами 1,1 или 1,2 или 2,1. Если нет, то это не дерево AVL. Если да, то мы делаем то же самое для node.left и node.right.

Моя проблема с этим алгоритмом заключается в том, что временная сложность очень велика и может доходить даже до O (n ^ 2). Есть ли более эффективный алгоритм?

Другой алгоритм, который я хочу найти, заключается в том, что при наличии действительного дерева AVL и ранга каждого узла (rank = height) мне нужно найти серию вставок, которые строят одно и то же дерево. Я думал о том, чтобы сделать это по отсортированному порядку клавиш, но результат не правильный.

Answer 1

AVL-проверка дерева

Вы действительно правильно поняли. Но вы упустили использование рекурсивного определения высоты дерева

height(node) =  1 + max(height(node.left), height(node.right))

, поэтому вы получили огромную сложность (хотя O(2^n) слишком пессимистично). Вместо непосредственного вычисления высоты узла при подходе сверху вниз, вы можете пойти другим путем и вычислить высоту отдельных узлов снизу вверх:

valid_avl(node):
    if node is null then
        return -1, True

    left_height, left_valid = valid_avl(node.left)
    right_height, right_valid = valid_avl(node.right)

    if not left_valid or not right_valid or abs(left_height - right_height) > 1 then
        return -1, False
    else
        return 1 + max(left_height, right_height), True

Возможно, вы захотите разделить эту функцию на две функции и избежать использования кортежей, в зависимости от языка, который вы используете. Обратите внимание, что выше, хотя выглядит похожим на Python просто псевдокод !!!

Восстановление дерева

Это на самом деле довольно просто. Получите все значения в дереве в level-order и вставьте их точно в этом порядке. Таким образом, дерево никогда не перебалансируется, и каждый узел автоматически помещается в правильное положение.