数据结构-非线性结构-树形结构：有序树 -＞二叉树 -＞平衡二叉树 -＞线段树 (Segment Tree) / 区间树【不是完全二叉树；用于处理区间类数据】【基于静态数组/链表】【竞赛】

我就是我 2023-10-04 12:27 9阅读 0赞

**平衡二叉树**（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；

![在这里插入图片描述][2021050422292281.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 4]

## 线段树的代码实现 ##

SegmentTree.java

/**
     * 线段树
     *
     * @author whx
     * @version 2018/8/25
     */
    public class SegmentTree<E> {
        
    
    	/**普通数据*/
    	private E[] data;
    	/**树结构数据*/
    	private E[] tree;
    	/**融合器*/
    	private Merger<E> merger;
    
    	public SegmentTree(E[] arr,Merger<E> merger){
        
    		this.merger = merger;
    		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];
    		buildSegmentTree(0, 0, data.length - 1);
    	}
    
    	/**
    	 * 在treeIndex的位置创建表示区间[l...r]的线段树
    	 *
    	 * @param treeIndex
    	 * @param left
    	 * @param right
    	 * @return void
    	 * @author whx
    	 * @version 2018/8/25
    	 */
    	private void buildSegmentTree(int treeIndex, int left, int right) {
        
    		if(left == right){
        
    			tree[treeIndex] = data[left];
    			return;
    		}
    
    		int leftTreeIndex = leftChild(treeIndex);
    		int rightTreeIndex = rightChild(treeIndex);
    
    		int mid = left + (right - left) / 2;
    		buildSegmentTree(leftTreeIndex,left,mid);
    		buildSegmentTree(rightTreeIndex,mid + 1,right);
    		//融合两个元素
    		tree[treeIndex] = merger.merge(tree[leftTreeIndex],tree[rightTreeIndex]);
    	}
    
    	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];
    	}
    
    	/**
    	 * 查找用数组实现的完全二叉树中该索引下节点的左孩子节点的索引
    	 *
    	 * @param index
    	 * @return int
    	 * @author whx
    	 * @version 2018/8/19
    	 */
    	public int leftChild(int index){
        
    		return (index * 2) + 1;
    	}
    
    	/**
    	 * 查找用数组实现的完全二叉树中该索引下节点的右孩子节点的索引
    	 *
    	 * @param index
    	 * @return int
    	 * @author whx
    	 * @version 2018/8/19
    	 */
    	public int rightChild(int index){
        
    		return (index * 2) + 2;
    	}
    
    	/**
    	 * 查询区间[start...end]的值
    	 *
    	 * @param start
    	 * @param end
    	 * @return E
    	 * @author whx
    	 * @version 2018/8/25
    	 */
    	public E query(int start, int end){
        
    		if(start < 0 || start > data.length ||
    				end < 0 || end > data.length ||
    						start > end){
        
    			throw new IllegalArgumentException("Index is illegal.");
    		}
    		return query(0, 0, data.length-1, start, end);
    	}
    
    	/**
    	 * 查询在以treeIndex为根的线段树区间为[l...r]的范围中，区间[start...end]的值
    	 *
    	 * @param treeIndex
    	 * @param l
    	 * @param r
    	 * @param start
    	 * @param end
    	 * @return E
    	 * @author whx
    	 * @version 2018/8/25
    	 */
    	private E query(int treeIndex, int l, int r, int start, int end){
        
    		if(l == start && r == end){
        
    			return tree[treeIndex];
    		}
    		int middle = l + (r - l) / 2;
    		int leftTreeIndex = leftChild(treeIndex);
    		int rightTreeIndex = rightChild(treeIndex);
    
    		if(start >= middle + 1){
        
    			return query(rightTreeIndex,middle+1,r,start,end);
    		}else if(end <= middle){
        
    			return query(leftTreeIndex,l,middle,start,end);
    		}
    
    		E leftResult = query(leftTreeIndex, l, middle, start, middle);
    		E rightResult = query(rightTreeIndex, middle + 1, r, middle + 1, end);
    		return merger.merge(leftResult,rightResult);
    	}
    
    	/**
    	 * 更新index位置的元素为e
    	 *
    	 * @param index
    	 * @param e
    	 * @return void
    	 * @author whx
    	 * @version 2018/8/26
    	 */
    	public void set(int index, E e){
        
    		if(index < 0 || index >= data.length){
        
    			throw new IllegalArgumentException("Index is illegal.");
    		}
    		set(0,0,data.length - 1,index,e);
    	}
    
    	/**
    	 * 更新在以treeIndex为根的线段树区间为[l...r]的范围中位置为index的值
    	 *
    	 * @param treeIndex
    	 * @param l
    	 * @param r
    	 * @param index
    	 * @param e
    	 * @return void
    	 * @author whx
    	 * @version 2018/8/26
    	 */
    	private void set(int treeIndex, int l, int r, int index, E e){
        
    		if(l == r){
        
    			tree[treeIndex] = e;
    			return;
    		}
    		int middle = l + (r - l) / 2;
    		int leftTreeIndex = leftChild(treeIndex);
    		int rightTreeIndex = rightChild(treeIndex);
    		if(index >= middle + 1){
        
    			set(rightTreeIndex,middle+1,r,index,e);
    		}else if(index <= middle){
        
    			set(leftTreeIndex,l,middle,index,e);
    		}
    		tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
    	}
    
    
    	@Override
    	public String toString() {
        
    		StringBuilder result = new StringBuilder();
    		result.append("SegmentTree: [");
    		for (int i = 0; i < tree.length; i++) {
        
    			if (tree[i] != null){
        
    				result.append(tree[i]);
    			}else {
        
    				result.append("null");
    			}
    			if (i != tree.length - 1) {
        
    				result.append(",");
    			}else {
        
    				result.append("]");
    			}
    		}
    		return result.toString();
    	}
    }

Merger.java

/**
     * 融合器
     *
     * @author whx
     * @version 2018/8/25
     */
    public interface Merger<E> {
        
    	/**
    	 * 融合两个元素
    	 *
    	 * @param a
    	 * @param b
    	 * @return E
    	 * @author whx
    	 * @version 2018/8/25
    	 */
    	E merge(E a, E b);
    }

Main.java

/**
     * @author whx
     * @version 2018/8/25
     */
    public class Main {
        
        public static void main(String[] args) {
        
    
            SegmentTree<Integer> segmentTree = new SegmentTree<Integer>(new Integer[]{
        -2, 0, 3, -5, 2, -1}, (a, b) -> a + b);
            System.out.println(segmentTree.toString());
            System.out.println(segmentTree.query(2, 4));
            System.out.println(segmentTree.query(0, 4));
            System.out.println(segmentTree.query(1, 4));
            System.out.println(segmentTree.query(3, 4));
            segmentTree.set(0, 20);
            System.out.println(segmentTree.toString());
        }
    }

--------------------

参考资料：  
[线段树详解 （原理，实现与应用）][Link 1]

[2021050422292281.png_pic_center]: https://img-blog.csdnimg.cn/2021050422292281.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210512081544133.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210504221605163.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210512082432602.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210512082711995.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20210504225457389.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[Link 1]: https://blog.csdn.net/zearot/article/details/48299459