数据结构第一弹-高级数据结构

大家好，今天和大家一起学习一下数据结构中的高级数据结构，比如Trie树，并查集等~

除了常见的数组、链表、栈、队列等基本数据结构外，还有许多高级数据结构能够解决特定问题，提供更高效或更优雅的解决方案。今天一起分享两种非常有用的高级数据结构——Trie树（字典树）和并查集（Union-Find）。

1. Trie树

1.1 概念

Trie树，也称为前缀树或字典树，是一种用于存储字符串集合的数据结构。它特别适用于快速查找和插入操作，尤其是在处理大量字符串时表现优异。Trie树中的每个节点代表一个字符，并且从根节点到某一节点的路径上所有字符连接起来即为该节点所代表的字符串。Trie树通常用于自动补全、拼写检查等功能。

1.2 工作原理

插入：从根节点开始遍历，根据当前字符创建新节点或移动到已存在的子节点。如果到达了单词末尾，则标记该节点表示一个完整的单词。
搜索：同样从根节点开始，按照目标字符串的字符顺序向下遍历。如果中途遇到不存在的字符，则返回未找到；如果成功遍历到字符串末尾并且最后一个节点被标记为单词结束，则表示找到了该单词。
删除：删除操作较为复杂，需要递归地从叶子节点向上回溯，只有当某个节点的所有子节点都为空且该节点不是其他单词的一部分时才能真正删除。

1.3 代码示例

class TrieNode {private final int ALPHABET_SIZE = 26;TrieNode[] children = new TrieNode[ALPHABET_SIZE];boolean isEndOfWord;public TrieNode() {isEndOfWord = false;for (int i = 0; i < ALPHABET_SIZE; i++) {children[i] = null;}}
}public class Trie {private TrieNode root;public Trie() {root = new TrieNode();}// 插入单词public void insert(String key) {TrieNode pCrawl = root;for (int level = 0; level < key.length(); level++) {int index = key.charAt(level) - 'a';if (pCrawl.children[index] == null)pCrawl.children[index] = new TrieNode();pCrawl = pCrawl.children[index];}pCrawl.isEndOfWord = true;}// 搜索单词public boolean search(String key) {TrieNode pCrawl = root;for (int level = 0; level < key.length(); level++) {int index = key.charAt(level) - 'a';if (pCrawl.children[index] == null)return false;pCrawl = pCrawl.children[index];}return (pCrawl != null && pCrawl.isEndOfWord);}// 删除单词public void delete(TrieNode root, String key, int depth) {if (root == null)return;if (depth == key.length()) {if (root.isEndOfWord)root.isEndOfWord = false;if (isEmpty(root))root = null;return;}int index = key.charAt(depth) - 'a';delete(root.children[index], key, depth + 1);if (isEmpty(root) && !root.isEndOfWord) {root = null;}}private boolean isEmpty(TrieNode node) {for (int i = 0; i < 26; i++) {if (node.children[i] != null)return false;}return true;}
}

2. 并查集

2.1 概念

并查集是一种用来管理不相交集合的数据结构，支持合并两个集合以及查询两个元素是否属于同一个集合的操作。它广泛应用于图论算法、网络分析等领域，如判断连通分量、检测环路等。

2.2 工作原理

初始化：每个元素最初都是自己集合的代表元。
查找：查找给定元素所属集合的代表元。为了优化效率，可以使用路径压缩技术，即将路径上的每个节点直接指向根节点。
合并：将两个集合合并成一个新的集合。这可以通过将一个集合的根节点指向另一个集合的根节点来完成。为了保持树的平衡，还可以采用按秩合并策略，即总是让较小的树成为较大的树的子树。

2.3 代码示例

public class UnionFind {private int[] parent;private int[] rank;public UnionFind(int size) {parent = new int[size];rank = new int[size];for (int i = 0; i < size; i++) {parent[i] = i;rank[i] = 0;}}// 查找public int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);  // 路径压缩}return parent[x];}// 合并public void union(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++;}}}// 判断是否属于同一集合public boolean isConnected(int x, int y) {return find(x) == find(y);}
}

3. 应用实例

3.1 Trie树的应用