• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(8.2)线段树基础表示

极客笔记 Geekerstar 11个月前 (05-20) 286次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

线段树基础

线段树不一定是一棵满的二叉树,也不是完全二叉树(从上往下码放,如果一排不够从下一排左边排起),但是线段树是平衡二叉树(对于整棵树来说,最大的深度和最小的深度之间的差最多只有可能为1),堆也是平衡二叉树(优势是不会像二分搜素树一样退化成链表)。

所以线段树依然可以用数组来表示,可以将其看做满二叉树,最后一层不存在的节点看成是空节点。

下面思考一个问题:如果区间有n个元素,数组表示需要有多少节点呢?

最终需要4n的空间,当然这4n不是所有的空间都被利用了,首先这是一个估计值,并且做了一些富余。

其次我们二叉树不一定是满二叉树,很多位置都是空的,最坏的情况下可能有一半的空间都是浪费的。

比如如果我们要考虑的区间有五个元素的话,索引为0到4,我们将它看成满二叉树就是这样一个位置,很多位置是空。

不过在这里我们不过多的考虑这些浪费的情况,这是因为对现在计算机来说,存储空间本身不是问题。

我们做算法的关键依然还是空间换时间,希望在时间性能上有巨大的提升。当然浪费本身是可以避免的,不使用数组而使用链式的结构可以避免这种浪费。

代码演示

下面来创建一个线段树,创建一个SegmentTree

public class SegmentTree<E> {

    private E[] tree;
    private E[] data;

    public SegmentTree(E[] arr){

        data = (E[])new Object[arr.length];
        for(int i = 0 ; i < arr.length ; i ++)
            data[i] = arr[i];

        tree = (E[])new Object[4 * arr.length];
    }

    public int getSize(){
        return data.length;
    }

    public E get(int index){
        if(index < 0 || index >= data.length)
            throw new IllegalArgumentException("Index is illegal.");
        return data[index];
    }

    // 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return 2*index + 1;
    }

    // 返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){
        return 2*index + 2;
    }
}

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(8.2)线段树基础表示
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00