哈夫曼樹

概念

考慮不同節(jié)點的權(quán)值，權(quán)值大的節(jié)點距離根節(jié)點近，權(quán)值小的節(jié)點距離根節(jié)點遠(yuǎn)。讓所有節(jié)點的訪問次數(shù)的距離最小的二叉樹，就是哈夫曼樹。

帶權(quán)路徑長度

樹的帶權(quán)路徑長度指樹中所有葉子節(jié)點到根節(jié)點的路徑長度與該葉子節(jié)點權(quán)值的乘積之和，如果在一棵二叉樹中共有n個葉子節(jié)點，用Wi表示第i個葉子節(jié)點的權(quán)值，Li表示第i個也葉子節(jié)點到根節(jié)點的路徑長度，則該二叉樹的帶權(quán)路徑長度

WPL=W1*L1 + W2*L2 + ... Wn*Ln。

哈夫曼樹的特性

1. 對于同一組權(quán)值，所能得到的赫夫曼樹不一定是唯一的。
2. 赫夫曼樹的左右子樹可以互換，因為這并不影響樹的帶權(quán)路徑長度。
3. 帶權(quán)值的節(jié)點都是葉子節(jié)點，不帶權(quán)值的節(jié)點都是某棵子二叉樹的根節(jié)點。
4. 權(quán)值越大的節(jié)點越靠近赫夫曼樹的根節(jié)點，權(quán)值越小的節(jié)點越遠(yuǎn)離赫夫曼樹的根節(jié)點。
5. 赫夫曼樹中只有葉子節(jié)點和度為2的節(jié)點，沒有度為1的節(jié)點。
6. 一棵有n個葉子節(jié)點的赫夫曼樹共有2n-1個節(jié)點。

哈夫曼樹的構(gòu)造

赫夫曼樹的構(gòu)建步驟如下：

1. 將給定的n個權(quán)值看做n棵只有根節(jié)點（無左右孩子）的二叉樹，組成一個集合HT，每棵樹的權(quán)值為該節(jié)點的權(quán)值。
2. 從集合HT中選出2棵權(quán)值最小的二叉樹，組成一棵新的二叉樹，其權(quán)值為這2棵二叉樹的權(quán)值之和。
3. 將步驟2中選出的2棵二叉樹從集合HT中刪去，同時將步驟2中新得到的二叉樹加入到集合HT中。
4. 重復(fù)步驟2和步驟3，直到集合HT中只含一棵樹，這棵樹便是赫夫曼樹。

假如給定如下5個權(quán)值：

則按照以上步驟，可以構(gòu)造出如下面左圖所示的赫夫曼樹，當(dāng)然也可能構(gòu)造出如下面右圖所示的赫夫曼樹，這并不是唯一的

平衡二叉樹(AVL樹)

定義

一個樹的左子樹和右子樹的深度相差絕對值不超過1，那么就是一個平衡二叉樹。

最小不平衡子樹

距離插入結(jié)點最近的，而且平衡因子的絕對值大于1的結(jié)點為根的子樹，稱為最小不平衡子樹。

構(gòu)建AVL樹(平衡二叉樹)

構(gòu)建平衡二叉樹時，會出現(xiàn)一個樹失衡的情況，那么當(dāng)一個樹從平衡二叉樹轉(zhuǎn)變成不平衡二叉樹時，需要進(jìn)行處理。處理方式包括左旋和右旋。

AVL樹中的結(jié)點的數(shù)據(jù)結(jié)構(gòu)可以表示為:

/**
 * Created by apple on 16/7/30.
 */
public class AVLNode {

    //節(jié)點的值
    public int key;

    //節(jié)點的平衡度
    public int balance;

    //分別指向節(jié)點的左孩子、右孩子與父節(jié)點
    public AVLNode left, right, parent;

    /**
     * @function 默認(rèn)構(gòu)造函數(shù)
     * @param k
     * @param p
     */
    AVLNode(int k, AVLNode p) {
        key = k;
        parent = p;
    }
}

