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

线段树基础

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

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

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

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

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

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

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

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

代码演示

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

public class SegmentTree {

    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;
    }
}

源码下载

[dm href=’https://www.jikewenku.com/product/1487.html’]下载地址[/dm]

导航目录

[dm href=’https://www.jikewenku.com/geeknote/2241.html’]查看导航[/dm]

本站所有文章均由网友分享,仅用于参考学习用,请勿直接转载,如有侵权,请联系网站客服删除相关文章。若由于商用引起版权纠纷,一切责任均由使用者承担
极客文库 » 数据结构笔记总结(8.2)线段树基础表示

Leave a Reply

欢迎加入「极客文库」,成为原创作者从这里开始!

立即加入 了解更多