PHP を使用して高度な検索ツリー データ構造を構築する

PHP を使用して高度な検索ツリーを構築するには、ノード クラス (Node) と検索ツリー クラス (SearchTree) を作成し、要素を挿入、検索、削除するためのメソッドを実装する必要があります。要素は対数時間計算量でバイナリ ツリーに格納され、各ノードには値とその左右のサブツリーへのリンクが含まれます。実際には、検索ツリーを作成して要素を挿入したり、特定の値を検索したり、ツリーから要素を削除したりすることもできます。

PHP を使用した高度な検索ツリー データ構造の構築

検索ツリーは、対数検索、挿入を可能にする効率的なデータ構造です。複雑な時間内で要素を削除します。この記事では、PHP を使用して高度な検索ツリーを構築する方法を説明します。

1. ノード クラスを作成します

まず、ツリー内のノードを表す Node という名前のクラスを作成します。

##2. 検索ツリー クラスを作成します

##次に、検索ツリー自体を表す SearchTree

という名前のクラスを作成します。 #3. 要素の挿入

新しい要素を挿入するには、

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

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

4 のメソッドを使用します。 # 要素を見つけるには、次のメソッドを使用できます:

class SearchTree {
    private $root;

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

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

5. 要素の削除

要素を削除するには、次のメソッドを使用できます (このは再帰的なプロセスです。具体的には実装は省略します):

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

実用的なケース

検索ツリーを作成し、いくつかの要素を挿入してみましょう:

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

次に、要素を見つけることができます:

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

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

最後に、要素を削除できます:

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

以上がPHP を使用して高度な検索ツリー データ構造を構築するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。