树用父子关系表达层级。二叉树每个节点最多两个孩子，但不一定有序；二叉搜索树要求左子树键更小、右子树更大，因此平均可快速查找，若按有序数据连续插入却可能退化为链表。

遍历决定信息处理顺序：前序先处理根，适合复制和序列化；中序遍历搜索树得到有序序列；后序先汇总孩子，适合计算高度、删除和树形动态规划；层序用队列按深度访问。遍历所有节点都是 O(n)，递归额外空间取决于高度 h。

AVL 树要求每个节点左右子树高度差不超过 1。插入删除破坏平衡后，通过单旋或双旋修复，查找与更新保持 O(log n)，但要维护高度且调整较严格。红黑树条件更宽松，更新常更经济。

B 树让一个节点保存多个键和孩子，显著降低高度，适合磁盘或页式存储；B+ 树通常把完整记录放在叶子，内部节点只做索引，叶子按顺序链接。这样范围扫描从起始叶开始顺链进行，内部节点也能容纳更多分隔键，数据库索引常采用这一思路。

实践比较不能只看大 O：内存指针树可能缓存命中差，外存结构更关心一次 I/O 读取多少键。误区包括把完全二叉树与搜索树混淆、认为搜索树必然 O(log n)、把 B 树叫二叉树，以及忽略重复键规则。小结：树的形状控制路径长度，节点容量适配存储介质，遍历顺序适配计算目标。