树和映射数据结构基础
raw/articles/2026/05/树和映射数据结构基础
一句话总结
二叉搜索树（BST）通过左小右大特性实现 O(logN) 查找，TreeMap/TreeSet 底层基于 BST，相比 HashMap 能维护键的有序性。
前置知识
核心内容
1. 二叉搜索树（BST）的优势
特性：左小右大
- 对于树中的每个节点，其 左子树的每个节点 的值都要小于这个节点的值
- 右子树的每个节点 的值都要大于这个节点的值
时间复杂度：
| 操作 | BST | 普通二叉树 |
|---|---|---|
| 查找 | O(logN) | O(N) |
| 插入 | O(logN) | - |
| 删除 | O(logN) | - |
BST 能快速定位目标节点，利用左小右大特性迅速缩小搜索范围。
2. TreeMap/TreeSet 实现原理
TreeMap 结构：
- 底层把键值对存储在一棵二叉搜索树的节点里面
- 类似 HashMap，但保持键的有序性
TreeNode 结构改造：
// 大写 K 为键的类型，大写 V 为值的类型
class TreeNode<K, V> {
K key;
V value;
TreeNode<K, V> left;
TreeNode<K, V> right;
TreeNode(K key, V value) {
this.key = key;
this.value = value;
}
}
TreeSet 与 TreeMap 关系：
- 正如 HashMap 和 HashSet 的关系
- TreeSet 是 TreeMap 的简单封装
3. TreeMap 主要 API
Map 键值映射的基本方法：
| 方法 | 功能 | 复杂度 |
|---|---|---|
put(key, value) |
增/改 | O(logN) |
get(key) |
查 | O(logN) |
remove(key) |
删 | O(logN) |
containsKey(key) |
是否包含键 | O(logN) |
keys() |
返回所有键（有序） | O(N) |
TreeMap 提供的额外方法（与键大小相关）：
| 方法 | 功能 | 复杂度 |
|---|---|---|
firstKey() |
查找最小键 | O(logN) |
lastKey() |
查找最大键 | O(logN) |
floorKey(key) |
查找小于等于 key 的最大键 | O(logN) |
ceilingKey(key) |
查找大于等于 key 的最小键 | O(logN) |
selectKey(k) |
查找排名为 k 的键 | O(logN) |
rank(key) |
查找键 key 的排名 | O(logN) |
rangeKeys(low, high) |
区间查找 | O(logN + M) |
4. TreeMap vs HashMap
| 特性 | TreeMap | HashMap |
|---|---|---|
| 底层结构 | 二叉搜索树 | 哈希表（数组+链表/红黑树） |
| 键的顺序 | 有序（自然顺序或比较器） | 无序（或插入顺序） |
| 时间复杂度 | O(logN) | O(1) 平均 |
| 额外功能 | 提供范围查询、排名等有序操作 | 无 |
TreeMap 的优势场景：
- 需要维护键的大小顺序
- 需要范围查询（如查找某个区间内的所有键）
- 需要获取最大/最小键
- 需要查询排名或按排名查找
HashMap 无法很好地处理键之间的大小关系，LinkedHashMap 也只能按「插入顺序」排列，做不到按「大小顺序」排列。
相关概念
相关实体
- labuladong：算法学习平台作者
待实现内容
本文仅讲解 TreeMap/TreeSet 的原理，完整实现放到了 二叉树系列习题 后面，建议先刷完二叉树习题培养递归思维再学习实现。
相关题目
- 力扣经典的
TreeNode结构理解 - BST 查找、插入、删除操作