算法和数据结构

知识树

graph LR
    A[算法与数据结构]
    
    A --> B[数据结构]
    B --> B1[线性结构]
    B1 --> B1a[数组 Array]
    B1 --> B1b[链表 Linked List]
    B1 --> B1c[栈 Stack]
    B1 --> B1d[队列 Queue]
    
    B --> B2[树结构]
    B2 --> B2a[二叉树 Binary Tree]
    B2 --> B2b[二叉搜索树 BST]
    B2 --> B2c[AVL 树]
    B2 --> B2d[红黑树 Red-Black Tree]
    B2 --> B2e[B 树 B-Tree]
    B2 --> B2f[堆 Heap]
    B2 --> B2g[Trie 前缀树]
    
    B --> B3[图结构]
    B3 --> B3a[有向图 Directed Graph]
    B3 --> B3b[无向图 Undirected Graph]
    B3 --> B3c[加权图 Weighted Graph]
    
    B --> B4[集合结构]
    B4 --> B4a[哈希表 Hash Table]
    B4 --> B4b[集合 Set]
    B4 --> B4c[位图 Bitmap]
    
    B --> B5[其他结构]
    B5 --> B5a[跳表 Skip List]
    B5 --> B5b[并查集 Union-Find]
    B5 --> B5c[线段树 Segment Tree]
    B5 --> B5d[树状数组 Fenwick Tree]
    
    A --> C[算法]
    C --> C1[排序算法]
    C1 --> C1a[冒泡排序 Bubble Sort]
    C1 --> C1b[选择排序 Selection Sort]
    C1 --> C1c[插入排序 Insertion Sort]
    C1 --> C1d[快速排序 Quick Sort]
    C1 --> C1e[归并排序 Merge Sort]
    C1 --> C1f[堆排序 Heap Sort]
    C1 --> C1g[计数排序 Counting Sort]
    
    C --> C2[搜索算法]
    C2 --> C2a[线性搜索 Linear Search]
    C2 --> C2b[二分搜索 Binary Search]
    C2 --> C2c[深度优先搜索 DFS]
    C2 --> C2d[广度优先搜索 BFS]
    
    C --> C3[图算法]
    C3 --> C3a[最短路径 Dijkstra/Bellman-Ford]
    C3 --> C3b[最小生成树 Prim/Kruskal]
    C3 --> C3c[拓扑排序 Topological Sort]
    
    C --> C4[动态规划 DP]
    C4 --> C4a[背包问题 Knapsack]
    C4 --> C4b[最长公共子序列 LCS]
    C4 --> C4c[最长递增子序列 LIS]
    
    C --> C5[贪心算法]
    C5 --> C5a[活动选择 Activity Selection]
    C5 --> C5b[哈夫曼编码 Huffman Coding]
    
    C --> C6[分治算法]
    C6 --> C6a[归并排序 Merge Sort]
    C6 --> C6b[快速排序 Quick Sort]
    
    C --> C7[数学与计算几何]
    C7 --> C7a[最大公约数 GCD]
    C7 --> C7b[快速幂 Fast Power]
    C7 --> C7c[凸包 Convex Hull]
    
    C --> C8[字符串算法]
    C8 --> C8a[KMP 算法]
    C8 --> C8b[Rabin-Karp]
    C8 --> C8c[Manacher]
    
    C --> C9[其他算法]
    C9 --> C9a[随机化算法 Randomized]
    C9 --> C9b[回溯算法 Backtracking]

数据结构

基础数据结构

数据结构	特点	操作	场景
数组 (Array)	连续内存存储，固定大小，元素类型相同	随机访问：O(1) 插入/删除：O(n)	快速查找 静态数据存储
链表 (Linked List)	非连续内存，动态大小，节点包含数据和指针 类型：单向链表、双向链表、循环链表	插入/删除：O(1) 查找：O(n)	频繁增删的场景（如LRU缓存）
栈 (Stack)	后进先出（LIFO），仅允许一端操作	入栈（push）：O(1) 出栈（pop）：O(1)	函数调用栈 括号匹配 表达式求值
队列 (Queue)	先进先出（FIFO），允许两端操作 变种：双端队列（Deque）、优先队列（Priority Queue）	入队/出队：O(1)（普通队列）	任务调度 广度优先搜索（BFS）

数组

1. 线性查找 (Linear Search)

• 功能描述：在数组中逐个检查元素，找到目标值并返回其索引，若不存在返回 -1。
• 时间复杂度：O(n)
• Java 代码实现：

  public int linearSearch(int[] arr, int target) {
      for (int i = 0; i < arr.length; i++) {
          if (arr[i] == target) {
              return i;
          }
      }
      return -1;
  }

2. 二分查找 (Binary Search)

• 功能描述：在有序数组中通过不断折半查找目标值，返回其索引，若不存在返回 -1。
• 时间复杂度：O(log n)
• Java 代码实现：

  public int binarySearch(int[] arr, int target) {
      int left = 0;
      int right = arr.length - 1;
      while (left <= right) {
          int mid = left + (right - left) / 2; // 防止溢出
          if (arr[mid] == target) {
              return mid;
          } else if (arr[mid] < target) {
              left = mid + 1;
          } else {
              right = mid - 1;
          }
      }
      return -1;
  }

3. 冒泡排序 (Bubble Sort)

• 功能描述：通过相邻元素两两比较并交换，将较大元素逐步“冒泡”到数组末尾，实现排序。
• 时间复杂度：O(n²)
• Java 代码实现：

  public void bubbleSort(int[] arr) {
      int n = arr.length;
      for (int i = 0; i < n - 1; i++) {
          for (int j = 0; j < n - i - 1; j++) {
              if (arr[j] > arr[j + 1]) {
                  // 交换元素
                  int temp = arr[j];
                  arr[j] = arr[j + 1];
                  arr[j + 1] = temp;
              }
          }
      }
  }

4. 快速排序 (Quick Sort)

• 功能描述：选择一个基准值（pivot），将数组分区并递归排序，适用于大多数情况的高效排序算法。
• 时间复杂度：O(n log n) 平均，O(n²) 最坏
• Java 代码实现：

  public void quickSort(int[] arr, int low, int high) {
      if (low < high) {
          int pi = partition(arr, low, high);
          quickSort(arr, low, pi - 1);
          quickSort(arr, pi + 1, high);
      }
  }
  
  private int partition(int[] arr, int low, int high) {
      int pivot = arr[high];
      int i = low - 1;
      for (int j = low; j < high; j++) {
          if (arr[j] <= pivot) {
              i++;
              int temp = arr[i];
              arr[i] = arr[j];
              arr[j] = temp;
          }
      }
      int temp = arr[i + 1];
      arr[i + 1] = arr[high];
      arr[high] = temp;
      return i + 1;
  }

5. 数组反转 (Reverse Array)

• 功能描述：使用双指针从两端向中间交换元素，将数组顺序反转。
• 时间复杂度：O(n)
• Java 代码实现：

  public void reverseArray(int[] arr) {
      int left = 0;
      int right = arr.length - 1;
      while (left < right) {
          int temp = arr[left];
          arr[left] = arr[right];
          arr[right] = temp;
          left++;
          right--;
      }
  }

6. 查找最大值 (Find Maximum)

• 功能描述：遍历数组，比较每个元素，找出最大值。
• 时间复杂度：O(n)
• Java 代码实现：

  public int findMax(int[] arr) {
      if (arr.length == 0) {
          throw new IllegalArgumentException("Array is empty");
      }
      int max = arr[0];
      for (int i = 1; i < arr.length; i++) {
          if (arr[i] > max) {
              max = arr[i];
          }
      }
      return max;
  }

7. 删除重复元素 (Remove Duplicates from Sorted Array)

• 功能描述：在有序数组中删除重复元素，返回新长度，原地修改数组。
• 时间复杂度：O(n)
• Java 代码实现：

  public int removeDuplicates(int[] arr) {
      if (arr.length == 0) {
          return 0;
      }
      int writeIndex = 1;
      for (int i = 1; i < arr.length; i++) {
          if (arr[i] != arr[i - 1]) {
              arr[writeIndex] = arr[i];
              writeIndex++;
          }
      }
      return writeIndex;
  }

8. 旋转数组 (Rotate Array)

• 功能描述：将数组向右旋转 k 个位置，使用三次反转法实现。
• 时间复杂度：O(n)
• Java 代码实现：

  public void rotate(int[] arr, int k) {
      k %= arr.length; // 处理 k 大于数组长度的情况
      reverse(arr, 0, arr.length - 1); // 反转整个数组
      reverse(arr, 0, k - 1);          // 反转前 k 个元素
      reverse(arr, k, arr.length - 1); // 反转剩余元素
  }
  
  private void reverse(int[] arr, int start, int end) {
      while (start < end) {
          int temp = arr[start];
          arr[start] = arr[end];
          arr[end] = temp;
          start++;
          end--;
      }
  }

9. 两数之和 (Two Sum)

• 功能描述：找到数组中两个元素的索引，其和等于目标值，使用哈希表优化。
• 时间复杂度：O(n)
• Java 代码实现：

  import java.util.HashMap;
  
  public int[] twoSum(int[] arr, int target) {
      HashMap<Integer, Integer> map = new HashMap<>();
      for (int i = 0; i < arr.length; i++) {
          int complement = target - arr[i];
          if (map.containsKey(complement)) {
              return new int[] {map.get(complement), i};
          }
          map.put(arr[i], i);
      }
      return new int[] {}; // 未找到返回空数组
  }

10. 归并排序 (Merge Sort)

• 功能描述：使用分治法将数组分成小块，分别排序后合并，稳定且适用于大数据。
• 时间复杂度：O(n log n)
• Java 代码实现：

  public void mergeSort(int[] arr, int left, int right) {
      if (left < right) {
          int mid = left + (right - left) / 2;
          mergeSort(arr, left, mid);
          mergeSort(arr, mid + 1, right);
          merge(arr, left, mid, right);
      }
  }
  
  private void merge(int[] arr, int left, int mid, int right) {
      int n1 = mid - left + 1;
      int n2 = right - mid;
      int[] leftArr = new int[n1];
      int[] rightArr = new int[n2];
  
      // 填充临时数组
      // 将原数组的左子数组（arr[left..mid]）复制到 leftArr。
      for (int i = 0; i < n1; i++) {
          leftArr[i] = arr[left + i];
      }
      // 将原数组的右子数组（arr[mid+1..right]）复制到 rightArr。
      for (int j = 0; j < n2; j++) {
          rightArr[j] = arr[mid + 1 + j];
      }
  
      // 合并
      int i = 0, j = 0, k = left;
      while (i < n1 && j < n2) {
          if (leftArr[i] <= rightArr[j]) {
              arr[k++] = leftArr[i++];
          } else {
              arr[k++] = rightArr[j++];
          }
      }
      while (i < n1) {
          arr[k++] = leftArr[i++];
      }
      while (j < n2) {
          arr[k++] = rightArr[j++];
      }
  }

11. 前缀和 (Prefix Sum)

• 功能描述：计算数组的前缀和，用于快速求解子数组和的问题。
• 时间复杂度：O(n) 预处理，O(1) 查询
• Java 代码实现：

  public int[] prefixSum(int[] arr) {
      int[] prefix = new int[arr.length];
      prefix[0] = arr[0];
      for (int i = 1; i < arr.length; i++) {
          prefix[i] = prefix[i - 1] + arr[i];
      }
      return prefix;
  }
  
  // 查询子数组和 [left, right]
  public int rangeSum(int[] prefix, int left, int right) {
      if (left == 0) {
          return prefix[right];
      }
      return prefix[right] - prefix[left - 1];
  }

12. 滑动窗口最大值 (Sliding Window Maximum)

• 功能描述：使用双端队列在固定窗口大小 k 内找到每个窗口的最大值。
• 时间复杂度：O(n)
• Java 代码实现：

  import java.util.ArrayDeque;
  
  public int[] maxSlidingWindow(int[] arr, int k) {
      if (arr == null || arr.length == 0 || k <= 0) {
          return new int[0];
      }
      int[] result = new int[arr.length - k + 1];
      ArrayDeque<Integer> deque = new ArrayDeque<>(); // 存储索引
  
      for (int i = 0; i < arr.length; i++) {
          // 移除超出窗口的元素
          while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
              deque.pollFirst();
          }
          // 移除小于当前元素的值
          while (!deque.isEmpty() && arr[deque.peekLast()] < arr[i]) {
              deque.pollLast();
          }
          deque.offerLast(i);
          // 窗口形成后记录最大值
          if (i >= k - 1) {
              result[i - k + 1] = arr[deque.peekFirst()];
          }
      }
      return result;
  }

13. 合并两个有序数组 (Merge Two Sorted Arrays)

• 功能描述：将两个有序数组合并为一个有序数组，原地修改第一个数组。
• 时间复杂度：O(m + n)，其中 m 和 n 是两个数组的长度
• Java 代码实现：

  public void mergeSortedArrays(int[] nums1, int m, int[] nums2, int n) {
      int p1 = m - 1; // nums1 的指针
      int p2 = n - 1; // nums2 的指针
      int p = m + n - 1; // 合并后数组的指针
  
      while (p2 >= 0 && p1 >= 0) {
          if (nums1[p1] > nums2[p2]) {
              nums1[p--] = nums1[p1--];
          } else {
              nums1[p--] = nums2[p2--];
          }
      }
      // 如果 nums2 还有剩余元素
      while (p2 >= 0) {
          nums1[p--] = nums2[p2--];
      }
  }

14. 数组中第 k 大元素 (Kth Largest Element)

• 功能描述：使用快速选择算法（QuickSelect）找到数组中第 k 大的元素。
• 时间复杂度：O(n) 平均，O(n²) 最坏
• Java 代码实现：

  public int findKthLargest(int[] arr, int k) {
      return quickSelect(arr, 0, arr.length - 1, arr.length - k);
  }
  
  private int quickSelect(int[] arr, int left, int right, int k) {
      if (left == right) {
          return arr[left];
      }
      int pivotIndex = partition(arr, left, right);
      if (k == pivotIndex) {
          return arr[k];
      } else if (k < pivotIndex) {
          return quickSelect(arr, left, pivotIndex - 1, k);
      } else {
          return quickSelect(arr, pivotIndex + 1, right, k);
      }
  }
  
  private int partition(int[] arr, int left, int right) {
      int pivot = arr[right];
      int i = left - 1;
      for (int j = left; j < right; j++) {
          if (arr[j] <= pivot) {
              i++;
              swap(arr, i, j);
          }
      }
      swap(arr, i + 1, right);
      return i + 1;
  }
  
  private void swap(int[] arr, int i, int j) {
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
  }

15. 数组元素移动零 (Move Zeroes)

• 功能描述：将数组中的所有零移动到末尾，保持非零元素相对顺序。
• 时间复杂度：O(n)
• Java 代码实现：

  public void moveZeroes(int[] arr) {
      int nonZeroIndex = 0;
      // 将非零元素移到前面
      for (int i = 0; i < arr.length; i++) {
          if (arr[i] != 0) {
              arr[nonZeroIndex++] = arr[i];
          }
      }
      // 填充剩余位置为零
      while (nonZeroIndex < arr.length) {
          arr[nonZeroIndex++] = 0;
      }
  }

链表

单链表

定义单链表

class ListNode {
    int val;         // 数据域
    ListNode next;   // 指向下一个节点的引用

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

遍历链表

原理

• 从头节点开始，沿 next 指针依次访问每个节点，直到遇到 null。
• 用于统计长度、查找节点或打印链表。

代码

public class Main {
    // 计算链表长度
    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        ListNode.printList(head); // 输出: 1 -> 2 -> 3 -> null
    }
}

复杂度

• 时间复杂度: O(n)，n 是链表长度。
• 空间复杂度: O(1)，只用一个指针。

---

反转链表

原理

• 使用三个指针（prev、curr、next）迭代反转每个节点的 next 指针。
• 核心思想：逐步调整指针方向，原地完成反转。

代码

public class Main {
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;  // 保存下一个节点
            curr.next = prev;           // 反转指针
            prev = curr;                // 前移 prev
            curr = next;                // 前移 curr
        }
        return prev;                    // 新头节点
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);

        ListNode reversed = reverseList(head);
        ListNode.printList(reversed); // 输出: 3 -> 2 -> 1 -> null
    }
}

复杂度

• 时间复杂度: O(n)，一次遍历。
• 空间复杂度: O(1)，原地操作。

---

反转链表指定区间

public ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null || head.next == null || left == right) {
            return head;
    }

    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode pre = dummy;

    for (int i = 1; i < left; i++) {
        pre = pre.next;
    }

    ListNode start = pre.next;
    ListNode curr = start.next;

    for (int i = left; i < right; i++) {
        start.next = curr.next;
        curr.next = pre.next;
        pre.next =curr;
        curr = start.next;
    }

    return dummy.next;
}

复杂度

• 时间复杂度: O(n)，一次遍历。
• 空间复杂度: O(1)，原地操作。

---

