判断是否平衡树的优化算法

布满荆棘的人生 2022-05-29 14:09 136阅读 0赞

**平衡二叉搜索树**

左右高度差不超过1  
高度可以保持在log2N，插入/删除/查找效率log2N

1.左边增加结点，bf–，右边增加结点，bf++  
2.如果增加过后，bf==0,说明高度不变，填平了矮的一边  
3.如果bf==|1|，说明本来平衡，继续往上更新bf  
4.如果bf==|2|，不再更新，开始调整

旋转  
1.左单旋/右单旋  
2.右左双旋/左右双旋

**面试题**

判断一个二叉树是否为平衡树（要求时间复杂度最优）

递归算法：(相当于前序 根->左->右)  
1.先计算左右子树高度  
2.左子树高度减去右子树高度绝对值小于2  
//判断  
1.当前树  
2.左子树  
3.右子树

优化算法->（后序 左->右->根）
    附带检查平衡因子
    时间复杂度：O(N)
    
    bool _IsBalance(Node* root, int& height)  
    {  
        if (root == NULL)
        {
            int height = 0;
            return true;  
        }
        int leftdepth = 0;
        int rightdepth = 0;  
    
        //只要有一棵子树不是平衡树，就可以结束递归操作 
        if (_IsBalance(root->_left, leftheight)== false)  
            return false;  
    
        if (_IsBalance(root->_right, rightheight) == false)  
            return false;  
    
        height = leftheight > rightheight ? (leftheight + 1) : (rightheight + 1);  
    
        return abs(leftheight - rightheight) > 2; 
    }

附加检查平衡因子
    
    bool _IsBalance(Node* root, int& height)  
    {  
        if (root == NULL)
        {
            int height = 0;
            return true;  
        }
        int leftdepth = 0;
        int rightdepth = 0;  
    
        //只要有一棵子树不是平衡树，就可以结束递归操作 
        if (_IsBalance(root->_left, leftheight)== false)  
            return false;  
    
        if (_IsBalance(root->_right, rightheight) == false)  
            return false;
    
        //检查平衡因子 
        if(rightheight - leftheight != _root->_bf)
        {
            cout<<"平衡因子异常"<<endl; 
        }
    
        height = leftheight > rightheight ? (leftheight + 1) : (rightheight + 1);  
    
        return abs(leftheight - rightheight) > 2; 
    }

特殊场景

因为在双旋时调用了两个单旋，而单旋最后将平衡因子置为0，导致双旋的平衡因子出现不可预知的错误。  
![这里写图片描述][70]

[70]: /images/20220529/9a70bb3c8d1a403aa18540bd63c20d33.png