資料結構——樹 相關知識

樹作為最重要的資料結構之一，有很多相關的知識mark在此用以查閱

樹

樹是一種層次結構，形如一個倒立的樹。根節點在最上方，葉節點向下延申。其中最常用的樹為二叉樹，即每個節點最多有兩個子節點。

空樹

當節點為0時，則稱該樹為空樹

樹的深度

僅有一個根節點的樹的深度為1，其他依次類推（從上往下）

樹的高度

從葉節點到樹根節點（從下往上）

平衡二叉樹（Balanced Binary Tree）

一顆空樹，或左右兩顆子樹的高度差不超過1，且左右兩顆子樹也同為平衡二叉樹（遞歸表述）

二叉排序樹（Binary Sort Tree）

一顆空樹，或左子樹的節點都小于根節點，右子樹的節點都大于根節點，且左右兩顆子樹也同為排序樹（遞歸表述）

* 可以使用DSF的LRD中序來實作有序周遊

滿二叉樹

除了最後一層節點外其餘節點都擁有子節點的二叉樹

完全二叉樹 

最後倒數第二層所擁有的子節點，自左向右排列，其餘節點都擁有子節點的二叉樹。

 哈夫曼樹

帶權路徑長度之和最小的樹（權值越大越淺）

prim算法适合稠密圖，kruskal算法适合簡單圖 👉最小生成樹

TRIE

根據詞頻來儲存的單詞查找樹，字首樹

哈希樹

為了便于查找，選取最小的十個質數，也就是2，3，5，7，11，13，17，23，29，31來mod，能包括的數就有10555815270個 

紅黑樹

 紅黑樹是每個節點都帶有顔色屬性的二叉查找樹，顔色或紅色或黑色。在二叉查找樹強制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:

性質1：節點是紅色或黑色。

性質2：根節點是黑色。

性質3：每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)

性質4：從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

AVL樹

 平衡二叉查找樹

紅黑樹和AVL樹一樣都對插入時間、删除時間和查找時間提供了最好可能的最壞情況擔保。