合并两个有序链表

原理

• 类似归并排序的合并过程，比较两个链表的节点值，逐步构建新链表。
• 使用哑节点（dummy node）简化边界处理。

代码

public class Main {
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // 哑节点
        ListNode curr = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }

        // 处理剩余节点
        curr.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        l1.next = new ListNode(3);
        l1.next.next = new ListNode(5);

        ListNode l2 = new ListNode(2);
        l2.next = new ListNode(4);
        l2.next.next = new ListNode(6);

        ListNode merged = mergeTwoLists(l1, l2);
        ListNode.printList(merged); // 输出: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
    }
}

复杂度

• 时间复杂度: O(n + m)，n 和 m 是两个链表长度。
• 空间复杂度: O(1)，仅用哑节点，不计输出空间。

---

检测链表中的环

原理

• 使用快慢指针法（Floyd 判圈算法）：
  • 慢指针每次走 1 步，快指针每次走 2 步。
  • 若有环，快慢指针会在环内相遇；若无环，快指针先到 null。

代码

public class Main {
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;         // 慢指针走 1 步
            fast = fast.next.next;    // 快指针走 2 步
            if (slow == fast) return true; // 相遇说明有环
        }
        return false;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = head.next; // 创建环: 1 -> 2 -> 3 -> 2

        System.out.println(hasCycle(head)); // 输出: true
    }
}

复杂度

• 时间复杂度: O(n)，快指针最多跑完环的长度。
• 空间复杂度: O(1)，只用两个指针。

---

删除链表中的节点

原理

• 普通删除: 找到目标节点的前驱，调整指针跳过目标。
• 特殊情况: 如果只给定要删除的节点（无前驱引用），将其值替换为下个节点的值，再删除下个节点。

代码

删除指定值的节点

public class Main {
    public static ListNode deleteNode(ListNode head, int val) {
        ListNode dummy = new ListNode(0, head); // 哑节点处理头节点删除
        ListNode curr = dummy;

        while (curr.next != null) {
            if (curr.next.val == val) {
                curr.next = curr.next.next; // 跳过目标节点
                break;
            }
            curr = curr.next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);

        ListNode result = deleteNode(head, 2);
        ListNode.printList(result); // 输出: 1 -> 3 -> null
    }
}

只给定节点删除（无前驱）

public class Main {
    public static void deleteNode(ListNode node) {
        // 假设 node 是要删除的节点，且不是尾节点
        node.val = node.next.val;    // 复制下个节点的值
        node.next = node.next.next;  // 跳过下个节点
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        ListNode nodeToDelete = head.next; // 删除 2

        deleteNode(nodeToDelete);
        ListNode.printList(head); // 输出: 1 -> 3 -> null
    }
}

复杂度

• 普通删除: O(n) 时间，O(1) 空间。
• 给定节点删除: O(1) 时间，O(1) 空间。

---

查找中间节点

原理

• 使用快慢指针：快指针走 2 步，慢指针走 1 步，快指针到尾时，慢指针在中间。

代码

public class Main {
    public static ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        ListNode middle = middleNode(head);
        System.out.println(middle.val); // 输出: 3 (偶数长度取后半中间)
    }
}

复杂度

• 时间复杂度: O(n)。
• 空间复杂度: O(1)。

双链表

双链表节点定义

class DoublyListNode {
    int val;
    DoublyListNode prev;
    DoublyListNode next;
    
    public DoublyListNode(int val) {
        this.val = val;
    }
}

双链表基本类

class DoublyLinkedList {
    private DoublyListNode head;
    private DoublyListNode tail;
    
    public DoublyLinkedList() {
        head = null;
        tail = null;
    }
    
    public DoublyListNode getHead() { return head; }
    public DoublyListNode getTail() { return tail; }
    public void setHead(DoublyListNode head) { this.head = head; }
    public void setTail(DoublyListNode tail) { this.tail = tail; }
}

在头部添加节点

// 时间复杂度: O(1), 空间复杂度: O(1)
public void addFirst(DoublyLinkedList list, int val) {
    DoublyListNode newNode = new DoublyListNode(val);
    if (list.getHead() == null) {
        list.setHead(newNode);
        list.setTail(newNode);
    } else {
        newNode.next = list.getHead();
        list.getHead().prev = newNode;
        list.setHead(newNode);
    }
}

在尾部添加节点

// 时间复杂度: O(1), 空间复杂度: O(1)
public void addLast(DoublyLinkedList list, int val) {
    DoublyListNode newNode = new DoublyListNode(val);
    if (list.getTail() == null) {
        list.setHead(newNode);
        list.setTail(newNode);
    } else {
        newNode.prev = list.getTail();
        list.getTail().next = newNode;
        list.setTail(newNode);
    }
}

删除指定值的第一个节点

// 时间复杂度: O(n), 空间复杂度: O(1)
public boolean remove(DoublyLinkedList list, int val) {
    DoublyListNode current = list.getHead();
    while (current != null) {
        if (current.val == val) {
            if (current == list.getHead()) {
                list.setHead(list.getHead().next);
                if (list.getHead() != null) {
                    list.getHead().prev = null;
                } else {
                    list.setTail(null);
                }
            }
            else if (current == list.getTail()) {
                list.setTail(list.getTail().prev);
                list.getTail().next = null;
            }
            else {
                current.prev.next = current.next;
                current.next.prev = current.prev;
            }
            return true;
        }
        current = current.next;
    }
    return false;
}

打印链表

// 时间复杂度: O(n), 空间复杂度: O(1)
public void printList(DoublyLinkedList list) {
    DoublyListNode current = list.getHead();
    while (current != null) {
        System.out.print(current.val + " ");
        current = current.next;
    }
    System.out.println();
}

反转双链表

// 时间复杂度: O(n), 空间复杂度: O(1)
public void reverse(DoublyLinkedList list) {
    if (list.getHead() == null || list.getHead().next == null) {
        return;
    }
    
    DoublyListNode current = list.getHead();
    DoublyListNode temp = null;
    
    while (current != null) {
        temp = current.prev;
        current.prev = current.next;
        current.next = temp;
        current = current.prev;
    }
    
    temp = list.getHead();
    list.setHead(list.getTail());
    list.setTail(temp);
}

查找中间节点

// 时间复杂度: O(n), 空间复杂度: O(1)
public DoublyListNode findMiddle(DoublyLinkedList list) {
    if (list.getHead() == null) return null;
    
    DoublyListNode slow = list.getHead();
    DoublyListNode fast = list.getHead();
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;
}

检测循环

// 时间复杂度: O(n), 空间复杂度: O(1)
public boolean hasCycle(DoublyLinkedList list) {
    if (list.getHead() == null) return false;
    
    DoublyListNode slow = list.getHead();
    DoublyListNode fast = list.getHead();
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

合并两个有序双链表

// 时间复杂度: O(n + m), 空间复杂度: O(n + m)
public DoublyLinkedList mergeSortedLists(DoublyLinkedList list1, DoublyLinkedList list2) {
    DoublyLinkedList merged = new DoublyLinkedList();
    DoublyListNode p1 = list1.getHead();
    DoublyListNode p2 = list2.getHead();
    
    while (p1 != null && p2 != null) {
        if (p1.val <= p2.val) {
            addLast(merged, p1.val);
            p1 = p1.next;
        } else {
            addLast(merged, p2.val);
            p2 = p2.next;
        }
    }
    
    while (p1 != null) {
        addLast(merged, p1.val);
        p1 = p1.next;
    }
    while (p2 != null) {
        addLast(merged, p2.val);
        p2 = p2.next;
    }
    
    return merged;
}

使用示例

public static void main(String[] args) {
    DoublyLinkedList list = new DoublyLinkedList();
    
    addLast(list, 1);
    addLast(list, 2);
    addLast(list, 3);
    
    System.out.println("Original list:");
    printList(list);  // 输出: 1 2 3
    
    reverse(list);
    System.out.println("Reversed list:");
    printList(list);  // 输出: 3 2 1
    
    DoublyListNode middle = findMiddle(list);
    System.out.println("Middle node value: " + middle.val);  // 输出: 2
}

单向循环链表

• 循环链表的特点是尾节点的 next 指向头节点，形成闭环。
• 这些算法适用于单向循环链表，操作时需要特别注意循环的维护。
• 分割算法假设链表长度为偶数时分成相等两半，奇数时第一部分少一个节点。

1. 循环链表节点定义

class CircularListNode {
    int val;
    CircularListNode next;
    
    public CircularListNode(int val) {
        this.val = val;
    }
}

2. 循环链表基本类

class CircularLinkedList {
    private CircularListNode tail;  // 指向最后一个节点
    
    public CircularLinkedList() {
        tail = null;
    }
    
    public CircularListNode getTail() { return tail; }
    public void setTail(CircularListNode tail) { this.tail = tail; }
}

3. 在尾部添加节点

// 时间复杂度: O(1), 空间复杂度: O(1)
public void addLast(CircularLinkedList list, int val) {
    CircularListNode newNode = new CircularListNode(val);
    if (list.getTail() == null) {
        list.setTail(newNode);
        newNode.next = newNode;  // 指向自己形成循环
    } else {
        newNode.next = list.getTail().next;  // 新节点指向头节点
        list.getTail().next = newNode;       // 原尾节点指向新节点
        list.setTail(newNode);              // 更新尾节点
    }
}

4. 在头部添加节点

// 时间复杂度: O(1), 空间复杂度: O(1)
public void addFirst(CircularLinkedList list, int val) {
    CircularListNode newNode = new CircularListNode(val);
    if (list.getTail() == null) {
        list.setTail(newNode);
        newNode.next = newNode;
    } else {
        newNode.next = list.getTail().next;  // 新节点指向原头节点
        list.getTail().next = newNode;       // 尾节点指向新节点
    }
}

5. 删除指定值的第一个节点

// 时间复杂度: O(n), 空间复杂度: O(1)
public boolean remove(CircularLinkedList list, int val) {
    if (list.getTail() == null) return false;
    
    CircularListNode current = list.getTail().next;  // 从头开始
    CircularListNode prev = list.getTail();
    
    do {
        if (current.val == val) {
            // 只有一个节点
            if (current == list.getTail() && current.next == current) {
                list.setTail(null);
            }
            // 删除头节点
            else if (current == list.getTail().next) {
                list.getTail().next = current.next;
            }
            // 删除尾节点
            else if (current == list.getTail()) {
                prev.next = list.getTail().next;
                list.setTail(prev);
            }
            // 删除中间节点
            else {
                prev.next = current.next;
            }
            return true;
        }
        prev = current;
        current = current.next;
    } while (current != list.getTail().next);
    
    return false;
}

6. 打印循环链表

// 时间复杂度: O(n), 空间复杂度: O(1)
public void printList(CircularLinkedList list) {
    if (list.getTail() == null) {
        System.out.println("List is empty");
        return;
    }
    
    CircularListNode current = list.getTail().next;
    do {
        System.out.print(current.val + " ");
        current = current.next;
    } while (current != list.getTail().next);
    System.out.println();
}

7. 检测循环（验证是否正确形成循环链表）

// 时间复杂度: O(n), 空间复杂度: O(1)
public boolean isCircular(CircularLinkedList list) {
    if (list.getTail() == null) return true;  // 空链表认为是循环的
    
    CircularListNode slow = list.getTail().next;
    CircularListNode fast = list.getTail().next;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;  // 快慢指针相遇说明有环
    }
    return false;  // 理论上循环链表总是返回true，除非链表损坏
}

8. 查找链表长度

// 时间复杂度: O(n), 空间复杂度: O(1)
public int getLength(CircularLinkedList list) {
    if (list.getTail() == null) return 0;
    
    int length = 0;
    CircularListNode current = list.getTail().next;
    do {
        length++;
        current = current.next;
    } while (current != list.getTail().next);
    
    return length;
}

9. 分割循环链表为两个循环链表

// 时间复杂度: O(n), 空间复杂度: O(1)
// 将链表分成两半，前半部分和后半部分分别形成新的循环链表
public CircularLinkedList[] splitList(CircularLinkedList list) {
    if (list.getTail() == null || list.getTail().next == list.getTail()) {
        return new CircularLinkedList[]{list, new CircularLinkedList()};
    }
    
    CircularListNode slow = list.getTail().next;
    CircularListNode fast = list.getTail().next;
    CircularListNode prev = list.getTail();
    
    // 找到中间节点
    while (fast != list.getTail().next || fast.next != list.getTail().next) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    // 分割
    CircularLinkedList list1 = new CircularLinkedList();
    CircularLinkedList list2 = new CircularLinkedList();
    
    list1.setTail(prev);
    list2.setTail(list.getTail());
    
    prev.next = list.getTail().next;  // 第一部分形成循环
    list2.getTail().next = slow;      // 第二部分形成循环
    
    return new CircularLinkedList[]{list1, list2};
}

使用示例

public static void main(String[] args) {
    CircularLinkedList list = new CircularLinkedList();
    
    addLast(list, 1);
    addLast(list, 2);
    addLast(list, 3);
    addLast(list, 4);
    
    System.out.println("Original list:");
    printList(list);  // 输出: 1 2 3 4
    
    System.out.println("Length: " + getLength(list));  // 输出: 4
    
    remove(list, 2);
    System.out.println("After removing 2:");
    printList(list);  // 输出: 1 3 4
    
    CircularLinkedList[] splitLists = splitList(list);
    System.out.println("First half:");
    printList(splitLists[0]);  // 输出: 1
    System.out.println("Second half:");
    printList(splitLists[1]);  // 输出: 3 4
}

栈

栈是一种后进先出（LIFO）的数据结构

• 数组实现：适合固定大小的场景，空间利用率高但不灵活。
• 链表实现：动态大小，无需预定义容量，适合不确定大小的场景。

---

1. 基于数组的栈实现

栈的基本类（数组实现）

class ArrayStack {
    private int[] arr;
    private int top;  // 栈顶指针
    private int capacity;
    
    public ArrayStack(int size) {
        arr = new int[size];
        capacity = size;
        top = -1;
    }
}

1.1 入栈（push）

// 时间复杂度: O(1), 空间复杂度: O(1)
public void push(ArrayStack stack, int val) {
    if (stack.top == stack.capacity - 1) {
        throw new IllegalStateException("Stack is full");
    }
    stack.arr[++stack.top] = val;
}

1.2 出栈（pop）

// 时间复杂度: O(1), 空间复杂度: O(1)
public int pop(ArrayStack stack) {
    if (stack.top == -1) {
        throw new IllegalStateException("Stack is empty");
    }
    return stack.arr[stack.top--];
}

1.3 查看栈顶元素（peek）

// 时间复杂度: O(1), 空间复杂度: O(1)
public int peek(ArrayStack stack) {
    if (stack.top == -1) {
        throw new IllegalStateException("Stack is empty");
    }
    return stack.arr[stack.top];
}

1.4 判断栈是否为空

// 时间复杂度: O(1), 空间复杂度: O(1)
public boolean isEmpty(ArrayStack stack) {
    return stack.top == -1;
}

1.5 判断栈是否已满

// 时间复杂度: O(1), 空间复杂度: O(1)
public boolean isFull(ArrayStack stack) {
    return stack.top == stack.capacity - 1;
}

---

2. 基于链表的栈实现

栈节点定义

class StackNode {
    int val;
    StackNode next;
    
    public StackNode(int val) {
        this.val = val;
    }
}

栈的基本类（链表实现）

class LinkedStack {
    private StackNode top;  // 栈顶指针
    
    public LinkedStack() {
        top = null;
    }
    
    public StackNode getTop() { return top; }
    public void setTop(StackNode top) { this.top = top; }
}

2.1 入栈（push）

// 时间复杂度: O(1), 空间复杂度: O(1)
public void push(LinkedStack stack, int val) {
    StackNode newNode = new StackNode(val);
    newNode.next = stack.getTop();
    stack.setTop(newNode);
}

2.2 出栈（pop）

// 时间复杂度: O(1), 空间复杂度: O(1)
public int pop(LinkedStack stack) {
    if (stack.getTop() == null) {
        throw new IllegalStateException("Stack is empty");
    }
    int val = stack.getTop().val;
    stack.setTop(stack.getTop().next);
    return val;
}

2.3 查看栈顶元素（peek）

// 时间复杂度: O(1), 空间复杂度: O(1)
public int peek(LinkedStack stack) {
    if (stack.getTop() == null) {
        throw new IllegalStateException("Stack is empty");
    }
    return stack.getTop().val;
}

2.4 判断栈是否为空

// 时间复杂度: O(1), 空间复杂度: O(1)
public boolean isEmpty(LinkedStack stack) {
    return stack.getTop() == null;
}

---

3. 栈的常用算法

3.1 反转栈

// 时间复杂度: O(n), 空间复杂度: O(n)
// 使用辅助栈反转原栈
public LinkedStack reverseStack(LinkedStack stack) {
    LinkedStack reversed = new LinkedStack();
    while (!isEmpty(stack)) {
        push(reversed, pop(stack));
    }
    return reversed;
}

