本文參考： 樹結構參考文獻
[圖片上傳失敗...(image-83b557-1539180310707)]
[圖片上傳失敗...(image-d6bf01-1539180310707)]
性質1. 節點是紅色或黑色，根是黑色，所有葉子都是黑色
性質2. 每個紅色節點必須有兩個黑色的子節點。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點，即紅黑相間)，從任壹節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點(簡稱黑高)。
[圖片上傳失敗...(image-52c714-1539180310707)]
B+樹是B樹的變體，也是壹種多路搜索樹：
[圖片上傳失敗...(image-c2ce8e-1539180310707)]
B+ 樹的性質：
1.所有關鍵字都出現在葉子結點的鏈表中（稠密索引），且鏈表中的關鍵字恰好是有序的；
2.不可能在非葉子結點命中；
3.非葉子結點相當於是葉子結點的索引（稀疏索引），葉子結點相當於是存儲（關鍵字）數據的數據層；
4. 更適合文件索引系統。
所以，B*樹分配新結點的概率比B+樹要低，空間使用率更高。
Tire樹稱為字典樹，又稱單詞查找樹，Trie樹，是壹種樹形結構，是壹種哈希樹的變種。典型應用是用於統計，排序和保存大量的字符串（但不僅限於字符串），所以經常被搜索引擎系統用於文本詞頻統計。它的優點是：利用字符串的公***前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希樹高。
Tire樹的三個基本性質：
Tire樹的應用：
給出N個單詞組成的熟詞表，以及壹篇全用小寫英文書寫的文章，請妳按最早出現的順序寫出所有不在熟詞表中的生詞。在這道題中，我們可以用數組枚舉，用哈希，用字典樹，先把熟詞建壹棵樹，然後讀入文章進行比較，這種方法效率是比較高的。
給定N個互不相同的僅由壹個單詞構成的英文名，讓妳將他們按字典序從小到大輸出。用字典樹進行排序，采用數組的方式創建字典樹，這棵樹的每個結點的所有兒子很顯然地按照其字母大小排序。對這棵樹進行先序遍歷即可。
對所有串建立字典樹，對於兩個串的最長公***前綴的長度即他們所在的結點的公***祖先個數，於是，問題就轉化為求公***祖先的問題。
[圖片上傳失敗...(image-f00bd3-1539180310707)]
[圖片上傳失敗...(image-d70c23-1539180310707)]
[圖片上傳失敗...(image-8a3963-1539180310707)]
[圖片上傳失敗...(image-69461e-1539180310707)]
[圖片上傳失敗...(image-987993-1539180310707)]
[圖片上傳失敗...(image-58f33c-1539180310707)]
參考文獻：
1、 blogs.com/pinard/p/6050306.html
4、 /qq_33935254/article/details/55505472