1.哈夫曼樹
給定n個(gè)權(quán)值作為n的葉子結(jié)點(diǎn)新荤，構(gòu)造一棵二叉樹揽趾，若帶權(quán)路徑長度達(dá)到最小，稱這樣的二叉樹為最優(yōu)二叉樹苛骨，也稱為哈夫曼樹(Huffman Tree)篱瞎。哈夫曼樹是帶權(quán)路徑長度最短的樹苟呐，權(quán)值較大的結(jié)點(diǎn)離根較近。
構(gòu)造哈夫曼樹：
假設(shè)有n個(gè)權(quán)值俐筋，則構(gòu)造出的哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)牵素。 n個(gè)權(quán)值分別設(shè)為 w1、w2澄者、…笆呆、wn，則哈夫曼樹的構(gòu)造規(guī)則為：
(1) 將w1粱挡、w2赠幕、…，wn看成是有n 棵樹的森林(每棵樹僅有一個(gè)結(jié)點(diǎn))询筏；
(2) 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹合并榕堰，作為一棵新樹的左、右子樹屈留，且新樹的根結(jié)點(diǎn)權(quán)值為其左、右子樹根結(jié)點(diǎn)權(quán)值之和测蘑；
(3)從森林中刪除選取的兩棵樹灌危，并將新樹加入森林；
(4)重復(fù)(2)碳胳、(3)步勇蝙，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹挨约。
2.AVL樹
二叉搜索樹： 若一個(gè)節(jié)點(diǎn)有左子樹味混，則左子樹的所有值均小于該節(jié)點(diǎn)的值，若一個(gè)節(jié)點(diǎn)有右子樹诫惭，那么右子樹的所有值必須小于該節(jié)點(diǎn)的值翁锡。
平衡二叉樹： 一棵平衡二叉樹的左右子樹的高度差不超過1，并且所有節(jié)點(diǎn)的左右子樹都滿足此條件夕土。
AVL樹： AVL是平衡二叉搜索樹馆衔。
AVL樹的旋轉(zhuǎn)： AVL樹的旋轉(zhuǎn)操作
