Maison >développement back-end >Problème PHP >Comment implémenter une arborescence de segments de ligne en PHP

Comment implémenter une arborescence de segments de ligne en PHP

醉折花枝作酒筹
醉折花枝作酒筹avant
2021-06-28 16:33:422070parcourir

L'arbre de segments de ligne est un arbre de recherche binaire, similaire à l'arbre d'intervalles. Il divise un intervalle en intervalles unitaires, et chaque intervalle unitaire correspond à un nœud feuille dans l'arbre de segments de ligne. Ci-dessous, l'éditeur partagera avec vous comment implémenter des arborescences de segments de ligne en PHP. Vous pouvez vous y référer si vous en avez besoin.

Comment implémenter une arborescence de segments de ligne en PHP

1. Les fonctionnalités

  • n'est pas nécessairement un arbre binaire complet

  • doit soyez paisible Arbre binaire

  • les nœuds feuilles stockent les valeurs réelles, tandis que les nœuds non-feuilles stockent le contenu personnalisé

2. Degré de complexité temporelle

操作 时间复杂度
查询 O(logn)

3. Illustration de l'arbre de segments de ligne

Comment implémenter une arborescence de segments de ligne en PHP

4. Code

<?php
/**
 * content: 线段树(区间树)
 * create: 2020-11-12
 */

namespace HeapBundle;

use ArrayBundle\BaseArray;

class SegmentTreeHeap
{
    /**
     * 传入的数组对象
     * @var BaseArray 
     */
    protected $array;

    /**
     * 数组
     * @var array 
     */
    protected $tree = [];

    public function __construct(BaseArray $array)
    {
        $this->array = $array;
        $this->build(0, 0, $this->array->getSize() - 1);
    }

    /**
     * 构建线段树
     * @param int $treeIndex
     * @param int $min
     * @param int $max
     * @throws \Exception
     */
    public function build(int $treeIndex, int $min, int $max)
    {
        // 如果线段区间的最小值和最小值相同,则表示为叶子结点
        if ($min == $max) {
            $this->tree[$treeIndex] = $this->array->get($max);
            return;
        }

        // 四舍五入取中间值  最大值减最小值然后除以2拿到中间值,并加上最小值
        $mid = floor(($max - $min) / 2) + $min;

        // 获取左儿子的索引值,并递归往下构建
        $leftIndex = $this->leftChildIndex($treeIndex);
        $this->build($leftIndex, $min, $mid);

        // 获取右儿子的索引值,并递归往下构建
        $rightIndex = $this->rightChildIndex($treeIndex);
        $this->build($rightIndex, $mid + 1, $max);

        // 非叶子结点的值保留的是它下面所有结点的相加值, 这里可以改为它下面结点的总和值
        $this->tree[$treeIndex] = $this->tree[$leftIndex] . &#39;+&#39; . $this->tree[$rightIndex];
    }

    /**
     * 打印线段树
     */
    public function varDump()
    {
        ksort($this->tree);
        print_r($this->tree);
    }

    /**
     * 获取线段树的长度
     * @return int
     */
    public function getSize(): int
    {
        return count($this->tree);
    }

    /**
     * 获取左儿子索引
     * @param int $parentIndex
     * @return int
     * @throws \Exception
     */
    public function leftChildIndex(int $parentIndex): int
    {
        if ($parentIndex < 0) throw new \Exception(&#39;父结点的索引不能小于0&#39;);
        return $parentIndex * 2 + 1;
    }

    /**
     * 获取右儿子索引
     * @param int $parentIndex
     * @return int
     * @throws \Exception
     */
    public function rightChildIndex(int $parentIndex): int
    {
        if ($parentIndex < 0) throw new \Exception(&#39;父结点的索引不能小于0&#39;);
        return $parentIndex * 2 + 2;
    }
}

Exemple

<?php
require_once __DIR__ . &#39;/../../vendor/autoload.php&#39;;
$array = new ArrayBundleBaseArray();
for ($i = 0; $i < 10; $i++) {
 $array->addLast($i + 10);
}
$heap = new HeapBundleSegmentTreeHeap($array);
$heap->varDump();
Array
(
    [0] => 10+11+12+13+14+15+16+17+18+19
    [1] => 10+11+12+13+14
    [2] => 15+16+17+18+19
    [3] => 10+11+12
    [4] => 13+14
    [5] => 15+16+17
    [6] => 18+19
    [7] => 10+11
    [8] => 12
    [9] => 13
    [10] => 14
    [11] => 15+16
    [12] => 17
    [13] => 18
    [14] => 19
    [15] => 10
    [16] => 11
    [23] => 15
    [24] => 16
)

Apprentissage recommandé. : Tutoriel vidéo php

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!

Déclaration:
Cet article est reproduit dans:. en cas de violation, veuillez contacter admin@php.cn Supprimer