1. 首页
  2. PHP
  3. 数据结构-PHP 线段树的实现

数据结构-PHP 线段树的实现

码农天地 -
数据结构-PHP 线段树的实现
1.线段树介绍

线段树是基于区间的统计查询，线段树是一种 二叉搜索树，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)，线段树是一颗 平衡二叉树。

2.线段树示意图

如下图所示，数组 E中，假设区间 0-9 一共 10 个元素，每个儿子节点区间元素的个数都是父亲节点元素个数的一半，若出现 奇数 的情况，则右儿子元素区间比 左儿子 元素区间多一个：

Tips：如图所示的中节点中区间指的是数组 E 的索引值。3.线段树需要空间分析

假设我们把 线段树 看做是一颗 满二叉树，并且不考虑添加元素的情况（即区间固定），对于区间有 n 个元素的数组若 n=2^k(k是正整数) 则需要 2n 的空间，最差的情况是若 n=2^k+1 则需要 4n 的空间，如下图所示，最下面一层没有元素的节点使用 null 填充：

Tips: 若索引是从 i=0 开始的，左儿子 left(i) = 2*i+1，右儿子 right(i) = 2*i+2，parent(i) = (i-1)/2 取整；

对于满二叉树来说，需要的节点数如下：

若当 n=2^k+1 需要的的空间数：

Tips：对于区间有 n 个元素的数组若 n=2^k(k是正整数) 则需要 2n 的空间，最差的情况是若 n=2^k+1 则需要 4n 的空间就足够了。4.定义 SegmentTree 线段树类

其中定义了 leftSon($i) 方法，表示求某个节点左儿子节点索引值的方法，rightSon($i) 表示求某个节点右儿子节点 索引值 的方法：

<?php
class SegmentTree
{
    private $data = []; //用于存储原始数组
    private $tree = []; //用于存储线段树节点元素的值
    /**
     * 构造函数 初始化线段树
     * SegmentTree constructor.
     * @param array $arr
     */
    public function __construct(array $arr) {
        for ($i = 0; $i < count($arr); $i++) {
            $this->data[$i] = $arr[$i];
        }
        //若是静态语言需要开 4n 空间来表示 $this->tree
    }
    public function getSize() {
        return count($this->data);
    }
    public function get(int $index) {
        if ($index < 0 || $index >= count($this->data)) {
            echo "索引错误";
            exit;
        }
        return $this->data[$index];
    }
    /**
     * 获取某个节点儿子节点索引，若索引是从 i=0 开始的，左儿子 left(i) = 2*i+1
     * @param $i
     * @return int
     */
    private function leftSon($i): int {
        return $i * 2 + 1;
    }
    /**
     * 获取某个节点右儿子节点索引，若索引是从 i=0 开始的，右儿子 left(i) = 2*i+2
     * @param $i
     * @return int
     */
    private function rightSon($i): int {
        return $i * 2 + 2;
    }
}
5.创建线段树

接下来使用递归思想去 创建线段树，下面给出递归函数 PHP 代码：

 if ($left == $right) {
            $this->tree[$i] = $this->data[$left]; //处理递归到叶子节点时 并赋值最原始的 $data 对应的索引值
        } else {
            $leftSon = $this->leftSon($i); //左儿子索引
            $rightSon = $this->rightSon($i); //右儿子索引
            $mid = $left + ceil(($right - $left) / 2);//求区间中值
            $this->buildSegmentTree($leftSon, $left, $mid - 1); //递归左儿子树
            $this->buildSegmentTree($rightSon, $mid, $right); //递归右儿子树
            $this->tree[$i] = $this->merge->operate($this->tree[$leftSon], $this->tree[$rightSon]); //这里是根据业务来定节点需要存储的元素
        }
Tips：其中节点元素存储的值需要根据业务来定，如上面代码表示的是每个节点存储的是 区间求和 的值，很显然这种方式不灵活，用户在实例化该类的时候可以传入一个 merge 对象用于元素操作的。6.节点元素计算规则

上述SegmentTree类中可以在 __construct() 方法中传入一个 $merge 对象，$merge 中可以定义一个 operate() 方法计算得出节点元素值，如下：

