c++ - 对函数进行逻辑检查以查找树是平衡的还是不平衡的

Question

我正在阅读编码书，其中一个问题要求编写一个函数来检查二叉树的高度是否平衡。例如，如果一棵树的右子树的高度为 4（意味着它的深度为 4），而左子树的深度为 6，则它不平衡，但如果它偏离 1，则没关系。

所以我实现了这个逻辑：

int FindNodeHeight(BTNode<int>* node) {

    if(!node)  return 0;
    return std::max(FindNodeHeight(node->lhs), FindNodeHeight(node->rhs)) + 1;
}

bool IsTreeBalanced(BinarySearchTree<int>* root) {

    int left = FindNodeHeight(root->root.lhs);
    int right = FindNodeHeight(root->root.rhs);

    std::cout << "left: " << left << " - right: " << right << std::endl;

    if(std::abs(left - right) > 1) {
        return false;
    }

    return true;
}

但我认为根据解决方案的解释可能是错误的，但我不明白为什么。以下是简化的类：

template <typename T>
// Binary Tree Node
class BTNode {
public:
    T data;
    BTNode* lhs;
    BTNode* rhs;

    BTNode() {
        lhs = NULL;
        rhs = NULL;
    }
};

template <typename T>
class BinarySearchTree {
public:
    BTNode<T> root;
};

这是创建图形和调用函数的主要位置：

BinarySearchTree<int>* t_unbalanced = new BinarySearchTree<int>();
t_unbalanced->root.data = 1;
t_unbalanced->root.lhs = new BTNode<int>(2);
t_unbalanced->root.rhs = new BTNode<int>(3);
t_unbalanced->root.rhs->rhs = new BTNode<int>(4);
t_unbalanced->root.rhs->rhs->rhs = new BTNode<int>(5);

if(IsTreeBalanced(t_unbalanced)) {
    cout << "Tree is balanced" << endl;
}
else {
    cout << "Tree is unbalanced" << endl;
}

Answer 1

考虑以下情况：

            x
           / \
          x   x
         /     \
        x       x
       /         \
      x           x
     /             \
    .               .
   .                 .
  .                   .
 /                     \
x                       x

您的算法表明树是平衡的，因为左树的高度等于右树的高度。然而树的高度是n/2=theta(n)!=O(log(n))。因此，树是不平衡的。

平衡搜索树是在最坏情况下高度为 O(logn) 并且操作 INSERT、DELETE 和 SEARCH 可以在 O(logn) 时间内实现的树。

见源。