通知
  • 关于网站更多信息请加QQ群(1061691290)
  • jpress升级到4.x,显示有些问题,修复中
  • 网站还会持续更新
文章来源于网络,无法注明出处的还请谅解,如果出处注明错误(如仍是载转),请联系我修改

数据结构-线段树详解(含java源代码)

1116人浏览 / 0人评论 / | 这是对我有帮助的文章  | 分类: 算法  | 标签: 设计模式与算法  | 

作者:不务正业的土豆
链接:https://blog.csdn.net/yyl424525/article/details/77859911
来源:CSDN

1 线段树的定义

首先,线段树是一棵二叉树。它的特点是:每个结点表示的是一个线段,或者说是一个区间。事实上,一棵线段树的根结点表示的是“整体”区间,而它的左右子树也是一棵线段树,分别表示区间的左半边和右半边。树中的每个结点表示一个区间[a,b]。每一个叶子结点表示一个单位区间。对于每一个非叶结点所表示的结点[a,b],其左孩子表示的区间为[a,(a+b)/2],右孩子表示的区间为[(a+b)/2,b]。 用T(a, b)表示一棵线段树,参数a,b表示区间[a,b],其中b-a称为区间的长度,记为L。
线段树主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,因此有时需要离散化让空间压缩。

2 线段树的实现

以下面这棵线段树为例:
segment_tree.png

2.1 节点定义

//    线段树的树节点
    class Node {
        int left, right;//左右区间的值
        boolean cover;//表示是否被覆盖
        int count;//表示此节点表示的线段区间出现的次数(被覆盖的次数),默认为0
        Node leftChild;
        Node rightChild;
    Node(int left, int right) {
        this.left = left;
        this.right = right;
        cover=false;
        count = 0;
    }
}

2.2 建立一棵线段树

/*

  • 外部接口
  • 建立一棵线段树
  • / public void build(int left,int right){ root = new Node(left, right); build(root); } / * 内部接口 * 建立一棵线段树 * / private void build(Node root) { int left = root.left; int right = root.right; //root节点为叶子节点 if (right - left == 1) { return; } else if (right - left > 1) { int mid = (left + right) >> 1;////将左右区间平分 Node leftNode = new Node(left, mid); Node rightNode = new Node(mid , right); root.leftChild = leftNode; root.rightChild = rightNode; // 递归的创建左右子树 build(leftNode); build(rightNode); } }

2.3 在一棵线段树里插入一条线段[c,d]

/

 
  • 插入一条线段[c,d]的外部接口

  • c为左端点

  • d为右端点

  • root 为此线段树的根节点

  • / public void insert(int c, int d) { insert(c,d,root); } / * 插入一条线段[c,d]的内部接口 * c为左端点 * d为右端点 * root 为此线段树的根节点 * */ private void insert(int c, int d, Node node) { if(node==null||c<node.left||d>node.right){ System.out.println("输入的参数不合法!"+"c:"+c+" "+"d:"+d); System.out.println("root:"+node.left+" "+node.right);

    return ;
    

    } if(node.left==c&&node.right==d) { node.count++; node.cover=true; return; } int mid=(node.left+node.right)>>1; if(d<=mid){ insert(c,d,node.leftChild); }

    else if(c>=mid) insert(c,d,node.rightChild); else { insert(c,mid,node.leftChild); insert(mid,d,node.rightChild); } }

2.4 在一棵线段树里删除一条线段[c,d]

* 删除一条线段[c,d]的外部接口
* c:删除线段的左端点
*d:删除线段的右端点
* root:删除线段树的根结点
* /
public  void delete(int c, int d){
delete(c,d,root);
}
/
* 删除一条线段[c,d]
* c:删除线段的左端点
*d:删除线段的右端点
* root:删除线段树的根结点
* */

