[数据结构与算法笔记04] Trees(二分树、二分搜索树、AVL树、伸展树、Sets&Map)

Answer 1

在大量数据输入时，linked lists 的获取时间较长，因此需要一种更高效的简单数据结构。这种数据结构被称为二分树，是实现 set 和 map 的基础。本文章将探讨以下内容：树的定义、实现、遍历方法、二分树、二分搜索树、AVL树、伸展树、二分搜索树的实现、平均深度分析、AVL树的平衡条件、旋转操作、伸展树、遍历方法、B-Tree 及 STL 中的 sets 和 maps。

树的定义是递归的集合，其中有一个特殊的节点作为根，其余节点通过边与根或其他节点相连。根据节点位置，树可以分为多个子树。实现时，二分树每节点最多有两个子树，这与常规树的子树数量不确定形成对比。

二分树搜索特性使其在搜索和计算方面具有优势。例如，计算表达式树可以通过遍历节点实现。使用二分树进行搜索操作，平均时间复杂度为 O(log n)。实现包括实现模板、树结构的指针、contains、findmax、findmin、insert 和 remove 方法等。

二分搜索树的实现利用比较运算符实现，确保树中所有节点遵循特定顺序。通过递归实现contains、findMin、findMax、insert 和 remove 方法，处理树的结构变化。

平均深度分析表明，除了空树和复制操作外，其他操作的平均时间复杂度为 O(log n)。证明过程涉及内部路径长度和深度的平均值。

为了保持二分搜索树的平衡，引入 AVL 树，其高度为 O(log n)。平衡条件要求左右子树高度相同或高度差不超过 1。在插入或删除节点后，AVL 树可能失去平衡，此时需要通过旋转操作来调整结构，保持平衡。

旋转操作分为单旋转和双旋转，分别针对不同类型的不平衡情况。单旋转调整不平衡节点及其子树，而双旋转涉及更多节点。实施旋转操作时，需要重新调整节点关系以恢复平衡。

伸展树是另一种自调整数据结构，通过访问操作后将节点移动到根节点位置，提高后续访问效率。伸展树的实现和操作将在后续章节中详细介绍。

树的遍历方法包括前序、中序和后序遍历，每种方法按照特定顺序访问节点。

B-Tree 是一种用于磁盘存储的多分支搜索树，特别适用于文件系统。B-Tree 的节点可以包含多个键值对，允许数据在磁盘中进行高效的存储和检索。

STL 中的 sets 和 maps 使用红黑树实现。insert、erase 和 find 方法提供对元素的操作，允许在常数时间内查找、插入和删除元素，同时避免重复元素。