平衡搜索树
2-3树
其实仔细来看2-3树好像是 B 树的一个特例，它规定了一个节点要么有一个 key 要么有两个 key。
- 如果有一个 key 那么他就有两个子节点，左边小于这个 key 右边大于这个 key
- 如果有两个 key 那么他就有三个子节点，左边小于，中间处于两者之间，右边大于
这样一来就会发现他其实也会处在插入的时候出现分裂的情况，当一个节点需要插入的时候我们先让他插入，这时候可能出现一个节点有三个 key 的情况，我们就打出四个分支，然后我们把中间的那个 key 分裂到父节点，然后左右的 key 分别作为左右子节点。
这时候我们能够发现当且仅当我们的根节点分裂的时候我们的 2-3 树的高度才会真正的加一。这也是和 B 树的性质相似的。
2-3 树最好情况就是当所有的节点都是 3 key 节点的时候，这时候我们的树高度最小，而最坏情况自然也就是一个二叉树的时候。
红黑树
红黑树我们可以把它看做为 2-3 树的变种，也就是说我们可以在 2-3 上进行一些改造生成对应的红黑树。一般来说我们就是将那些具有三个子节点的节点拆分成两个节点，key 大的那个作为根，小的那个作为左子节点，然后他们之间使用红色连接起来（用红色连接的意思就是父节点是黑的，子节点是红的），也就可以看出红黑树更偏向于左边。下面是一个具体的例子：
红黑树的三个基本操作：
左旋转
从第一个图到第二个，这个在什么情况下需要呢？当我们插入一个新节点的时候我们发现插入后就是图一的情况，这时候我们还原到 2-3 树我们发现因为 s 节点更大，所以 s 节点应该是根节点， e 节点应该是 s 节点的子节点才对。所以产生了这样的操作！
所以说，当我们插入一个节点的时候我们发现插入到了右边的节点了我们就需要左旋转进行调整。
右旋转
右旋转刚和和左旋转相反。
颜色翻转
颜色翻转就是
当红黑树是这种情况的时候我们会发现他对应的 2-3 树是有问题的，需要进行分裂，所以说这里的颜色翻转就是把他的子节点都表示为黑色，自己变成红色。
红黑树的插入操作
上面看到了关于红黑树的三个基本操作，这三个操作其实在我们插入的时候都是用的上的，并且重要的是在 AVL 树我们也可以仿照这种思想去完成平衡操作。
上面一般就是我们进行插入的时候会遇到的所有需要处理的情况。
- 首先看第一个，就是在插入的时候 C 被插入到了左节点，这时候根据 2-3 树的规定我们是需要进行旋转的，把 C 作为根节点，就类似于把 C 提起来，然后 A 节点随着重力到达左节点。也就是左旋转
- 第二种情况就是左右节点都是红节点的时候我们就需要进行颜色翻转，让左右子节点都变黑，根节点边城红节点
- 第三种情况一开始属于有两个连续的红节点在左边，这时候我们仅仅需要进行一次右旋转就变成了第二种情况了
- 第四种情况我们可以看到首先进行一次左旋转，然后右旋转又再次回到了第二种情况，也就是颜色翻转 所以说无论怎么变化我们只需要这三个基本操作我们就可以保证红黑树的性质不被破坏。 所以最终的代码就是
我们的 AVL 树完全可以按照这个套路在接着写。