1 二叉树
这是最基础的树形结构。
- 定义：每个节点最多只有两个子节点（左子树和右子树）。
- 优点：比链表快，插入和查找的平均时间复杂度是 O(log N)。
缺点：不稳定。在极端情况下（比如插入的数据本身已经是有序的，如 6, 7, 8, 9），它会退化成一条链表。
此时查找时间复杂度会降到 O(N)，性能急剧下降。
2 二叉平衡树
为了解决二叉树的退化问题，平衡树诞生了。
- 定义：在二叉树的基础上增加了约束：左右子树的高度差不能超过 1。
- 工作原理：每次插入或删除数据时，如果平衡被破坏，它会通过旋转操作来自动调整结构，使其始终保持平衡。
- 优点：避免了二叉树退化成链表的问题，查找效率非常稳定，始终维持在 O(log N)。
- 缺点：
- 树太高：当数据量非常大时（例如几百万条），log N 的深度可能依然有 20-30 层。每一次从磁盘读取一层数据，就是一次磁盘 I/O，非常慢。
- 数据量问题：它适用于内存中的查找，但不适用于海量数据的磁盘存储。
- 平衡二叉树插入数据导致破坏平衡的类型分为四种：LL、LR、RR、RL，具体解决方法包括对应的旋转操作。
3 B 树
当数据量大到无法全部放入内存，必须存放在磁盘上时，B 树出现了。它是一种多路搜索树。
- 核心思想：不再像二叉树那样只有一个节点一个数据，而是一个节点可以存储多个值，并且拥有多个子节点（多叉的）。
- 结构特点：
- 每个节点包含键值和数据（或指针）。
- 节点内的键值从小到大排序。
- 所有节点（包括根节点和中间节点）都可能存储实际的数据。
- 优点：降低了树的高度。因为一个节点存了多个值，树变得更矮更胖，从而减少了磁盘 I/O 次数。
- 缺点：
