平衡树
1. 二叉搜索树的优点
二叉搜索树作为数据存储的结构，最大的优势是可以快速找到给定关键字的项，并且可以快速的实现插入和删除数据操作
因为二叉搜索树采用了二分查找的策略
2. 二叉搜索树存在的问题
但是二叉搜索树有一个麻烦的问题：若插入的数据是一个有序数列(从小到大/从大到小)，会造成二叉搜索树在某个方向上深度很深，
使得数据在树的左右分布不均匀，二叉搜索树变成不平衡树，极端情况下，树会变化变成一个链表，事件复杂度由O(log(n)) -->O(N)
3. 因此，为了保证二叉搜索树的搜索效率，应该尽量使得树的左右子孙个数相等，使得二叉搜索树变成平衡树
4. 常见的平衡树
AVL树：最早的一种平衡树(每个节点多保存了一个数据)，但是AVL树插入和删除操作效率不如红黑树
红黑树：
1. 通过一些特性来保证树的平衡
2. 有余数平衡树，事件复杂度为O(log(n))
3. 插入/删除效率要高于AVL树，所以平衡树的应用基本都是红黑树
5. 红黑树简介
1. 红黑树是数据结构中的难点，难点中的难点
2. 大型的网络公司才会考察红黑树
3. 小公司基本不考察红黑树，因为难
6. 红黑树的规则
1. 节点是红色或者黑色的
2. 根节点是黑色
3. 每个叶节点都是黑色的空节点(NIL节点)
4. 每个红色节点的两个子节点都是黑色的(每个叶节点到根的所有路径上不能由两个连续的红色节点)
5. 从任何节点到其每个叶子节点的所有路径包含相同的黑色节点
上述五条红黑树的规则可以保证以下特性：
1. 从根到叶的最长可能路径，不会超过最短可能路径的两倍
如何做到的呢？
。。。
2. 红黑树基本是平衡的
3. 虽然不能保证绝对的平衡，到那时可以确保在最坏的情况下依然是高效的