找出二叉树是否平衡或效率不高 [英] to find out if a binary tree is balanced or not efficiently

问题描述

如果一个二叉树的左子树&都被认为是高度平衡的，右子树是平衡的，并且左子树和右子树的高度之差小于或等于1。

<我必须找出给定的二叉树是否平衡！

基于上述概念，我使用了以下代码：

  bool isbalanced（结构节点* root）
 {
 int left，right; 
 if（root == NULL）
返回true; 
 else 
 {
 left = height（root-> left）; 
 right = height（root-> right）; 
 if（abs（left-right）< = 1&& isbalanced（root-> right）== true&& isbalanced（root-&left; left）== true）
返回true； 
 else 
 {
 return false; 
} 
} 
} 
  

我使用单独的height（）函数：

  int height（结构节点* root）
 {
 if（ root == NULL）
返回0; 
 int left = height（root-> left）; 
 int right = height（root-> right）; 
 if（left> right）
返回1 + left; 
否则
返回1 +右； 
} 
  

如果树是平衡的或不平衡的，我将获得正确的解决方案。但是如果给定的树倾斜，则时间复杂度将为O（n ^ 2）。

有没有一种方法可以使我以更高效的方式完成此任务

解决方案

您要遍历左右子树两次：一次获取它们的高度，再次测试它们是否平衡。通过使用同时包含高度和平衡标志的结构，您可以省去一半的工作，将一个结构向下传递，由左侧的子树填充，再将另一个右侧的结构填充。

然后，您可以通过在扫描右侧时使用左侧子树中的信息来进一步改进（反之亦然）。在整体树不平衡但每个子树都平衡的许多情况下，可以使用左侧子树信息（并带有适当的记账 ¹ ）来尽早切断右侧子树的搜索。

¹ _{簿记详细信息留给读者练习}

A binary tree is said to be height balanced if both its left sub-tree & right sub-tree are balanced and the difference between the height of left sub-tree and right sub-tree is less than or equal to 1.

i have to find out if a given binary tree is balanced or not!

based on the above concept i have used the following code:

bool isbalanced(struct node *root)
{
    int left,right;
    if(root==NULL)
    return true;
    else
    {
        left=height(root->left);
        right=height(root->right);
        if(abs(left-right)<=1 && isbalanced(root->right)==true && isbalanced(root->left)==true)
        return true;
        else
        {
            return false;
        }
    }
}

I have calculated the height using a separate height() function:

int height(struct node *root)
{
    if(root==NULL)
    return 0;
    int left=height(root->left);
    int right=height(root->right);
    if(left>right)
    return 1+left;
    else
    return 1+right;
}

I am getting the correct solution if the tree is balanced or unbalanced. But if the given tree is skewed the time complexity would be O(n^2).

Can there be a method so that i can accomplish this task in a more efficient way?

解决方案

You are traversing the left and right subtrees twice: once to get their height and again to test whether they are balanced. You can eliminate half the work by using a structure that contains both the height and a balanced flag, passing one structure down to be filled in by the left subtree and another by the right.

You can then improve on this even more by using the information from the left subtree when scanning the right (or vice versa). The left subtree information can be used (with appropriate bookkeeping¹) to cut off the right subtree search early in many cases where the overall tree is unbalanced but each subtree is balanced.

¹ _{bookkeeping details are left as an exercise for the reader}

这篇关于找出二叉树是否平衡或效率不高的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！