3.2 检查括号匹配

// 时间复杂度: O(n), 空间复杂度: O(n)
// 检查字符串中的括号是否匹配
public boolean isValidParentheses(String s) {
    LinkedStack stack = new LinkedStack();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '{' || c == '[') {
            push(stack, c);
        } else if (c == ')' || c == '}' || c == ']') {
            if (isEmpty(stack)) return false;
            int top = pop(stack);
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return isEmpty(stack);
}

3.3 计算后缀表达式（逆波兰表达式）

// 时间复杂度: O(n), 空间复杂度: O(n)
// 计算后缀表达式的值
public int evaluatePostfix(String[] tokens) {
    LinkedStack stack = new LinkedStack();
    for (String token : tokens) {
        if (token.matches("-?\\d+")) {  // 是数字
            push(stack, Integer.parseInt(token));
        } else {  // 是运算符
            int b = pop(stack);
            int a = pop(stack);
            switch (token) {
                case "+": push(stack, a + b); break;
                case "-": push(stack, a - b); break;
                case "*": push(stack, a * b); break;
                case "/": push(stack, a / b); break;
            }
        }
    }
    return pop(stack);
}

3.4 最小栈（获取栈中最小元素）

// 支持在 O(1) 时间获取最小元素的栈
class MinStack {
    private LinkedStack mainStack;
    private LinkedStack minStack;  // 辅助栈存储最小值
    
    public MinStack() {
        mainStack = new LinkedStack();
        minStack = new LinkedStack();
    }
    
    // 时间复杂度: O(1), 空间复杂度: O(1)
    public void push(int val) {
        push(mainStack, val);
        if (isEmpty(minStack) || val <= peek(minStack)) {
            push(minStack, val);
        }
    }
    
    // 时间复杂度: O(1), 空间复杂度: O(1)
    public int pop() {
        int val = pop(mainStack);
        if (val == peek(minStack)) {
            pop(minStack);
        }
        return val;
    }
    
    // 时间复杂度: O(1), 空间复杂度: O(1)
    public int getMin() {
        if (isEmpty(minStack)) {
            throw new IllegalStateException("Stack is empty");
        }
        return peek(minStack);
    }
}

---

使用示例

public static void main(String[] args) {
    // 数组栈示例
    ArrayStack arrayStack = new ArrayStack(5);
    push(arrayStack, 1);
    push(arrayStack, 2);
    push(arrayStack, 3);
    System.out.println("Array Stack top: " + peek(arrayStack));  // 输出: 3
    System.out.println("Popped: " + pop(arrayStack));           // 输出: 3
    
    // 链表栈示例
    LinkedStack linkedStack = new LinkedStack();
    push(linkedStack, 1);
    push(linkedStack, 2);
    push(linkedStack, 3);
    LinkedStack reversed = reverseStack(linkedStack);
    System.out.println("Reversed Stack top: " + peek(reversed));  // 输出: 1
    
    // 括号匹配
    String s = "{[()]}";
    System.out.println("Parentheses valid: " + isValidParentheses(s));  // 输出: true
    
    // 后缀表达式
    String[] postfix = {"2", "1", "+", "3", "*"};
    System.out.println("Postfix result: " + evaluatePostfix(postfix));  // 输出: 9
    
    // 最小栈
    MinStack minStack = new MinStack();
    minStack.push(3);
    minStack.push(5);
    minStack.push(2);
    System.out.println("Min value: " + minStack.getMin());  // 输出: 2
}

队列

队列是一种先进先出（FIFO）的数据结构

• 数组队列：简单实现，但空间利用率低，出队后空间不可复用。
• 链表队列：动态大小，适合不确定长度的场景。
• 循环队列：优化数组队列，复用空间，适合固定大小场景。
• 双端队列：支持两端操作，灵活性更高。
• 优先队列：基于最小堆实现，保证每次出队的是最小元素。

---

1. 基于数组的队列实现

队列的基本类（数组实现）

class ArrayQueue {
    private int[] arr;
    private int front;  // 队首指针
    private int rear;   // 队尾指针
    private int capacity;
    
    public ArrayQueue(int size) {
        arr = new int[size];
        capacity = size;
        front = 0;
        rear = -1;
    }
}

1.1 入队（enqueue）

// 时间复杂度: O(1), 空间复杂度: O(1)
public void enqueue(ArrayQueue queue, int val) {
    if (queue.rear == queue.capacity - 1) {
        throw new IllegalStateException("Queue is full");
    }
    queue.arr[++queue.rear] = val;
}

1.2 出队（dequeue）

// 时间复杂度: O(1), 空间复杂度: O(1)
public int dequeue(ArrayQueue queue) {
    if (queue.front > queue.rear) {
        throw new IllegalStateException("Queue is empty");
    }
    return queue.arr[queue.front++];
}

1.3 查看队首元素（peek）

// 时间复杂度: O(1), 空间复杂度: O(1)
public int peek(ArrayQueue queue) {
    if (queue.front > queue.rear) {
        throw new IllegalStateException("Queue is empty");
    }
    return queue.arr[queue.front];
}

1.4 判断队列是否为空

// 时间复杂度: O(1), 空间复杂度: O(1)
public boolean isEmpty(ArrayQueue queue) {
    return queue.front > queue.rear;
}

1.5 判断队列是否已满

// 时间复杂度: O(1), 空间复杂度: O(1)
public boolean isFull(ArrayQueue queue) {
    return queue.rear == queue.capacity - 1;
}

---

2. 基于链表的队列实现

队列节点定义

class QueueNode {
    int val;
    QueueNode next;
    
    public QueueNode(int val) {
        this.val = val;
    }
}

队列的基本类（链表实现）

class LinkedQueue {
    private QueueNode front;  // 队首指针
    private QueueNode rear;   // 队尾指针
    
    public LinkedQueue() {
        front = null;
        rear = null;
    }
    
    public QueueNode getFront() { return front; }
    public QueueNode getRear() { return rear; }
    public void setFront(QueueNode front) { this.front = front; }
    public void setRear(QueueNode rear) { this.rear = rear; }
}

2.1 入队（enqueue）

// 时间复杂度: O(1), 空间复杂度: O(1)
public void enqueue(LinkedQueue queue, int val) {
    QueueNode newNode = new QueueNode(val);
    if (queue.getRear() == null) {
        queue.setFront(newNode);
        queue.setRear(newNode);
    } else {
        queue.getRear().next = newNode;
        queue.setRear(newNode);
    }
}

2.2 出队（dequeue）

// 时间复杂度: O(1), 空间复杂度: O(1)
public int dequeue(LinkedQueue queue) {
    if (queue.getFront() == null) {
        throw new IllegalStateException("Queue is empty");
    }
    int val = queue.getFront().val;
    queue.setFront(queue.getFront().next);
    if (queue.getFront() == null) {
        queue.setRear(null);
    }
    return val;
}

2.3 查看队首元素（peek）

// 时间复杂度: O(1), 空间复杂度: O(1)
public int peek(LinkedQueue queue) {
    if (queue.getFront() == null) {
        throw new IllegalStateException("Queue is empty");
    }
    return queue.getFront().val;
}

2.4 判断队列是否为空

// 时间复杂度: O(1), 空间复杂度: O(1)
public boolean isEmpty(LinkedQueue queue) {
    return queue.getFront() == null;
}

---

3. 队列的常用算法

3.1 循环队列（基于数组优化）

class CircularQueue {
    private int[] arr;
    private int front;
    private int rear;
    private int capacity;
    
    public CircularQueue(int size) {
        arr = new int[size];
        capacity = size;
        front = 0;
        rear = 0;
    }
    
    // 时间复杂度: O(1), 空间复杂度: O(1)
    public void enqueue(int val) {
        if ((rear + 1) % capacity == front) {
            throw new IllegalStateException("Queue is full");
        }
        arr[rear] = val;
        rear = (rear + 1) % capacity;
    }
    
    // 时间复杂度: O(1), 空间复杂度: O(1)
    public int dequeue() {
        if (front == rear) {
            throw new IllegalStateException("Queue is empty");
        }
        int val = arr[front];
        front = (front + 1) % capacity;
        return val;
    }
}

3.2 双端队列（Deque）

class Deque {
    private QueueNode front;
    private QueueNode rear;
    
    public Deque() {
        front = null;
        rear = null;
    }
    
    // 时间复杂度: O(1), 空间复杂度: O(1)
    public void addFront(int val) {
        QueueNode newNode = new QueueNode(val);
        if (front == null) {
            front = rear = newNode;
        } else {
            newNode.next = front;
            front = newNode;
        }
    }
    
    // 时间复杂度: O(1), 空间复杂度: O(1)
    public void addRear(int val) {
        QueueNode newNode = new QueueNode(val);
        if (rear == null) {
            front = rear = newNode;
        } else {
            rear.next = newNode;
            rear = newNode;
        }
    }
    
    // 时间复杂度: O(1), 空间复杂度: O(1)
    public int removeFront() {
        if (front == null) {
            throw new IllegalStateException("Deque is empty");
        }
        int val = front.val;
        front = front.next;
        if (front == null) rear = null;
        return val;
    }
    
    // 时间复杂度: O(1), 空间复杂度: O(1)
    public int removeRear() {
        if (rear == null) {
            throw new IllegalStateException("Deque is empty");
        }
        int val = rear.val;
        if (front == rear) {
            front = rear = null;
        } else {
            QueueNode current = front;
            while (current.next != rear) {
                current = current.next;
            }
            rear = current;
            rear.next = null;
        }
        return val;
    }
}

3.3 优先队列（最小堆实现）

class PriorityQueue {
    private int[] arr;
    private int size;
    private int capacity;
    
    public PriorityQueue(int capacity) {
        this.capacity = capacity;
        arr = new int[capacity];
        size = 0;
    }
    
    // 时间复杂度: O(log n), 空间复杂度: O(1)
    public void enqueue(int val) {
        if (size == capacity) {
            throw new IllegalStateException("Priority Queue is full");
        }
        arr[size] = val;
        heapifyUp(size);
        size++;
    }
    
    // 时间复杂度: O(log n), 空间复杂度: O(1)
    public int dequeue() {
        if (size == 0) {
            throw new IllegalStateException("Priority Queue is empty");
        }
        int val = arr[0];
        arr[0] = arr[--size];
        heapifyDown(0);
        return val;
    }
    
    private void heapifyUp(int index) {
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (arr[parent] > arr[index]) {
                swap(arr, parent, index);
                index = parent;
            } else {
                break;
            }
        }
    }
    
    private void heapifyDown(int index) {
        while (true) {
            int smallest = index;
            int left = 2 * index + 1;
            int right = 2 * index + 2;
            if (left < size && arr[left] < arr[smallest]) smallest = left;
            if (right < size && arr[right] < arr[smallest]) smallest = right;
            if (smallest == index) break;
            swap(arr, index, smallest);
            index = smallest;
        }
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

---

使用示例

public static void main(String[] args) {
    // 数组队列
    ArrayQueue arrayQueue = new ArrayQueue(5);
    enqueue(arrayQueue, 1);
    enqueue(arrayQueue, 2);
    System.out.println("Array Queue front: " + peek(arrayQueue));  // 输出: 1
    System.out.println("Dequeued: " + dequeue(arrayQueue));       // 输出: 1
    
    // 链表队列
    LinkedQueue linkedQueue = new LinkedQueue();
    enqueue(linkedQueue, 1);
    enqueue(linkedQueue, 2);
    System.out.println("Linked Queue front: " + peek(linkedQueue));  // 输出: 1
    
    // 循环队列
    CircularQueue circularQueue = new CircularQueue(3);
    circularQueue.enqueue(1);
    circularQueue.enqueue(2);
    System.out.println("Circular Queue dequeued: " + circularQueue.dequeue());  // 输出: 1
    
    // 双端队列
    Deque deque = new Deque();
    deque.addFront(1);
    deque.addRear(2);
    System.out.println("Deque front: " + deque.removeFront());  // 输出: 1
    System.out.println("Deque rear: " + deque.removeRear());    // 输出: 2
    
    // 优先队列
    PriorityQueue pq = new PriorityQueue(5);
    pq.enqueue(3);
    pq.enqueue(1);
    pq.enqueue(2);
    System.out.println("Priority Queue min: " + pq.dequeue());  // 输出: 1
}

树形结构

数据结构	特点	变种/类型	操作	场景
二叉树 (Binary Tree)	每个节点最多两个子节点	- 二叉搜索树 (BST)：左子树值 < 根 < 右子树值 - 平衡二叉树 (AVL树/红黑树)：自动平衡高度	查找/插入（BST平均O(log n)，平衡树O(log n)）	快速查找 排序
堆 (Heap)	完全二叉树，父节点与子节点有大小关系	- 最大堆：父节点≥子节点 - 最小堆：父节点≤子节点	插入：O(log n) 取最值：O(1)	优先队列 堆排序
多叉树	支持多个子节点的树结构	- B树/B+树：多路平衡树，减少磁盘I/O - 字典树 (Trie)：前缀树，存储字符串集合	依赖具体类型（如B树查找O(log n)，Trie前缀查询O(m)，m为字符串长度）	B树/B+树：数据库索引 Trie：自动补全

二叉树

普通二叉树

二叉树节点定义

所有算法基于以下二叉树节点类：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

1. 前序遍历 (Preorder Traversal)

• 功能描述：按照“根-左-右”的顺序递归遍历二叉树。
• 时间复杂度：O(n)，其中 n 是节点数
• Java 代码实现：

public void preorderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    System.out.print(root.val + " "); // 访问根节点
    preorderTraversal(root.left);     // 遍历左子树
    preorderTraversal(root.right);    // 遍历右子树
}

2. 中序遍历 (Inorder Traversal)

• 功能描述：按照“左-根-右”的顺序递归遍历二叉树，对于二叉搜索树（BST）会输出有序序列。
• 时间复杂度：O(n)
• Java 代码实现：

public void inorderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    inorderTraversal(root.left);      // 遍历左子树
    System.out.print(root.val + " "); // 访问根节点
    inorderTraversal(root.right);     // 遍历右子树
}

3. 后序遍历 (Postorder Traversal)

• 功能描述：按照“左-右-根”的顺序递归遍历二叉树，常用于释放节点内存。
• 时间复杂度：O(n)
• Java 代码实现：

public void postorderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    postorderTraversal(root.left);    // 遍历左子树
    postorderTraversal(root.right);   // 遍历右子树
    System.out.print(root.val + " "); // 访问根节点
}

4. 层序遍历 (Level Order Traversal)

• 功能描述：使用队列按层从上到下、从左到右遍历二叉树。
• 时间复杂度：O(n)
• Java 代码实现：

import java.util.LinkedList;
import java.util.Queue;

public void levelOrderTraversal(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

5. 计算二叉树深度 (Maximum Depth)

• 功能描述：递归计算二叉树的最大深度（根到最远叶节点的路径长度）。
• 时间复杂度：O(n)
• Java 代码实现：

public int maxDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftDepth = maxDepth(root.left);
    int rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
}

6. 判断是否平衡二叉树 (Check Balanced Binary Tree)

• 功能描述：检查二叉树是否平衡，即任意节点的左右子树高度差不超过 1。
• 时间复杂度：O(n)
• Java 代码实现：

public boolean isBalanced(TreeNode root) {
    return height(root) != -1;
}

private int height(TreeNode root) {
    if (root == null) {
        return 0;
    }
    int leftHeight = height(root.left);
    if (leftHeight == -1) return -1; // 左子树不平衡
    int rightHeight = height(root.right);
    if (rightHeight == -1) return -1; // 右子树不平衡
    if (Math.abs(leftHeight - rightHeight) > 1) {
        return -1; // 当前节点不平衡
    }
    return Math.max(leftHeight, rightHeight) + 1;
}

7. 二叉树路径总和 (Path Sum)

• 功能描述：判断是否存在从根到叶节点的路径，其节点值之和等于目标值。
• 时间复杂度：O(n)
• Java 代码实现：

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }
    if (root.left == null && root.right == null) { // 叶节点
        return targetSum == root.val;
    }
    return hasPathSum(root.left, targetSum - root.val) || 
           hasPathSum(root.right, targetSum - root.val);
}

8. 反转二叉树 (Invert Binary Tree)

• 功能描述：将二叉树的左右子树交换，递归反转整棵树。
• 时间复杂度：O(n)
• Java 代码实现：

public TreeNode invertTree(TreeNode root) {
    if (root == null) {
        return null;
    }
    TreeNode temp = root.left;
    root.left = root.right;
    root.right = temp;
    invertTree(root.left);
    invertTree(root.right);
    return root;
}

9. 二叉搜索树验证 (Validate Binary Search Tree)

• 功能描述：验证二叉树是否为二叉搜索树（BST），即左子树值 < 根 < 右子树值。
• 时间复杂度：O(n)
• Java 代码实现：

