不同数据结构
- 无序链表 直接遍历循环一遍，O(n)
- 有序数组
二分查找法，O(lgn)。
但插入效率不高，二分查找插入后，后面数据要全后移一位，O(lgn) + O(n) = O(n) - 查找二叉树
将数据结构直接做成二分+链式的。规则 左结点 < 根结点 < 右结点
这样查找、插入都是对数级别 O(lgn)。二分查完后直接末尾插入。
但查找二叉树在最坏的情况下，等同于一个有序链式数组，查找效率又变回了O(n)
所以我们引入平衡二叉树概念，让二叉树更满~
- 平衡查找树（2-3结点查找树）
平衡的概念是，保证左右子树的高度差不能大于1，让树铺更满，达到任何情况下都是 lgn。
原有1对2叫2-结点，规则不变。
新增一种2对3结点，称为3-结点。
规则 左结点 < 根结点-左 < 中结点 < 根结点-右 < 右结点
时间复杂度一览
平衡查找树
新规则依然可以类似的二分查找，从上到下依次判断。
每个结点跟俩元素根据大小，判断应该走哪个分支。
但插入会复杂一点，不同于普通查找树插入到末尾结点的下面空位置。
而是直接塞到末尾结点上，则插入后：
2-结点变成3-结点。
3-结点变成4-结点。这个就要升级一下了，将中间的元素挤上去变成一个两层的2-结点树
在整个树结构里，就会将元素挤到根结点里，然后根结点等于也插入了一个元素，规则一样。
整个流程类似于三进制系统，末尾+1后向前依次判断是否进一位。
所以不同于普通查找树从上到下末尾不停插。
平衡二叉树是从下到上不停的挤上去，这样就保证了平衡。
红黑树（平衡查找树的一种实现）
2-3查找树是改造结点+分支，红黑树思想是只改分支链接线。
红链接：将两个2-结点连起来，等同于一个3-结点。
黑链接：和之前的普通连接一样。
被某个颜色链接指向的结点，也叫做红/黑结点。根结点是黑。
注意：
- 红链接均为左链接
- 没有结点同时包含俩红链接
- 该树是 完美黑色平衡的。即任意空链接到根结点的路径上黑链接数量相同。
红链接如果横着画，就更好理解了，直接看上去就和2-3结点树差不多，比较满~平衡~
等价于一个2-3结点，所以lgn有保证，且又不破坏传统二叉树的1对2结构。 那么如何构建呢？ 2-3树永远都是在末尾的结点直接插入一个新元素。 同理红黑树则永远在末尾插入一个红链接元素，相当于在这个节点内插入。 然后在插入后要考虑是否挤上去的问题，除此之外红黑树还需要保证红链接在左的特性。 这里就要用到 旋转 去保证操作后的红黑规则。
主要分为左转和右旋
左旋是为了把红链接从右边旋转到左边，保证规则。
右旋转则是把红链接从左转到右边，为什么逆着规则呢？
如果连续俩左红链接不平衡了，所以要右旋转，调整成一个完整的1对2结点
实际流程如下：
对于2-结点插入新元素
对于3-结点插入新元素
2-结点很简单，插入后右红左旋转成左红
3-结点比较复杂，不同情况，最终希望转成一个左右红，然后进一位（左右红变黑，指向根结点的链接变红）
总的依然是从下到上，依次判断左旋先都保证红链接在左。然后如果仨是连续俩左链式失衡，则根结点右旋转变成一个平衡的左右红，然后再颜色变化进一位升级。
其实和2-3结点很类似，颜色变化就类似于4-结点往上挤一位
只不过多了旋转用来保证红链接在左，以及进一位之前的位置调整
综上
- 右红+左黑，左旋转调整成左红右黑
- 左红+左子左红，右旋转成双红，然后颜色变换
应用
Java中有封装基于红黑树的实现 java.util.TreeMap
问题
Q：为什么红链接不能在右？ A：其实都都行，方便计算代码实现
