树是什么
树是一种非线性数据结构，像一棵倒挂的树：最上面是根，下面分出节点，最末没有子节点的叫叶子。从根到某个节点经过的边数叫深度。例如，家族族谱就是一棵树——爷爷是根，爸爸是节点，你是叶子。
二叉树
二叉树是每个节点最多有两个子节点的树，分别叫左孩子和右孩子。它是最常用的树结构，因为简单且适合递归处理。比如，一个文件夹下最多两个子文件夹，就是二叉树。
遍历：DFS（前中后序）与 BFS（层序）
遍历就是按某种顺序访问所有节点。DFS（深度优先搜索）沿着一条路走到黑再回头，分为三种：
- 前序：根 → 左 → 右（先处理当前节点）
- 中序：左 → 根 → 右（对二叉搜索树可得到排序结果）
- 后序：左 → 右 → 根（先处理子节点）
BFS（广度优先搜索）也叫层序，一层一层从上到下访问，像排队一样。
二叉搜索树：左小右大、查找 O(log n)
二叉搜索树（BST）是一种特殊的二叉树：对于任意节点，左子树所有值 < 节点值 < 右子树所有值。查找时，每次比较就能排除一半，所以平均时间复杂度是 O(log n)，就像查字典时翻到中间页。
为什么要平衡（否则退化成链表）
如果插入数据有序（如1,2,3,4），BST会变成一条斜线，退化成链表，查找时间变成O(n)。为了避免这种情况，需要平衡——让左右子树高度差不超过1（如AVL树、红黑树），保证操作始终高效。
| 结构 | 平均查找 | 最坏查找 |
|---|---|---|
| 平衡BST | O(log n) | O(log n) |
| 不平衡BST | O(log n) | O(n) |
BST 的插入与删除
插入：和查找一样，一路比大小往下走，遇到空位就把新节点挂上，时间 O(log n)。
删除分三种情况：
- 删叶子节点：没有孩子，直接摘掉。
- 只有一个孩子：让那个孩子直接顶上来。
- 有两个孩子：找它的中序后继（右子树里最小的节点）来顶替它的位置，这样「左小右大」依然成立。