🐥

【C＃によるコード付】AVL木とは？2分探索木の違いも解説

2024/07/16に公開

データ構造

 はじめにデータ構造の一つであるAVL木は、2分探索木 (Binary Search Tree, BST) の一種であり、自己平衡性を保つ特性を持ちます。本記事では、AVL木の基本概念と、2分探索木との違いについて解説します。また、C#でのAVL木の実装例も紹介します。
二分探索木については以下の記事で実装、説明を行っています。

https://zenn.dev/student_blog/articles/d7e198cecbfa3d

 AVL木とは？AVL木は、自己平衡2分探索木の一種であり、以下の特性を持ちます。
各ノードの左部分木と右部分木の高さの差は最大で1です。
この特性により、AVL木は常にほぼ平衡な状態を保ちます。
これにより、AVL木は挿入、削除、検索の操作が最悪でも O(log n) の時間複雑度で実行可能です。

 AVL木の例        30
     (2-2=0)
       / \
     20   40
 (1-0=1) (1-1=0)  
    /    /  \
   10   35   50
この木では、各ノードの左右の部分木の高さの差は1以下です。()内は左部分木の高さ-右部分木の高さを表しています。

 AVL木の操作
 挿入新しいノードを挿入する際、以下の手順を取ります。
根ノードからスタートし、新しいノードの値を比較します。
新しいノードの値が小さい場合は左部分木、大きい場合は右部分木に進みます。
空の位置に到達したら、そこに新しいノードを挿入します。
挿入後に部分木の高さを更新し、AVL木のバランスを保つために必要に応じて回転操作を行います。

 バランスを取る方法ここでは、左の木に対して挿入が起きて、左の木の高さが+1された場合を考えます。（右の木への挿入は左右を入れ替えただけで同じ操作です。）
バランスが-1から0になる場合：バランスが取れたことになる。自身の高さも変わらないので親もバランスを取れている。
バランスが0から1になる場合：バランスが取れたことになる。しかし、自身の高さが+1されてしまうので親から根にかけてバランスが許容範囲外である可能性が生じる。そのため、修正の必要がある。
バランスが1から2になる場合：2パターンある
左の子の左の子の高さが1増える場合：以下に示すように右回転をすることで、バランスを回復させる。
左の子の右の子の高さが1増える場合：以下に示すように左回転をして右回転を行うことでバランスを回復させる。


 回転
 右回転例(Right Rotation)右回転は、左部分木の高さが右部分木の高さよりも大きくなった場合に行います。

次のAVL木において、ノード5を根とする部分木の左部分木が不均衡です。
        5
       / \
      3   7
     / \
    2   4
   /
  1
ノード5を右回転させます。
ノード3が新しい根になります。
ノード5がノード3の右子ノードになります。
ノード4がノード5の左子ノードになります。
右回転後の木:
        3
       / \
      2   5
     /   / \
    1   4   7

 左回転例 (Left Rotation)左回転は、右部分木の高さが左部分木の高さよりも大きくなった場合に行います。

次のAVL木において、ノード3を根とする部分木の右部分木が不均衡です。
    3
   / \
  1   5
     / \
    4   7
         \
          9
ノード3を左回転させます。
ノード5が新しい根になります。
ノード3がノード5の左子ノードになります。
ノード7がノード3の右子ノードになります。
左回転後の木:
    5
   / \
  3   7
 / \   \
1   4   9

 C#による実装以下に、AVL木の基本的な実装例を示します。
using System;
using System.Collections.Generic;
using System.Threading;

/// <summary>
/// AVL木を実装します．
/// AVL木では一般にノードクラスを定義します．
/// </summary>
/// <typeparam name="T"></typeparam>
public class AVLNode<T> where T : IComparable<T>
{
  public T Data;
  public AVLNode<T> Left;
  public AVLNode<T> Right;
  public int Balance;

  public AVLNode(T _data)
  {
    Data = _data;
    Left = null;
    Right = null;
    Balance = 0;
  }
}

/// <summary>
/// AVL木の実装クラスです．
/// </summary>
/// <typeparam name="T"></typeparam>
public class AVLTree<T> where T : IComparable<T>
{
  public AVLNode<T> Root;

  public AVLTree()
  {
    Root = null;
  }

  /// <summary>
  /// 要素の挿入を行います
  /// </summary>
  /// <param name="_data"></param>
  public void Insert(T _data)
  {
    bool _grow;
    (Root, _grow) = InsertRec(Root, _data);
  }

