資料結構學習：平衡二叉樹和哈夫曼樹
平衡二叉樹：
樹上任一結點的左子樹和右子樹的深度之差不超過1
結點的平衡因子 = 左子樹高 - 右子樹高
是以平衡二叉樹結點的平衡因子絕對值小于等于1
平衡二叉樹的插入
從插入點往回找第一個不平衡結點，調整以該結點為根的子樹
最小不平衡子樹：
從插入點往回找第一個不平衡結點，以該結點為根的子樹
在插入操作中，隻要将最小不平衡子樹調整為平衡，則其他祖先結點都會恢複平衡
調整最小不平衡子樹
目标：
1.恢複平衡
2.保持二叉排序樹的特性
調整最小不平衡子樹A
LL: 在A的左孩子的左子樹中插入導緻不平衡
RR: 在A的右孩子的右子樹中插入導緻不平衡
LR: 在A的左孩子的右子樹中插入導緻不平衡
RL:在A的右孩子的左子樹中插入導緻不平衡
1)LL平衡旋轉(右單旋轉)。
由于在結點A的左孩子(L)的左子樹（(L)上插入了新結點，A的平衡因子由1增至2，導緻以A為根的子樹失去平衡，需要一次向右的旋轉操作。
将A的左孩子B向右上旋轉代替A成為根結點，将A結點向右下旋轉成為B的右子樹的根結點，而B的原右子樹則作為A結點的左子樹。
Eg:
代碼思路：
2）RR平衡旋轉（左單旋轉)。
由于在結點A的右孩子（R)的右子樹®上插入了新結點，A的平衡因子由-1減至-2，導緻以A為根的子樹失去平衡，需要一次向左的旋轉操作。
将A的右孩子向左上旋轉代替A成為根結點信将A結點向在下旋轉戊為B的左子樹的根結點，而B的原左子樹則作為A結點的右子樹
代碼思路：
3)LR平衡旋轉（先左後右雙旋轉）。
由于在A的左孩子(L)的右子樹®上插入新結點，A的平衡因子由1增至2，導緻以A為根的子樹失去平衡，需要進行兩次旋轉操作，先左旋轉後右旋轉。
先将A結點的左孩子B的右子樹的根結點C向左上旋轉提升到B結點的位置，然後再把該C結點向右上旋轉提升到A結點的位置
4）RL平衡旋轉（先右後左雙旋轉）。
由于在A的右孩子(R）的左子樹(L)上插入新結點，A的平衡因子由-1減至-2,導緻以A為根的子樹失去平衡，需要進行兩次旋轉操作，先右旋轉後左旋轉。
先将A結點的右孩子B的左子樹的根結點C向右上旋轉提升到B結點的位置，然後再把該C結點向左上旋轉提升到A結點的位置
哈夫曼樹
結點的權：
有某種現實含義的數值
結點的帶權路徑長度：
從樹的根節點到該結點的路徑長度（經過的邊數）與該結點上權值的乘積
樹的帶權路徑長度：
樹中所有葉結點的帶權路徑長度之和（WPL）
在含有n個帶權葉結點的二叉樹中，其中帶權路徑長度WPL最小的二叉樹成為哈夫曼樹
也稱為最優二叉樹
哈夫曼樹的構造
給定n個權值分别為w1, w2… wn,的結點,構造哈夫曼樹的算法描述如下:
1）将這n個結點分别作為n棵僅含一個結點的二叉樹，構成森林F.
2）構造一個新結點，從F中選取兩棵根結點權值最小的樹作為新結點的左、右子樹，并且将新結點的權值置為左、右子樹上根結點的權值之和。
3) 從F中删除剛才選出的兩棵樹,同時将新得到的樹加入F中。
4)重複步驟2）和3）,直至F中隻剩下一棵樹為止。
特點：
1）每個初始結點最終都成為葉結點，且權值越小的結點到根節點的路徑長度越大
2）哈夫曼樹的結點總數為2n-1
3）哈夫曼樹中不存在度為1的結點
4）哈夫曼樹不唯一，但WPL必然相同且為最優
固定長度編碼：
每個字元用相等長度的二進制位表示
可變長度編碼：
允許對不同字元用不等長的二進制位表示
若沒有一個編碼是另一個編碼的字首，則這樣的編碼為字首編碼