数据结构：红黑树
二叉搜索树BST(Binary Search Tree):
该树特点是任意一个节点的左子树的节点都比它小，右子树的节点都比它大。
例如：
BST带来的好处：
- 不管是插入还是读取的时候都需要跟每一层中1个节点比较就可以了。
例如上面的树中，找10节点，先比较7，10>7，走树的右半部分，左半部分就不用再比较了。然后10<11，走左边，10=10就找到了。查询的时间复杂度依赖树的深度。同理，写入节点的时候也一样，例如插入9，9>7，走右部分，9<11，然后9<10就插入到10的左边
当有n个节点，那么树的深度就是logn,即BST的时间复杂度是：O(logn).
还有一个搜索方式是：二分查找法
二分查找法是说一个有序的数，在找值的时候先找中间的这个值，如果当前值比中间值大，就选择中间值的右边查找，反之选择中间值的左边查找。假设当前值比中间值大，那么就在当前的中间值的右边重新选择中间值，看当前值是否比重新选择的中间值大，如果是就再右边进行2分。
二分查找法和BST还是很像的，但是有序数组最差的情况下是logn，但是BST最差情况下是要退化成O(n)的。
为什么很多情况下，都使用的是BST而不是有序数组的二分查找法？
答：在插入的时候，有序数组的查找是用的2分查找，但是其插入是比较费劲的。因为首先插入一个值同样先需要查找到某个数需要插入的地方，需要把这个位置后面所有的数都网后挪1格，然后把数插进去，因为后面所有的数都需要往后移动1格，所以时间复杂度就成了O(n)。
BST的缺点：
- 当数据是连续自增和自减 的时候(如1、2、3、4、5..)最终会变成如下图，整个树状的结构就变成了线性结构了
所以这种情况下，时间复杂度就退化了。一般语言内部为我们实现的存储结构中，真正用原生BST的很少，都是经过优化的数据结构。
其中一种优化就是AVL树。
AVL树(自平衡二叉树)
特点：本身是BST，是BST的一种，只不过AVL需要满足一个条件：任意一个节点的左子树和右子树深度差小于等于1.因此，AVL的复杂度都是O(logn)，最差的情况下也是O(logn)
Red-Black Tree(红黑树):
特点：
- 每个节点要么是红节点要么是黑节点
- 其root节点是黑节点，
- 叶子节点是黑节点
- 红节点 的子节点必须是黑节点
- 新插入的节点是红节点【红节点在后面可能会有一个平衡的过程，所以红节点也有可能变成黑节点】
- 从任意一个节点出发，到叶子节点的路径上所拥有的黑节点数必须是一样的。
其中叶子节点是黑节点保证了整个树的一半以上是黑节点，且是满二叉树。
红黑树和AVL平衡的标准不一样：
- AVL的平衡是为了保证左子树和右子树的深度差<=1(比较严格的条件)
- 红黑树的平衡是为了2条路径上的黑节点数相同
所以红黑树路径上的黑节点数的上下界：
- 2条路径上的节点数相同
- 节点数差1倍【此时红节点数相同，因为红节点的子节点必须是黑节点，所以，此时的红节点和黑节点是交错的】
综上，红黑树的左右深度差一倍以内。【即红黑树要实现的最终效果】
所以红黑树要比AVL插入的条件更宽松。这种i相对宽松的条件使得插入节点时候变换是更少的，所以红黑树写的性能会更高一些。
面试题：jdk8中hashmap的实现每一个桶是一个链表，当链表长度达到8以上就会变成红黑树。那么jdk8为什么选择红黑树这种数据结构，而不是BST或AVL树。【或者：为什么TreeMap(继承SortMap)底层是红黑树而非AVL和BST】
BST是如果趋势比较明显，那么就会退化为链表。AVL树又没有红黑树的平衡条件宽松，使得节点插入的时候带来的整个树的变动没有红黑树小。红黑树的复杂度是O(logn)。为什么红黑树深度差一倍，复杂度还是O(logn)。这要看树的搜索过程的复杂度和插入的复杂度完全依赖于树的深度的，所以要看红黑树的复杂度能不能达到logn，就要看红黑树的深度是不是达到logn或者logn的常数倍。在AVL树中，保证了深度差是<=1，所以层数是logn层。
而在红黑树中，假设有n个节点=nr+nb,看树的深度是多少层，如果把树中所有的红节点都盖住不看，那么整棵树就是一颗AVL树。所以整棵树的层度是lognb层。现在要看红节点，红节点最差的情况下就是红黑相间，树的层数就会翻一倍=2*lognb层，最终的复杂度是O(2*lognb)=O(lognb)，其中的nb和n的关系是：黑节点的数至少占整个树的一半以上。所以最差的情况下，nb = n.所以红黑树最后的复杂度就是logn了。
红黑树的插入流程：
插入的节点是红节点，这时候主要判断的是父节点和父节点的兄弟节点（叔节点）.
真正的插入的时候对应的操作，可以访问https://visualgo.net/zh