Home > Backend Development > PHP Tutorial > Build advanced search tree data structures with PHP

Build advanced search tree data structures with PHP

王林
Release: 2024-05-07 14:45:02
Original
410 people have browsed it

Building advanced search trees using PHP involves creating node classes (Node) and search tree classes (SearchTree), and implementing methods for inserting, finding, and deleting elements. The elements are stored in a binary tree in logarithmic time complexity, with each node containing a value and links to its left and right subtrees. In practice, you can create a search tree and insert elements, find specific values, or even delete elements from the tree.

用 PHP 构建先进的搜索树数据结构

Using PHP to build advanced search tree data structures

The search tree is an efficient data structure that allows logarithmic Find, insert and delete elements within time complexity. This article will guide you through building an advanced search tree using PHP.

1. Create a node class

First, create a class named Node to represent the nodes in the tree:

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

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

2. Create a search tree class

Next, create a class named SearchTree to represent the search tree itself:

class SearchTree {
    private $root;

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

    // 其他方法(见下文)
}
Copy after login

3. Insert element

To insert a new element, you can use the following method:

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);
        }
    }
}
Copy after login

4. Find the element

To To find an element, you can use the following method:

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);
        }
    }
}
Copy after login

5. Delete element

To delete an element, you can use the following method (this is a recursive process, specifically Implementation omitted):

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

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

Practical case

Let us create a search tree and insert some elements:

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

Then, we can find an element :

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

Finally, we can delete an element:

$tree->delete(12);
Copy after login

The above is the detailed content of Build advanced search tree data structures with PHP. For more information, please follow other related articles on the PHP Chinese website!

Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template