Java版数据结构和算法+AI算法和技能（已完结）

获课：666it.top/14825/ Java数据结构精讲：从数组到红黑树的实战演练 一、数据结构基础：从数组开始 数组是Java中最基础的数据结构之一，它存储相同类型的数据元素，通过下标可以快速访问任意元素，时间复杂度为O(1)。数组的特点包括： 内存连续分配 固定长度（初始化后大小不可变） 查询速度快但增删效率低 Java  int[] arr = new int[5]; // 声明并初始化一个长度为5的整型数组 数组的局限性在于插入和删除元素时需要移动大量元素，平均时间复杂度为O(n)。为解决这个问题，链表结构应运而生。 二、链表结构：动态内存分配 链表通过节点(Node)的指针连接实现动态内存分配，不需要连续的内存空间。Java中的LinkedList就是基于双向链表实现的。 链表分为： 单链表：每个节点包含数据和指向下一个节点的指针 双链表：节点包含指向前后节点的指针 循环链表：尾节点指向头节点形成环 链表操作特点： 插入/删除时间复杂度O(1) 随机访问需要遍历，时间复杂度O(n) 三、树结构：从二叉树到平衡树 1. 二叉树基础 二叉树是每个节点最多有两个子节点的树结构，常用于实现高效搜索算法。 Java  class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } } 2. 二叉搜索树(BST) 二叉搜索树满足： 左子树所有节点值小于根节点 右子树所有节点值大于根节点 左右子树也都是BST BST的平均查找时间复杂度为O(log n)，但在最坏情况下（如插入有序数据）会退化为链表，时间复杂度降为O(n)。 四、红黑树：自平衡二叉搜索树 1. 红黑树基本概念 红黑树是一种自平衡二叉搜索树，通过在节点中添加颜色属性（红/黑）和遵循特定规则来保持树的平衡。 红黑树的五大性质： 每个节点是红色或黑色 根节点是黑色 每个叶子节点（NIL节点）是黑色 红色节点的子节点必须是黑色（不能有连续红色节点） 从任一节点到其每个叶子节点的路径包含相同数目的黑色节点 2. 红黑树与AVL树对比 红黑树放弃完全平衡，追求大致平衡 插入/删除操作旋转次数更少（最多3次旋转即可恢复平衡） 查找效率略低于AVL树，但综合性能更好 3. Java中的红黑树实现 Java 8的HashMap在链表长度超过阈值(8)时会转换为红黑树结构，显著提升了哈希冲突时的性能。 红黑树节点基本结构： Java  class RBTreeNode { private int value; private boolean isBlack; // 颜色标记 private RBTreeNode left; private RBTreeNode right; private RBTreeNode parent; public RBTreeNode(int value) { this.isBlack = false; // 新节点默认为红色 this.value = value; } // getter和setter方法 } 4. 红黑树操作 红黑树的核心操作包括旋转和颜色调整： 左旋示例代码： Java  private void leftRotate(RBTreeNode x) { RBTreeNode y = x.right; x.right = y.left; if (y.left != null) { y.left.parent = x; } y.parent = x.parent; if (x.parent == null) { this.root = y; } else if (x == x.parent.left) { x.parent.left = y; } else { x.parent.right = y; } y.left = x; x.parent = y; } 插入操作步骤： 按照BST规则插入新节点（红色） 检查并修复违反的红黑树性质情况1：插入节点是根节点 → 染黑情况2：父节点是黑色 → 无需处理情况3：父节点和叔节点都是红色 → 父叔染黑，祖父染红，递归处理祖父情况4/5：父红叔黑，且插入节点与父节点方向不一致 → 旋转父节点转为情况5情况5：父红叔黑，且插入节点与父节点方向一致 → 旋转祖父节点并重新着色 五、实战应用：Java集合框架中的数据结构 Java集合框架中不同数据结构的底层实现： ArrayList：动态数组实现，自动扩容 LinkedList：双向链表实现 HashMap：数组+链表/红黑树（Java8+） TreeMap：红黑树实现的有序映射 HashMap红黑树优化示例： 当哈希桶中的链表长度超过8时，Java 8会将链表转换为红黑树，将查找时间复杂度从O(n)降低到O(log n)。当元素减少到6个以下时，会转换回链表。 六、性能分析与选择指南 数据结构 平均查找 平均插入 平均删除 最坏查找 空间复杂度 数组 O(1) O(n) O(n) O(1) O(n) 链表 O(n) O(1) O(1) O(n) O(n) BST O(log n) O(log n) O(log n) O(n) O(n) 红黑树 O(log n) O(log n) O(log n) O(log n) O(n) 选择建议： 查询多、增删少 → 数组/ArrayList 增删频繁、随机访问少 → LinkedList 需要有序且高效查找 → 红黑树(TreeMap/TreeSet) 键值存储、哈希分布均匀 → HashMap 七、进阶学习资源 《算法导论》中关于红黑树的详细数学证明 OpenJDK源码中HashMap和TreeMap的实现 可视化工具：红黑树在线演示网站可以帮助理解插入删除过程 多线程环境下构建红黑树的优化技术（如分段构建）