今天主要復習下數據結構的東西 

1. 自平衡二叉查找樹

   1. AVL樹（高平衡樹）(wiki)
      1. 特性：任何節點的兩個子樹的高度最大差別為一
      2. 時間復雜度：查找、插入和刪除在平均和最壞情況下都是O（log n）
   2. 紅黑樹（對稱二叉B樹）(wiki)
      1. 特性：
         1. 節點是紅色或黑色
         2. 根是黑色
         3. 所有葉子都是黑色（葉子是NIL節點）
         4. 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
         5. 從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。
      2. 優勢：
         1. 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長，在高度上的理論上限允許紅黑樹在最壞情況下都是高效的
         2. 統計性能好
      3. 用途：用來構造關聯數組（Map）和集合（Set）

2. B樹

   1. B-樹 (百度百科)
      1. 特性：關鍵字分布在整顆樹中，查找成功立即結束（區別于B+樹）
      2. 性能：搜索效率等價于二分查找
      3. 用途：常用于文件引索系統
   2. B+樹
      1. 特性：每個關鍵字不保存數據，只用來索引，所有數據都保存在葉子節點，查找成功也要跳到葉子節點才結束（區別于B-樹）
      2. 用途：通常用于數據庫和操作系統的文件系統中
   3. B*樹
      1. B+樹的變體，在B+樹的非根和非葉子結點再增加指向兄弟的指針；B樹定義了非葉子結點關鍵字個數至少為(2/3)M，即塊的最低使用率為2/3（代替B+樹的1/2）；

3. 鍵樹

   1. 鍵樹（數字查找樹）
      1. 每條通往葉子節點的路徑都是一個關鍵字符串
   2. trie樹（字典樹）
      1. 典型應用是用于統計，排序和保存大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計
      2. 優點：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希表高

參見我的另一篇博客：some-sort-algorithms這里用java再實現一遍，代碼比較多，放到另一篇博客去了：some-sort-algorithms-java

1. 二分查找