二叉树基础
二叉树每个节点最多有两个子节点。满二叉树每层节点数达到最大；完全二叉树除最后一层外满，最后一层从左到右连续。
遍历方式：前序（根-左-右）、中序（左-根-右）、后序（左-右-根）、层序（BFS）。中序遍历二叉搜索树可得有序序列。
二叉搜索树（BST）
BST 满足：左子树所有节点 < 根 < 右子树所有节点。查找、插入、删除平均 O(log n)，但最坏 O(n)——退化为链时。
删除分三种情况：无子节点直接删；一个子节点用子节点替代；两个子节点用后继（右子树最小）或前驱替代，再递归删除后继节点。
AVL 树
AVL 是自平衡 BST，保证任意节点左右子树高度差不超过 1。通过旋转恢复平衡：左旋、右旋、左右双旋、右左双旋。
平衡因子 = 左高 - 右高，插入/删除后若 |平衡因子| > 1 则旋转。AVL 查询效率高，但插入删除可能引发多次旋转，写操作开销大。
红黑树
红黑树通过五条规则保持近似平衡：节点红或黑；根和叶（NIL）为黑；红节点的子节点必为黑；任意节点到叶的路径黑节点数相同。
插入/删除通过变色和旋转维护规则。相比 AVL，红黑树允许更大高度差，旋转次数少，插入删除更高效，广泛应用于 STL map、Java TreeMap、Linux 内核等。