线段树和Trie
1.为什么使用线段树
最经典的线段树问题：RMQ（区间最值问题）和区间求和
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dv3DZ3j8-1639912767031)(D:\HJ2012\java数据结构\无标题.png)]
2.构建线段树
1>线段树不是完全二叉树，是平衡二叉树。可以使用数组表示树的结点
2>给定一个数组arr，获取生成线段树的高度
2的（h-1）次方 ≥ arr. length的最小值
3>生成的线段树的结点个数最多为： 2h次方 − 1
4>生成线段树
/**
* 构建线段树
*
* @param start 区间的开始
* @param end 区间的结尾
* @param index 线段树对应[start:end]区间的索引
*/
private void buildingSegmentTree(int start, int end, int index) {
// 1、递归到底的情况
if (start == end) {
this.data[index] = this.source[start];
return;
}
// 2、递归操作
int mid = start + (end - start) / 2;
int leftIndex = 2 * index + 1;
int rightIndex = leftIndex + 1;
buildingSegmentTree(start, mid, leftIndex);
buildingSegmentTree(mid + 1, end, rightIndex);
this.data[index] = this.merger.merge(this.data[leftIndex], this.data[rightIndex]);
}
注意：int mid = (start + end)/2;可能会超范围，所以使用 int mid = start +(end -start)/2
此构建线段树的方法只支持求和操作，为了具有通用性，可以设计一个融合接口Merge
public interface Merger<T> {
T merge(T a, T b);
}
3、查询操作
/**
* 进行查询操作
*
* @param start 线段树结点所表示区间的start
* @param end 线段树结点所表示区间的end
* @param index 线段树上结点的索引
* @param from 查询区间的开始
* @param to 查询区间的结尾
* @return
*/
private T query(int start, int end, int index, int from, int to) {
// 1、递归到底的情况
if (start == from && end == to) {
return this.data[index];
}
// 2、递归操作（【1】 左边完全不包含 【2】右边完全不包含 【3】左右都包含）
int leftIndex = 2 * index + 1;
int rightIndex = leftIndex + 1;
int mid = start + (end - start) / 2;
if (from > mid) {
return query(mid + 1, end, rightIndex, from, to);
} else if (to <= mid) {
return query(start, mid, leftIndex, from, to);
} else {
// 左边
T leftValue = query(start, mid, leftIndex, from, mid);
// 右边
T rightValue = query(mid + 1, end, rightIndex, mid + 1, to);
return this.merger.merge(leftValue, rightValue);
}
}
4.更新操作
/**
* 更新源数组索引为index位置的值为val
*
* @param site 索引
* @param val 值
*/
public void update(int site, T val) {
if (site < 0 || site >= this.source.length) {
throw new IllegalArgumentException("index is invalid!");
}
// 重新渲染线段树
update(0, this.source.length - 1, 0, site, val);
}
private void update(int start, int end, int index, int orindex, T val) {
// 1、递归到底的情况
if (start == end && start == orindex) {
this.source[orindex] = this.data[index] = val;
return;
}
// 2、递归操作
int mid = start + (end - start) / 2;
int leftIndex = 2 * index + 1;
int rightIndex = leftIndex + 1;
if (mid < orindex) {
update(mid + 1, end, rightIndex, orindex, val);
} else {
update(start, mid, leftIndex, orindex, val);
}
this.data[index] = this.merger.merge(this.data[leftIndex], this.data[rightIndex]);
}
5、Trie
在计算机科学中，trie，又称前缀树或字典树。与二叉查找树不同，值不是直接保存在节点中，而是由节点在树中的位置
决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。
Trie的典型应用是用于统计，它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较
6、Trie结点结构
每个结点都有若干指向下个结点的指针
// 结点
private class Node {
boolean isWord;// 是否是单词
Map<Character, Node> next; //该结点下所有的字符对应的结点
Node() {
isWord = false;
next = new HashMap<>();
}
}
private Node root;// 根
private int size; // 单词个数
public Trie() {
this.size = 0;
this.root = new Node();
}
public int getSize() {
return this.size;
}
7、Trie添加操作
// 添加操作
public void addStr(String str) {
if (str == null || str.length() == 0) {
return;
}
Node cur = root;
for (int i = 0; i < str.length(); i++) {
char c = str.charAt(i);
Map<Character, Node> children = cur.next;
if (!children.keySet().contains(c)) {
children.put(c, new Node());
}
cur = children.get(c);
}
if (!cur.isWord) {
cur.isWord = true;
this.size += 1;
}
}
8.判断是否存在指定的单词
// 判断是否存在指定的单词
public boolean matchWord(String word) {
if (word == null || word.length() == 0) {
return false;
}
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
Map<Character, Node> children = cur.next;
if (!children.keySet().contains(c)) {
return false;
}
cur = children.get(c);
}
return cur.isWord;
}
9.判断是否存在以pre开始的单词
// 判断是否存在以pre开始的单词
public boolean matchStartPre(String pre) {
if (pre == null || pre.length() == 0) {
return false;
}
Node cur = root;
for (int i = 0; i < pre.length(); i++) {
char c = pre.charAt(i);
Map<Character, Node> children = cur.next;
if (!children.keySet().contains(c)) {
return false;
}
cur = children.get(c);
}
return true;
}
10.模糊匹配
public boolean search(String express) {
if (express == null || express.length() == 0) {
return false;
}
return match(root, express, 0);
}
/**
* @param node 当前结点
* @param express 表达式
* @param index 表达式中匹配字符的索引
* @return
*/
private boolean match(Node node, String express, int index) {
if (index == express.length()) {
return true;
}
char c = express.charAt(index);
if (c != '.') {
Map<Character, Node> children = node.next;
if (!children.keySet().contains(c)) {
return false;
}
return match(children.get(c), express, index + 1);
} else {
Map<Character, Node> children = node.next;
Set<Character> set = children.keySet();
for (Character chr : set) {
if (match(children.get(chr), express, index + 1)) {
return true;
}
}
return false;
}
}
11.删除操作
1、如果单词是另外一个单词的前缀，只需将该单词最后一个结点的isWord修改成false
2、如果单词的所有字符都没有分支，删除整个单词
3、如果单词除了最后一个字符，其他的字符存在多个分支
4、对第2种情况的补充：如果单词的所有字符都没有分支，但是存在前缀作为单词的情况，例如：pan,panda,在删除 panda时，使用第三种情况进行处理（node.next.size() == 1 && node.isword）
public List<String> matchStartExpressWords(String express) {
List<String> list = new ArrayList<>();
if (express != null && express.length() != 0) {
match(root, express, 0, list);
}
return list;
}
/**
* @param node 当前结点
* @param express 表达式
* @param index 表达式中匹配字符的索引
* @param list 存储结果
*/
private void match(Node node, String express, int index, List<String> list) {
// 递归终止条件
if (express.length() == index) {
findWords(node, list);
return;
}
// 递归操作
char c = express.charAt(index);
if (c != '.') {
Map<Character, Node> children = node.next;
if (!children.containsKey(c)) {
return;
}
match(children.get(c), express, index + 1, list);
} else {
Map<Character, Node> children = node.next;
for (Character chr : children.keySet()) {
match(children.get(chr), express, index + 1, list);
}
}
}
// 递归操作，获取单词
public void findWords(Node node, List<String> list) {
if (node.isWord) {
list.add(node.val);
}
// 递归终止条件
if (node.next.size() == 0) {
return;
}
Map<Character, Node> children = node.next;
Set<Character> keys = children.keySet();
for (Character key : keys) {
findWords(children.get(key), list);
}
}
// 删除单词
public void deleteWord(String word) {
if (word == null || word.length() == 0) {
throw new IllegalArgumentException("word is invalid");
}
Node cur = this.root;
Node multiNode = null; // 记录分叉结点
int multiIndex = -1; // 记录分叉字符的索引
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
Map<Character, Node> children = cur.next;
if (!children.containsKey(c)) {
return;
} else {
Node node = children.get(c);
if (node.next.size() > 1 || (node.next.size() == 1 && node.isWord)) {
multiNode = node;
multiIndex = i;
}
cur = node;
}
}
// 真正的删除操作
if (cur.isWord) {
if (cur.next.size() > 0) {
cur.isWord = false;
} else if (multiNode == null) {
this.root.next.remove(word.charAt(0));
} else {
multiNode.next.remove(word.charAt(multiIndex + 1));
}
this.size -= 1;
}
}
12.测试
public static void main(String[] args) {
String[] strs = {"pand", "panda", "service", "ex_serviceman", "gun", "army", "oil","coal", "petol", "pan"};
Trie trie = new Trie();
Arrays.stream(strs).forEach(item -> trie.addStr(item));
// System.out.println(trie.getSize());
// System.out.println(trie.matchWord("pan"));
// System.out.println(trie.search("p.l"));
// 匹配所有以express表达式为前缀的字符串
// List<String> list = trie.matchStartExpressWords("pan");
// list.stream().forEach(System.out::println);
trie.deleteWord("pand");
System.out.println(trie.matchWord("panda"));
System.out.println(trie.matchWord("pand"));
System.out.println(trie.matchWord("pan"));
}