简介
作用
- 核心作用：高效搜索
- 其他作用：表示层级关系、组织数据
分类
二叉搜索树
- 对于任意节点：
- 左子树所有节点的值都小于该节点的值。
- 右子树所有节点的值都大于该节点的值。
- 主要作用： 支持高效的查找、插入、删除操作，平均时间复杂度为 O(log n)。
平衡树
- 通过旋转和重新组织节点来保持树的平衡，确保树的高度接近 log n。
- 常见类型：AVL树、红黑树。
- 主要作用： 提供稳定的 O(log n) 时间复杂度的查找、插入和删除操作。
B树
- 多路平衡搜索树，节点可以有多个子节点。
- 主要作用：广泛用于数据库和文件系统中，支持高效的磁盘读写操作。
Trie树
- 又称前缀树，用于存储字符串集合。
- 主要作用：高效的字符串查找和前缀匹配。
堆
- 完全二叉树，满足堆属性（最大堆或最小堆）。
- 主要作用：实现优先队列，支持高效的插入和删除最大/最小元素操作。
C++标准库中的树结构
- STL中的
std::map和std::set通常基于红黑树实现，提供有序的键值对存储和集合操作。 - C++20引入了
std::unordered_map和std::unordered_set，它们基于哈希表实现，提供平均常数时间复杂度的查找、插入和删除操作。