字典樹的數據結構

字典樹，即 Trie 樹，又稱單詞查找樹或鍵樹，是一種樹形結構。典型應用是用於統計和排 序大量的字符串(但不僅限於字符串)，所以經常被搜索引擎系統用於文本詞頻統計。
它的優點是:最大限度地減少 無謂的字符串比較，查詢效率 比哈希表高。

字典樹的基本性質

1. 結點本身不存完整單詞。
2. 從根結點到某一結點，路徑上經過的字符連接起來，為該結點對應的 字符串。
3. 每個結點的所有子結點路徑代表的字符都不相同。

字典樹的核心思想

Trie 樹的核心思想是空間換時間。
利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。

並查集

適用場景：組團、配對問題。

基本操作

• makeSet(s):建立一個新的並查集，其中包含 s 個單元素集合。
• unionSet(x, y):把元素 x 和元素 y 所在的集合合併，要求 x 和 y 所在
  的集合不相交，如果相交則不合並。
• find(x):找到元素 x 所在的集合的代表，該操作也可以用於判斷兩個元 素是否位於同一個集合，只要將它們各自的代表比較一下就可以了。

高級搜索

1. 樸素搜索
2. 優化方式:不重複(fibonacci)、剪枝(生成括號問題)

3. 搜索方向:

   • DFS: depth first search 深度優先搜索
   • BFS: breadth first search 廣度優先搜索
   • 雙向搜索
   • 啓發式搜索

平衡二叉樹 AVL 樹

1. 發明者 G. M. Adelson-Velsky 和 Evgenii Landis 。
2. Balance Factor(平衡因子): 是它的左子樹的高度減去它的右子樹的高度(有時相反)。 balancefactor={-1, 0, 1}
3. 通過旋轉操作來進行平衡(四種)。
4. 平衡二叉樹有多種，常見為 AVL 樹、紅黑樹。

旋轉操作

1. 左旋
2. 右旋
3. 左右旋
4. 右左旋