PHP实现线段树

1. 特征

  • 不一定是完全二叉树

  • 一定是平和二叉树

  • 叶子结点存储的是实际的值,非叶子结点存的是自定义的内容

2. 时间复杂度

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

3. 线段树的图解

【php】8. 数据结构(PHP实现) -- 线段树的实现

4. 代码

<?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] . '+' . $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('父结点的索引不能小于0');

return $parentIndex * 2 + 1;

}

/**

* 获取右儿子索引

* @param int $parentIndex

* @return int

* @throws \Exception

*/

public function rightChildIndex(int $parentIndex): int

{

if ($parentIndex < 0) throw new \Exception('父结点的索引不能小于0');

return $parentIndex * 2 + 2;

}

}

5.示例

<?php

require_once __DIR__ . '/../../vendor/autoload.php';

$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

)

以上是 PHP实现线段树 的全部内容, 来源链接: utcz.com/a/111212.html

回到顶部