检查给定 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

您可能希望将 this 函数拆分为两个函数并避免使用元组，具体取决于您使用的语言。请注意，上面的内容虽然看起来类似于 python 只是伪代码！！！

重建树

这个其实比较简单。获取 level-order 中树中的所有值，并严格按照此顺序插入它们。这样树就永远不会重新平衡，每个节点都会自动放置在正确的位置。

检查给定 BST 是否为有效 AVL 树的有效伪代码

An efficient pseudo-code that check if a given BST is a valid AVL tree

algorithm

insert

binary-search-tree

pseudocode

avl-tree

AVL-树检查

重建树