模板类二叉搜索树的高度修正function

Question

问题遇到的现象和发生背景

我现在遇到一个问题是关于二叉搜索树的高度修正， 不是AVL就是正常的二叉搜索树。

问题是当插入、删除运行的时候，二叉搜索树的高度会发生变化(下图可看） 那么这个fix_height的意义就在于，如何在这些一系列操作完成之后，依然维持住树的正确高度。

问题相关代码，请勿粘贴截图

    // This assumes that the subtrees rooted at node's children have   // 这里假设根节点
    // correct heights and then walks up the tree from node to the root 
    // correcting the heights.
    // You can imlement this, or correct the heights another way
    void fix_height(Node* node);


template <typename T>
int BST<T>:: getHieght(Node * node)
{   
    node = root_;
    if(node==nullptr)
    {
        return 0;
    }
    else 
    {
        return node->height;
        // int left_height = getHieght(node->left);
        // int right_height = getHieght(node->right); 
        // return max(left_height, right_height) + 1;
    }
    
}



 template <typename T>
void BST<T>:: fix_height(Node* node){
    //int height = 0;

    if(node==nullptr)
    {
     node->height=-1;
    }   
    else if(node->left==nullptr && node->right==nullptr)
    {
        node->height=0;
    }
    else
    {
        node->height=max(getHieght(node->left),getHieght(node->right))+1;
        
    }

运行结果及报错内容

运行结果就是Test没有通过，因为需要修正高度的function有插入，删除最小值，和右旋，这三个都没有过高度修正的测试
插入：a.out: unit_tests.hpp:101: void Tester::test_insert_heights(): Assertion `your_heights == real_heights' failed.

删除最小值：a.out: unit_tests.hpp:137: void Tester::test_delete_min_heights(): Assertion `your_heights == real_heights' failed.

右旋： a.out: unit_tests.hpp:342: void Tester::test_rotate_heights(): Assertion `your_heights == real_heights' failed.

删除 ：a.out: unit_tests.hpp:218: void Tester::test_erase_heights(): Assertion `your_heights == real_heights' failed.

我的解答思路和尝试过的方法

我试图通过不同的情况来更新node的高度，像是如果node是root那么高度就会是-1，当node是leaf node(也就是没有子嗣的node)的时候就设高度为0，但结果都是错误的

我想要达到的结果

希望有哪位能解决我这个问题，如果不会这个function也没问题，另一种方法则是在插入function最后自己更新高度，其他function也是同理，但该如何更新我也不清楚，所以只能跟着这个例子走。

Answer 1

template <typename T>
int BST<T>::update_height(Node* node){
    if(node==nullptr)
    {
        return -1;
    }
    else if(node->left==nullptr && node->right==nullptr)
    {
        node->height=0;
        return 0;
    }
    else
    {
        node->height=max(update_height(node->left),update_height(node->right))+1;
        return node->height;
    }
}

Answer 2

我们的fix_height 是void，没办法return 0

Answer 3

void fix_height(Node* node)
{
  update_height(node);
}

Answer 4

另起炉灶啊，这么牛啊