PHP データ構造: AVL ツリーのバランス、効率的で秩序あるデータ構造の維持

AVL ツリーは、高速かつ効率的なデータ操作を保証するバランスのとれた二分探索ツリーです。バランスを達成するために、左回転と右回転の操作を実行し、バランスに反するサブツリーを調整します。 AVL ツリーは高さバランシングを利用して、ツリーの高さがノード数に対して常に小さくなるようにし、対数時間計算量 (O(log n)) のルックアップ操作を可能にし、大規模なデータ セットでもデータ構造の効率を維持します。

PHP データ構造: AVL ツリーのバランスの取れた方法で、効率的で順序付けされたデータ構造を維持します。

AVL (Adelson-Velsky および Landis) ツリーは、高速かつ効率的な検索を保証するためにバランスを維持するバイナリ検索ツリーです。 、挿入および削除操作。重要なのは高さのバランスであり、ツリーの高さ (ルート ノードから最も深いリーフ ノードまでの距離) がツリー内のノードの数に比べて常に小さくなるようにします。

AVL ツリーのバランスを実現するには、2 つの主な操作を実行する必要があります:

1. 左回転: バランスに違反しているサブツリーを、左のサブツリーから右のサブツリーに回転して調整します。
2. 右回転: バランスに違反しているサブツリーを調整し、右のサブツリーから左のサブツリーに回転します。

AVL ツリーの実装

簡単な二分探索ツリー クラスから始めます:

class BinarySearchTree {
    protected $root;

    // 插入节点
    public function insert($value) {
        // ...
    }

    // 查找节点
    public function search($value) {
        // ...
    }
}

AVL ツリーを実装するには、次の関数を追加する必要があります:

class AVLTree extends BinarySearchTree {
    // 获取节点的高度
    public function height(Node $node) {
        // ...
    }

    // 检查节点是否平衡
    public function isBalanced(Node $node) {
        // ...
    }

    // 左旋节点
    public function leftRotate(Node $node) {
        // ...
    }

    // 右旋节点
    public function rightRotate(Node $node) {
        // ...
    }
}

実際的なケース

AVL を使ってみましょう整数のセットを格納し、検索操作を実行します:

$avlTree = new AVLTree();
$avlTree->insert(10);
$avlTree->insert(5);
$avlTree->insert(15);
$avlTree->insert(3);
$avlTree->insert(7);
$avlTree->insert(12);
$avlTree->insert(17);

// 查找值 12
$result = $avlTree->search(12);

if ($result) {
    echo "找到值 " . $result->value . PHP_EOL;
} else {
    echo "未找到值 12" . PHP_EOL;
}

バランスの取れた AVL ツリーでは、データ量が多くても、検索操作は対数計算量 (O(log n)) 内で効率的に完了できます。 、データ構造の維持 高速かつ効率的。

以上がPHP データ構造: AVL ツリーのバランス、効率的で秩序あるデータ構造の維持の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。