數(shù)據(jù)結(jié)構(gòu)-平衡二叉樹

定義

平衡二叉樹，是對二叉搜索樹的一種優(yōu)化。

向二叉搜索樹中插入元素時，不同的插入次序，將構(gòu)造出不同結(jié)構(gòu)的樹。通俗來講，就是會導(dǎo)致樹的深度和平均查找長度(ASL averge search length)不同；以下圖為例。

bst_tree_insert

明顯可以看出，中間(b)這種結(jié)構(gòu)是比較好的。整個二叉搜索樹左右兩邊顯得比較平均，不像最后一種完全成了一顆右斜樹，或者說是單向鏈表，同時也可以看到其ASL=3.0 是這三種結(jié)構(gòu)中最小的。

總的來說，目的就是想讓整個二叉搜索樹變得比較矮胖，而不是高瘦，或者是一邊倒的傾斜。因?yàn)?，矮胖意味著樹比較低，使得查找某個元素的能更快速。

平衡因子：Balance Factor,簡稱BF,BF(T)=hL-hR. 其中L和hR分別為二叉樹左右子樹的高度。

平衡二叉樹：(AVL 樹）：空樹，或者任一結(jié)點(diǎn)左、右子樹高度差的絕對值不超過1. 即|BF(T)|<=1.

avl_tree

圖中結(jié)點(diǎn)3和5的平衡因子均為2，因此不是平衡二叉樹。最后一棵樹，根節(jié)點(diǎn)7平衡因子為2，同樣不是平衡二叉樹。

對于給定結(jié)點(diǎn)數(shù)為n的AVL樹，最大高度為O(log2n).

也就說，從n個數(shù)中，查找一個特定值時，最多需要log2n次。因此，AVL 是一種特別適合進(jìn)行查找操作的樹。

平衡二叉樹的調(diào)整

四種失衡的情況

在平衡二叉樹中，當(dāng)我們插入新的元素時，為了保證二叉搜索樹的特性，很容易導(dǎo)致某些結(jié)點(diǎn)失衡，即該結(jié)點(diǎn)的平衡因子大于1。

而在二叉樹中，任意結(jié)點(diǎn)孩子最多只有左右兩個，而且導(dǎo)致失去平衡的必要條件就是當(dāng)前結(jié)點(diǎn)的兩顆子樹的高度差等于2。因此，致使一個結(jié)點(diǎn)失衡的插入操作有以下4中。

  • 在結(jié)點(diǎn)的左子樹的左子樹插入元素,LL 插入；
  • 在結(jié)點(diǎn)的左子樹的右子樹插入元素,LR 插入；
  • 在結(jié)點(diǎn)的右子樹的左子樹插入元素,RL 插入；
  • 在結(jié)點(diǎn)的右子樹的右子樹插入元素,RR 插入。
失去平衡的二叉搜索樹
  • LL(一）中結(jié)點(diǎn)1的插入導(dǎo)致結(jié)點(diǎn)8失衡，而插入的位置是在其左子樹的左子樹上，同樣LL(二）中，結(jié)點(diǎn)3插入同樣導(dǎo)致結(jié)點(diǎn)8失衡，這里需要注意子樹是從受影響的結(jié)點(diǎn)算起，雖然3插在了右邊，但他依舊是在8（失衡結(jié)點(diǎn)）左子樹的左子樹上，因此屬于LL 插入。
  • LR(一）,結(jié)點(diǎn)5插入導(dǎo)致結(jié)點(diǎn)8失衡，插入位置是在其左子樹的右子樹上，同樣LR(二)結(jié)點(diǎn)7的插入也是同理，因此這二者都屬于LR 插入。

后面兩種失衡現(xiàn)象可以當(dāng)做是前兩者的鏡像，原理都是一樣的。

對四種失衡情況的調(diào)整策略

面對以上4種失衡的情況，在AVL 樹中將采用LL(左左)，LR(左右)，RR(右右)和RL(右左) 四種旋轉(zhuǎn)方式進(jìn)行調(diào)整。

1. LL(左左）旋轉(zhuǎn)

ll

如圖，這種情況下BL結(jié)點(diǎn)插入元素導(dǎo)致結(jié)點(diǎn)A失衡，因此我們的操作就是圍繞失衡的結(jié)點(diǎn)（圖中A）和導(dǎo)致其失衡的結(jié)點(diǎn)（圖中B）進(jìn)行。具體來說就是圍繞結(jié)點(diǎn)B 將樹順時針（左手）旋轉(zhuǎn)，最終結(jié)果就是B成為了根節(jié)點(diǎn)（相對而言），A 變成了B的右子樹，而B原來的右子樹（BR）變成了A 的左子樹。

看一下代碼實(shí)現(xiàn)：

    /**
     * 左旋
     *
     * @param node 失衡結(jié)點(diǎn) 
     * @return 旋轉(zhuǎn)后根節(jié)點(diǎn)
     */
    private TreeNode<T> leftRotate(TreeNode<T> node) {
        // 將失衡結(jié)點(diǎn)的左子樹賦給一個臨時結(jié)點(diǎn)，也就是將A的左子樹B 賦給新的結(jié)點(diǎn)
        TreeNode<T> newRoot = node.leftChild;
        // 將B 被右子樹BR 掛在A 的左子樹上
        node.leftChild = newRoot.rightChild;
        // B 的右子樹為失衡的結(jié)點(diǎn)即A
        newRoot.rightChild = node;
        // 結(jié)點(diǎn)A 的高度為左右子樹高度最大值加1
        node.height = getMax(height(node.leftChild), height(node.rightChild)) + 1;
        // 結(jié)點(diǎn)B 的高度為左右子樹高度最大值加1
        newRoot.height = getMax(height(newRoot.leftChild), newRoot.height) + 1;
        // 返回根節(jié)點(diǎn)
        return newRoot;
    }

結(jié)合注釋應(yīng)該很好理解。

2. RR(右右）旋轉(zhuǎn)

rr

理解了LL，RR就是同理了，圍繞的同樣是導(dǎo)致失衡的結(jié)點(diǎn)B,只不過旋轉(zhuǎn)方向變成了逆時針（右手向內(nèi)）。

    /**
     * 右旋
     *
     * @param node
     * @return
     */
    private TreeNode<T> rightRotate(TreeNode<T> node) {
        TreeNode<T> newRoot = node.rightChild;
        node.rightChild = newRoot.leftChild;
        newRoot.leftChild = node;

        node.height = getMax(height(node.leftChild), height(node.rightChild)) + 1;
        newRoot.height = getMax(height(newRoot.rightChild), node.height) + 1;

        return newRoot;
    }

3. LR(右左）旋轉(zhuǎn)

lr

看上面的圖可能有點(diǎn)暈，這里看以具體的例子。

rl_example

上圖中Jan結(jié)點(diǎn)的插入導(dǎo)致May結(jié)點(diǎn)失衡，而Jan結(jié)點(diǎn)又處在May結(jié)點(diǎn)左子樹的右子樹上，是LR 插入導(dǎo)致的失衡，面對這種情況我們可以進(jìn)行LR旋轉(zhuǎn)，需要關(guān)注的三個結(jié)點(diǎn)是May,Aug和Mar。具體來說，LR 旋轉(zhuǎn)可以分解為RR旋轉(zhuǎn)和LL旋轉(zhuǎn)。首先圍繞Aug和Mar,進(jìn)行一次RR旋轉(zhuǎn)，然后圍繞Mar和May在進(jìn)行一次LL旋轉(zhuǎn)。這樣最終就完成了LR 旋轉(zhuǎn)，最終的結(jié)果是樹仍然為AVL樹。

    /**
     * LR 左右旋轉(zhuǎn)
     *
     * @param node
     * @return
     */
    private TreeNode<T> leftRightRotate(TreeNode<T> node) {
        // 首先圍繞失衡結(jié)點(diǎn)的左子樹(圖中Aug) 和Mar進(jìn)行一次右旋，這樣Mar 和 Aug 換了位置
        node.leftChild = rightRotate(node.leftChild);
        // 最后，圍繞May和Mar進(jìn)行一次左旋
        return leftRotate(node);
    }

4. RL(左右）旋轉(zhuǎn)

rl

前面說過了，RL其實(shí)就是LR 的鏡像，因此這里道理都是一樣的，只過順序顛倒而已。

/**
     * RL 右左旋轉(zhuǎn)
     *
     * @param node
     * @return
     */
    private TreeNode<T> rightLeftRotate(TreeNode<T> node) {
        node.rightChild = leftRotate(node.rightChild);
        return rightRotate(node);
    }

AVL 樹的實(shí)現(xiàn)

以上就是AVL 樹所有的理論基礎(chǔ)，下面看看如何去實(shí)現(xiàn)。

  • 結(jié)點(diǎn)的定義

AVL 樹首先是二叉搜索樹，因此它的結(jié)點(diǎn)也必須是可比較。同時為了方便，會加入一個表示當(dāng)前結(jié)點(diǎn)高度的height字段。

/**
 * Created by engineer on 2017/10/31.
 *
 * AVL 樹節(jié)點(diǎn)定義
 */

public class TreeNode<T extends Comparable<T>> {

    // 數(shù)據(jù)域
    private T data;
    // 左子樹
    public TreeNode<T> leftChild;
    // 右子樹
    public TreeNode<T> rightChild;

    //當(dāng)前結(jié)點(diǎn)的高度
    public int height;


    public TreeNode(T data) {
        this(null, data, null);
    }

    public TreeNode(TreeNode leftChild, T data, TreeNode rightChild) {
        this(data, leftChild, rightChild, 0);
    }

    public TreeNode(T data, TreeNode<T> leftChild, TreeNode<T> rightChild, int height) {
        this.data = data;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
        this.height = height;
    }

    public T getData() {
        return data;
    }

    public TreeNode<T> getLeftChild() {
        return leftChild;
    }

    public TreeNode<T> getRightChild() {
        return rightChild;
    }

    public void setData(T data) {
        this.data = data;
    }

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }
}
  • 平衡二叉樹插入
/**
     * 插入結(jié)點(diǎn)
     *
     * @param value
     */
    public void insert(T value) {
        root = insert(root, value);
    }

    private TreeNode<T> insert(TreeNode<T> node, T value) {
        if (node == null) {
            // 新建節(jié)點(diǎn)
            node = new TreeNode<T>(value);
            if (node == null) {
                return null;
            }
        } else {
            int cmp = value.compareTo(node.getData());

            if (cmp < 0) {    // 應(yīng)該將value插入到"node的左子樹"的情況
                node.leftChild = insert(node.leftChild, value);
                // 插入節(jié)點(diǎn)后，若AVL樹失去平衡，則進(jìn)行相應(yīng)的調(diào)節(jié)。
                if (height(node.leftChild) - height(node.rightChild) == 2) {
                    if (value.compareTo(node.leftChild.getData()) < 0)
                        node = leftRotate(node);
                    else
                        node = leftRightRotate(node);
                }
            } else if (cmp > 0) {    // 應(yīng)該將value插入到"node的右子樹"的情況
                node.rightChild = insert(node.rightChild, value);
                // 插入節(jié)點(diǎn)后，若AVL樹失去平衡，則進(jìn)行相應(yīng)的調(diào)節(jié)。
                if (height(node.rightChild) - height(node.leftChild) == 2) {
                    if (value.compareTo(node.rightChild.getData()) > 0)
                        node = rightRotate(node);
                    else
                        node = rightLeftRotate(node);
                }
            } else {    // cmp==0
                System.out.println("添加失?。翰辉试S添加相同的節(jié)點(diǎn)！");
            }
        }

        node.height = getMax(height(node.leftChild), height(node.rightChild)) + 1;

        return node;
    }

測試平衡二叉樹

public class AvlTreeTest {

    private static Integer[] arrays = new Integer[]{10, 8, 3, 12, 9, 4, 5, 7, 1, 11, 17};

    public static void main(String[] args) {
        AvlTree<Integer> mAvlTree = new AvlTree<>();
        for (int i = 0; i < arrays.length; i++) {
            mAvlTree.insert(arrays[i]);
        }

        mAvlTree.printTree();
    }
}

這里我們測試平衡二叉樹采用和上一節(jié)二叉搜索樹中同樣的數(shù)據(jù)。首先看一下樹遍歷打印結(jié)果：

前序遍歷：8 4 3 1 5 7 10 9 12 11 17 
中序遍歷：1 3 4 5 7 8 9 10 11 12 17 
后序遍歷：1 3 7 5 4 9 11 17 12 10 8

這樣的遍歷的結(jié)構(gòu)，相對應(yīng)的平衡二叉樹將是如下：

平衡二叉樹

在和上一節(jié)構(gòu)造的二叉樹對比一下:

二叉搜索樹

很明顯，平衡二叉樹是一種更加友好的搜索樹，在平衡二叉樹中查找7這個元素，最大比較4次，而在普通的二叉搜索樹中需要找6次。總體來說，平衡二叉樹結(jié)合平衡因子構(gòu)造出了一顆十分便于查找的二叉搜索樹。

好了，平衡二叉樹就到這里了。

參考文檔

AVL樹(三)之 Java的實(shí)現(xiàn)

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容