Rebalance:平衡調(diào)整

AVL樹的調(diào)整過程很類似于數(shù)學(xué)歸納法，每次在插入新節(jié)點之后都會找到離新插入節(jié)點最近的非平衡葉節(jié)點，然后對其進(jìn)行旋轉(zhuǎn)操作以使得樹中的每個節(jié)點都處于平衡狀態(tài)。

Left Rotation:左旋,右子樹右子節(jié)點

當(dāng)新插入的結(jié)點為右子樹的右子結(jié)點時，我們需要進(jìn)行左旋操作來保證此部分子樹繼續(xù)處于平衡狀態(tài)。(左下右上)

復(fù)雜一點的情況

如果要上去的有左結(jié)點，那么這個左結(jié)點放在要下來的右結(jié)點的右邊

/**
 * @param a
 * @return
 * @function 左旋操作
 */
private AVLNode rotateLeft(AVLNode a) {

    //指向當(dāng)前節(jié)點的右孩子
    AVLNode b = a.right;

    //將當(dāng)前節(jié)點的右孩子掛載到當(dāng)前節(jié)點的父節(jié)點
    b.parent = a.parent;

    //將原本節(jié)點的右孩子掛載到新節(jié)點的左孩子
    a.right = b.left;

    if (a.right != null)
        a.right.parent = a;

    //將原本節(jié)點掛載到新節(jié)點的左孩子上
    b.left = a;

    //將原本節(jié)點的父節(jié)點設(shè)置為新節(jié)點
    a.parent = b;

    //如果當(dāng)前節(jié)點的父節(jié)點不為空
    if (b.parent != null) {
        if (b.parent.right == a) {
            b.parent.right = b;
        } else {
            b.parent.left = b;
        }
    }

    //重新計算每個節(jié)點的平衡度
    setBalance(a, b);

    return b;
}

Right Rotation:右旋,左子樹左子節(jié)點

當(dāng)新插入的結(jié)點為左子樹的左子結(jié)點時，我們需要進(jìn)行右旋操作來保證此部分子樹繼續(xù)處于平衡狀態(tài)。(右下左上)

復(fù)雜的情況

如果要上去的結(jié)點有右結(jié)點，那么這個右結(jié)點就放在要下來的結(jié)點的左邊

private AVLNode rotateRight(AVLNode a) {

    AVLNode b = a.left;
    b.parent = a.parent;

    a.left = b.right;

    if (a.left != null)
        a.left.parent = a;

    b.right = a;
    a.parent = b;

    if (b.parent != null) {
        if (b.parent.right == a) {
            b.parent.right = b;
        } else {
            b.parent.left = b;
        }
    }

    setBalance(a, b);

    return b;
}

Left-Right Rotation:先左旋再右旋,左子樹右子節(jié)點

在某些情況下我們需要進(jìn)行兩次旋轉(zhuǎn)操作，譬如在如下的情況下，某個結(jié)點被插入到了左子樹的右子結(jié)點：(這種情況下，需要旋轉(zhuǎn)結(jié)點的根結(jié)點的父結(jié)點和子結(jié)點都比它大)

1. 原始樹

   
   

2. 首先要以A為軸進(jìn)行左旋操作

   
   

3. 然后需要以C為軸進(jìn)行右旋操作

   
   

4. 最終得到的又是一棵平衡樹

   
   

復(fù)雜情況

private AVLNode rotateLeftThenRight(AVLNode n) {
    n.left = rotateLeft(n.left);
    return rotateRight(n);
}

Right-Left Rotation:先右旋再左旋,右子樹左子節(jié)點

1. 原始的樹

   
   

2. 先右旋

   
   

3. 再左旋

   
   

4. 結(jié)果

   
   

復(fù)雜情況

private AVLNode rotateRightThenLeft(AVLNode n) {
    n.right = rotateRight(n.right);
    return rotateLeft(n);
}

數(shù)據(jù)結(jié)構(gòu)導(dǎo)讀目錄