public boolean isValidBST(TreeNode root) {
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean isValidBST(TreeNode root, long min, long max) {
    if (root == null) {
        return true;
    }
    if (root.val <= min || root.val >= max) {
        return false;
    }
    return isValidBST(root.left, min, root.val) && 
           isValidBST(root.right, root.val, max);
}

10. 最低公共祖先 (Lowest Common Ancestor)

• 功能描述：在二叉树中找到两个节点的最低公共祖先（LCA）。
• 时间复杂度：O(n)
• Java 代码实现：

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) {
        return root;
    }
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
    if (left != null && right != null) {
        return root; // p 和 q 分居两侧，root 是 LCA
    }
    return left != null ? left : right; // p 和 q 在同一侧
}

11. 前序遍历（非递归）(Preorder Traversal - Iterative)

• 功能描述：使用栈模拟递归，按照“根-左-右”的顺序遍历二叉树。
• 时间复杂度：O(n)，空间复杂度 O(h)，h 为树高
• Java 代码实现：

import java.util.Stack;

public void preorderTraversalIterative(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " "); // 访问根节点
        if (node.right != null) {         // 先压右子树（后访问）
            stack.push(node.right);
        }
        if (node.left != null) {          // 后压左子树（先访问）
            stack.push(node.left);
        }
    }
}

12. 中序遍历（非递归）(Inorder Traversal - Iterative)

• 功能描述：使用栈模拟递归，按照“左-根-右”的顺序遍历二叉树，先将左子树压栈到底。
• 时间复杂度：O(n)，空间复杂度 O(h)
• Java 代码实现：

import java.util.Stack;

public void inorderTraversalIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
        // 压入所有左子节点
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        System.out.print(current.val + " "); // 访问根节点
        current = current.right;             // 处理右子树
    }
}

13. 后序遍历（非递归）(Postorder Traversal - Iterative)

• 功能描述：使用栈模拟递归，按照“左-右-根”的顺序遍历二叉树，需记录上一次访问的节点以区分回溯路径。
• 时间复杂度：O(n)，空间复杂度 O(h)
• Java 代码实现：

import java.util.Stack;

public void postorderTraversalIterative(TreeNode root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode current = root;
    TreeNode lastVisited = null;
    while (current != null || !stack.isEmpty()) {
        // 压入所有左子节点
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        TreeNode peekNode = stack.peek();
        // 如果没有右子树或右子树已访问，访问当前节点
        if (peekNode.right == null || peekNode.right == lastVisited) {
            System.out.print(peekNode.val + " ");
            lastVisited = stack.pop();
        } else {
            current = peekNode.right; // 处理右子树
        }
    }
}

14. 层序遍历（非递归）(Level Order Traversal - Iterative)

• 功能描述：使用队列按层从上到下、从左到右遍历二叉树（已在之前提供，这里重复列出以保持完整性）。
• 时间复杂度：O(n)，空间复杂度 O(w)，w 为树的最大宽度
• Java 代码实现：

import java.util.LinkedList;
import java.util.Queue;

