Java數(shù)據(jù)結(jié)構(gòu)之線段樹詳解
更新時(shí)間：2022年01月23日 10:44:00 作者：strongmore
線段樹是一種二叉搜索樹，與區(qū)間樹相似，它將一個(gè)區(qū)間劃分成一些單元區(qū)間，每個(gè)單元區(qū)間對應(yīng)線段樹中的一個(gè)葉結(jié)點(diǎn)。本文將介紹線段樹的Java實(shí)現(xiàn)代碼，需要的可以參考一下
介紹
線段樹(又名區(qū)間樹)也是一種二叉樹，每個(gè)節(jié)點(diǎn)的值等于左右孩子節(jié)點(diǎn)值的和，線段樹示例圖如下
以求和為例，根節(jié)點(diǎn)表示區(qū)間0-5的和，左孩子表示區(qū)間0-2的和，右孩子表示區(qū)間3-5的和，依次類推。
代碼實(shí)現(xiàn)
/**
* 使用數(shù)組實(shí)現(xiàn)線段樹
*/
public class SegmentTree<E> {
private Node[] data;
private int size;
private Merger<E> merger;
public SegmentTree(E[] source, Merger<E> merger) {
this.merger = merger;
this.size = source.length;
this.data = new Node[size * 4];
buildTree(0, source, 0, size - 1);
}
public E search(int queryLeft, int queryRight) {
if (queryLeft < 0 || queryLeft > size || queryRight < 0 || queryRight > size
|| queryLeft > queryRight) {
throw new IllegalArgumentException("index is illegal");
}
return search(0, queryLeft, queryRight);
}
/**
* 查詢區(qū)間queryLeft-queryRight的值
*/
private E search(int treeIndex, int queryLeft, int queryRight) {
Node treeNode = data[treeIndex];
int left = treeNode.left;
int right = treeNode.right;
if (left == queryLeft && right == queryRight) {
return elementData(treeIndex);
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int middle = left + ((right - left) >> 1);
if (queryLeft > middle) {
return search(rightTreeIndex, queryLeft, queryRight);
} else if (queryRight <= middle) {
return search(leftTreeIndex, queryLeft, queryRight);
}
E leftEle = search(leftTreeIndex, queryLeft, middle);
E rightEle = search(rightTreeIndex, middle + 1, queryRight);
return merger.merge(leftEle, rightEle);
}
public void update(int index, E e) {
update(0, index, e);
}
/**
* 更新索引為index的值為e
*/
private void update(int treeIndex, int index, E e) {
Node treeNode = data[treeIndex];
int left = treeNode.left;
int right = treeNode.right;
if (left == right) {
treeNode.data = e;
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int middle = left + ((right - left) >> 1);
if (index > middle) {
update(rightTreeIndex, index, e);
} else {
update(leftTreeIndex, index, e);
}
treeNode.data = merger.merge(elementData(leftTreeIndex), elementData(rightTreeIndex));
}
private void buildTree(int treeIndex, E[] source, int left, int right) {
if (left == right) {
data[treeIndex] = new Node<>(source[left], left, right);
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int middle = left + ((right - left) >> 1);
buildTree(leftTreeIndex, source, left, middle);
buildTree(rightTreeIndex, source, middle + 1, right);
E treeData = merger.merge(elementData(leftTreeIndex), elementData(rightTreeIndex));
data[treeIndex] = new Node<>(treeData, left, right);
}
@Override
public String toString() {
return Arrays.toString(data);
}
private E elementData(int index) {
return (E) data[index].data;
}
private int leftChild(int index) {
return index * 2 + 1;
}
private int rightChild(int index) {
return index * 2 + 2;
}
private static class Node<E> {
E data;
int left;
int right;
Node(E data, int left, int right) {
this.data = data;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return String.valueOf(data);
}
}
public interface Merger<E> {
E merge(E e1, E e2);
}
}
我們以LeetCode上的一個(gè)問題來分析線段樹的構(gòu)建，查詢和更新，LeetCode307問題如下：
給定一個(gè)整數(shù)數(shù)組，查詢索引區(qū)間[i,j]的元素的總和。
線段樹構(gòu)建
private void buildTree(int treeIndex, E[] source, int left, int right) {
if (left == right) {
data[treeIndex] = new Node<>(source[left], left, right);
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int middle = left + ((right - left) >> 1);
buildTree(leftTreeIndex, source, left, middle);
buildTree(rightTreeIndex, source, middle + 1, right);
E treeData = merger.merge(elementData(leftTreeIndex), elementData(rightTreeIndex));
data[treeIndex] = new Node<>(treeData, left, right);
}
測試代碼
public class Main {
public static void main(String[] args) {
Integer[] nums = {-2, 0, 3, -5, 2, -1};
SegmentTree<Integer> segmentTree = new SegmentTree<>(nums, Integer::sum);
System.out.println(segmentTree);
}
}
最后構(gòu)造出的線段樹如下，前面為元素值，括號中為包含的區(qū)間。
遞歸構(gòu)造過程為
- 當(dāng)左指針和右指針相等時(shí)，表示為葉子節(jié)點(diǎn)
- 將左孩子和右孩子值相加，構(gòu)造當(dāng)前節(jié)點(diǎn)，依次類推
區(qū)間查詢
/**
* 查詢區(qū)間queryLeft-queryRight的值
*/
private E search(int treeIndex, int queryLeft, int queryRight) {
Node treeNode = data[treeIndex];
int left = treeNode.left;
int right = treeNode.right;
if (left == queryLeft && right == queryRight) {
return elementData(treeIndex);
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int middle = left + ((right - left) >> 1);
if (queryLeft > middle) {
return search(rightTreeIndex, queryLeft, queryRight);
} else if (queryRight <= middle) {
return search(leftTreeIndex, queryLeft, queryRight);
}
E leftEle = search(leftTreeIndex, queryLeft, middle);
E rightEle = search(rightTreeIndex, middle + 1, queryRight);
return merger.merge(leftEle, rightEle);
}
查詢區(qū)間2-5的和
public class Main {
public static void main(String[] args) {
Integer[] nums = {-2, 0, 3, -5, 2, -1};
SegmentTree<Integer> segmentTree = new SegmentTree<>(nums, Integer::sum);
System.out.println(segmentTree);
System.out.println(segmentTree.search(2, 5)); // -1
}
}
查詢過程為
- 待查詢的區(qū)間和當(dāng)前節(jié)點(diǎn)的區(qū)間相等，返回當(dāng)前節(jié)點(diǎn)值
- 待查詢左區(qū)間大于中間區(qū)間值，查詢右孩子
- 待查詢右區(qū)間小于中間區(qū)間值，查詢左孩子
- 待查詢左區(qū)間在左孩子，右區(qū)間在右孩子，兩邊查詢結(jié)果相加
更新
/**
* 更新索引為index的值為e
*/
private void update(int treeIndex, int index, E e) {
Node treeNode = data[treeIndex];
int left = treeNode.left;
int right = treeNode.right;
if (left == right) {
treeNode.data = e;
return;
}
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
int middle = left + ((right - left) >> 1);
if (index > middle) {
update(rightTreeIndex, index, e);
} else {
update(leftTreeIndex, index, e);
}
treeNode.data = merger.merge(elementData(leftTreeIndex), elementData(rightTreeIndex));
}
更新只影響元素值，不影響元素區(qū)間。
更新其實(shí)和構(gòu)建的邏輯類似，找到待更新的實(shí)際索引，依次更新父節(jié)點(diǎn)的值。
總結(jié)
線段樹可以很好地處理區(qū)間問題，如區(qū)間求和，求最大最小值等。
以上就是Java 數(shù)據(jù)結(jié)構(gòu)之線段樹詳解的詳細(xì)內(nèi)容，更多關(guān)于Java 線段樹的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
下面小編就為大家?guī)硪黄猨ava異常處理的簡單練習(xí)。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2016-06-06
Java修改eclipse中web項(xiàng)目的server部署路徑問題
這篇文章主要介紹了Java修改eclipse中web項(xiàng)目的server部署路徑,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-11-11
Java二分查找算法實(shí)現(xiàn)代碼實(shí)例
這篇文章主要介紹了Java二分查找算法實(shí)現(xiàn)代碼實(shí)例,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2019-11-11
獲取系統(tǒng)參數(shù)System.getProperties()與配置文件參數(shù)@Value(“${key}“)
這篇文章主要介紹了獲取系統(tǒng)參數(shù)System.getProperties()與配置文件參數(shù)@Value("${key}"),本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-05-05
泛型在java中有很重要的地位，在面向?qū)ο缶幊碳案鞣N設(shè)計(jì)模式中有非常廣泛的應(yīng)用。java泛型知識(shí)點(diǎn)也是Java開發(fā)崗位必問的一個(gè)話題，今天小編就給大家普及下Java泛型常見面試題，感興趣的朋友一起看看吧2021-06-06
這篇文章主要介紹了Spring中使用ehcache緩存的方法及原理詳解,ehcache具有很強(qiáng)的靈活性,提供了LRU、LFU和FIFO緩存淘汰算法,Ehcache 1.2引入了最近最少使用、最久未使用和先進(jìn)先 出緩存淘汰算法, 構(gòu)成了完整的緩存淘汰算法,,需要的朋友可以參考下2024-01-01
詳解SpringBoot中的index首頁的訪問、自定義Favicon圖標(biāo)
這篇文章主要介紹了SpringBoot中的index首頁的訪問、自定義Favicon圖標(biāo),本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2023-08-08
Java使用Redisson分布式鎖實(shí)現(xiàn)原理
Redisson分布式鎖 之前的基于注解的鎖有一種鎖是基本redis的分布式鎖，這篇文章主要介紹了Java使用Redisson分布式鎖實(shí)現(xiàn)原理，非常具有實(shí)用價(jià)值，需要的朋友可以參考下2018-10-10
這篇文章主要為大家介紹了ReentrantLock獲取鎖釋放鎖的流程示例分析詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-11-11
這篇文章主要為大家詳細(xì)介紹了spring消息轉(zhuǎn)換器的使用，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-07-07