天天看點

資料結構——樹 相關知識

樹作為最重要的資料結構之一,有很多相關的知識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樹一樣都對插入時間、删除時間和查找時間提供了最好可能的最壞情況擔保。 

繼續閱讀