树
度：每个节点的子节点数量
树高：树的总层数
根节点：入度为0的节点
二叉树
每个节点最多有两个子节点
二叉查找树
任意节点左子树上的节点都小于当前节点，右子树上的节点都大于当前节点
平衡二叉树
任意节点的左右子树的高度差不超过1
AVL树
AVL 树是一种平衡二叉树，得名于其发明者的名字（ Adelson-Velskii 以及 Landis）。
- 首先是一个二叉查找树
- 然后任意节点的左右子树的高度差（平衡因子）不超过1
维护平衡
需要沿着从被插入/删除的节点到根的路径对树进行维护
- 从被插入/删除的节点开始，不断地往父节点方向寻找不平衡的节点
- 以不平衡的节点作为支点对子树进行旋转（左旋/右旋）
旋转情况：
左左（根节点的左子树的左子树中出现插入不平衡）：一次右旋
左右（根节点的左子树的右子树中出现插入不平衡）：先局部（根节点左子树）左旋，再整体右旋
右右（根节点的右子树的右子树中出现插入不平衡）：一次左旋
右左（根节点的右子树的左子树中出现插入不平衡）：先局部（根节点右子树）右旋，再整体左旋
红黑树
红黑树是一种自平衡的二叉搜索树。每个节点额外存储了一个 color 字段 ("RED" or "BLACK")，用于确保树在插入和删除时保持平衡。
红黑树不是高度平衡的，而是通过红黑规则进行平衡调整
红黑树添加节点的规则
添加节点默认是红色的效率高
