数据结构 - 一些常见的树
二叉排序树（二叉查找树）
- 左子树上所有结点的值均小于根结点
- 右子树上所有结点的值均大于根结点
- 左右子树均为二叉排序树
平衡二叉树
- 二叉排序树
- 根节点的左右子树深度差最多相差1
- 根节点的左右子树也是平衡二叉树
LL 型：支撑点转换、顺时针旋转、旋转优先原则整理
RR 型：支撑点转换、逆时针旋转、旋转优先原则整理
LR 型：左子树支撑点转换、逆时针旋转、根支撑点转换、顺时针旋转
RL 型：右子树支撑点转换、顺时针旋转、根支撑点转换、逆时针旋转
红黑树
- 每个结点要么是红色，要么是黑色
- 根节点必须是黑色
- 红色结点不能连续
- 任何一个结点到叶子的所有路径都包含相同数目的黑色节点
- 任何一个结点的左右子树高度差不会超过矮的一方（接*衡的二叉树）