<?php
class SegmentTree
{
    private $data = [];
    private $tree = [];
    private $merge = null; //表示的是一个 节点操作的对象
    /**
     * 构造函数 初始化线段树
     * SegmentTree constructor.
     * @param array $arr
     */
    public function __construct(array $arr, $merge) {
        $this->merge = $merge;
        for ($i = 0; $i < count($arr); $i++) {
            $this->data[$i] = $arr[$i];
        }
        //若是静态语言需要开 4n 空间来表示 $this->tree
        //递归创建线段树
        $this->buildSegmentTree(0, 0, count($this->data) - 1);
    }
    private function buildSegmentTree(int $i, int $left, int $right) {
        if ($left == $right) {
            $this->tree[$i] = $this->data[$left]; //处理递归到叶子节点时 并赋值最原始的 $data 对应的索引值
        } else {
            $leftSon = $this->leftSon($i); //左儿子索引
            $rightSon = $this->rightSon($i); //右儿子索引
            $mid = $left + ceil(($right - $left) / 2);//求区间中值
            $this->buildSegmentTree($leftSon, $left, $mid - 1); //递归左儿子树
            $this->buildSegmentTree($rightSon, $mid, $right); //递归右儿子树
            $this->tree[$i] = $this->merge->operate($this->tree[$leftSon], $this->tree[$rightSon]); //这里是根据业务来定节点需要存储的元素
        }
    }
    public function getSize() {
        return count($this->data);
    }
    public function get(int $index) {
        if ($index < 0 || $index >= count($this->data)) {
            echo "索引错误";
            exit;
        }
        return $this->data[$index];
    }
    /**
     * 获取某个节点儿子节点索引，若索引是从 i=0 开始的，左儿子 left(i) = 2*i+1
     * @param $i
     * @return int
     */
    private function leftSon($i): int {
        return $i * 2 + 1;
    }
    /**
     * 获取某个节点右儿子节点索引，若索引是从 i=0 开始的，右儿子 left(i) = 2*i+2
     * @param $i
     * @return int
     */
    private function rightSon($i): int {
        return $i * 2 + 2;
    }
}
6.1 Merge 类定义

如下定义就可以很灵活的处理每个节点的计算规则：

class Merge{
    public funcrion operate($left,$right){
    //这里可以定义需要操作的规则
    return $left+$right; //如求平均值，这里可以 return ($left+$right)/2;
    }
}
7. 求和演示

若是各个线段区间存储的是区间求和，则 Merge 类中的 operate() 方法返回是两个元素的和，代码如下：

<?php
require 'SegmentTree.php';
class Merge
{
    public function operate($left, $right) {
        return $left + $right;
    }
}
$merge = new Merge();
$arr = [0,1,2,3,4,5,6,7,8,9];
$merge = new Merge();
$segmentTree = new SegmentTree($arr,$merge);
print_r($segmentTree);

输出如下：

此时线段树的节点元素值示意图如下：

8. 线段树的区间查询

这里以查询 [2-6] 区间为例，若要查询区间 [2-6] 的求和需要根据区间来寻找需要求的值，示意图如下：

PHP 代码使用递归思想实现如下：

 public function query($qleft, $qright) {
        if ($qleft < 0 || $qright >= count($this->data) || $qright < $qleft) {
            echo "索引范围错误";
            exit;
        }
        return $this->recursionQuery(0, 0, count($this->data) - 1, $qleft, $qright);
    }
    /**
     * 递归查询区间
     * @param $left 当前节点区间左端值
     * @param $right 当前节点区间右端值
     * @param $qleft 需要查询的区间左端值
     * @param $qright 需要查询的区间右端值
     */
    private function recursionQuery($i, $left, $right, $qleft, $qright) {
        $mid = $left + ceil(($right - $left) / 2);//求区间中值向上取整
        //先处理满足区间条件的情况
        if ($qleft == $left && $qright == $right) { //查询左右端和当前节点左右端重合
            return $this->tree[$i];
        } elseif ($qright < $mid) { //查询左右端在中值左边，那么结果区间在左儿子树
            return $this->recursionQuery($this->leftSon($i), $left, $mid - 1, $qleft, $qright);
        } elseif ($qleft >= $mid) { //查询左右端在中值右边，那么结果区间在右儿子树
            return $this->recursionQuery($this->rightSon($i), $mid, $right, $qleft, $qright);
        } else { //中值在查询左右端中间 将区间分成两边，结果在左右儿子树上都有
            $leftSon = $this->recursionQuery($this->leftSon($i), $left, $mid - 1, $qleft, $mid - 1);
            $righttSon = $this->recursionQuery($this->rightSon($i), $mid, $right, $mid, $qright);
            return $this->merge->operate($leftSon, $righttSon);
        }
    }

输出如下：

