大綱：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
性質(zhì)：紅黑樹是每個節(jié)點都帶有顏色屬性的二叉查找樹吊洼，顏色為紅色或黑色。在二叉查找樹強制一般要求以外制肮，對于任何有效的紅黑樹我們增加了如下的額外要求：
- 節(jié)點是紅色或黑色冒窍。
- 根是黑色。
- 所有葉子都是黑色（葉子是NIL節(jié)點）弄企。
- 每個紅色節(jié)點必須有兩個黑色的子節(jié)點超燃。（從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點。）
- 從任一節(jié)點到其每個葉子的所有簡單路徑都包含相同數(shù)目的黑色節(jié)點拘领。
紅黑樹相對于AVL樹來說意乓，犧牲了部分平衡性以換取插入/刪除操作時少量的旋轉(zhuǎn)操作，整體來說性能要優(yōu)于AVL樹约素。
Q1：JDK 中 TreeMap 和 TreeSet届良，1.8 之后的 HashMap 和 ConcurrentHashMap。
TreeMap 和 TreeSet:
TreeMap 的實現(xiàn)是紅黑樹算法圣猎，TreeSet里面絕大部分方法都是直接調(diào)用TreeMap方法來實現(xiàn)的士葫。
相同點：
TreeMap和TreeSet都是有序的集合，也就是說他們存儲的值都是排好序的送悔。
TreeMap和TreeSet都是非同步集合慢显，因此他們不能在多線程之間共享，不過可以使用方法Collections.synchroinzedMap()來實現(xiàn)同步欠啤。
運行速度都要比Hash集合慢荚藻，他們內(nèi)部對元素的操作時間復(fù)雜度為O(logN)，而HashMap/HashSet則為O(1)洁段。
不同點：
最主要的區(qū)別就是TreeSet和TreeMap分別實現(xiàn)Set和Map接口应狱；
TreeSet只存儲一個對象，而TreeMap存儲兩個對象Key和Value（僅僅key對象有序）祠丝；
TreeSet中不能有重復(fù)對象疾呻，而TreeMap中可以存在。
HashMap 和 ConcurrentHashMap：https://juejin.im/post/5b551e8df265da0f84562403#heading-16
Q2：介紹二叉查找樹写半、23查找樹岸蜗，再介紹紅黑樹原理
二叉查找樹（Binary Search Tree，簡稱BST）是一棵二叉樹叠蝇，它的左子節(jié)點的值比父節(jié)點的值要小璃岳，右節(jié)點的值要比父節(jié)點的值大。它的高度決定了它的查找效率。
2-3樹：2-節(jié)點矾睦，含有一個鍵和兩條鏈接；3-節(jié)點炎功，含有兩個鍵和三條鏈接枚冗；一棵完美平衡的2-3樹中所有空鏈到根節(jié)點的距離都應(yīng)該是相同的。
Q3：與 B+ 樹進行比較
b+樹：
1）B+樹包含2種類型的結(jié)點：內(nèi)部結(jié)點（也稱索引結(jié)點）和葉子結(jié)點蛇损。根結(jié)點本身即可以是內(nèi)部結(jié)點赁温，也可以是葉子結(jié)點。根結(jié)點的關(guān)鍵字個數(shù)最少可以只有1個淤齐。
2）B+樹與B樹最大的不同是內(nèi)部結(jié)點不保存數(shù)據(jù)股囊，只用于索引，所有數(shù)據(jù)（或者說記錄）都保存在葉子結(jié)點中更啄。
3） m階B+樹表示了內(nèi)部結(jié)點最多有m-1個關(guān)鍵字（或者說內(nèi)部結(jié)點最多有m個子樹）稚疹，階數(shù)m同時限制了葉子結(jié)點最多存儲m-1個記錄。
4）內(nèi)部結(jié)點中的key都按照從小到大的順序排列祭务，對于內(nèi)部結(jié)點中的一個key内狗，左樹中的所有key都小于它，右子樹中的key都大于等于它义锥。葉子結(jié)點中的記錄也按照key的大小排列柳沙。
5）每個葉子結(jié)點都存有相鄰葉子結(jié)點的指針，葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接拌倍。
