树结构：二叉树、二叉搜索树、AVL树与线段树详解

该思维导图概述了四种树结构：普通二叉树、二叉搜索树、AVL树和线段树。普通二叉树包含节点值、左子节点和右子节点，支持插入和中序遍历。二叉搜索树在此基础上增加了搜索功能，并具有左子树值小于根节点、右子树值大于根节点的性质。AVL树为自平衡二叉搜索树，通过旋转操作维持平衡，保证查找、插入、删除的时间复杂度为O(log n)。线段树则用于处理区间查询和更新问题，通过自底向上构建和更新区间信息，并利用二进制划分高效查询。

源码

# 树结构
## 普通二叉树 Tree
- 节点包含
  - 值
  - 左子节点
  - 右子节点
- 功能
  - 插入
    - 在左子树或右子树插入
  - 中序遍历
    - 左子树 -> 根节点 -> 右子树
  - 前序遍历
    - 根节点 -> 左子树 -> 右子树
  - 后序遍历
    - 左子树 -> 右子树 -> 根节点
## 二叉搜索树 BinarySearchTree
- 继承自普通二叉树
- 增加搜索功能
  - 查找节点
  - 删除节点
- 树的性质
  - 左子树的值 < 根节点
  - 右子树的值 > 根节点
- 应用场景
  - 动态查找
  - 排序
## AVL树 AVLTree
- 继承自二叉搜索树
- 自平衡特性
  - 维护平衡因子
- 旋转操作用于保持平衡
  - 左旋
  - 右旋
  - 左右重
  - 右左重
- 时间复杂度
  - 查找: O(log n)
  - 插入: O(log n)
  - 删除: O(log n)
- 应用场景
  - 高效动态数据集合
## 线段树 SegmentTree
- 用途
  - 处理区间查询
    - 求和
    - 最大值
    - 最小值
  - 更新问题
    - 更新单个数据点
    - 区间更新
- 数据存储
  - 树的叶子节点存储原始数据
  - 父节点存储区间信息
- 操作
  - 构建
    - 自底向上计算区间信息
    - 时间复杂度: O(n)
  - 更新
    - 自底向上更新父节点信息
    - 时间复杂度: O(log n)
  - 查询
    - 二分查找区间
    - 时间复杂度: O(log n)

图片