首页 文章

一种有效的伪代码，用于检查给定的BST是否是有效的AVL树

提问于
浏览 次
0

如果给定的BST树是有效的AVL树，我需要编写一个算法（伪代码） . 在这样做时，我需要给每个节点一个等级（在AVL树等级中意味着节点的高度），因此结果将是有效的AVL树 .

我想到了一个简单的算法，它在每个步骤中计算一个节点的高度和它的两个儿子的高度（如果儿子是空的，那么高度是-1），然后检查高度之间的差异是否为1,1或1,2或2,1 . 如果没有那么它不是AVL树 . 如果是，我们对node.left和node.right执行相同操作 .

我的算法问题是时间复杂度非常大，甚至可以达到O（n ^ 2） . 有更高效的算法吗？

我想要找到的另一种算法是，当给出一个有效的AVL树和每个节点的等级（rank = height）时，我需要找到一系列构建同一棵树的插入 . 我想通过键的排序顺序来做，但结果不对 .

algorithm insert binary-search-tree pseudocode avl-tree

1 回答

  • 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树中的所有值，并按此顺序插入它们 . 这样，树永远不会重新 balancer ，每个节点都会自动放置在正确的位置 .

    回复于

相关问题