AVL木の特徴と実装概要

AVL木は自己平衡二分探索木の一種で、挿入や削除操作を行っても常に木が平衡な状態を保つことが特徴です。この特性により、AVL木は最悪のケースでもO(log n)の時間で基本操作を行うことができます。

AVL木の特徴

1. 自己平衡性:
2. AVL木は各ノードに「高さ」の情報を持たせ、挿入や削除の際に木の高さの差（バランス因子）を調整します。

3. バランス因子は、左部分木の高さから右部分木の高さを引いた値で、-1, 0, 1の範囲に収まる必要があります。

4. 挿入と削除:

5. データの挿入や削除の後、AVL木はそれ自体を再平衡化します。これにより、木が常に平衡状態を保ちます。

6. 探索の効率性:

7. AVL木は二分探索木の特性を持ちながらも、より厳密に平衡性を保つため、探索操作が非常に効率的です。

AVL木の実装概要

AVL木の基本操作（挿入、削除、探索）は以下のように実装されます。

ノードの定義

まず、AVL木のノードを定義します。

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1  # 初期の高さは1

高さとバランス因子の計算

次に、ノードの高さとバランス因子を計算するための関数を作成します。

def get_height(node):
    if not node:
        return 0
    return node.height

def get_balance(node):
    if not node:
        return 0
    return get_height(node.left) - get_height(node.right)

回転操作

AVL木では、木が不均衡な場合に回転を行います。回転には右回転と左回転があります。

def right_rotate(y):
    x = y.left
    T2 = x.right

    # 回転実行
    x.right = y
    y.left = T2

    # 高さの更新
    y.height = max(get_height(y.left), get_height(y.right)) + 1
    x.height = max(get_height(x.left), get_height(x.right)) + 1

    return x

def left_rotate(x):
    y = x.right
    T2 = y.left

    # 回転実行
    y.left = x
    x.right = T2

    # 高さの更新
    x.height = max(get_height(x.left), get_height(x.right)) + 1
    y.height = max(get_height(y.left), get_height(y.right)) + 1

    return y

挿入操作

挿入操作では、通常の二分探索木による挿入を行った後、木のバランスを整えます。

def insert(root, key):
    # 通常のBST挿入
    if not root:
        return Node(key)
    elif key < root.key:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)

    # 高さの更新
    root.height = 1 + max(get_height(root.left), get_height(root.right))

    # バランスの確認
    balance = get_balance(root)

    # 左左ケース
    if balance > 1 and key < root.left.key:
        return right_rotate(root)

    # 右右ケース
    if balance < -1 and key > root.right.key:
        return left_rotate(root)

    # 左右ケース
    if balance > 1 and key > root.left.key:
        root.left = left_rotate(root.left)
        return right_rotate(root)

    # 右左ケース
    if balance < -1 and key < root.right.key:
        root.right = right_rotate(root.right)
        return left_rotate(root)

    return root

探索操作

AVL木の探索は、通常の二分探索木と同様に行います。

def search(root, key):
    if root is None or root.key == key:
        return root
    if key < root.key:
        return search(root.left, key)
    return search(root.right, key)

実装例

最後に、AVL木の実装をテストするためのサンプルコードを示します。

if __name__ == "__main__":
    root = None

    # ノードの挿入
    keys = [10, 20, 30, 40, 50, 25]
    for key in keys:
        root = insert(root, key)

    # 探索
    search_key = 30
    result = search(root, search_key)
    if result:
        print(f"キー {search_key} は AVL木に存在します。")
    else:
        print(f"キー {search_key} は AVL木に存在しません。")

まとめ

AVL木は、自己平衡を保つことで効率的なデータ検索を実現するデータ構造です。今回は、AVL木の基本的な特徴、ノードの定義、基本操作の実装を行いました。AVL木を利用することで、大量のデータを効率的に管理することが可能です。