当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

线段树-入门

发表于: 2013-01-05   作者:bylijinnan   来源:转载   浏览:
摘要: /** * 线段树入门 * 问题:已知线段[2,5] [4,6] [0,7];求点2,4,7分别出现了多少次 * 以下代码建立的线段树用链表来保存,且树的叶子结点类似[i,i] * * 参考链接:http://hi.baidu.com/semluhiigubbqvq/item/be736a33a8864789f4e4ad18 * @author lijinna


/**
 * 线段树入门
 * 问题:已知线段[2,5] [4,6] [0,7];求点2,4,7分别出现了多少次
 * 以下代码建立的线段树用链表来保存,且树的叶子结点类似[i,i]
 * 
 * 参考链接:http://hi.baidu.com/semluhiigubbqvq/item/be736a33a8864789f4e4ad18
 * @author lijinnan
 */
public class SegmentTreeLearn {

    public static void main(String[] args) {
        SegmentTree tree = new SegmentTree(0, 7);
        int[][] segments = {
                {2, 5}, 
                {4, 6}, 
                {0, 7}
        };
        int[] targets = {2, 4, 7};
        for (int i = 0, len = segments.length; i < len; i++) {
            int[] segment = segments[i];
            tree.insert(segment[0], segment[1]);
        }
        for(int target : targets) {
            System.out.println(target + ":" + tree.caculateExistingTimes(target));
        }
    }
    


}

class SegmentTree {

    //递归定义的,因此很多操作都是递归实现
    private class Segment {
        int left;
        int right;
        int count;
        Segment leftChild;
        Segment rightChild;
    }
    
    private Segment root;
    
    public SegmentTree (int left, int right) {
        root = new Segment();
        build(root, left, right);
    }
    
    public void insert(int left, int right) {
        insert(root, left, right);
    }
    
    public int caculateExistingTimes(int target) {
        return caculateExistingTimes(root, target);
    }
    
    //从根节点开始查找叶子结点[target, target],对经过的节点的count求和
    private int caculateExistingTimes(Segment root, int target) {
        int result = 0;
        while( root.left != root.right) {
            int rootMid = root.left + (root.right - root.left) / 2;
            result += root.count;
            if (target <= rootMid) {
                root = root.leftChild;
            } else if (target > rootMid) {
                root = root.rightChild;
            }
        }
        return result;
    }
   
    private void build(Segment root, int left, int right) {
        root.left = left;
        root.right = right;
        if (left != right) {
            int mid = left + (right - left) / 2;
            root.leftChild = new Segment();
            root.rightChild = new Segment();
            build(root.leftChild, left, mid);
            build(root.rightChild, mid + 1, right);
        }
    }
    
    private void insert(Segment root, int left, int right) {
        
        int rootLeft = root.left;
        int rootRight = root.right;
        int rootMid = rootLeft + (rootRight - rootLeft) / 2;
        
        //匹配,出现次数加1
        if (left == rootLeft && right == rootRight) {
            root.count++;
            return;
        }
        
        if (right <= rootMid) {
            insert(root.leftChild, left, right);
        } else if (left > rootMid){
            insert(root.rightChild, left, right);
        } else {
            insert(root.leftChild, left, rootMid);
            insert(root.rightChild, rootMid + 1, right);
        }
    }
    
}

线段树-入门

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
线段树的入门级 总结 转载于:http://blog.csdn.net/x314542916/article/details/7837276 真正的入
线段树的入门级 总结 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每
从简单说起,线段树其实可以理解成一种特殊的二叉树。但是这种二叉树较为平衡,和静态二叉树一样,
线段树(interval tree) 是把区间逐次二分得到的一树状结构,它反映了包括归并排序在内的很多分治算
 树结构的基本思想是分割,普通 二叉搜索树是按照数据来划分(想了解二叉搜索树的请移步: Here),
从简单说起,线段树其实可以理解成一种特殊的二叉树。但是这种二叉树较为平衡,和静态二叉树一样,
这里从一个问题引入: 在自然数,且所有的数不大于30000的范围内讨论一个问题:现在已知n条线段,把
引用Wiki对线段树的介绍: 线段树(Segment Tree)是一种二叉搜索树,它将一个区间划分成一些单元区
先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是一种基于区间的树,每个节点表示一个“线段
定义 线段树是一种的二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号