知识点1-树（Trie树、红黑树、B+树）

大纲：http://naotu.baidu.com/file/b49ccc722da46972dfe3a720cd414a11

1. Trie树：https://shenlvmeng.github.io/blog/2015/11/02/trie/

2. 红黑树：https://zh.wikipedia.org/zh-hans/%E7%BA%A2%E9%BB%91%E6%A0%91

性质：红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

1. 节点是红色或黑色。
2. 根是黑色。
3. 所有叶子都是黑色（叶子是NIL节点）。
4. 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
   红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。

讲的很好的文章：https://www.jianshu.com/p/37c845a5add6

Q1：JDK 中 TreeMap 和 TreeSet，1.8 之后的 HashMap 和 ConcurrentHashMap。

TreeMap 和 TreeSet:
TreeMap 的实现是红黑树算法，TreeSet里面绝大部分方法都是直接调用TreeMap方法来实现的。
相同点：
TreeMap和TreeSet都是有序的集合，也就是说他们存储的值都是排好序的。
TreeMap和TreeSet都是非同步集合，因此他们不能在多线程之间共享，不过可以使用方法Collections.synchroinzedMap()来实现同步。
运行速度都要比Hash集合慢，他们内部对元素的操作时间复杂度为O(logN)，而HashMap/HashSet则为O(1)。
不同点：
最主要的区别就是TreeSet和TreeMap分别实现Set和Map接口；
TreeSet只存储一个对象，而TreeMap存储两个对象Key和Value（仅仅key对象有序）；
TreeSet中不能有重复对象，而TreeMap中可以存在。
HashMap 和 ConcurrentHashMap：https://juejin.im/post/5b551e8df265da0f84562403#heading-16

Q2：介绍二叉查找树、23查找树，再介绍红黑树原理

二叉查找树（Binary Search Tree，简称BST）是一棵二叉树，它的左子节点的值比父节点的值要小，右节点的值要比父节点的值大。它的高度决定了它的查找效率。
2-3树：2-节点，含有一个键和两条链接；3-节点，含有两个键和三条链接；一棵完美平衡的2-3树中所有空链到根节点的距离都应该是相同的。

Q3：与 B+ 树进行比较

b+树：
1）B+树包含2种类型的结点：内部结点（也称索引结点）和叶子结点。根结点本身即可以是内部结点，也可以是叶子结点。根结点的关键字个数最少可以只有1个。
2）B+树与B树最大的不同是内部结点不保存数据，只用于索引，所有数据（或者说记录）都保存在叶子结点中。
3） m阶B+树表示了内部结点最多有m-1个关键字（或者说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录。
4）内部结点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都小于它，右子树中的key都大于等于它。叶子结点中的记录也按照key的大小排列。
5）每个叶子结点都存有相邻叶子结点的指针，叶子结点本身依关键字的大小自小而大顺序链接。