Structure de données PHP : l'équilibre des arborescences AVL, maintenant une structure de données efficace et ordonnée

L'arbre AVL est un arbre de recherche binaire équilibré qui garantit des opérations de données rapides et efficaces. Pour atteindre l'équilibre, il effectue des opérations de virage à gauche et à droite, en ajustant les sous-arbres qui violent l'équilibre. Les arbres AVL utilisent l'équilibrage de hauteur pour garantir que la hauteur de l'arbre est toujours petite par rapport au nombre de nœuds, permettant des opérations de recherche de complexité temporelle logarithmique (O (log n)) et maintenant l'efficacité de la structure de données même sur de grands ensembles de données.

Structure de données PHP : la manière équilibrée de l'arborescence AVL, maintenant une structure de données efficace et ordonnée

L'arbre AVL (Adelson-Velsky et Landis) est un arbre de recherche binaire qui maintient l'équilibre pour assurer une recherche rapide et efficace , opérations d’insertion et de suppression. La clé est l’équilibrage de la hauteur, garantissant que la hauteur de l’arbre (la distance entre le nœud racine et le nœud feuille le plus profond) est toujours petite par rapport au nombre de nœuds dans l’arbre.

Pour atteindre l'équilibre dans un arbre AVL, nous devons effectuer deux opérations principales :

1. Rotation à gauche : Ajustez le sous-arbre qui viole l'équilibre en le faisant pivoter du sous-arbre gauche vers le sous-arbre droit.
2. Rotation à droite : ajustez le sous-arbre qui viole l'équilibre et faites-le pivoter du sous-arbre droit vers le sous-arbre gauche.

Implémentation de l'arbre AVL

Nous commençons par une simple classe d'arbre de recherche binaire :

class BinarySearchTree {
    protected $root;

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

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

Pour implémenter l'arbre AVL, nous devons ajouter les fonctions suivantes :

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

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

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

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

Cas pratique

Utilisons AVL tree Stockez un ensemble d'entiers et effectuez une opération de recherche :

$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;
}

Dans un arbre AVL bien équilibré, même si la quantité de données est importante, l'opération de recherche peut être effectuée efficacement dans une complexité temporelle logarithmique (O(log n)) , en maintenant la structure des données. Rapide et efficace.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!