public void levelOrderTraversalIterative(TreeNode root) {
    if (root == null) {
        return;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

二叉搜索树 (Binary Search Tree, BST)

• 定义: 左子树所有节点值 < 根节点值 < 右子树所有节点值。
• 特性: 支持高效的查找、插入和删除，但可能退化为链表。
• 应用场景:
  • 数据库索引
  • 动态集合管理
  • 符号表

结构图

graph TD
    A[10] --> B[5]
    A --> C[15]
    B --> D[3]
    B --> E[7]
    C --> F[13]

---

1. 二叉搜索树节点定义

class BSTNode {
    int val;
    BSTNode left;
    BSTNode right;
    
    public BSTNode(int val) {
        this.val = val;
    }
}

2. 二叉搜索树基本类

class BinarySearchTree {
    private BSTNode root;
    
    public BinarySearchTree() {
        root = null;
    }
    
    public BSTNode getRoot() { return root; }
    public void setRoot(BSTNode root) { this.root = root; }
}

---

3. 二叉搜索树常用算法

3.1 插入节点

// 时间复杂度: O(h) 其中 h 是树高，平均 O(log n)，最坏 O(n)
// 空间复杂度: O(h) 递归调用栈
public void insert(BinarySearchTree bst, int val) {
    bst.setRoot(insertRec(bst.getRoot(), val));
}

private BSTNode insertRec(BSTNode root, int val) {
    if (root == null) {
        return new BSTNode(val);
    }
    if (val < root.val) {
        root.left = insertRec(root.left, val);
    } else if (val > root.val) {
        root.right = insertRec(root.right, val);
    }
    return root;
}

3.2 删除节点

// 时间复杂度: O(h) 其中 h 是树高，平均 O(log n)，最坏 O(n)
// 空间复杂度: O(h) 递归调用栈
public void delete(BinarySearchTree bst, int val) {
    bst.setRoot(deleteRec(bst.getRoot(), val));
}

private BSTNode deleteRec(BSTNode root, int val) {
    if (root == null) return null;
    
    if (val < root.val) {
        root.left = deleteRec(root.left, val);
    } else if (val > root.val) {
        root.right = deleteRec(root.right, val);
    } else {
        // 节点找到，处理删除
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        
        // 有两个子节点，找到右子树最小值替换
        root.val = findMin(root.right).val;
        root.right = deleteRec(root.right, root.val);
    }
    return root;
}

private BSTNode findMin(BSTNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

3.3 查找节点

// 时间复杂度: O(h) 其中 h 是树高，平均 O(log n)，最坏 O(n)
// 空间复杂度: O(h) 递归调用栈
public boolean search(BinarySearchTree bst, int val) {
    return searchRec(bst.getRoot(), val);
}

private boolean searchRec(BSTNode root, int val) {
    if (root == null || root.val == val) {
        return root != null;
    }
    if (val < root.val) {
        return searchRec(root.left, val);
    }
    return searchRec(root.right, val);
}

3.4 前序遍历（Preorder Traversal）

// 时间复杂度: O(n) 其中 n 是节点数
// 空间复杂度: O(h) 递归调用栈
public void preorder(BinarySearchTree bst) {
    preorderRec(bst.getRoot());
    System.out.println();
}

private void preorderRec(BSTNode root) {
    if (root != null) {
        System.out.print(root.val + " ");
        preorderRec(root.left);
        preorderRec(root.right);
    }
}

3.5 中序遍历（Inorder Traversal）

// 时间复杂度: O(n) 其中 n 是节点数
// 空间复杂度: O(h) 递归调用栈
public void inorder(BinarySearchTree bst) {
    inorderRec(bst.getRoot());
    System.out.println();
}

private void inorderRec(BSTNode root) {
    if (root != null) {
        inorderRec(root.left);
        System.out.print(root.val + " ");
        inorderRec(root.right);
    }
}

3.6 后序遍历（Postorder Traversal）

// 时间复杂度: O(n) 其中 n 是节点数
// 空间复杂度: O(h) 递归调用栈
public void postorder(BinarySearchTree bst) {
    postorderRec(bst.getRoot());
    System.out.println();
}

private void postorderRec(BSTNode root) {
    if (root != null) {
        postorderRec(root.left);
        postorderRec(root.right);
        System.out.print(root.val + " ");
    }
}

3.7 查找最小值

// 时间复杂度: O(h) 其中 h 是树高，平均 O(log n)，最坏 O(n)
// 空间复杂度: O(1)
public int findMin(BinarySearchTree bst) {
    if (bst.getRoot() == null) {
        throw new IllegalStateException("Tree is empty");
    }
    BSTNode current = bst.getRoot();
    while (current.left != null) {
        current = current.left;
    }
    return current.val;
}

3.8 查找最大值

// 时间复杂度: O(h) 其中 h 是树高，平均 O(log n)，最坏 O(n)
// 空间复杂度: O(1)
public int findMax(BinarySearchTree bst) {
    if (bst.getRoot() == null) {
        throw new IllegalStateException("Tree is empty");
    }
    BSTNode current = bst.getRoot();
    while (current.right != null) {
        current = current.right;
    }
    return current.val;
}

3.9 计算树的高度

// 时间复杂度: O(n) 其中 n 是节点数
// 空间复杂度: O(h) 递归调用栈
public int height(BinarySearchTree bst) {
    return heightRec(bst.getRoot());
}

private int heightRec(BSTNode root) {
    if (root == null) return -1;
    int leftHeight = heightRec(root.left);
    int rightHeight = heightRec(root.right);
    return Math.max(leftHeight, rightHeight) + 1;
}

3.10 验证是否是有效的BST

// 时间复杂度: O(n) 其中 n 是节点数
// 空间复杂度: O(h) 递归调用栈
public boolean isValidBST(BinarySearchTree bst) {
    return isValidBSTRec(bst.getRoot(), Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean isValidBSTRec(BSTNode root, long min, long max) {
    if (root == null) return true;
    if (root.val <= min || root.val >= max) return false;
    return isValidBSTRec(root.left, min, root.val) && 
           isValidBSTRec(root.right, root.val, max);
}

---

使用示例

public static void main(String[] args) {
    BinarySearchTree bst = new BinarySearchTree();
    
    // 插入节点
    insert(bst, 5);
    insert(bst, 3);
    insert(bst, 7);
    insert(bst, 1);
    insert(bst, 9);
    
    // 遍历
    System.out.println("Inorder:");
    inorder(bst);    // 输出: 1 3 5 7 9
    
    System.out.println("Preorder:");
    preorder(bst);   // 输出: 5 3 1 7 9
    
    System.out.println("Postorder:");
    postorder(bst);  // 输出: 1 3 9 7 5
    
    // 查找
    System.out.println("Search 3: " + search(bst, 3));  // 输出: true
    System.out.println("Search 4: " + search(bst, 4));  // 输出: false
    
    // 最小值和最大值
    System.out.println("Min: " + findMin(bst));  // 输出: 1
    System.out.println("Max: " + findMax(bst));  // 输出: 9
    
    // 删除
    delete(bst, 3);
    System.out.println("After deleting 3, Inorder:");
    inorder(bst);    // 输出: 1 5 7 9
    
    // 高度
    System.out.println("Height: " + height(bst));  // 输出: 2
    
    // 验证BST
    System.out.println("Is valid BST: " + isValidBST(bst));  // 输出: true
}

---

说明

• 时间复杂度：大多数操作依赖树高 h，在平衡 BST 中 h ≈ log n，在退化为链表时 h = n。
• 插入、删除、查找：核心操作，利用 BST 的性质快速定位。
• 遍历：前序、中序、后序是基本的树遍历方式，中序遍历 BST 会得到有序序列。
• 最小值和最大值：利用 BST 左子树最小、右子树最大的特性。
• 高度和验证：辅助功能，用于分析树结构和正确性。

---

平衡二叉树

AVL树 (自平衡二叉搜索树)

AVL 树通过在插入和删除时保持平衡因子（左右子树高度差不超过 1）来确保树的高度始终接近 log n，从而保证操作的高效性。

• 定义: BST的改进，任何节点的左右子树高度差不超过1。
• 特性: 通过旋转保持平衡，保证O(log n)操作。
• 应用场景:
  • 需要频繁查找的实时系统
  • 内存管理中的动态分配

---

AVL 树节点定义

class AVLNode {
    int val;
    AVLNode left;
    AVLNode right;
    int height;  // 节点高度，用于平衡计算
    
    public AVLNode(int val) {
        this.val = val;
        this.height = 0;
    }
}

AVL 树基本类

class AVLTree {
    private AVLNode root;
    
    public AVLTree() {
        root = null;
    }
    
    public AVLNode getRoot() { return root; }
    public void setRoot(AVLNode root) { this.root = root; }
}

---

获取节点高度

// 时间复杂度: O(1), 空间复杂度: O(1)
public int getHeight(AVLNode node) {
    return node == null ? -1 : node.height;
}

获取平衡因子

// 时间复杂度: O(1), 空间复杂度: O(1)
public int getBalanceFactor(AVLNode node) {
    return node == null ? 0 : getHeight(node.left) - getHeight(node.right);
}

更新节点高度

// 时间复杂度: O(1), 空间复杂度: O(1)
public void updateHeight(AVLNode node) {
    node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
}

右旋转（Right Rotation）

// 时间复杂度: O(1), 空间复杂度: O(1)
public AVLNode rightRotate(AVLNode y) {
    AVLNode x = y.left;
    AVLNode T2 = x.right;
    
    x.right = y;
    y.left = T2;
    
    updateHeight(y);
    updateHeight(x);
    
    return x;
}

左旋转（Left Rotation）

// 时间复杂度: O(1), 空间复杂度: O(1)
public AVLNode leftRotate(AVLNode x) {
    AVLNode y = x.right;
    AVLNode T2 = y.left;
    
    y.left = x;
    x.right = T2;
    
    updateHeight(x);
    updateHeight(y);
    
    return y;
}

插入节点

// 时间复杂度: O(log n), 空间复杂度: O(log n) 递归调用栈
public void insert(AVLTree tree, int val) {
    tree.setRoot(insertRec(tree.getRoot(), val));
}

private AVLNode insertRec(AVLNode root, int val) {
    if (root == null) {
        return new AVLNode(val);
    }
    
    if (val < root.val) {
        root.left = insertRec(root.left, val);
    } else if (val > root.val) {
        root.right = insertRec(root.right, val);
    } else {
        return root;  // 不允许重复值
    }
    
    updateHeight(root);
    int balance = getBalanceFactor(root);
    
    // 左左情况
    if (balance > 1 && val < root.left.val) {
        return rightRotate(root);
    }
    // 右右情况
    if (balance < -1 && val > root.right.val) {
        return leftRotate(root);
    }
    // 左右情况
    if (balance > 1 && val > root.left.val) {
        root.left = leftRotate(root.left);
        return rightRotate(root);
    }
    // 右左情况
    if (balance < -1 && val < root.right.val) {
        root.right = rightRotate(root.right);
        return leftRotate(root);
    }
    
    return root;
}

删除节点

// 时间复杂度: O(log n), 空间复杂度: O(log n) 递归调用栈
public void delete(AVLTree tree, int val) {
    tree.setRoot(deleteRec(tree.getRoot(), val));
}

private AVLNode deleteRec(AVLNode root, int val) {
    if (root == null) return null;
    
    if (val < root.val) {
        root.left = deleteRec(root.left, val);
    } else if (val > root.val) {
        root.right = deleteRec(root.right, val);
    } else {
        // 找到要删除的节点
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        
        AVLNode minNode = findMin(root.right);
        root.val = minNode.val;
        root.right = deleteRec(root.right, minNode.val);
    }
    
    if (root == null) return null;
    
    updateHeight(root);
    int balance = getBalanceFactor(root);
    
    // 左左情况
    if (balance > 1 && getBalanceFactor(root.left) >= 0) {
        return rightRotate(root);
    }
    // 左右情况
    if (balance > 1 && getBalanceFactor(root.left) < 0) {
        root.left = leftRotate(root.left);
        return rightRotate(root);
    }
    // 右右情况
    if (balance < -1 && getBalanceFactor(root.right) <= 0) {
        return leftRotate(root);
    }
    // 右左情况
    if (balance < -1 && getBalanceFactor(root.right) > 0) {
        root.right = rightRotate(root.right);
        return leftRotate(root);
    }
    
    return root;
}

private AVLNode findMin(AVLNode node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

查找节点

// 时间复杂度: O(log n), 空间复杂度: O(log n) 递归调用栈
public boolean search(AVLTree tree, int val) {
    return searchRec(tree.getRoot(), val);
}

private boolean searchRec(AVLNode root, int val) {
    if (root == null || root.val == val) {
        return root != null;
    }
    if (val < root.val) {
        return searchRec(root.left, val);
    }
    return searchRec(root.right, val);
}

中序遍历（Inorder Traversal）

// 时间复杂度: O(n), 空间复杂度: O(log n) 递归调用栈
public void inorder(AVLTree tree) {
    inorderRec(tree.getRoot());
    System.out.println();
}

private void inorderRec(AVLNode root) {
    if (root != null) {
        inorderRec(root.left);
        System.out.print(root.val + " ");
        inorderRec(root.right);
    }
}

验证 AVL 树性质

// 时间复杂度: O(n), 空间复杂度: O(log n) 递归调用栈
public boolean isAVLTree(AVLTree tree) {
    return isAVLRec(tree.getRoot());
}

private boolean isAVLRec(AVLNode root) {
    if (root == null) return true;
    
    int balance = getBalanceFactor(root);
    if (balance < -1 || balance > 1) return false;
    
    return isAVLRec(root.left) && isAVLRec(root.right);
}

---

使用示例

public static void main(String[] args) {
    AVLTree tree = new AVLTree();
    
    // 插入节点
    insert(tree, 10);
    insert(tree, 20);
    insert(tree, 30);
    insert(tree, 40);
    insert(tree, 50);
    insert(tree, 25);
    
    System.out.println("Inorder traversal:");
    inorder(tree);  // 输出: 10 20 25 30 40 50
    
    // 删除节点
    delete(tree, 30);
    System.out.println("After deleting 30:");
    inorder(tree);  // 输出: 10 20 25 40 50
    
    // 查找
    System.out.println("Search 20: " + search(tree, 20));  // 输出: true
    System.out.println("Search 30: " + search(tree, 30));  // 输出: false
    
    // 验证 AVL 性质
    System.out.println("Is AVL Tree: " + isAVLTree(tree));  // 输出: true
}

---

说明

• 平衡因子：AVL 树通过平衡因子（左子树高度 - 右子树高度）保持平衡，范围在 [-1, 1]。
• 旋转操作：
  • 右旋转：处理左子树过高的情况（左左或左右）。
  • 左旋转：处理右子树过高的情况（右右或右左）。
• 时间复杂度：
  • 插入、删除、查找为 O(log n)，因为 AVL 树始终保持平衡。
  • 遍历和验证为 O(n)，需要访问所有节点。
• 空间复杂度：
  • 递归操作依赖树高 h，由于 AVL 树平衡，h ≈ log n。
• 特点：
  • 相比普通 BST，AVL 树通过旋转操作保证了高效性，但增加了维护成本。

---

红黑树 (Red-Black Tree)

红黑树是一种自平衡二叉搜索树，通过颜色（红/黑）和五条性质保持平衡，确保操作时间复杂度为 O(log n)。

• 定义: 自平衡BST，具有颜色属性（红/黑），遵循特定规则：
  1. 节点是红色或黑色
  2. 根节点是黑色
  3. 红色节点的子节点必须是黑色
  4. 从根到叶的每条路径黑色节点数相同
• 红黑树性质：
  1. 每个节点是红色或黑色。
  2. 根节点是黑色。
  3. 所有叶子（NIL）是黑色。
  4. 红色节点的子节点必须是黑色（不能有连续红色节点）。
  5. 从根到任一叶子的路径上黑色节点数量相同。
• 特性: 保证O(log n)操作，广泛用于系统实现。
• 应用场景:
  • Java的TreeMap/TreeSet
  • Linux内核调度
  • 数据库B+树基础

---

红黑树节点定义

class RBNode {
    int val;
    RBNode left;
    RBNode right;
    RBNode parent;
    boolean isRed;  // true 表示红色，false 表示黑色
    
    public RBNode(int val) {
        this.val = val;
        this.isRed = true;  // 新节点默认为红色
    }
}

红黑树基本类

class RedBlackTree {
    private RBNode root;
    private static final RBNode NIL = new RBNode(0);  // 哨兵节点，代表空节点
    
    public RedBlackTree() {
        NIL.isRed = false;  // NIL 节点始终为黑色
        NIL.left = NIL.right = NIL.parent = NIL;
        root = NIL;
    }
    
    public RBNode getRoot() { return root; }
    public void setRoot(RBNode root) { this.root = root; }
}

---

左旋转（Left Rotation）

// 时间复杂度: O(1), 空间复杂度: O(1)
public void leftRotate(RedBlackTree tree, RBNode x) {
    RBNode y = x.right;
    x.right = y.left;
    if (y.left != RedBlackTree.NIL) {
        y.left.parent = x;
    }
    y.parent = x.parent;
    if (x.parent == RedBlackTree.NIL) {
        tree.setRoot(y);
    } else if (x == x.parent.left) {
        x.parent.left = y;
    } else {
        x.parent.right = y;
    }
    y.left = x;
    x.parent = y;
}

右旋转（Right Rotation）

// 时间复杂度: O(1), 空间复杂度: O(1)
public void rightRotate(RedBlackTree tree, RBNode y) {
    RBNode x = y.left;
    y.left = x.right;
    if (x.right != RedBlackTree.NIL) {
        x.right.parent = y;
    }
    x.parent = y.parent;
    if (y.parent == RedBlackTree.NIL) {
        tree.setRoot(x);
    } else if (y == y.parent.left) {
        y.parent.left = x;
    } else {
        y.parent.right = x;
    }
    x.right = y;
    y.parent = x;
}

插入节点

// 时间复杂度: O(log n), 空间复杂度: O(1)
public void insert(RedBlackTree tree, int val) {
    RBNode node = new RBNode(val);
    node.left = node.right = node.parent = RedBlackTree.NIL;
    
    RBNode y = RedBlackTree.NIL;
    RBNode x = tree.getRoot();
    
    // BST 插入
    while (x != RedBlackTree.NIL) {
        y = x;
        if (node.val < x.val) {
            x = x.left;
        } else {
            x = x.right;
        }
    }
    node.parent = y;
    if (y == RedBlackTree.NIL) {
        tree.setRoot(node);
    } else if (node.val < y.val) {
        y.left = node;
    } else {
        y.right = node;
    }
    
    // 修复红黑树性质
    insertFixup(tree, node);
}

private void insertFixup(RedBlackTree tree, RBNode z) {
    while (z.parent.isRed) {
        if (z.parent == z.parent.parent.left) {
            RBNode y = z.parent.parent.right;  // 叔叔节点
            if (y.isRed) {  // 情况 1：叔叔是红色
                z.parent.isRed = false;
                y.isRed = false;
                z.parent.parent.isRed = true;
                z = z.parent.parent;
            } else {
                if (z == z.parent.right) {  // 情况 2：叔叔是黑色，z 是右孩子
                    z = z.parent;
                    leftRotate(tree, z);
                }
                // 情况 3：叔叔是黑色，z 是左孩子
                z.parent.isRed = false;
                z.parent.parent.isRed = true;
                rightRotate(tree, z.parent.parent);
            }
        } else {  // 对称情况
            RBNode y = z.parent.parent.left;
            if (y.isRed) {
                z.parent.isRed = false;
                y.isRed = false;
                z.parent.parent.isRed = true;
                z = z.parent.parent;
            } else {
                if (z == z.parent.left) {
                    z = z.parent;
                    rightRotate(tree, z);
                }
                z.parent.isRed = false;
                z.parent.parent.isRed = true;
                leftRotate(tree, z.parent.parent);
            }
        }
    }
    tree.getRoot().isRed = false;  // 根节点始终为黑色
}

删除节点

// 时间复杂度: O(log n), 空间复杂度: O(1)
public void delete(RedBlackTree tree, int val) {
    RBNode z = searchNode(tree.getRoot(), val);
    if (z == RedBlackTree.NIL) return;
    
    RBNode y = z;
    RBNode x;
    boolean yOriginalColor = y.isRed;
    
    if (z.left == RedBlackTree.NIL) {
        x = z.right;
        transplant(tree, z, z.right);
    } else if (z.right == RedBlackTree.NIL) {
        x = z.left;
        transplant(tree, z, z.left);
    } else {
        y = findMin(z.right);
        yOriginalColor = y.isRed;
        x = y.right;
        if (y.parent == z) {
            x.parent = y;
        } else {
            transplant(tree, y, y.right);
            y.right = z.right;
            y.right.parent = y;
        }
        transplant(tree, z, y);
        y.left = z.left;
        y.left.parent = y;
        y.isRed = z.isRed;
    }
    
    if (!yOriginalColor) {
        deleteFixup(tree, x);
    }
}

private void transplant(RedBlackTree tree, RBNode u, RBNode v) {
    if (u.parent == RedBlackTree.NIL) {
        tree.setRoot(v);
    } else if (u == u.parent.left) {
        u.parent.left = v;
    } else {
        u.parent.right = v;
    }
    v.parent = u.parent;
}

private void deleteFixup(RedBlackTree tree, RBNode x) {
    while (x != tree.getRoot() && !x.isRed) {
        if (x == x.parent.left) {
            RBNode w = x.parent.right;  // 兄弟节点
            if (w.isRed) {  // 情况 1
                w.isRed = false;
                x.parent.isRed = true;
                leftRotate(tree, x.parent);
                w = x.parent.right;
            }
            if (!w.left.isRed && !w.right.isRed) {  // 情况 2
                w.isRed = true;
                x = x.parent;
            } else {
                if (!w.right.isRed) {  // 情况 3
                    w.left.isRed = false;
                    w.isRed = true;
                    rightRotate(tree, w);
                    w = x.parent.right;
                }
                // 情况 4
                w.isRed = x.parent.isRed;
                x.parent.isRed = false;
                w.right.isRed = false;
                leftRotate(tree, x.parent);
                x = tree.getRoot();
            }
        } else {  // 对称情况
            RBNode w = x.parent.left;
            if (w.isRed) {
                w.isRed = false;
                x.parent.isRed = true;
                rightRotate(tree, x.parent);
                w = x.parent.left;
            }
            if (!w.right.isRed && !w.left.isRed) {
                w.isRed = true;
                x = x.parent;
            } else {
                if (!w.left.isRed) {
                    w.right.isRed = false;
                    w.isRed = true;
                    leftRotate(tree, w);
                    w = x.parent.left;
                }
                w.isRed = x.parent.isRed;
                x.parent.isRed = false;
                w.left.isRed = false;
                rightRotate(tree, x.parent);
                x = tree.getRoot();
            }
        }
    }
    x.isRed = false;
}

查找节点

// 时间复杂度: O(log n), 空间复杂度: O(1)
public boolean search(RedBlackTree tree, int val) {
    return searchNode(tree.getRoot(), val) != RedBlackTree.NIL;
}

private RBNode searchNode(RBNode root, int val) {
    RBNode current = root;
    while (current != RedBlackTree.NIL && current.val != val) {
        if (val < current.val) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
    return current;
}

中序遍历（Inorder Traversal）

// 时间复杂度: O(n), 空间复杂度: O(log n) 递归调用栈
public void inorder(RedBlackTree tree) {
    inorderRec(tree.getRoot());
    System.out.println();
}

private void inorderRec(RBNode root) {
    if (root != RedBlackTree.NIL) {
        inorderRec(root.left);
        System.out.print(root.val + " ");
        inorderRec(root.right);
    }
}

查找最小值

// 时间复杂度: O(log n), 空间复杂度: O(1)
public int findMin(RedBlackTree tree) {
    RBNode minNode = findMin(tree.getRoot());
    if (minNode == RedBlackTree.NIL) {
        throw new IllegalStateException("Tree is empty");
    }
    return minNode.val;
}

private RBNode findMin(RBNode node) {
    while (node.left != RedBlackTree.NIL) {
        node = node.left;
    }
    return node;
}

---

使用示例

public static void main(String[] args) {
    RedBlackTree tree = new RedBlackTree();
    
    // 插入节点
    insert(tree, 10);
    insert(tree, 20);
    insert(tree, 30);
    insert(tree, 15);
    insert(tree, 5);
    
    System.out.println("Inorder traversal:");
    inorder(tree);  // 输出: 5 10 15 20 30
    
    // 删除节点
    delete(tree, 20);
    System.out.println("After deleting 20:");
    inorder(tree);  // 输出: 5 10 15 30
    
    // 查找
    System.out.println("Search 15: " + search(tree, 15));  // 输出: true
    System.out.println("Search 20: " + search(tree, 20));  // 输出: false
    
    // 最小值
    System.out.println("Min value: " + findMin(tree));  // 输出: 5
}

---

说明

• 旋转操作：
  • 左旋转和右旋转用于调整树结构，保持平衡。
• 插入和删除：
  • 插入后通过调整颜色和旋转修复红黑性质。
  • 删除后通过四种情况修复，确保黑色高度一致。
• 时间复杂度：
  • 插入、删除、查找为 O(log n)，因为红黑树高度始终保持在 2log(n+1) 以内。
  • 遍历为 O(n)。
• 空间复杂度：
  • 大多数操作只需常数额外空间，递归调用栈为 O(log n)。

---

完全二叉树

完全二叉树是一种特殊的二叉树，所有层（除可能的最底层）都被填满，最底层的节点尽量靠左排列。完全二叉树常用于实现堆。

---

1. 完全二叉树节点定义

class CBTNode {
    int val;
    CBTNode left;
    CBTNode right;
    
    public CBTNode(int val) {
        this.val = val;
    }
}

2. 完全二叉树基本类（基于数组实现）

由于完全二叉树可以用数组高效存储（无需显式指针），以下实现主要基于数组形式，适用于堆等场景。如果需要基于链表的实现，可以另行说明。

class CompleteBinaryTree {
    private int[] arr;    // 数组存储完全二叉树
    private int size;     // 当前节点数
    private int capacity; // 最大容量
    
    public CompleteBinaryTree(int capacity) {
        this.capacity = capacity;
        arr = new int[capacity];
        size = 0;
    }
    
    public int[] getArr() { return arr; }
    public int getSize() { return size; }
    public void setSize(int size) { this.size = size; }
}

---

3. 完全二叉树常用算法

3.1 插入节点（尾部插入）

// 时间复杂度: O(1), 空间复杂度: O(1)
// 在完全二叉树末尾插入节点（不调整堆序性）
public void insert(CompleteBinaryTree tree, int val) {
    if (tree.getSize() >= tree.capacity) {
        throw new IllegalStateException("Tree is full");
    }
    tree.getArr()[tree.getSize()] = val;
    tree.setSize(tree.getSize() + 1);
}

3.2 删除最后一个节点

// 时间复杂度: O(1), 空间复杂度: O(1)
public int removeLast(CompleteBinaryTree tree) {
    if (tree.getSize() == 0) {
        throw new IllegalStateException("Tree is empty");
    }
    int val = tree.getArr()[tree.getSize() - 1];
    tree.setSize(tree.getSize() - 1);
    return val;
}

3.3 获取父节点索引

// 时间复杂度: O(1), 空间复杂度: O(1)
public int getParentIndex(int index) {
    if (index <= 0) return -1;  // 根节点无父节点
    return (index - 1) / 2;
}

3.4 获取左子节点索引

// 时间复杂度: O(1), 空间复杂度: O(1)
public int getLeftChildIndex(int index, CompleteBinaryTree tree) {
    int left = 2 * index + 1;
    return left < tree.getSize() ? left : -1;
}

3.5 获取右子节点索引

// 时间复杂度: O(1), 空间复杂度: O(1)
public int getRightChildIndex(int index, CompleteBinaryTree tree) {
    int right = 2 * index + 2;
    return right < tree.getSize() ? right : -1;
}

3.6 检查是否为完全二叉树（基于链表实现）

// 时间复杂度: O(n), 空间复杂度: O(w), w 是树的最大宽度（队列空间）
// 使用层序遍历检查是否满足完全二叉树性质
public boolean isCompleteBinaryTree(CBTNode root) {
    if (root == null) return true;
    
    Queue<CBTNode> queue = new LinkedList<>();
    queue.offer(root);
    boolean mustBeLeaf = false;  // 标记后续节点必须是叶子
    
    while (!queue.isEmpty()) {
        CBTNode node = queue.poll();
        
        // 如果之前遇到过空节点，后续节点必须是叶子
        if (mustBeLeaf && (node.left != null || node.right != null)) {
            return false;
        }
        
        // 检查左子节点
        if (node.left != null) {
            queue.offer(node.left);
        } else if (node.right != null) {  // 有右无左，不是完全二叉树
            return false;
        }
        
        // 检查右子节点
        if (node.right != null) {
            queue.offer(node.right);
        } else {
            mustBeLeaf = true;  // 后续节点必须没有子节点
        }
    }
    return true;
}

3.7 计算树的高度

// 时间复杂度: O(1), 空间复杂度: O(1)
// 对于完全二叉树，高度可以通过节点数直接计算
public int getHeight(CompleteBinaryTree tree) {
    if (tree.getSize() == 0) return -1;
    return (int) Math.floor(Math.log(tree.getSize()) / Math.log(2));
}

3.8 层序遍历（Level Order Traversal）

// 时间复杂度: O(n), 空间复杂度: O(w), w 是树的最大宽度
public void levelOrder(CompleteBinaryTree tree) {
    for (int i = 0; i < tree.getSize(); i++) {
        System.out.print(tree.getArr()[i] + " ");
    }
    System.out.println();
}

3.9 堆化（Heapify）- 最小堆调整

// 时间复杂度: O(log n), 空间复杂度: O(1)
// 从指定节点向下调整为最小堆
public void minHeapify(CompleteBinaryTree tree, int index) {
    int smallest = index;
    int left = getLeftChildIndex(index, tree);
    int right = getRightChildIndex(index, tree);
    
    if (left != -1 && tree.getArr()[left] < tree.getArr()[smallest]) {
        smallest = left;
    }
    if (right != -1 && tree.getArr()[right] < tree.getArr()[smallest]) {
        smallest = right;
    }
    
    if (smallest != index) {
        swap(tree.getArr(), index, smallest);
        minHeapify(tree, smallest);
    }
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

3.10 构建最小堆

// 时间复杂度: O(n), 空间复杂度: O(1)
// 将整个数组调整为最小堆
public void buildMinHeap(CompleteBinaryTree tree) {
    for (int i = tree.getSize() / 2 - 1; i >= 0; i--) {
        minHeapify(tree, i);
    }
}

3.11 最大堆化（Max Heapify）

// 时间复杂度: O(log n), 空间复杂度: O(1)
// 从指定节点向下调整为最大堆
public void maxHeapify(CompleteBinaryTree tree, int index) {
    int largest = index;
    int left = getLeftChildIndex(index, tree);
    int right = getRightChildIndex(index, tree);
    
    if (left != -1 && tree.getArr()[left] > tree.getArr()[largest]) {
        largest = left;
    }
    if (right != -1 && tree.getArr()[right] > tree.getArr()[largest]) {
        largest = right;
    }
    
    if (largest != index) {
        swap(tree.getArr(), index, largest);
        maxHeapify(tree, largest);  // 递归调整子树
    }
}

private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

3.12 构建最大堆

// 时间复杂度: O(n), 空间复杂度: O(1)
// 将整个数组调整为最大堆
public void buildMaxHeap(CompleteBinaryTree tree) {
    for (int i = tree.getSize() / 2 - 1; i >= 0; i--) {
        maxHeapify(tree, i);
    }
}

3.13 插入并调整为最大堆

// 时间复杂度: O(log n), 空间复杂度: O(1)
// 插入新元素并上浮调整为最大堆
public void insertMaxHeap(CompleteBinaryTree tree, int val) {
    if (tree.getSize() >= tree.capacity) {
        throw new IllegalStateException("Tree is full");
    }
    tree.getArr()[tree.getSize()] = val;
    tree.setSize(tree.getSize() + 1);
    siftUpMax(tree, tree.getSize() - 1);
}

private void siftUpMax(CompleteBinaryTree tree, int index) {
    while (index > 0) {
        int parent = getParentIndex(index);
        if (tree.getArr()[parent] < tree.getArr()[index]) {
            swap(tree.getArr(), parent, index);
            index = parent;
        } else {
            break;
        }
    }
}

3.14 删除最大值（根节点）

// 时间复杂度: O(log n), 空间复杂度: O(1)
// 删除并返回最大值，然后调整为最大堆
public int extractMax(CompleteBinaryTree tree) {
    if (tree.getSize() == 0) {
        throw new IllegalStateException("Tree is empty");
    }
    int max = tree.getArr()[0];
    tree.getArr()[0] = tree.getArr()[tree.getSize() - 1];
    tree.setSize(tree.getSize() - 1);
    if (tree.getSize() > 0) {
        maxHeapify(tree, 0);
    }
    return max;
}

---

使用示例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 基于数组的完全二叉树
        CompleteBinaryTree tree = new CompleteBinaryTree(10);
        
        // 插入节点
        insert(tree, 5);
        insert(tree, 3);
        insert(tree, 7);
        insert(tree, 1);
        insert(tree, 9);
        
        System.out.println("Level order before heapify:");
        levelOrder(tree);  // 输出: 5 3 7 1 9
        
        // 构建最小堆
        buildMinHeap(tree);
        System.out.println("Level order after min heapify:");
        levelOrder(tree);  // 输出: 1 3 7 5 9
        
        // 获取高度
        System.out.println("Height: " + getHeight(tree));  // 输出: 2
        
        // 删除最后一个节点
        removeLast(tree);
        System.out.println("After removing last node:");
        levelOrder(tree);  // 输出: 1 3 7 5
        
        // 基于链表的完全二叉树检查
        CBTNode root = new CBTNode(1);
        root.left = new CBTNode(2);
        root.right = new CBTNode(3);
        root.left.left = new CBTNode(4);
        System.out.println("Is complete binary tree: " + isCompleteBinaryTree(root));  // 输出: true
    }
}

---

说明

• 实现方式：
  • 主要基于数组实现，因为完全二叉树可以用数组连续存储，适合堆等应用。
  • 提供了基于链表的 isCompleteBinaryTree 检查算法，展示树结构的验证。
• 时间复杂度：
  • 插入和删除最后一个节点为 O(1)，因为只操作数组末尾。
  • 堆化操作（如 minHeapify）为 O(log n)，构建堆为 O(n)。
  • 遍历和检查为 O(n)。
• 空间复杂度：
  • 数组实现大多为 O(1) 额外空间。
  • 层序遍历和检查使用队列，空间为 O(w)，w 是树的最大宽度。
• 与堆的关系：
  • 完全二叉树常用于实现堆（如最小堆、最大堆），因此包含了堆化相关算法。
  • 如果不考虑堆序性，完全二叉树仅关注结构完整性。
• 扩展：
  • 如果需要最大堆调整、前序/中序遍历等其他算法，可以告诉我，我会补充。

完全二叉树的算法相对简单，主要优势在于其结构特性便于数组存储和高效操作，尤其在堆的实现中应用广泛。

多叉树

多路平衡树

B树

B 树是一种自平衡的多路搜索树，广泛用于数据库和文件系统，能够高效处理大量数据。B 树的每个节点可以有多个键和子节点，保持树的平衡以确保操作时间为 O(log n)。

B 树性质：

1. 每个节点最多有 2t-1 个键，最多 2t 个子节点。
2. 每个非根节点至少有 t-1 个键，至少 t 个子节点。
3. 根节点至少有 1 个键（除非树为空）。
4. 所有叶子节点在同一层。

---

B 树节点定义

class BTreeNode {
    int[] keys;           // 键数组
    BTreeNode[] children; // 子节点数组
    int keyCount;         // 当前键数量
    boolean isLeaf;       // 是否为叶子节点
    int t;                // 最小度数（定义 B 树的阶）

    public BTreeNode(int t, boolean isLeaf) {
        this.t = t;
        this.isLeaf = isLeaf;
        this.keys = new int[2 * t - 1];      // 最多 2t-1 个键
        this.children = new BTreeNode[2 * t]; // 最多 2t 个子节点
        this.keyCount = 0;
    }
}

B 树基本类

class BTree {
    private BTreeNode root;
    private int t;  // 最小度数

    public BTree(int t) {
        this.t = t;
        this.root = new BTreeNode(t, true);
    }

    public BTreeNode getRoot() { return root; }
    public void setRoot(BTreeNode root) { this.root = root; }
}

---

搜索键

// 时间复杂度: O(t log_t n), 其中 t 是度数，n 是键总数
// 空间复杂度: O(1)
public BTreeNode search(BTree tree, int key) {
    return searchRec(tree.getRoot(), key);
}

private BTreeNode searchRec(BTreeNode node, int key) {
    int i = 0;
    while (i < node.keyCount && key > node.keys[i]) {
        i++;
    }
    if (i < node.keyCount && key == node.keys[i]) {
        return node;  // 找到键
    }
    if (node.isLeaf) {
        return null;  // 未找到且是叶子节点
    }
    return searchRec(node.children[i], key);  // 递归搜索子节点
}

插入键

// 时间复杂度: O(t log_t n), 空间复杂度: O(t) 递归栈
public void insert(BTree tree, int key) {
    BTreeNode root = tree.getRoot();
    if (root.keyCount == 2 * tree.t - 1) {  // 根节点已满
        BTreeNode newRoot = new BTreeNode(tree.t, false);
        newRoot.children[0] = root;
        splitChild(newRoot, 0, root, tree.t);
        insertNonFull(newRoot, key, tree.t);
        tree.setRoot(newRoot);
    } else {
        insertNonFull(root, key, tree.t);
    }
}

private void insertNonFull(BTreeNode node, int key, int t) {
    int i = node.keyCount - 1;
    if (node.isLeaf) {
        while (i >= 0 && key < node.keys[i]) {
            node.keys[i + 1] = node.keys[i];
            i--;
        }
        node.keys[i + 1] = key;
        node.keyCount++;
    } else {
        while (i >= 0 && key < node.keys[i]) {
            i--;
        }
        i++;
        if (node.children[i].keyCount == 2 * t - 1) {
            splitChild(node, i, node.children[i], t);
            if (key > node.keys[i]) {
                i++;
            }
        }
        insertNonFull(node.children[i], key, t);
    }
}

private void splitChild(BTreeNode parent, int i, BTreeNode fullChild, int t) {
    BTreeNode newNode = new BTreeNode(t, fullChild.isLeaf);
    newNode.keyCount = t - 1;
    
    // 复制后半部分键到新节点
    for (int j = 0; j < t - 1; j++) {
        newNode.keys[j] = fullChild.keys[j + t];
    }
    
    // 如果不是叶子节点，复制子节点
    if (!fullChild.isLeaf) {
        for (int j = 0; j < t; j++) {
            newNode.children[j] = fullChild.children[j + t];
        }
    }
    
    fullChild.keyCount = t - 1;
    
    // 调整父节点的子节点
    for (int j = parent.keyCount; j > i; j--) {
        parent.children[j + 1] = parent.children[j];
    }
    parent.children[i + 1] = newNode;
    
    // 提升中间键到父节点
    for (int j = parent.keyCount - 1; j >= i; j--) {
        parent.keys[j + 1] = parent.keys[j];
    }
    parent.keys[i] = fullChild.keys[t - 1];
    parent.keyCount++;
}

删除键

// 时间复杂度: O(t log_t n), 空间复杂度: O(t) 递归栈
public void delete(BTree tree, int key) {
    deleteRec(tree.getRoot(), key, tree.t);
    if (tree.getRoot().keyCount == 0 && !tree.getRoot().isLeaf) {
        tree.setRoot(tree.getRoot().children[0]);
    }
}

private void deleteRec(BTreeNode node, int key, int t) {
    int i = 0;
    while (i < node.keyCount && key > node.keys[i]) {
        i++;
    }
    
    if (i < node.keyCount && key == node.keys[i]) {
        if (node.isLeaf) {
            removeFromLeaf(node, i);
        } else {
            removeFromNonLeaf(node, i, t);
        }
    } else if (!node.isLeaf) {
        deleteFromSubtree(node, i, key, t);
    }
}

private void removeFromLeaf(BTreeNode node, int i) {
    for (int j = i + 1; j < node.keyCount; j++) {
        node.keys[j - 1] = node.keys[j];
    }
    node.keyCount--;
}

private void removeFromNonLeaf(BTreeNode node, int i, int t) {
    int key = node.keys[i];
    BTreeNode pred = node.children[i];
    BTreeNode succ = node.children[i + 1];
    
    if (pred.keyCount >= t) {
        int predKey = getPredecessor(pred);
        node.keys[i] = predKey;
        deleteRec(pred, predKey, t);
    } else if (succ.keyCount >= t) {
        int succKey = getSuccessor(succ);
        node.keys[i] = succKey;
        deleteRec(succ, succKey, t);
    } else {
        mergeNodes(node, i, t);
        deleteRec(node.children[i], key, t);
    }
}

private void deleteFromSubtree(BTreeNode node, int i, int key, int t) {
    BTreeNode child = node.children[i];
    if (child.keyCount < t) {
        fillChild(node, i, t);
    }
    deleteRec(child, key, t);
}

private int getPredecessor(BTreeNode node) {
    while (!node.isLeaf) {
        node = node.children[node.keyCount];
    }
    return node.keys[node.keyCount - 1];
}

private int getSuccessor(BTreeNode node) {
    while (!node.isLeaf) {
        node = node.children[0];
    }
    return node.keys[0];
}

private void mergeNodes(BTreeNode node, int i, int t) {
    BTreeNode left = node.children[i];
    BTreeNode right = node.children[i + 1];
    
    left.keys[left.keyCount] = node.keys[i];
    for (int j = 0; j < right.keyCount; j++) {
        left.keys[left.keyCount + 1 + j] = right.keys[j];
    }
    if (!left.isLeaf) {
        for (int j = 0; j <= right.keyCount; j++) {
            left.children[left.keyCount + 1 + j] = right.children[j];
        }
    }
    
    left.keyCount += right.keyCount + 1;
    for (int j = i + 1; j < node.keyCount; j++) {
        node.keys[j - 1] = node.keys[j];
        node.children[j] = node.children[j + 1];
    }
    node.keyCount--;
}

private void fillChild(BTreeNode node, int i, int t) {
    if (i != 0 && node.children[i - 1].keyCount >= t) {
        borrowFromPrev(node, i, t);
    } else if (i != node.keyCount && node.children[i + 1].keyCount >= t) {
        borrowFromNext(node, i, t);
    } else {
        if (i != node.keyCount) {
            mergeNodes(node, i, t);
        } else {
            mergeNodes(node, i - 1, t);
        }
    }
}

private void borrowFromPrev(BTreeNode node, int i, int t) {
    BTreeNode child = node.children[i];
    BTreeNode sibling = node.children[i - 1];
    
    for (int j = child.keyCount - 1; j >= 0; j--) {
        child.keys[j + 1] = child.keys[j];
    }
    if (!child.isLeaf) {
        for (int j = child.keyCount; j >= 0; j--) {
            child.children[j + 1] = child.children[j];
        }
    }
    
    child.keys[0] = node.keys[i - 1];
    if (!child.isLeaf) {
        child.children[0] = sibling.children[sibling.keyCount];
    }
    node.keys[i - 1] = sibling.keys[sibling.keyCount - 1];
    child.keyCount++;
    sibling.keyCount--;
}

private void borrowFromNext(BTreeNode node, int i, int t) {
    BTreeNode child = node.children[i];
    BTreeNode sibling = node.children[i + 1];
    
    child.keys[child.keyCount] = node.keys[i];
    if (!child.isLeaf) {
        child.children[child.keyCount + 1] = sibling.children[0];
    }
    node.keys[i] = sibling.keys[0];
    
    for (int j = 1; j < sibling.keyCount; j++) {
        sibling.keys[j - 1] = sibling.keys[j];
    }
    if (!sibling.isLeaf) {
        for (int j = 1; j <= sibling.keyCount; j++) {
            sibling.children[j - 1] = sibling.children[j];
        }
    }
    child.keyCount++;
    sibling.keyCount--;
}

遍历（中序遍历）

// 时间复杂度: O(n), 空间复杂度: O(t) 递归栈
public void inorder(BTree tree) {
    inorderRec(tree.getRoot());
    System.out.println();
}

private void inorderRec(BTreeNode node) {
    if (node != null) {
        int i;
        for (i = 0; i < node.keyCount; i++) {
            if (!node.isLeaf) {
                inorderRec(node.children[i]);
            }
            System.out.print(node.keys[i] + " ");
        }
        if (!node.isLeaf) {
            inorderRec(node.children[i]);
        }
    }
}

---

使用示例

public class Main {
    public static void main(String[] args) {
        BTree tree = new BTree(3);  // 最小度数 t=3
        
        // 插入键
        insert(tree, 10);
        insert(tree, 20);
        insert(tree, 5);
        insert(tree, 6);
        insert(tree, 12);
        insert(tree, 30);
        
        System.out.println("Inorder traversal:");
        inorder(tree);  // 输出: 5 6 10 12 20 30
        
        // 搜索
        System.out.println("Search 6: " + (search(tree, 6) != null));  // 输出: true
        System.out.println("Search 15: " + (search(tree, 15) != null));  // 输出: false
        
        // 删除
        delete(tree, 6);
        System.out.println("After deleting 6:");
        inorder(tree);  // 输出: 5 10 12 20 30
    }
}

---

说明

• 时间复杂度：
  • 搜索、插入、删除为 O(t log_t n)，其中 t 是度数，n 是键总数。
  • 遍历为 O(n)。
• 空间复杂度：
  • 每个节点占用 O(t) 空间，递归栈为 O(t)。
• 算法特点：
  • 插入：通过分裂满节点保持平衡。
  • 删除：通过借用或合并子节点保持最小键数。
  • 搜索：利用有序键快速定位。
• 应用：
  • B 树适用于磁盘存储系统，因其多路结构减少了 I/O 操作。
• 扩展：
  • 如果需要范围查询、最小/最大值等其他算法，可以告诉我，我会补充。

这个实现假设键为整数，t 为固定值。如果需要动态调整 t 或支持其他数据类型，可以进一步修改。有什么具体需求，请告诉我！

B+ 树

B+ 树是 B 树的变种，广泛用于数据库和文件系统，特点是所有键值存储在叶子节点，非叶子节点仅用于索引，且叶子节点通过链表连接，便于范围查询。

B+ 树性质：

1. 所有键值存储在叶子节点，非叶子节点仅存储索引。
2. 每个节点最多有 2t-1 个键，最多 2t 个子节点。
3. 每个非根节点至少有 t-1 个键，至少 t 个子节点。
4. 叶子节点通过链表连接。

---

B+ 树节点定义

class BPlusNode {
    int[] keys;           // 键数组
    BPlusNode[] children; // 子节点数组（仅非叶子节点使用）
    int keyCount;         // 当前键数量
    boolean isLeaf;       // 是否为叶子节点
    BPlusNode next;       // 叶子节点的下一个指针
    int t;                // 最小度数（定义 B+ 树的阶）

    public BPlusNode(int t, boolean isLeaf) {
        this.t = t;
        this.isLeaf = isLeaf;
        this.keys = new int[2 * t - 1];      // 最多 2t-1 个键
        this.children = isLeaf ? null : new BPlusNode[2 * t]; // 最多 2t 个子节点
        this.keyCount = 0;
        this.next = null;
    }
}

B+ 树基本类

class BPlusTree {
    private BPlusNode root;
    private int t;  // 最小度数

    public BPlusTree(int t) {
        this.t = t;
        this.root = new BPlusNode(t, true);
    }

    public BPlusNode getRoot() { return root; }
    public void setRoot(BPlusNode root) { this.root = root; }
}

搜索键

// 时间复杂度: O(t log_t n), 其中 t 是度数，n 是键总数
// 空间复杂度: O(1)
public BPlusNode search(BPlusTree tree, int key) {
    BPlusNode node = tree.getRoot();
    while (!node.isLeaf) {
        int i = 0;
        while (i < node.keyCount && key > node.keys[i]) {
            i++;
        }
        node = node.children[i];
    }
    int i = 0;
    while (i < node.keyCount && key > node.keys[i]) {
        i++;
    }
    return (i < node.keyCount && node.keys[i] == key) ? node : null;
}

插入键

// 时间复杂度: O(t log_t n), 空间复杂度: O(t) 递归栈
public void insert(BPlusTree tree, int key) {
    BPlusNode root = tree.getRoot();
    if (root.keyCount == 2 * tree.t - 1) {
        BPlusNode newRoot = new BPlusNode(tree.t, false);
        newRoot.children[0] = root;
        splitChild(newRoot, 0, root, tree.t);
        tree.setRoot(newRoot);
        insertNonFull(tree.getRoot(), key, tree.t);
    } else {
        insertNonFull(root, key, tree.t);
    }
}

private void insertNonFull(BPlusNode node, int key, int t) {
    if (node.isLeaf) {
        int i = node.keyCount - 1;
        while (i >= 0 && key < node.keys[i]) {
            node.keys[i + 1] = node.keys[i];
            i--;
        }
        node.keys[i + 1] = key;
        node.keyCount++;
    } else {
        int i = 0;
        while (i < node.keyCount && key > node.keys[i]) {
            i++;
        }
        BPlusNode child = node.children[i];
        if (child.keyCount == 2 * t - 1) {
            splitChild(node, i, child, t);
            if (key > node.keys[i]) {
                i++;
            }
        }
        insertNonFull(node.children[i], key, t);
    }
}

private void splitChild(BPlusNode parent, int i, BPlusNode fullChild, int t) {
    BPlusNode newNode = new BPlusNode(t, fullChild.isLeaf);
    newNode.keyCount = t - 1;
    
    // 复制后半部分键到新节点
    for (int j = 0; j < t - 1; j++) {
        newNode.keys[j] = fullChild.keys[j + t];
    }
    
    // 如果是叶子节点，设置链表指针
    if (fullChild.isLeaf) {
        newNode.next = fullChild.next;
        fullChild.next = newNode;
    } else {
        // 如果不是叶子节点，复制子节点
        for (int j = 0; j < t; j++) {
            newNode.children[j] = fullChild.children[j + t];
        }
    }
    
    fullChild.keyCount = t - 1;
    
    // 调整父节点的子节点和键
    for (int j = parent.keyCount; j > i; j--) {
        parent.children[j + 1] = parent.children[j];
    }
    parent.children[i + 1] = newNode;
    
    for (int j = parent.keyCount - 1; j >= i; j--) {
        parent.keys[j + 1] = parent.keys[j];
    }
    parent.keys[i] = fullChild.keys[t - 1];  // 中间键提升到父节点
    parent.keyCount++;
}

删除键

// 时间复杂度: O(t log_t n), 空间复杂度: O(t) 递归栈
public void delete(BPlusTree tree, int key) {
    deleteRec(tree.getRoot(), key, tree.t);
    if (tree.getRoot().keyCount == 0 && !tree.getRoot().isLeaf) {
        tree.setRoot(tree.getRoot().children[0]);
    }
}

private void deleteRec(BPlusNode node, int key, int t) {
    int i = 0;
    while (i < node.keyCount && key > node.keys[i]) {
        i++;
    }
    
    if (node.isLeaf) {
        if (i < node.keyCount && node.keys[i] == key) {
            for (int j = i + 1; j < node.keyCount; j++) {
                node.keys[j - 1] = node.keys[j];
            }
            node.keyCount--;
        }
    } else {
        BPlusNode child = node.children[i];
        if (child.keyCount < t) {
            fillChild(node, i, t);
            if (i > node.keyCount) i--;  // 合并可能导致索引调整
        }
        deleteRec(node.children[i], key, t);
    }
}

private void fillChild(BPlusNode node, int i, int t) {
    if (i != 0 && node.children[i - 1].keyCount >= t) {
        borrowFromPrev(node, i, t);
    } else if (i != node.keyCount && node.children[i + 1].keyCount >= t) {
        borrowFromNext(node, i, t);
    } else {
        if (i != node.keyCount) {
            mergeNodes(node, i, t);
        } else {
            mergeNodes(node, i - 1, t);
        }
    }
}

private void borrowFromPrev(BPlusNode node, int i, int t) {
    BPlusNode child = node.children[i];
    BPlusNode sibling = node.children[i - 1];
    
    if (child.isLeaf) {
        for (int j = child.keyCount - 1; j >= 0; j--) {
            child.keys[j + 1] = child.keys[j];
        }
        child.keys[0] = sibling.keys[sibling.keyCount - 1];
        node.keys[i - 1] = sibling.keys[sibling.keyCount - 1];
    } else {
        for (int j = child.keyCount - 1; j >= 0; j--) {
            child.keys[j + 1] = child.keys[j];
        }
        child.keys[0] = node.keys[i - 1];
        node.keys[i - 1] = sibling.keys[sibling.keyCount - 1];
        child.children[child.keyCount + 1] = child.children[child.keyCount];
        for (int j = child.keyCount - 1; j >= 0; j--) {
            child.children[j + 1] = child.children[j];
        }
        child.children[0] = sibling.children[sibling.keyCount];
    }
    child.keyCount++;
    sibling.keyCount--;
}

private void borrowFromNext(BPlusNode node, int i, int t) {
    BPlusNode child = node.children[i];
    BPlusNode sibling = node.children[i + 1];
    
    if (child.isLeaf) {
        child.keys[child.keyCount] = sibling.keys[0];
        node.keys[i] = sibling.keys[1];
        for (int j = 1; j < sibling.keyCount; j++) {
            sibling.keys[j - 1] = sibling.keys[j];
        }
    } else {
        child.keys[child.keyCount] = node.keys[i];
        node.keys[i] = sibling.keys[0];
        child.children[child.keyCount + 1] = sibling.children[0];
        for (int j = 1; j < sibling.keyCount; j++) {
            sibling.keys[j - 1] = sibling.keys[j];
        }
        for (int j = 1; j <= sibling.keyCount; j++) {
            sibling.children[j - 1] = sibling.children[j];
        }
    }
    child.keyCount++;
    sibling.keyCount--;
}

private void mergeNodes(BPlusNode node, int i, int t) {
    BPlusNode left = node.children[i];
    BPlusNode right = node.children[i + 1];
    
    if (left.isLeaf) {
        for (int j = 0; j < right.keyCount; j++) {
            left.keys[left.keyCount + j] = right.keys[j];
        }
        left.next = right.next;
    } else {
        left.keys[left.keyCount] = node.keys[i];
        for (int j = 0; j < right.keyCount; j++) {
            left.keys[left.keyCount + 1 + j] = right.keys[j];
        }
        for (int j = 0; j <= right.keyCount; j++) {
            left.children[left.keyCount + 1 + j] = right.children[j];
        }
    }
    
    left.keyCount += right.keyCount + (left.isLeaf ? 0 : 1);
    for (int j = i + 1; j < node.keyCount; j++) {
        node.keys[j - 1] = node.keys[j];
        node.children[j] = node.children[j + 1];
    }
    node.keyCount--;
}

范围查询

// 时间复杂度: O(t log_t n + k), 其中 k 是范围内的键数
// 空间复杂度: O(k) 用于存储结果
public List<Integer> rangeSearch(BPlusTree tree, int low, int high) {
    List<Integer> result = new ArrayList<>();
    BPlusNode node = tree.getRoot();
    
    // 找到第一个大于等于 low 的叶子节点
    while (!node.isLeaf) {
        int i = 0;
        while (i < node.keyCount && low > node.keys[i]) {
            i++;
        }
        node = node.children[i];
    }
    
    // 遍历叶子节点链表
    while (node != null) {
        for (int i = 0; i < node.keyCount; i++) {
            if (node.keys[i] >= low && node.keys[i] <= high) {
                result.add(node.keys[i]);
            }
            if (node.keys[i] > high) {
                return result;
            }
        }
        node = node.next;
    }
    return result;
}

遍历（叶子节点顺序遍历）

// 时间复杂度: O(n), 空间复杂度: O(1)
public void traverse(BPlusTree tree) {
    BPlusNode node = tree.getRoot();
    while (!node.isLeaf) {
        node = node.children[0];
    }
    while (node != null) {
        for (int i = 0; i < node.keyCount; i++) {
            System.out.print(node.keys[i] + " ");
        }
        node = node.next;
    }
    System.out.println();
}

---

使用示例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        BPlusTree tree = new BPlusTree(3);  // 最小度数 t=3
        
        // 插入键
        insert(tree, 10);
        insert(tree, 20);
        insert(tree, 5);
        insert(tree, 6);
        insert(tree, 12);
        insert(tree, 30);
        
        System.out.println("Traversal:");
        traverse(tree);  // 输出: 5 6 10 12 20 30
        
        // 搜索
        System.out.println("Search 6: " + (search(tree, 6) != null));  // 输出: true
        System.out.println("Search 15: " + (search(tree, 15) != null));  // 输出: false
        
        // 删除
        delete(tree, 6);
        System.out.println("After deleting 6:");
        traverse(tree);  // 输出: 5 10 12 20 30
        
        // 范围查询
        List<Integer> range = rangeSearch(tree, 10, 20);
        System.out.println("Range [10, 20]: " + range);  // 输出: [10, 12, 20]
    }
}

---

说明

• 时间复杂度：
  • 搜索、插入、删除为 O(t log_t n)，t 是度数，n 是键总数。
  • 范围查询为 O(t log_t n + k)，k 是范围内的键数。
  • 遍历为 O(n)。
• 空间复杂度：
  • 每个节点占用 O(t) 空间，递归栈为 O(t)。
  • 范围查询结果占用 O(k) 空间。
• 算法特点：
  • 插入：分裂时将中间键提升到父节点，叶子节点保持链表。
  • 删除：仅从叶子节点删除，通过借用或合并保持平衡。
  • 范围查询：利用叶子节点链表高效实现。
• 与 B 树的区别：
  • B+ 树叶子节点存储所有数据，非叶子节点仅用于导航。
  • 叶子节点链表支持顺序访问和范围查询。
• 应用：
  • 数据库索引（如 MySQL InnoDB），因其支持高效范围查询和顺序访问。

这个实现假设键为整数，t 为固定值。如果需要支持其他数据类型或动态 t，可以进一步修改。有什么具体需求，请告诉我！

Trie (前缀树)

Trie 是一种树形数据结构，特别适合处理字符串的前缀查询和搜索问题。

• 定义: 多叉树，用于存储字符串集合，每个节点代表一个字符。
• 特性: 高效前缀查询，空间换时间。
• 应用场景:
  • 自动补全（如搜索引擎）
  • 拼写检查
  • IP路由表

---

1. Trie 节点定义

class TrieNode {
    TrieNode[] children;  // 子节点数组，通常大小为字符集大小
    boolean isEnd;        // 标记是否为单词结尾
    
    public TrieNode() {
        children = new TrieNode[26];  // 假设只处理小写字母 a-z
        isEnd = false;
    }
}

2. Trie 基本类

class Trie {
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public TrieNode getRoot() { return root; }
}

---

3. Trie 常用算法

3.1 插入字符串

// 时间复杂度: O(m), 其中 m 是字符串长度
// 空间复杂度: O(m), 最坏情况下为每个字符创建一个新节点
public void insert(Trie trie, String word) {
    TrieNode node = trie.getRoot();
    for (char c : word.toCharArray()) {
        int index = c - 'a';  // 假设小写字母
        if (node.children[index] == null) {
            node.children[index] = new TrieNode();
        }
        node = node.children[index];
    }
    node.isEnd = true;  // 标记单词结尾
}

3.2 搜索完整单词

// 时间复杂度: O(m), 其中 m 是单词长度
// 空间复杂度: O(1)
public boolean search(Trie trie, String word) {
    TrieNode node = trie.getRoot();
    for (char c : word.toCharArray()) {
        int index = c - 'a';
        if (node.children[index] == null) {
            return false;
        }
        node = node.children[index];
    }
    return node.isEnd;  // 必须是单词结尾
}

3.3 检查前缀

// 时间复杂度: O(m), 其中 m 是前缀长度
// 空间复杂度: O(1)
public boolean startsWith(Trie trie, String prefix) {
    TrieNode node = trie.getRoot();
    for (char c : prefix.toCharArray()) {
        int index = c - 'a';
        if (node.children[index] == null) {
            return false;
        }
        node = node.children[index];
    }
    return true;  // 只要前缀存在即可，不要求是单词结尾
}

3.4 删除字符串

// 时间复杂度: O(m), 其中 m 是字符串长度
// 空间复杂度: O(1) 不考虑递归栈，递归栈为 O(m)
public void delete(Trie trie, String word) {
    deleteRec(trie.getRoot(), word, 0);
}

private boolean deleteRec(TrieNode node, String word, int depth) {
    if (depth == word.length()) {
        if (!node.isEnd) return false;  // 不是单词结尾，无需删除
        node.isEnd = false;  // 取消单词结尾标记
        return isEmpty(node);  // 检查是否可以删除该节点
    }
    
    int index = word.charAt(depth) - 'a';
    if (node.children[index] == null) return false;
    
    boolean shouldDeleteCurrent = deleteRec(node.children[index], word, depth + 1);
    if (shouldDeleteCurrent) {
        node.children[index] = null;
        return isEmpty(node);
    }
    return false;
}

private boolean isEmpty(TrieNode node) {
    for (TrieNode child : node.children) {
        if (child != null) return false;
    }
    return !node.isEnd;
}

3.5 查找所有以某前缀开头的单词

// 时间复杂度: O(p + n), 其中 p 是前缀长度，n 是以该前缀开头的单词总数
// 空间复杂度: O(n), 用于存储结果
public List<String> findWordsWithPrefix(Trie trie, String prefix) {
    List<String> result = new ArrayList<>();
    TrieNode node = trie.getRoot();
    
    // 定位到前缀节点
    for (char c : prefix.toCharArray()) {
        int index = c - 'a';
        if (node.children[index] == null) {
            return result;  // 前缀不存在
        }
        node = node.children[index];
    }
    
    // 从该节点开始 DFS 收集所有单词
    findWordsRec(node, prefix, result);
    return result;
}

private void findWordsRec(TrieNode node, String prefix, List<String> result) {
    if (node.isEnd) {
        result.add(prefix);
    }
    for (int i = 0; i < 26; i++) {
        if (node.children[i] != null) {
            findWordsRec(node.children[i], prefix + (char)('a' + i), result);
        }
    }
}

3.6 计算 Trie 中单词总数

// 时间复杂度: O(n), 其中 n 是 Trie 中所有节点数
// 空间复杂度: O(h), 其中 h 是 Trie 高度（递归栈）
public int countWords(Trie trie) {
    return countWordsRec(trie.getRoot());
}

private int countWordsRec(TrieNode node) {
    if (node == null) return 0;
    int count = node.isEnd ? 1 : 0;
    for (TrieNode child : node.children) {
        count += countWordsRec(child);
    }
    return count;
}

---

使用示例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Trie trie = new Trie();
        
        // 插入单词
        insert(trie, "apple");
        insert(trie, "app");
        insert(trie, "banana");
        
        // 搜索单词
        System.out.println("Search 'apple': " + search(trie, "apple"));    // 输出: true
        System.out.println("Search 'app': " + search(trie, "app"));        // 输出: true
        System.out.println("Search 'appl': " + search(trie, "appl"));      // 输出: false
        
        // 检查前缀
        System.out.println("Starts with 'app': " + startsWith(trie, "app"));  // 输出: true
        System.out.println("Starts with 'ban': " + startsWith(trie, "ban"));  // 输出: true
        
        // 删除单词
        delete(trie, "app");
        System.out.println("After deleting 'app', search 'app': " + search(trie, "app"));  // 输出: false
        
        // 查找前缀单词
        List<String> words = findWordsWithPrefix(trie, "a");
        System.out.println("Words with prefix 'a': " + words);  // 输出: [apple]
        
        // 统计单词数
        System.out.println("Total words: " + countWords(trie));  // 输出: 2
    }
}

---

说明

• Trie 特点：
  • 每个节点表示一个字符，路径表示字符串。
  • 适合前缀查询、自动补全等场景。
• 时间复杂度：
  • 插入、搜索、检查前缀为 O(m)，m 是字符串长度。
  • 删除为 O(m)，但涉及递归清理。
  • 查找前缀单词为 O(p + n)，p 是前缀长度，n 是匹配单词数。
  • 统计单词为 O(n)，n 是所有节点数。
• 空间复杂度：
  • 插入可能需要 O(m) 空间来存储新节点。
  • 其他操作通常为 O(1) 或 O(h)，h 是 Trie 高度。
• 假设：
  • 这里假设只处理小写字母（26 个字符）。如果需要支持更多字符（如 ASCII 或 Unicode），可以调整 children 数组大小。
• 扩展：
  • 如果需要支持大小写、数字等，可以将 children 改为 Map<Character, TrieNode>。
  • 如果需要其他算法（如最长公共前缀、模糊匹配等），可以告诉我，我会补充。

哈希结构

数据结构	特点	冲突解决方法	操作	场景
哈希表 (Hash Table)	键值对存储，通过哈希函数快速定位	- 链地址法：链表存储冲突元素 - 开放寻址法：探测下一个空位 包括线性探测、二次探测和双重哈希	插入：O(1) 删除：O(1) 查找：O(1)（理想情况下）	缓存（如Redis） 快速去重

哈希表是一种基于键值对（Key-Value Pair）的高效数据结构，通过哈希函数将键映射到存储位置，支持快速的插入、查找和删除操作。实现一个简单的哈希表，处理冲突使用链地址法（Separate Chaining）。

---

哈希表节点定义（链地址法）

class HashNode {
    int key;
    int value;
    HashNode next;  // 链表指针，处理冲突
    
    public HashNode(int key, int value) {
        this.key = key;
        this.value = value;
        this.next = null;
    }
}

哈希表基本类

class HashTable {
    private HashNode[] table;  // 哈希表数组
    private int capacity;      // 哈希表容量
    private int size;          // 当前键值对数量
    
    public HashTable(int capacity) {
        this.capacity = capacity;
        this.table = new HashNode[capacity];
        this.size = 0;
    }
    
    // 简单哈希函数
    private int hash(int key) {
        return Math.abs(key) % capacity;  // 取模运算
    }
    
    public int getSize() { return size; }
}

插入键值对

// 时间复杂度: 平均 O(1), 最坏 O(n)（冲突严重时）
// 空间复杂度: O(1)（不计链表节点）
public void put(HashTable ht, int key, int value) {
    int index = ht.hash(key);
    if (ht.table[index] == null) {
        ht.table[index] = new HashNode(key, value);
    } else {
        HashNode current = ht.table[index];
        while (current != null) {
            if (current.key == key) {  // 键已存在，更新值
                current.value = value;
                return;
            }
            if (current.next == null) break;
            current = current.next;
        }
        current.next = new HashNode(key, value);  // 插入到链表末尾
    }
    ht.size++;
}

查找键值对

// 时间复杂度: 平均 O(1), 最坏 O(n)（冲突严重时）
// 空间复杂度: O(1)
public Integer get(HashTable ht, int key) {
    int index = ht.hash(key);
    HashNode current = ht.table[index];
    while (current != null) {
        if (current.key == key) {
            return current.value;
        }
        current = current.next;
    }
    return null;  // 未找到
}

删除键值对

// 时间复杂度: 平均 O(1), 最坏 O(n)（冲突严重时）
// 空间复杂度: O(1)
public boolean remove(HashTable ht, int key) {
    int index = ht.hash(key);
    HashNode current = ht.table[index];
    HashNode prev = null;
    
    while (current != null) {
        if (current.key == key) {
            if (prev == null) {
                ht.table[index] = current.next;
            } else {
                prev.next = current.next;
            }
            ht.size--;
            return true;
        }
        prev = current;
        current = current.next;
    }
    return false;  // 未找到
}

检查键是否存在

// 时间复杂度: 平均 O(1), 最坏 O(n)（冲突严重时）
// 空间复杂度: O(1)
public boolean containsKey(HashTable ht, int key) {
    int index = ht.hash(key);
    HashNode current = ht.table[index];
    while (current != null) {
        if (current.key == key) {
            return true;
        }
        current = current.next;
    }
    return false;
}

获取所有键

// 时间复杂度: O(n + m), 其中 n 是键值对数，m 是数组容量
// 空间复杂度: O(n)
public List<Integer> getAllKeys(HashTable ht) {
    List<Integer> keys = new ArrayList<>();
    for (int i = 0; i < ht.capacity; i++) {
        HashNode current = ht.table[i];
        while (current != null) {
            keys.add(current.key);
            current = current.next;
        }
    }
    return keys;
}

调整容量（动态扩容）

// 时间复杂度: O(n), 空间复杂度: O(n)
public void resize(HashTable ht, int newCapacity) {
    HashNode[] oldTable = ht.table;
    ht.table = new HashNode[newCapacity];
    ht.capacity = newCapacity;
    ht.size = 0;
    
    for (HashNode node : oldTable) {
        while (node != null) {
            put(ht, node.key, node.value);
            node = node.next;
        }
    }
}

---

使用示例

import java.util.*;

public class Main {
    public static void main(String[] args) {
        HashTable ht = new HashTable(5);
        
        // 插入键值对
        put(ht, 1, 100);
        put(ht, 2, 200);
        put(ht, 6, 600);  // 可能与 1 冲突（6 % 5 = 1）
        put(ht, 3, 300);
        
        // 查找
        System.out.println("Get 2: " + get(ht, 2));    // 输出: 200
        System.out.println("Get 6: " + get(ht, 6));    // 输出: 600
        System.out.println("Get 5: " + get(ht, 5));    // 输出: null
        
        // 检查键
        System.out.println("Contains 1: " + containsKey(ht, 1));  // 输出: true
        
        // 删除
        remove(ht, 2);
        System.out.println("After removing 2, get 2: " + get(ht, 2));  // 输出: null
        
        // 获取所有键
        System.out.println("All keys: " + getAllKeys(ht));  // 输出: [1, 6, 3]
        
        // 扩容
        resize(ht, 10);
        System.out.println("After resize, get 6: " + get(ht, 6));  // 输出: 600
    }
}

---

说明

• 链地址法特点：
  • 使用链表处理冲突，适合动态负载。
  • 平均时间复杂度为 O(1)，但冲突严重时退化为 O(n)。
• 时间复杂度：
  • 插入、查找、删除：平均 O(1)，最坏 O(n)。
  • 获取所有键和扩容：O(n)。
• 空间复杂度：
  • 基本操作 O(1)，存储所有键值对为 O(n)。
  • 扩容时临时需要 O(n) 额外空间。
• 哈希函数：
  • 这里使用简单的模运算，可根据需求优化（如乘法散列）。
• 负载因子：
  • 当 size/capacity 超过某个阈值（如 0.7），应调用 resize 扩容以保持性能。
• 应用：
  • 哈希表用于键值存储（如 HashMap）、缓存、数据库索引等。

开放寻址法处理冲突

---

哈希表基本类（开放寻址法通用）

class OpenAddressingHashTable {
    private class Entry {
        int key;
        int value;
        boolean isDeleted;  // 懒删除标记

        Entry(int key, int value) {
            this.key = key;
            this.value = value;
            this.isDeleted = false;
        }
    }

    private Entry[] table;
    private int capacity;
    private int size;
    private final double LOAD_FACTOR_THRESHOLD = 0.75;  // 负载因子阈值

    public OpenAddressingHashTable(int capacity) {
        this.capacity = capacity;
        this.table = new Entry[capacity];
        this.size = 0;
    }

    // 初始哈希函数
    private int hash(int key) {
        return Math.abs(key) % capacity;
    }

    // 第二个哈希函数（用于双重哈希）
    private int hash2(int key) {
        return 7 - (key % 7);  // 确保步长不为 0
    }

    public int getSize() { return size; }
    public int getCapacity() { return capacity; }

    // 扩容 - 时间复杂度: O(n)
    private void resize(int newCapacity) {
        Entry[] oldTable = table;
        table = new Entry[newCapacity];
        capacity = newCapacity;
        size = 0;
        for (Entry entry : oldTable) {
            if (entry != null && !entry.isDeleted) {
                putLinear(entry.key, entry.value);  // 选择一种方法重新插入
            }
        }
    }

    // 检查负载因子并扩容
    private void checkLoadFactor() {
        if ((double) size / capacity >= LOAD_FACTOR_THRESHOLD) {
            resize(capacity * 2);
        }
    }

---

线性探测（Linear Probing）实现

发生冲突时，线性向后查找下一个空位。时间复杂度：平均 O(1)，但随着负载因子增加，可能退化为 O(n)。

// 线性探测函数
private int probeLinear(int key, int i) {
    return (hash(key) + i) % capacity;
}

// 插入 - 时间复杂度: 平均 O(1), 最坏 O(n)
public void putLinear(int key, int value) {
    checkLoadFactor();
    int i = 0;
    int index;
    do {
        index = probeLinear(key, i);
        if (table[index] == null || table[index].isDeleted) {
            table[index] = new Entry(key, value);
            size++;
            return;
        } else if (table[index].key == key) {
            table[index].value = value;  // 更新值
            return;
        }
        i++;
    } while (i < capacity);
    throw new IllegalStateException("Hash table is full");
}

// 查找 - 时间复杂度: 平均 O(1), 最坏 O(n)
public Integer getLinear(int key) {
    int i = 0;
    int index;
    do {
        index = probeLinear(key, i);
        if (table[index] == null) {
            return null;
        } else if (!table[index].isDeleted && table[index].key == key) {
            return table[index].value;
        }
        i++;
    } while (i < capacity && table[index] != null);
    return null;
}

// 删除 - 时间复杂度: 平均 O(1), 最坏 O(n)
public boolean removeLinear(int key) {
    int i = 0;
    int index;
    do {
        index = probeLinear(key, i);
        if (table[index] == null) {
            return false;
        } else if (!table[index].isDeleted && table[index].key == key) {
            table[index].isDeleted = true;
            size--;
            return true;
        }
        i++;
    } while (i < capacity && table[index] != null);
    return false;
}

---

二次探测（Quadratic Probing）实现

冲突时按二次函数（i²）偏移查找。

// 二次探测函数
private int probeQuadratic(int key, int i) {
    return (hash(key) + i * i) % capacity;
}

// 插入 - 时间复杂度: 平均 O(1), 最坏 O(n)
public void putQuadratic(int key, int value) {
    checkLoadFactor();
    int i = 0;
    int index;
    do {
        index = probeQuadratic(key, i);
        if (table[index] == null || table[index].isDeleted) {
            table[index] = new Entry(key, value);
            size++;
            return;
        } else if (table[index].key == key) {
            table[index].value = value;
            return;
        }
        i++;
    } while (i < capacity);
    throw new IllegalStateException("Hash table is full");
}

// 查找 - 时间复杂度: 平均 O(1), 最坏 O(n)
public Integer getQuadratic(int key) {
    int i = 0;
    int index;
    do {
        index = probeQuadratic(key, i);
        if (table[index] == null) {
            return null;
        } else if (!table[index].isDeleted && table[index].key == key) {
            return table[index].value;
        }
        i++;
    } while (i < capacity && table[index] != null);
    return null;
}

// 删除 - 时间复杂度: 平均 O(1), 最坏 O(n)
public boolean removeQuadratic(int key) {
    int i = 0;
    int index;
    do {
        index = probeQuadratic(key, i);
        if (table[index] == null) {
            return false;
        } else if (!table[index].isDeleted && table[index].key == key) {
            table[index].isDeleted = true;
            size--;
            return true;
        }
        i++;
    } while (i < capacity && table[index] != null);
    return false;
}

---

双重哈希（Double Hashing）实现

使用第二个哈希函数确定探测步长。

    // 双重哈希探测函数
    private int probeDouble(int key, int i) {
        return (hash(key) + i * hash2(key)) % capacity;
    }

    // 插入 - 时间复杂度: 平均 O(1), 最坏 O(n)
    public void putDouble(int key, int value) {
        checkLoadFactor();
        int i = 0;
        int index;
        do {
            index = probeDouble(key, i);
            if (table[index] == null || table[index].isDeleted) {
                table[index] = new Entry(key, value);
                size++;
                return;
            } else if (table[index].key == key) {
                table[index].value = value;
                return;
            }
            i++;
        } while (i < capacity);
        throw new IllegalStateException("Hash table is full");
    }

    // 查找 - 时间复杂度: 平均 O(1), 最坏 O(n)
    public Integer getDouble(int key) {
        int i = 0;
        int index;
        do {
            index = probeDouble(key, i);
            if (table[index] == null) {
                return null;
            } else if (!table[index].isDeleted && table[index].key == key) {
                return table[index].value;
            }
            i++;
        } while (i < capacity && table[index] != null);
        return null;
    }

    // 删除 - 时间复杂度: 平均 O(1), 最坏 O(n)
    public boolean removeDouble(int key) {
        int i = 0;
        int index;
        do {
            index = probeDouble(key, i);
            if (table[index] == null) {
                return false;
            } else if (!table[index].isDeleted && table[index].key == key) {
                table[index].isDeleted = true;
                size--;
                return true;
            }
            i++;
        } while (i < capacity && table[index] != null);
        return false;
    }
}

---

使用示例

public class Main {
    public static void main(String[] args) {
        // 线性探测
        OpenAddressingHashTable htLinear = new OpenAddressingHashTable(5);
        htLinear.putLinear(1, 100);
        htLinear.putLinear(6, 600);  // 冲突：6 % 5 = 1
        htLinear.putLinear(2, 200);
        System.out.println("Linear Probing - Get 6: " + htLinear.getLinear(6));  // 输出: 600
        htLinear.removeLinear(6);
        System.out.println("Linear Probing - After remove 6: " + htLinear.getLinear(6));  // 输出: null

        // 二次探测
        OpenAddressingHashTable htQuadratic = new OpenAddressingHashTable(5);
        htQuadratic.putQuadratic(1, 100);
        htQuadratic.putQuadratic(6, 600);
        htQuadratic.putQuadratic(2, 200);
        System.out.println("Quadratic Probing - Get 6: " + htQuadratic.getQuadratic(6));  // 输出: 600
        htQuadratic.removeQuadratic(6);
        System.out.println("Quadratic Probing - After remove 6: " + htQuadratic.getQuadratic(6));  // 输出: null

        // 双重哈希
        OpenAddressingHashTable htDouble = new OpenAddressingHashTable(5);
        htDouble.putDouble(1, 100);
        htDouble.putDouble(6, 600);
        htDouble.putDouble(2, 200);
        System.out.println("Double Hashing - Get 6: " + htDouble.getDouble(6));  // 输出: 600
        htDouble.removeDouble(6);
        System.out.println("Double Hashing - After remove 6: " + htDouble.getDouble(6));  // 输出: null
    }
}

---

说明

• 负载因子控制：
  • 设置 LOAD_FACTOR_THRESHOLD = 0.75，当 size/capacity ≥ 0.75 时，自动扩容为两倍容量。
  • 扩容通过 resize 方法实现，时间复杂度 O(n)。
• 冲突处理方法：
  • 线性探测：简单，但容易主聚集。
  • 二次探测：减少主聚集，但可能次聚集，需确保容量为素数以覆盖所有位置。
  • 双重哈希：最优，避免聚集，但需设计合适的第二个哈希函数。
• 时间复杂度：
  • 平均 O(1)（负载因子低时），最坏 O(n)（表满或聚集严重）。
• 空间复杂度：
  • O(1) 额外空间（不计数组本身），扩容时临时需要 O(n)。
• 优化点：
  • 这里使用懒删除（标记删除），避免破坏探测序列。
  • 哈希函数简单，可根据实际需求优化（如乘法散列）。
  • 二次探测和双重哈希未强制容量为素数，实际应用中建议调整。

图结构

类别	内容	描述	适用场景
表示方式	邻接矩阵	二维数组表示顶点关系，matrix[i][j]表示边权重或是否存在边	适合稠密图（边较多）
	邻接表	链表数组表示顶点关系，每个顶点关联一个邻接顶点链表	适合稀疏图（边较少）
算法场景	最短路径 (Dijkstra算法)	从单一源点计算到所有顶点的最短路径，基于贪心策略	网络路由、路径规划
	最小生成树 (Prim/Kruskal算法)	- Prim：从某顶点扩展生成树 - Kruskal：按边权重排序合并	网络设计（如电缆布线）
	拓扑排序	对有向无环图（DAG）排序，输出顶点线性序列	任务调度、依赖解析（如编译顺序）

高级数据结构

数据结构	特点	操作	场景
并查集 (Union-Find)	管理元素分组，支持合并集合和查询所属集合	合并（Union）：近似O(1) 查找（Find）：近似O(1)（路径压缩优化后）	连通性问题（如社交网络好友关系）
跳表 (Skip List)	多层链表结构，利用概率平衡，提升查询效率	插入：O(log n) 删除：O(log n) 查找：O(log n)	Redis有序集合实现
布隆过滤器 (Bloom Filter)	概率型数据结构，判断元素“可能存在”或“一定不存在”	添加：O(1) 查询：O(1)	缓存穿透防护 垃圾邮件过滤

算法