二叉樹等其他數據結構整理

數據結構 MySQL 科技優家 2017-04-05

深度優先周遊:先根次序、後根次序、中根次序。

廣度優先周遊:逐層訪問。

哈夫曼樹(最優二叉樹):葉節點權值之和最小。算法題目常常給若干葉節點,讓你構造最優二叉樹。只需要從最小的兩個葉節點值開始,其父節點為兩者之和,並與第三個最小葉節點成為兄弟節點,依次類推,形成最優二叉樹。

三種經典的數據類型來實現高效的符號表:二叉查找樹(B樹)、紅黑樹、散列表。可以看看MYSQL索引的實現,雖然沒有用二叉查找樹和紅黑樹,但是用到B+樹(多路搜索樹)和散列表(hash)。可參考

B+ 的搜索與 B- 樹也基本相同,區別是 B+ 樹只有達到葉子結點才命中( B- 樹可 以在非葉子結點命中),其性能也等價於在關鍵字全集做一次二分查找;(即B+樹的子樹個數與根節點關鍵字個數相同,且關鍵字出現在葉子節點的鏈表裡),所以mysql索引使用中MyISAM使用B+,但索引文件和數據分開的;葉子節點存放物理地址,InnoDB也使用B+,葉子節點直接存放數據,其數據文件本身按B+結構形成的索引文件。

二叉查找數:和快速排序幾乎一樣。二叉查找樹的原則是根節點大於左子節點,小於右子節點。

平衡查找樹:為了避免動態插入維持平衡的高代價,所以出現三節點或更多節點,而且每個節點允許保存多個鍵值。

紅黑樹:平衡二叉查找樹,

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

性質2. 根節點是黑色。

性質3 每個葉節點(NIL節點,空節點)是黑色的。

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

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

平衡二叉樹(AVL樹):它的左子樹和右子樹都是平衡二叉樹,且左子樹和右子樹的深度之差的絕對值不超過1。

TreeMap實現採用紅黑樹卻不適用二叉查找樹?

其實這個問題就是在問紅黑樹相對於排序二叉樹的優點。我們都知道排序二叉樹雖然可以快速檢索,但在最壞的情況下:如果插入的節點集本身就是有序的,要麼是由小到大排列,要麼是由大到小排列,那麼最後得到的排序二叉樹將變成鏈表:所有節點只有左節點(如果插入節點集本身是大到小排列);或所有節點只有右節點(如果插入節點集本身是小到大排列)。在這種情況下,排序二叉樹就變成了普通鏈表,其檢索效率就會很差。

為了改變排序二叉樹存在的不足,紅黑樹誕生了,它是一個更高效的檢索二叉樹,因此常常用來實現關聯數組。追求的是局部平衡,而不是平衡二叉樹的嚴格平衡。借來一張圖展示:

二叉樹等其他數據結構整理

相關推薦

推薦中...