特定のアルゴリズム - 複雑さはO（N）

Question

Iバイナリツリー満たしている場合、このプロパティを確認することができるプログラムを記述する必要がなければならない：ツリーの各ノードは、その高さのために

（左右）のサブツリーは、最大1

良くないために異なっていなければなりません：

グッド：

私が構築されたアルゴリズムは、O((n^2)log(n))複雑性を有します。

ありがとうございました！私が知っている

bool check(node* root){ 
    if(!root->right && !root->left){ 
     return; 
    } 

    int h; 
    int n_node; 
    int hRight, hLeft; 

    h = height(root); 
    hRight = height_right(root); 
    hLeft = height_left(root); 

    n_node = pow(2, heihgt+1)-1; 

    if((hRight > n_node/2 && hLeft <= n_node/4) || (hLeft > n_node/2 && hRight <= n_node/4) 
     return true; 
} 

は格好良いではないですが、それは試みです。 このアルゴリズムは、firtsノード（ルート）に対してのみ機能するため、O（nlog（n））であることに注意してください。だから私はノードをスクロールするために別のブロックの中に入れなければならない。

Answer 1

ノードの数ではなく、高さの点で、バランスのとれたツリーの定義が正面にあるときにノードを数える理由は不明です。

難しい部分は、深さを計算して別々に残高をチェックすると、あまりにも複雑すぎることになるということです（O（n^2）と思います）。

したがって、ツリーを横断するときに両方を計算するヘルパー関数が必要です。
これは非常に簡単なソリューションです：

// Returns whether 'root' is a balanced tree. 
// Also stores the tree's height in *height. 
bool balanced_height(node* root, int* height) 
{ 
    // The trivial base case – an empty tree is balanced and has height 0. 
    if (root == nullptr) 
    { 
     *height = 0; 
     return true; 
    } 

    // Information gathering using recursion: 
    // Find out whether the subtrees are balanced, and get their heights. 
    int leftheight = 0; 
    int rightheight = 0; 
    bool leftbalance = balanced_height(root->left, &leftheight); 
    bool rightbalance = balanced_height(root->right, &rightheight); 

    // Now that we know the heights of the subtrees, we can store the height of this tree. 
    *height = max(leftheight, rightheight) + 1; 

    // Finally, a translation into C++ of the definition: 
    // A tree is balanced if and only if 
    // - the subtrees are balanced, and 
    // - the heights of the subtrees differ by at most one. 
    return leftbalance && rightbalance && abs(leftheight - rightheight) <= 1; 
} 

bool balanced(node* root) 
{ 
    int height = 0; 
    return balanced_height(root, &height); 
} 

それは我々がじゃないので、最初は、アンバランスである場合に、第2のサブツリーを横断しないことにより、アンバランスの場合にはわずかに速い（しかし、同じ複雑さを持つ）行うことができますその場合には何でも高さを使うようになります。
この最適化は練習として残されています。