  /// <summary>
  /// 挿入のために再帰的に行います．
  /// 戻り値bool(_grow)は木の高さが変更された場合にtrueになります．
  /// </summary>
  /// <param name="_node"></param>
  /// <param name="_data"></param>
  /// <returns></returns>
  private (AVLNode<T>, bool) InsertRec(AVLNode<T> _node, T _data)
  {
    bool _grow = true;

    //nullならばその場所に要素を挿入する．
    //そのために，return _nodeを行う．
    if (_node == null)
    {
      _node = new AVLNode<T>(_data);
      return (_node, true);
    }

    //挿入ノードの値が比較ノードの値よりも小さいならば，Leftを探索
    if (_data.CompareTo(_node.Data) < 0)
    {
      (_node.Left, _grow) = InsertRec(_node.Left, _data);

      //左の木の高さが+1されたならば，バランスは+1される．
      if (_grow) { _node.Balance++; (_node, _grow) = Balance(_node); }
    }

    //大きいならば，Rightを探索
    else
    {
      (_node.Right, _grow) = InsertRec(_node.Right, _data);

      //右の木の高さが+1されたならば，バランスは-1される．
      if (_grow) { _node.Balance--; (_node, _grow) = Balance(_node); }
    }

    return (_node, _grow);
  }

  /// <summary>
  /// バランスをとるための操作を行う．
  /// </summary>
  /// <returns></returns>
  private (AVLNode<T>, bool) Balance(AVLNode<T> _node)
  {
    if (_node.Balance == 0)
    {
      return (_node, false);
    }
    else if (Math.Abs(_node.Balance) == 1)
    {
      return (_node, true);
    }
    else
    {
      //左木部分が2長い
      if (_node.Balance == 2)
      {
        //左子ノードから見て左 > 右
        if (_node.Left.Balance > 0)
        {
          //右回転を行う
          _node = RotateRight(_node);
          _node.Balance = 0;
          return (_node, false);
        }
        //左子ノードから見て左 < 右
        else
        {
          //左回転を行って，右回転を行う
          _node.Left = RotateLeft(_node.Left);
          _node = RotateRight(_node);
          _node.Balance = 0;
          return (_node, false);
        }
      }
      //右木部分が2長い
      else
      {
        //右子ノードからみて左 < 右
        if (_node.Right.Balance < 0)
        {
          //左回転を行う
          _node = RotateLeft(_node);
          _node.Balance = 0;
          return (_node, false);
        }
        //右子ノードからみて左 < 右
        else
        {
          //右回転を行い，左回転を行う．
          _node.Right = RotateRight(_node.Right);
          _node = RotateLeft(_node);
          _node.Balance = 0;
          return (_node, false);
        }
      }
    }
  }

  /// <summary>
  /// 右回転を行う．
  /// </summary>
  /// <param name="_node"></param>
  /// <returns></returns>
  private AVLNode<T> RotateLeft(AVLNode<T> _node)
  {
    AVLNode<T> _right = _node.Right;
    _node.Right = _right.Left;
    _right.Left = _node;

    //ノードのバランスを求める．
    CalBalance(_node);
    return _right;
  }

  /// <summary>
  /// 左回転を行う．
  /// </summary>
  /// <param name="_node"></param>
  /// <returns></returns>
  private AVLNode<T> RotateRight(AVLNode<T> _node)
  {
    AVLNode<T> _left = _node.Left;
    _node.Left = _left.Right;
    _left.Right = _node;

    //ノードのバランスを求める．
    CalBalance(_node);
    return _left;
  }

  /// <summary>
  /// ノードのバランスを求める．
  /// </summary>
  /// <param name="_node"></param>
  private void CalBalance(AVLNode<T> _node)
  {
    _node.Balance = 0;
    if (_node.Left == null && _node.Right != null)
    {
      _node.Balance = -1;
    }
    else if (_node.Left != null && _node.Right == null)
    {
      _node.Balance = 1;
    }
  }
}

public class Example
{
  public static void Main()
  {
    AVLTree<int> tree = new AVLTree<int>();
    tree.Insert(34);
    tree.Insert(51);
    tree.Insert(72);
    tree.Insert(17);
    tree.Insert(44);
    tree.Insert(50);
  }
}

 2分探索木との違いAVL木と2分探索木の主な違いは次の通りです。
構造の特性:
2分探索木: 各ノードの左部分木は小さい値、右部分木は大きい値。
AVL木: 各ノードの左部分木と右部分木の高さの差が最大1であるため、常に平衡を保つ。
性能:
2分探索木: 平均的には効率的ですが、最悪の場合 O(n) の操作時間がかかる可能性があります。
AVL木: 最悪の場合でも O(log n) の操作時間を保証します。

 まとめAVL木は、自己平衡性を保つことで、効率的な検索、挿入、削除操作を実現するデータ構造です。一方、標準の2分探索木は、特に平衡が保たれない場合に性能が低下する可能性があります。これらのデータ構造の理解と使い分けは、効率的なプログラミングにおいて重要です。C#での実装例を参考に、ぜひ自分でも試してみてください。

 参考書籍データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)

https://amzn.to/3YtOnpz

はじめに

AVL木とは？

AVL木の例

AVL木の操作

挿入

バランスを取る方法

回転

右回転例(Right Rotation)

左回転例 (Left Rotation)

C#による実装

2分探索木との違い

まとめ

参考書籍

Discussion