二叉树

每个节点最多有两个子节点。

满二叉树

除了叶子节点，每个节点都有左节点和右节点。

完全二叉树

二叉查找树

有序集合，节点大于左节点小于有节点。

平衡二叉树

AVL树

红黑树

自平衡的二叉查找树。左转、右转、变色。
我们先回顾一下概念，红黑树之所以叫红黑树，是因为它有这些约束：

1. 节点要么是红色要么是黑色
2. 根节点必须是黑色
3. 叶子节点挂两个空节点(逻辑上)是黑色
4. 每个红色节点有两个黑色子节点，推导出一条路径上不能有两个连续的红色节点
5. 每条路径上必须有相同数量的黑色节点

每一条规则都很简单，并且它们都在讲颜色的限制，正符合红黑树这个名字。我们开始做插入操作：新插入的节点是红色。
不需要做任何变色或者旋转的情况：
新插入的节点父节点是黑色，皆大欢喜。
需要做变色的情况：

1. 新插入的节点是根节点，根据rule2,颜色变成黑色，相当简单。
2. 如果它的父节点也是红色，违反了rule4，此时如果发现叔节点也是红色，那么将父与叔节点标记为黑色，祖节点为红色，然后把祖节点当作新插入的节点递归重复这一判断，直到根节点，将根节点颜色设置为黑色。

需要做变色与旋转的情况：
当叔节点是黑色，需要做旋转，这是此文的重点。
我们一般会使用左左，右右，左右，右左来表示插入节点与父节点所在的位置，然后根据这些位置来做旋转的应用。文字通常是难记的，放弃文字描述，而使用符号以及图像来记忆：
左左：/ 一根斜线(此时最好用手比划一下)，顶点表示祖节点，中间点表示父节点，底点表示插入节点
右右: \ 一根反斜线，表示同上
左右：< 一个小于号，顶点表示祖节点，中间尖点表示父节点，底点表示插入节点
右左：> 一个大于号，表示同上

B树

B+树

B*树

Trie树