Java高级数据结构 | AI生成和翻译
数据结构是高效算法的基础。让我们探索四种强大的数据结构：跳表、并查集、AVL树和二叉索引树。这些结构广泛应用于需要快速搜索、合并、平衡或区间查询的场景。
1. 跳表：概率性搜索
跳表是一种分层链表，支持快速搜索、插入和删除操作，平均时间复杂度为O(log n)，可作为平衡树的替代方案。
Java实现
import java.util.Random;
public class SkipList {
static class Node {
int value;
Node[] next;
Node(int value, int level) {
this.value = value;
this.next = new Node[level + 1];
}
}
private Node head;
private int maxLevel;
private Random rand;
private int level;
SkipList() {
maxLevel = 16;
head = new Node(-1, maxLevel);
rand = new Random();
level = 0;
}
private int randomLevel() {
int lvl = 0;
while (rand.nextBoolean() && lvl < maxLevel) lvl++;
return lvl;
}
void insert(int value) {
Node[] update = new Node[maxLevel + 1];
Node current = head;
for (int i = level; i >= 0; i--) {
while (current.next[i] != null && current.next[i].value < value) current = current.next[i];
update[i] = current;
}
current = current.next[0];
int newLevel = randomLevel();
if (newLevel > level) {
for (int i = level + 1; i <= newLevel; i++) update[i] = head;
level = newLevel;
}
Node newNode = new Node(value, newLevel);
for (int i = 0; i <= newLevel; i++) {
newNode.next[i] = update[i].next[i];
update[i].next[i] = newNode;
}
}
boolean search(int value) {
Node current = head;
for (int i = level; i >= 0; i--) {
while (current.next[i] != null && current.next[i].value < value) current = current.next[i];
}
current = current.next[0];
return current != null && current.value == value;
}
public static void main(String[] args) {
SkipList sl = new SkipList();
sl.insert(3);
sl.insert(6);
sl.insert(7);
System.out.println("Search 6: " + sl.search(6));
System.out.println("Search 5: " + sl.search(5));
}
}
输出:
Search 6: true
Search 5: false
2. 并查集（不相交集）：连通性追踪
并查集高效管理不相交集合，通过路径压缩和按秩合并启发式方法，支持近似O(1)摊还时间的合并与查找操作。
Java实现
public class UnionFind {
private int[] parent, rank;
UnionFind(int n) {
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
void union(int x, int y) {
int rootX = find(x), rootY = find(y);
if (rootX != rootY) {
if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
else {
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
public static void main(String[] args) {
UnionFind uf = new UnionFind(5);
uf.union(0, 1);
uf.union(2, 3);
uf.union(1, 4);
System.out.println("0 and 4 connected: " + (uf.find(0) == uf.find(4)));
System.out.println("2 and 4 connected: " + (uf.find(2) == uf.find(4)));
}
}
输出:
0 and 4 connected: true
2 and 4 connected: false
3. AVL树：自平衡二叉搜索树
AVL树是一种自平衡二叉搜索树，其子树间的高度差（平衡因子）最多为1，确保所有操作的时间复杂度为O(log n)。
Java实现
public class AVLTree {
static class Node {
int key, height;
Node left, right;
Node(int key) {
this.key = key;
this.height = 1;
}
}
private Node root;
int height(Node node) { return node == null ? 0 : node.height; }
int balanceFactor(Node node) { return node == null ? 0 : height(node.left) - height(node.right); }
Node rightRotate(Node y) {
Node x = y.left, T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
Node leftRotate(Node x) {
Node y = x.right, T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
Node insert(Node node, int key) {
if (node == null) return new Node(key);
if (key < node.key) node.left = insert(node.left, key);
else if (key > node.key) node.right = insert(node.right, key);
else return node;
node.height = Math.max(height(node.left), height(node.right)) + 1;
int balance = balanceFactor(node);
if (balance > 1 && key < node.left.key) return rightRotate(node);
if (balance < -1 && key > node.right.key) return leftRotate(node);
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
void insert(int key) { root = insert(root, key); }
void preOrder(Node node) {
if (node != null) {
System.out.print(node.key + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(40);
tree.insert(50);
tree.insert(25);
System.out.print("Preorder: ");
tree.preOrder(tree.root);
}
}
输出: Preorder: 30 20 10 25 40 50
4. 二叉索引树（Fenwick树）：区间查询
二叉索引树（BIT）高效处理区间和查询与更新操作，时间复杂度为O(log n)，常用于竞赛编程。
Java实现
public class BinaryIndexedTree {
private int[] bit;
private int n;
BinaryIndexedTree(int[] arr) {
n = arr.length;
bit = new int[n + 1];
for (int i = 0; i < n; i++) update(i, arr[i]);
}
void update(int index, int val) {
index++;
while (index <= n) {
bit[index] += val;
index += index & (-index);
}
}
int getSum(int index) {
int sum = 0;
index++;
while (index > 0) {
sum += bit[index];
index -= index & (-index);
}
return sum;
}
int rangeSum(int l, int r) { return getSum(r) - getSum(l - 1); }
public static void main(String[] args) {
int[] arr = {2, 1, 1, 3, 2, 3, 4, 5};
BinaryIndexedTree bit = new BinaryIndexedTree(arr);
System.out.println("Sum from 0 to 5: " + bit.getSum(5));
System.out.println("Range sum 2 to 5: " + bit.rangeSum(2, 5));
bit.update(3, 6); // 在索引3处加6
System.out.println("New range sum 2 to 5: " + bit.rangeSum(2, 5));
}
}
输出:
Sum from 0 to 5: 12
Range sum 2 to 5: 9
New range sum 2 to 5: 15
博客7：Java中的搜索与模拟算法
搜索与模拟算法解决路径查找和概率问题。让我们探索A*搜索和蒙特卡洛模拟。
1. A*搜索：启发式路径查找
A*是一种启发式搜索算法，使用启发函数在图中寻找最短路径，结合了Dijkstra算法和贪心搜索的优点。广泛应用于游戏和导航系统。
Java实现
import java.util.*;
public class AStar {
static class Node implements Comparable<Node> {
int x, y, g, h, f;
Node parent;
Node(int x, int y) {
this.x = x;
this.y = y;
this.g = 0;
this.h = 0;
this.f = 0;
}
public int compareTo(Node other) { return this.f - other.f; }
}
static int heuristic(int x1, int y1, int x2, int y2) {
return Math.abs(x1 - x2) + Math.abs(y1 - y2); // 曼哈顿距离
}
static void aStarSearch(int[][] grid, int[] start, int[] goal) {
int rows = grid.length, cols = grid[0].length;
PriorityQueue<Node> open = new PriorityQueue<>();
boolean[][] closed = new boolean[rows][cols];
Node startNode = new Node(start[0], start[1]);
Node goalNode = new Node(goal[0], goal[1]);
startNode.h = heuristic(start[0], start[1], goal[0], goal[1]);
startNode.f = startNode.h;
open.add(startNode);
int[][] dirs = {};
while (!open.isEmpty()) {
Node current = open.poll();
if (current.x == goal[0] && current.y == goal[1]) {
printPath(current);
return;
}
closed[current.x][current.y] = true;
for (int[] dir : dirs) {
int newX = current.x + dir[0], newY = current.y + dir[1];
if (newX >= 0 && newX < rows && newY >= 0 && newY < cols && grid[newX][newY] != 1 && !closed[newX][newY]) {
Node neighbor = new Node(newX, newY);
neighbor.g = current.g + 1;
neighbor.h = heuristic(newX, newY, goal[0], goal[1]);
neighbor.f = neighbor.g + neighbor.h;
neighbor.parent = current;
open.add(neighbor);
}
}
}
System.out.println("No path found!");
}
static void printPath(Node node) {
List<int[]> path = new ArrayList<>();
while (node != null) {
path.add(new int[]{node.x, node.y});
node = node.parent;
}
Collections.reverse(path);
System.out.println("Path:");
for (int[] p : path) System.out.println("(" + p[0] + ", " + p[1] + ")");
}
public static void main(String[] args) {
int[][] grid = {
{0, 0, 0, 0},
{0, 1, 1, 0},
{0, 0, 0, 0}
};
int[] start = {0, 0}, goal = {2, 3};
aStarSearch(grid, start, goal);
}
}
输出:
Path:
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
2. 蒙特卡洛模拟：概率估计
蒙特卡洛方法使用随机抽样来估计结果，例如通过在正方形和圆形中模拟点来近似计算π值。
Java实现
import java.util.Random;
public class MonteCarlo {
static double estimatePi(int points) {
Random rand = new Random();
int insideCircle = 0;
for (int i = 0; i < points; i++) {
double x = rand.nextDouble();
double y = rand.nextDouble();
if (x * x + y * y <= 1) insideCircle++; // 在单位圆内
}
return 4.0 * insideCircle / points; // 比例乘以4近似π
}
public static void main(String[] args) {
int points = 1000000;
double pi = estimatePi(points);
System.out.println("Estimated π with " + points + " points: " + pi);
System.out.println("Actual π: " + Math.PI);
}
}
输出（因随机性而有所变化）:
Estimated π with 1000000 points: 3.1418
Actual π: 3.141592653589793