与えられた二分木がAVL木かどうかを判定するC++プログラム

AVL木（AVL Tree）とは、すべてのノードにおいて、左部分木と右部分木の高さの差が1を超えないことが保証されている自己平衡型二分探索木です。このバランス特性により、木が片側に偏ることを防ぎ、検索・挿入・削除などの操作を常に高い効率で実行できます。

この記事では、与えられた二分木がAVL木であるかどうかを判定するC++プログラムを紹介します。

AVL木の条件

ある二分木がAVL木であるためには、次の条件を満たす必要があります。

• すべてのノードで「左部分木の高さ − 右部分木の高さ」の絶対値が1以下である
• さらに、左右の部分木もそれぞれAVL木である（条件は再帰的に適用される）

アルゴリズム

判定は再帰的に行います。まず根の左右の部分木の高さを求め、その差が1以下であることを確認します。同時に、左右の部分木に対しても同じ判定を再帰的に適用します。空の木（NULL）はAVL木として扱います。

Begin
関数 AVL()：与えられた木がAVL木ならば真(true)、そうでなければ偽(false)を返す
    if(root == NULL)
        return 1
    leftheight = height(root->left)     // 左部分木の高さ
    rightheight = height(root->right)  // 右部分木の高さ
    if(abs(leftheight-rightheight) <= 1 && AVL(root->left) && AVL(root->right))
        return 1
    return 0
End

C++による実装例

#include <bits/stdc++.h>
using namespace std;

class nod { // ノードの宣言
public:
    int data;
    nod* l;
    nod* r;
};

nod* newNod(int d) { // 新しいノードを生成する
    nod* Nod = new nod();
    Nod->data = d;
    Nod->l = NULL;
    Nod->r = NULL;
    return(Nod);
}

int max(int x, int y) { // 2つの値のうち大きい方を返す
    return (x >= y)? x: y;
}

// 木の高さ（根から最も遠い葉ノードまでの最長経路上のノード数）を求める
int height(nod* node) {
    if(node == NULL)
        return 0;
    return 1 + max(height(node->l), height(node->r));
}

// 与えられた木がAVL木かどうかを判定する
bool AVL(nod *root) {
    int lh; // 左部分木の高さ
    int rh; // 右部分木の高さ
    if(root == NULL)
        return 1;
    lh = height(root->l);
    rh = height(root->r);
    if(abs(lh-rh) <= 1 && AVL(root->l) && AVL(root->r)) return 1;
    return 0;
}

int main() {
    // 例1：バランスの取れた木
    nod *root = newNod(7);
    root->l = newNod(6);
    root->r = newNod(12);
    root->l->l = newNod(4);
    root->l->r = newNod(5);
    root->r->r = newNod(13);
    if(AVL(root))
        cout << \"The Tree is AVL Tree\"<<endl;
    else
        cout << \"The Tree is not AVL Tree \"<<endl;

    // 例2：右側に偏った不平衡な木
    nod *root1 = newNod(7);
    root1->l = newNod(6);
    root1->r = newNod(12);
    root1->l->l = newNod(4);
    root1->l->r = newNod(5);
    root1->r->r = newNod(13);
    root1->r->r->r = newNod(26);
    if(AVL(root1))
        cout << \"The Tree is AVL Tree\"<<endl;
    else
        cout << \"The Tree is not AVL Tree \"<<endl;
    return 0;
}

実行結果

The Tree is AVL Tree
The Tree is not AVL Tree

出力の解説

例1の木は、すべてのノードで左右部分木の高さの差が1以内に収まっているため「AVL木である」と判定されます。一方、例2の木では値13のノードの下にさらに26が連なり、右側に偏りが生じて高さの差が2になるため「AVL木ではない」と判定されます。

計算量に関する補足

この実装ではAVL()の各呼び出し内でheight()を再帰的に計算しているため、最悪の場合の時間計算量はO(n²)となります。各ノードの高さを一度だけ求めてボトムアップに判定するよう改良すれば、O(n)まで改善できます。学習用途には十分なシンプルな実装ですが、大規模な木を扱う場合は留意してください。