AVLツリーの挿入、回転、およびバランス係数の説明

AVLツリーとは何ですか?

AVLツリーは、二分探索木のサブタイプです。発明者のアデルソン、ベルスキー、ランディスにちなんで名付けられたAVL木は、二分探索木が示すすべての特性に加えて、動的な自己平衡の特性を備えています。

BSTは、ノードで構成されるデータ構造です。次の保証があります。

  1. 各ツリーにはルートノード(上部)があります。
  2. ルートノードには、0個、1個、または2個の子ノードがあります。
  3. 各子ノードには、0、1、または2つの子ノードなどがあります。
  4. 各ノードには最大2つの子があります。
  5. 各ノードについて、その左側の子孫は現在のノードよりも小さく、現在のノードは右側の子孫よりも小さくなっています。

AVLツリーには追加の保証があります。

  1. 右と左のサブツリーの深さの違いは、複数にすることはできません。この保証を維持するために、AVLの実装には、要素を追加するとこの保証が混乱する場合にツリーのバランスを取り直すアルゴリズムが含まれます。

AVLツリーには、最悪の場合のルックアップ、挿入、および削除のO(log n)時間があります。

右回転

AVLツリーの右回転

左回転

AVLツリーの左回転

AVL挿入プロセス

通常の二分探索木の挿入と同様の挿入を行います。挿入後、左または右の回転を使用してAVLプロパティを修正します。

  • 右のサブツリーの左の子に不均衡がある場合は、左右の回転を実行します。
  • 左サブツリーの左の子に不均衡がある場合は、右回転を実行します。
  • 右サブツリーの右の子に不均衡がある場合は、左回転を実行します。
  • 左サブツリーの右の子に不均衡がある場合は、右左回転を実行します。

AVLツリーは、自己平衡二分探索木です。AVLツリーは、次のプロパティを持つ二分木です。->すべてのノードのサブツリーの高さは最大で1つ異なります。->すべてのサブツリーはAVLツリーです。

AVLツリーは、左右のサブツリーの高さをチェックし、差が1以下であることを確認します。この差はバランス係数と呼ばれます。AVLツリーの高さは常にO(Logn)です。ここで、nはツリー内のノードの数です。

AVLツリーローテーション

AVLツリーでは、挿入や削除などのすべての操作を実行した後、ツリー内のすべてのノードのバランス係数を確認する必要があります。すべてのノードがバランス係数の条件を満たす場合、操作を終了します。それ以外の場合は、バランスをとる必要があります。回転操作を使用して、操作によってツリーのバランスが崩れるたびに、ツリーのバランスを取ります。

回転操作は、ツリーのバランスをとるために使用されます.4つの回転があり、2つのタイプに分類されます。

シングル左回転(LL回転)

LL回転では、すべてのノードが現在の位置から1つ左に移動します。

単一右回転(RR回転)

RR回転では、すべてのノードが現在の位置から1つ右に移動します。

左右回転(LR回転)

LR回転は、単一の左回転とそれに続く単一の右回転の組み合わせです。LR回転では、最初にすべてのノードが現在の位置から1つの位置を左に移動し、次に1つの位置を右に移動します。

右左回転(RL回転)

RL回転は、単一の右回転とそれに続く単一の左回転の組み合わせです。RL回転では、最初にすべてのノードが現在の位置から1つの位置を右に移動し、次に1つの位置を左に移動します。

AVL木の時間分析

AVLツリーは、任意のノードの左側のサブツリーと右側のサブツリーの高さの差が1を超えることはできないという追加のプロパティを持つ二分探索木です。

アルゴリズム平均最悪の場合:スペース:O(n)、時間:O(n)

AVL木の応用

AVLツリーは、挿入と削除がそれほど頻繁ではないが、そこに存在するアイテムを頻繁に検索する必要があるデータベースを設計している場合に役立ちます。