时间戳

首页 > 解决方案 > C++ 提高了检查 BST 是否高度平衡的效率？

c++ - C++ 提高了检查 BST 是否高度平衡的效率？

问题描述

我正在尝试实现一个函数isOk(Node*, int&)来检查 BST 的每个节点是否遵循以下属性：

- 其左右子树的高度最多可以相差 1 级。

一个例子可能是：

例子

这是我写的函数：

    bool isOk(Node* tree, int& maxH)
    {
        //if leaf, property is respected
        if(!tree->left_ && !tree->right_) return true;
        
        //otherwise
        int hL = 0;
        int hR = 0;
        bool propL = isOk(tree->left_, hL);
        bool propR = isOk(tree->right_, hR);
        
        if(propL) hL++;
        if(propR) hR++;
        if(hL - hR => -1 && hL - hR <= 1) {
                maxH = max(hL, hR);
                return true;
        }
        else return false;
    }

我们假设结构节点是这样的：

struct Node
{
    Node* left_;
    Node* right_;
    int label_;

    //no constructor or destructor, this is not the focus
};

最初我写了这部分：

/*...*/
    int hL = 0;
    int hR = 0;
    bool propL = isOk(tree->left_, hL);
    bool propR = isOk(tree->right_, hR);
    
    if(propL) hL++;
    if(propR) hR++;
/*...*/

通过以下方式：

int hL = height(tree->left_);
int hR = height(tree->right_);
bool propL = isOk(tree->left_, hL);
bool propR = isOk(tree->right_, hR);

函数height(Node*)是：

int height( Node* tree)
{
    if(tree== NULL) return 0;
    int leftH = 0;
    int rightH = 0;
    leftH = height(tree->left_);
    rightH = height(tree->right_);
    return 1 + max(leftH, rightH);
}

height现在，如果我没记错的话，复杂度应该是 O(n)。所以，如果在我的isOk函数中使用它，它的整体复杂性应该会大大增加，对吧？

也就是说，我试图跟踪每个子树的高度，每次hL和hR每次调用isOk.

这是我做错了什么吗？请在我错的地方纠正我。

谢谢！

标签： c++algorithmperformancebinary-search-tree

解决方案

可以isOk返回一个pair<bool, int>，其中bool表示返回此值的节点是否遵循所述属性并int表示它在树中的高度。

假设pair<boor, int> propL, propR是当前节点的左右孩子分别返回的值，则当前节点将满足所述属性 iff propL->first == true && propR->first == true && (int)abs(propL->second-propR->second) <= 1。然后这个值连同当前节点的高度（等于max(propL->second, propR->second) + 1）将返回给当前节点的父节点。

推荐阅读