数据结构

1、红黑树：

是一种自平衡的二叉树，

1. 每个节点都有红色或黑色
2. 树的根始终是黑色的 (黑土地孕育黑树根， )
3. 没有两个相邻的红色节点（红色节点不能有红色父节点或红色子节点，并没有说不能出现连续的黑色节点）
4. 从节点（包括根）到其任何后代NULL节点(叶子结点下方挂的两个空节点，并且认为他们是黑色的)的每条路径都具有相同数量的黑色节点

瞬间懵逼？了解一下印象就行，开始玩魔方都是要照着魔方公式一点点玩的，多玩几次就熟悉了。红黑树也一样，红黑树有两大操作:

1. recolor (重新标记黑色或红色)
2. rotation (旋转，这是树达到平衡的关键)

时间复杂度O(logN) 查找、插入、删除

平衡二叉树是左边子节点比父节点小，右边子节点比父节点大，左节点深度和右节点深度相同，或者右节点深度跟左节点深度相差1，比较严苛，需要不断的变化，使得二叉树平衡，损坏性能CPU。

红黑树是相对宽松的平衡二叉树，最差情况下，右节点深度跟左节点深度相差2倍

红黑树，超强动静图详解，简单易懂 - 知乎 (zhihu.com)

2、java集合容器

ConcurrentHashMap

3、排序算法

常见的排序算法——常见的10种排序 - sc_FlyingDreams - 博客园 (cnblogs.com)

冒泡排序

　　每轮依次比较相邻数字的大小，将大数字向后移动，最终达到有序状态。

选择排序

　　每轮比较将当前值与未排序的值依次比较，找出最小的值，将其与当前值交换，达到有序状态

插入排序

　　依次遍历数组，每次将当前值插入已经排好序的数组中，最终达到有序状态。

希尔排序

　　将整个数组划分为不同的组，一般以n/2的对应划分，将所有组中的元素分别进行插入排序，  排好序后再次以,(n/2)/2,....1的划分并排序，最终达到有序。

归并排序

　　将数组划分为不同的组，依次对所有的组排序，最后再对排好序的组进行合并，采用了递归的思想，可以自顶向下及自底向上

快速排序

　　将数组根据某一数值划分为两个独立部分，一部分比关键字小，一部分比关键字大，然后再分别对这两部分进行排列，达到整个序列有序。 

堆排序

　　将数组元素组织为堆的结构，包括大顶堆及小顶堆，依次取出头部元素，调整堆结构，最终达到有序。

计数排序

　　要求输入元素是确定范围且范围较小的，分配最大值与最小值之差的大小的空间，将出现的数字放入指定位置，如果重复则加1.放完后取出就有序了

桶排序

　　计数排序升级版，最好应用于均匀分布的数据，将数据分配到有限数量的桶中，单个桶再排序，如果数据都进了一个桶中，排序就基本没有用了。

基数排序

　　利用数字的位数，先按地位数字，将数组元素放入10个桶中，这样最后一位就拍好了，在取出，按次低位进行排序，在取出，值到最高位，再取出就有序了。