9.完整 PHP 代码9.1 SegmentTree 类
<?php
class SegmentTree
{
    private $data = [];
    private $tree = [];
    private $merge = null; //表示的是一个 节点操作的对象
    /**
     * 构造函数 初始化线段树
     * SegmentTree constructor.
     * @param array $arr
     */
    public function __construct(array $arr, $merge) {
        $this->merge = $merge;
        for ($i = 0; $i < count($arr); $i++) {
            $this->data[$i] = $arr[$i];
        }
        //若是静态语言需要开 4n 空间来表示 $this->tree
        //递归创建线段树
        $this->buildSegmentTree(0, 0, count($this->data) - 1);
    }
    public function query($qleft, $qright) {
        if ($qleft < 0 || $qright >= count($this->data) || $qright < $qleft) {
            echo "索引范围错误";
            exit;
        }
        return $this->recursionQuery(0, 0, count($this->data) - 1, $qleft, $qright);
    }
    /**
     * 递归查询区间
     * @param $left 当前节点区间左端值
     * @param $right 当前节点区间右端值
     * @param $qleft 需要查询的区间左端值
     * @param $qright 需要查询的区间右端值
     */
    private function recursionQuery($i, $left, $right, $qleft, $qright) {
        $mid = $left + ceil(($right - $left) / 2);//求区间中值向上取整
        //先处理满足区间条件的情况
        if ($qleft == $left && $qright == $right) { //查询左右端和当前节点左右端重合
            return $this->tree[$i];
        } elseif ($qright < $mid) { //查询左右端在中值左边，那么结果区间在左儿子树
            return $this->recursionQuery($this->leftSon($i), $left, $mid - 1, $qleft, $qright);
        } elseif ($qleft >= $mid) { //查询左右端在中值右边，那么结果区间在右儿子树
            return $this->recursionQuery($this->rightSon($i), $mid, $right, $qleft, $qright);
        } else { //中值在查询左右端中间 将区间分成两边，结果在左右儿子树上都有
            $leftSon = $this->recursionQuery($this->leftSon($i), $left, $mid - 1, $qleft, $mid - 1);
            $righttSon = $this->recursionQuery($this->rightSon($i), $mid, $right, $mid, $qright);
            return $this->merge->operate($leftSon, $righttSon);
        }
    }
    private function buildSegmentTree(int $i, int $left, int $right) {
        if ($left == $right) {
            $this->tree[$i] = $this->data[$left]; //处理递归到叶子节点时 并赋值最原始的 $data 对应的索引值
        } else {
            $leftSon = $this->leftSon($i); //左儿子索引
            $rightSon = $this->rightSon($i); //右儿子索引
            $mid = $left + ceil(($right - $left) / 2);//求区间中值
            $this->buildSegmentTree($leftSon, $left, $mid - 1); //递归左儿子树
            $this->buildSegmentTree($rightSon, $mid, $right); //递归右儿子树
            $this->tree[$i] = $this->merge->operate($this->tree[$leftSon], $this->tree[$rightSon]); //这里是根据业务来定节点需要存储的元素
        }
    }
    public function getSize() {
        return count($this->data);
    }
    public function get(int $index) {
        if ($index < 0 || $index >= count($this->data)) {
            echo "索引错误";
            exit;
        }
        return $this->data[$index];
    }
    /**
     * 获取某个节点儿子节点索引，若索引是从 i=0 开始的，左儿子 left(i) = 2*i+1
     * @param $i
     * @return int
     */
    private function leftSon($i): int {
        return $i * 2 + 1;
    }
    /**
     * 获取某个节点右儿子节点索引，若索引是从 i=0 开始的，右儿子 left(i) = 2*i+2
     * @param $i
     * @return int
     */
    private function rightSon($i): int {
        return $i * 2 + 2;
    }
}
9.2 输出演示代码
<?php
require 'SegmentTree.php';
class Merge
{
    public function operate($left, $right) {
        return $left + $right;
    }
}
$merge = new Merge();
$arr = [0,1,2,3,4,5,6,7,8,9];
$merge = new Merge();
$segmentTree = new SegmentTree($arr,$merge);
echo $segmentTree->query(2,6);

代码仓库 ：https://gitee.com/love-for-po...

扫码关注爱因诗贤

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。

php介绍

PHP即“超文本预处理器”，是一种通用开源脚本语言。PHP是在服务器端执行的脚本语言，与C语言类似，是常用的网站编程语言。PHP独特的语法混合了C、Java、Perl以及 PHP 自创的语法。利于学习，使用广泛，主要适用于Web开发领域。
更多关于php的阅读
上一篇： php中传值与传引用的区别有哪些？
下一篇： Leetcode PHP题解--D131 746. Min Cost Climbing Stairs

Tags 标签

php算法程序员

扩展阅读

隐藏apache版本信息
2018-09-30 10:56:15 []
CentOS 6.5安装php5.6
2018-09-30 11:36:53 []
PHP版ZIP压缩解压类库
2018-12-22 13:11:00 []
CentOS7.2安装 PHP7.3.4 操作详细教程
2020-06-28 19:09:43 []
PHP 设置脚本超时时间、PHP脚本内存限制设置
2020-06-28 19:09:43 []
PHP 函数filesize获取文件大小错误，一直不变
2020-06-28 19:09:43 []
Linux php: command not found
2020-02-05 01:30:13 []
php 缓冲区 buffer 原理
2020-06-28 19:09:43 []
PHP中三种设置脚本最大执行时间的方法
2020-06-28 19:17:34 []

加个好友，技术交流

1628738909466805.jpg

码农天地

首页 HTML/CSS WEB服务器 PHP Linux 数据库 异常报错 插件工具 美文欣赏 站长直荐
友情链接：码农天地爱厂家深圳钻石回收麦思会议

Copyright © 2019-2024| 沪ICP备19030844号-2 | SiteMap