关于检查树是否平衡的函数的疑问？

发布于 2024-11-27 17:01:03 字数 248 浏览 2 评论 0原文

我在《Coding Interview Cracked》一书中看到，要检查 BST 是否平衡，只需找出最大和最小高度之间的差异，但我不确定它是否 100% 正确。虽然我无法找到反测试用例。

任何人都可以确认这种方法是否正确。

用于检查树是否平衡。

|MaxHieght(root) - MinHieght(root)| <=1
   return true
else return false

原文

I read in a book named "Coding Interview Cracked", that to check whether a BST is balanced or not, just find out the difference between the maximum and minimum height but I not sure whether it is 100% correct. Though I am unable to find a counter test case.

Can anyone confirm whether this approach is correct or not.

For checking whether a tree is balanced or not.

|MaxHieght(root) - MinHieght(root)| <=1
   return true
else return false

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

若言繁花未落 2024-12-04 17:01:03

给出平衡的定义（来自 Pedias Wiki）

节点的平衡因子是其左子树的高度减去
其右子树（有时是相反的）和节点的高度
平衡因子 1、0 或 -1 被认为是平衡的。一个节点具有任意
其他平衡因素被认为不平衡，需要重新平衡
树。平衡因子要么直接存储在每个节点上，要么
根据子树的高度计算。

这似乎是正确的。由于 minHeight 和 maxHeight 将等于任一侧的高度，因此看起来定义成立

回复收藏 0 原文

海夕 2024-12-04 17:01:03

如果您愿意，也可以尝试这种方式。

bool isBalanced(node curPtr)
{
        static int heightLeft,heightRight; //Need to save previous return value

        if ( !curPtr )
        {
                return 0;
        }

        heightLeft  = isBalanced(curPtr->lChild);
        heightRight = isBalanced(curPtr->rChild);

        ++heightLeft;   // Height of the Tree should be atleast 1 ( ideally )
        ++heightRight;


        return ( ( ( heightLeft - heightRight ) == 0 ) || (( heightRight - heightLeft ) == 0 ) );
}

华泰

You can try this way also, if you feel like.

bool isBalanced(node curPtr)
{
        static int heightLeft,heightRight; //Need to save previous return value

        if ( !curPtr )
        {
                return 0;
        }

        heightLeft  = isBalanced(curPtr->lChild);
        heightRight = isBalanced(curPtr->rChild);

        ++heightLeft;   // Height of the Tree should be atleast 1 ( ideally )
        ++heightRight;


        return ( ( ( heightLeft - heightRight ) == 0 ) || (( heightRight - heightLeft ) == 0 ) );
}

HTH

回复收藏 0 原文

~没有更多了~