algorithm - 检查给定 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 中树中的所有值并按此顺序准确插入它们。这样树就永远不会重新平衡，每个节点都会自动放置在正确的位置。