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

我想实现一个函数 isOk(Node*, int&) 检查BST的每个节点是否遵守了以下属性。

-左右两棵子树的高度可以相差最多一级

一个例子可以是: -它的左右子树的高度最多可以相差1级。

example

这是我写的函数

    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;
    }

我们假设一个Node结构是这样的:

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 函数,其整体复杂度应该会大大增加吧?

话说回来,我试着追踪每一个子树的高度,每次递增 hLhR 每当 isOk.

我这是做错了什么吗?请纠正我哪里错了。

谢谢你

解决方案:

可以有 isOk 归还 pair<bool, int> 其中 bool 表示返回该值的节点是否遵循该属性,并且 int 代表它在树上的高度。

假设 pair<boor, int> propL, propR 分别是当前节点的左、右子节点返回的值,那么当前节点将满足上述属性,如果 propL->first == true && propR->first == true && (int)abs(propL->second-propR->second) <= 1. 然后这个值和当前节点的高度(等于 max(propL->second, propR->second) + 1)将被返回给当前节点的父节点。

给TA打赏
共{{data.count}}人
人已打赏
未分类

衰落数的蟒蛇矩阵

2022-9-8 8:59:36

未分类

如何从嵌套的字典中创建逗号分隔的值?

2022-9-8 8:59:38

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索