PHP를 사용하여 고급 검색 트리 데이터 구조 구축

PHP를 사용하여 고급 검색 트리를 구축하려면 노드 클래스(Node) 및 검색 트리 클래스(SearchTree)를 만들고 요소를 삽입, 찾기 및 삭제하는 방법을 구현해야 합니다. 요소는 로그 시간 복잡도의 이진 트리에 저장되며 각 노드에는 값이 포함되어 있으며 왼쪽 및 오른쪽 하위 트리에 대한 링크가 있습니다. 실제로는 검색 트리를 만들고 요소를 삽입하고 특정 값을 찾거나 트리에서 요소를 삭제할 수도 있습니다.

PHP를 사용하여 고급 검색 트리 데이터 구조 구축

검색 트리는 로그 시간 복잡도에서 요소를 찾고, 삽입하고, 삭제할 수 있는 효율적인 데이터 구조입니다. 이 기사에서는 PHP를 사용하여 고급 검색 트리를 구축하는 과정을 안내합니다.

1. 노드 클래스 만들기

먼저, 트리의 노드를 나타내는 Node라는 클래스를 만듭니다. 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. 검색 트리 클래스를 만듭니다

다음, 검색 트리 자체를 나타내는 SearchTree라는 클래스를 만듭니다.

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. 요소 삽입

새 요소를 삽입하려면 다음 방법을 사용하세요.

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. 요소

요소를 찾으려면 다음 방법을 사용할 수 있습니다:

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

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

5. 요소 삭제

요소를 삭제하려면 다음 방법을 사용할 수 있습니다(이는 재귀 프로세스이며 구체적인 구현은 다음과 같습니다). 생략):

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

실제 사례

검색 트리를 만들고 일부 요소를 삽입해 보겠습니다. 🎜

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

🎜 그런 다음 요소를 찾을 수 있습니다. 🎜

$tree->delete(12);

🎜마지막으로 요소를 삭제할 수 있습니다. 🎜rrreee

위 내용은 PHP를 사용하여 고급 검색 트리 데이터 구조 구축의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!