Erstellen Sie mit PHP erweiterte Suchbaum-Datenstrukturen

Das Erstellen erweiterter Suchbäume mit PHP umfasst das Erstellen von Knotenklassen (Node) und Suchbaumklassen (SearchTree) sowie das Implementieren von Methoden zum Einfügen, Suchen und Löschen von Elementen. Die Elemente werden in einem Binärbaum in logarithmischer Zeitkomplexität gespeichert, wobei jeder Knoten einen Wert enthält und mit seinen linken und rechten Teilbäumen verknüpft ist. In der Praxis können Sie einen Suchbaum erstellen und Elemente einfügen, bestimmte Werte suchen oder sogar Elemente aus dem Baum löschen.

Erstellen Sie eine erweiterte Suchbaum-Datenstruktur mit PHP.

Der Suchbaum ist eine effiziente Datenstruktur, die das Suchen, Einfügen und Löschen von Elementen in logarithmischer Zeitkomplexität ermöglicht. Dieser Artikel führt Sie durch den Aufbau eines erweiterten Suchbaums mit PHP.

1. Erstellen Sie eine Knotenklasse

Erstellen Sie zunächst eine Klasse mit dem Namen Node, um die Knoten im Baum darzustellen: 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 Erstellen Sie eine Suchbaumklasse

Als nächstes Erstellen Sie eine Klasse namens SearchTree, um den Suchbaum selbst darzustellen:

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. Elemente einfügen

Um ein neues Element einzufügen, verwenden Sie die folgende Methode:

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. Elemente suchen

Um ein Element zu finden, können Sie die folgende Methode verwenden:

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

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

5. Ein Element löschen

Um ein Element zu löschen, können Sie die folgende Methode verwenden (dies ist ein rekursiver Prozess, die spezifische Implementierung wird weggelassen) :

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

Praktischer Fall

Erstellen wir einen Suchbaum und fügen einige Elemente ein: 🎜

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

🎜 Dann können wir ein Element finden: 🎜

$tree->delete(12);

🎜Zuletzt können wir ein Element löschen: 🎜rrreee

Das obige ist der detaillierte Inhalt vonErstellen Sie mit PHP erweiterte Suchbaum-Datenstrukturen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!