Créez des structures de données d'arborescence de recherche avancées avec PHP

Construire des arbres de recherche avancés à l'aide de PHP implique de créer des classes de nœuds (Node) et des classes d'arbres de recherche (SearchTree), ainsi que de mettre en œuvre des méthodes d'insertion, de recherche et de suppression d'éléments. Les éléments sont stockés dans un arbre binaire en complexité temporelle logarithmique, chaque nœud contenant une valeur et des liens vers ses sous-arbres gauche et droit. En pratique, vous pouvez créer un arbre de recherche et insérer des éléments, rechercher des valeurs spécifiques ou même supprimer des éléments de l'arbre.

Créer une structure de données d'arborescence de recherche avancée à l'aide de PHP

L'arbre de recherche est une structure de données efficace qui permet de rechercher, d'insérer et de supprimer des éléments dans une complexité temporelle logarithmique. Cet article vous guidera dans la création d'un arbre de recherche avancé à l'aide de PHP.

1. Créez une classe de nœuds

Tout d'abord, créez une classe nommée Node pour représenter les nœuds dans l'arborescence : Node 的类来表示树中的节点：

class Node {
    public $value;
    public $left;
    public $right;

    public function __construct($value) {
        $this->value = $value;
        $this->left = null;
        $this->right = null;
    }
}

2. 创建搜索树类

接下来，创建一个名为 SearchTree

class SearchTree {
    private $root;

    public function __construct() {
        $this->root = null;
    }

    // 其他方法（见下文）
}

2. Créez une classe d'arbre de recherche

Ensuite, Créez une classe appelée SearchTree pour représenter l'arbre de recherche lui-même :

public function insert($value) {
    if ($this->root === null) {
        $this->root = new Node($value);
    } else {
        $this->_insert($value, $this->root);
    }
}

private function _insert($value, $node) {
    if ($value < $node->value) {
        if ($node->left === null) {
            $node->left = new Node($value);
        } else {
            $this->_insert($value, $node->left);
        }
    } else {
        if ($node->right === null) {
            $node->right = new Node($value);
        } else {
            $this->_insert($value, $node->right);
        }
    }
}

3. Insérer des éléments

Pour insérer un nouvel élément, utilisez la méthode suivante :

public function find($value) {
    if ($this->root === null) {
        return null;
    } else {
        return $this->_find($value, $this->root);
    }
}

private function _find($value, $node) {
    if ($value === $node->value) {
        return $node;
    } elseif ($value < $node->value) {
        if ($node->left === null) {
            return null;
        } else {
            return $this->_find($value, $node->left);
        }
    } else {
        if ($node->right === null) {
            return null;
        } else {
            return $this->_find($value, $node->right);
        }
    }
}

4. Pour rechercher un élément, vous pouvez utiliser la méthode suivante :

public function delete($value) {
    if ($this->root === null) {
        return;
    } else {
        $this->root = $this->_delete($value, $this->root);
    }
}

private function _delete($value, $node) {
    // ...
}

5. Supprimer un élément

Pour supprimer un élément, vous pouvez utiliser la méthode suivante (il s'agit d'un processus récursif, l'implémentation spécifique est omise) :

$tree = new SearchTree();
$tree->insert(10);
$tree->insert(5);
$tree->insert(15);
$tree->insert(7);
$tree->insert(12);
$tree->insert(20);

Cas pratique

Créons un arbre de recherche et insérons quelques éléments :

$foundNode = $tree->find(12);
if ($foundNode !== null) {
    echo "Found the node with value 12." . PHP_EOL;
}

🎜 Ensuite, on peut trouver un élément : 🎜

$tree->delete(12);

🎜Enfin, on peut supprimer un élément : 🎜rrreee

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!