private void delete(int c, int d, Node node) {
    if (node == null || c &lt; node.left || d &gt; node.right)
    {
        System.out.println("输入的参数不合法!");
        return;
    }
    if(c==node.left&amp;&amp;d==node.right)
    {
        node.count--;
           if(node.count==0)
            node.cover=false;

        return;
    }
    int mid=(node.left+node.right)&gt;&gt;1;
    if(d&lt;=mid)
        delete(c,d,node.leftChild);
    else if(c&gt;=mid)
        delete(c,d,node.rightChild);
    else {
        delete(c,mid,node.leftChild);
        delete(mid,d,node.rightChild);//注意不是mid+1,比如区间【1,10】的左右两部分分别是【1,5】,【5,10】
    }
}

2.5 前序遍历线段树

/*
* 前序遍历
* 外部接口
* */
public void preOrder(){
preOrder(root);
}

/*
* 前序遍历
* 内部接口
* */
private void preOrder(Node root){

// 叶子节点 if(root.right-root.left==1) { System.out.println("["+root.left+","+root.right+"]:"+root.count); return ; } else if(root.right-root.left>1){ System.out.println("["+root.left+","+root.right+"]:"+root.count); preOrder(root.leftChild); preOrder(root.rightChild); } }

2.6 计算多条线段所覆盖的区域总长度

问题:桌子上零散地放着若干个盒子,桌子的后方是一堵墙。现在从桌子的前方射来一束平行光, 把盒子的影子投射到了墙上。问影子的总宽度是多少?
分析:可以把题目抽象地描述如下:x轴上有若干条线段,求线段覆盖的总长度。这就是给每个节点添加一个布尔型cover的原因。cover=1表示该结点所对应的区间被完全覆盖,cover=0表示该结点所对应的区间未被完全覆盖。

/*

  • 外部接口
  • 统计线段树中cover为true的线段的总长度
  • */ public int Count(){ return Count(root); }
/*
* 内部接口
* 统计线段树中cover为true的线段的总长度
* */
private int Count(Node node){
    if(node.cover==true)//不继续往下查找,否则会重复
        return node.right-node.left;
    else {
        if(node.right-node.left==1)
            return 0;
        else
            return Count(node.leftChild)+Count(node.rightChild);
    }
}

2.7 测试

public class SegmentTreeTest {
public static void main(String[] args) {
SegmentTree segmentTree=new SegmentTree();
segmentTree.build(1,10);
segmentTree.insert(3,5);
segmentTree.insert(3,5);
segmentTree.insert(2,5);
segmentTree.insert(3,9);
segmentTree.insert(1,10);
//[2,5]被分为[2,3],[3,5]
//[3,9]被分为[3,5],[5,9]
//[5,9]被分为[5,7],[7,8]+[8,9]
System.out.println("前序遍历线段树:");
segmentTree.preOrder();

    System.out.println("删除线段:");
    segmentTree.delete(1,10);
    segmentTree.delete(3,5);

    System.out.println("前序遍历线段树:");
    segmentTree.preOrder();

    System.out.println("被覆盖的长度:"+segmentTree.Count());

// 输出为[2,3]+[3,5]+[5,7]+[7,8]+[8,9]=7

}

}

输出:

前序遍历线段树:
[1,10]:1
[1,5]:0
[1,3]:0
[1,2]:0
[2,3]:1
[3,5]:4
[3,4]:0
[4,5]:0
[5,10]:0
[5,7]:1
[5,6]:0
[6,7]:0
[7,10]:0
[7,8]:1
[8,10]:0
[8,9]:1
[9,10]:0
删除线段:
前序遍历线段树:
[1,10]:0
[1,5]:0
[1,3]:0
[1,2]:0
[2,3]:1
[3,5]:3
[3,4]:0
[4,5]:0
[5,10]:0
[5,7]:1
[5,6]:0
[6,7]:0
[7,10]:0
[7,8]:1
[8,10]:0
[8,9]:1
[9,10]:0
被覆盖的长度:7

2.8 完整源代码

public class SegmentTree {
Node root;
/*

  • 外部接口
  • 建立一棵线段树
  • / public void build(int left,int right){ root = new Node(left, right); build(root); } / * 内部接口 * 建立一棵线段树 * */ private void build(Node root) { int left = root.left; int right = root.right; //root节点为叶子节点 if (right - left == 1) { return; } else if (right - left > 1) { int mid = (left + right) >> 1;////将左右区间平分 Node leftNode = new Node(left, mid); Node rightNode = new Node(mid , right); root.leftChild = leftNode; root.rightChild = rightNode; // 递归的创建左右子树 build(leftNode); build(rightNode); } }
/*
 * 插入一条线段[c,d]的外部接口
 * c为左端点
 * d为右端点
 * root 为此线段树的根节点
 * */
public void insert(int c, int d) {
insert(c,d,root);
}
/*
* 插入一条线段[c,d]的内部接口
* c为左端点
* d为右端点
* root 为此线段树的根节点
* */
private void insert(int c, int d, Node node) {
   if(node==null||c&lt;node.left||d&gt;node.right){
       System.out.println("输入的参数不合法!"+"c:"+c+" "+"d:"+d);
       System.out.println("root:"+node.left+" "+node.right);

       return ;
   }
   if(node.left==c&amp;&amp;node.right==d)
   {
       node.count++;
       node.cover=true;
       return;
   }
   int mid=(node.left+node.right)&gt;&gt;1;
   if(d&lt;=mid){
       insert(c,d,node.leftChild);
   }

   else if(c&gt;=mid)
       insert(c,d,node.rightChild);
   else {
       insert(c,mid,node.leftChild);
       insert(mid,d,node.rightChild);
   }
}

  /*
* 删除一条线段[c,d]的外部接口
* c:删除线段的左端点
*d:删除线段的右端点
* root:删除线段树的根结点
* */
  public  void delete(int c, int d){
      delete(c,d,root);
  }
/*
* 删除一条线段[c,d]
* c:删除线段的左端点
*d:删除线段的右端点
* root:删除线段树的根结点
* */
private void delete(int c, int d, Node node) {
    if (node == null || c &lt; node.left || d &gt; node.right)
    {
        System.out.println("输入的参数不合法!");
        return;
    }
    if(c==node.left&amp;&amp;d==node.right)
    {
        node.count--;
        if(node.count==0)
            node.cover=false;
        return;
    }
    int mid=(node.left+node.right)&gt;&gt;1;
    if(d&lt;=mid)
        delete(c,d,node.leftChild);
    else if(c&gt;=mid)
        delete(c,d,node.rightChild);
    else {
        delete(c,mid,node.leftChild);
        delete(mid,d,node.rightChild);//注意不是mid+1,比如区间【1,10】的左右两部分分别是【1,5】,【5,10】
    }
}
 /*
* 前序遍历
* 外部接口
* */
 public void preOrder(){
     preOrder(root);
 }

/*
* 前序遍历
* 内部接口
* */
private void preOrder(Node root){

// 叶子节点 if(root.right-root.left==1) { System.out.println("["+root.left+","+root.right+"]:"+root.count); return ; } else if(root.right-root.left>1){ System.out.println("["+root.left+","+root.right+"]:"+root.count); preOrder(root.leftChild); preOrder(root.rightChild); } }

/*
  • 外部接口
  • 统计线段树中cover为true的线段的总长度
  • */ public int Count(){ return Count(root); }
/*
* 内部接口
* 统计线段树中cover为true的线段的总长度
* */
private int Count(Node node){
    if(node.cover==true)//不继续往下查找,否则会重复
        return node.right-node.left;
    else {
        if(node.right-node.left==1)
            return 0;
        else
            return Count(node.leftChild)+Count(node.rightChild);
    }
}


//    线段树的树节点
class Node {
    int left, right;//左右区间的值
    boolean cover;//表示是否被覆盖
    int count;//表示此节点表示的线段区间出现的次数(被覆盖的次数),默认为0
    Node leftChild;
    Node rightChild;

    Node(int left, int right) {
        this.left = left;
        this.right = right;
        count = 0;
        cover=false;
    }
}

}

有错误的地方欢迎指出


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!