圖解AVL樹科技頭條網 - 每日頭條資訊!

2020-04-26 09:25:20 sandag

1：AVL樹簡介

二叉搜索樹在一般情況下其搜索的時間複雜度為O(logn)，但某些特殊情況下會退化為鏈表，導致樹的高度變大且搜索的時間複雜度變為O(n)，發揮不出樹這種數據結構的優勢，因此平衡二叉樹便應運而生，通過保證樹的高度來保證查詢的時間複雜度為O(logn)，想想人類實在是太聰明瞭！

2：構造AVL樹

在構造一棵AVL樹的時候如何保持平衡呢？其手段便是通過各種旋轉變換來調整以此保證整棵樹的高度，調整的原則是左右子樹的高度不能大於1的絕對值(平衡因子)先來介紹下旋轉的方法吧。

2.1：LL型

當插入元素後構成LL型，如下圖所示，則以2為支，高右轉，把3右旋下來保證平衡。

2.2：RR型

當插入元素後構成RR型，如下圖所示，則以2為支，高左轉，把1左旋轉下來保證平衡。

2.3：LR型

當插入元素後構成LR型，如下圖所示，先2,3整體左旋，在根據LL型進行右旋轉來保證平衡。

2.4：RL型

當插入元素後構成RL型，如下圖所示，先將5右轉，在與6進行交換，在根據RR型進行旋轉來保證平衡。

2.5：其他情況

當因為插入一個元素而導致出現兩個不平衡點，應該調整距離插入節點最近的不平衡點

2.6：自測題

測試題：以關鍵字序列{16、3、7、11、9、26、18、14、15}構造一顆AVL樹

2.7：java實現AVL的構造

<code>package AVL;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName AVLTree.java
 * @Description TODO
 * @createTime 2020年03月30日 18:28:00
 */
public class AVLTree {


    /**
     * 獲取左右節點的高度差,即平衡因子
     * @param root
     * @return
     */
    public int getBalance(Node root) {
        return root==null?0:getHeight(root.left)-getHeight(root.right);
    }

    /**
     * 獲取節點的高度
     * @param root
     * @return
     */
    public int getHeight(Node root) {
        return root == null ? 0 : root.height;
    }

    /**
     * 更新節點的高度
     * @param root
     * @return
     */
    private  int updateHeight(Node root) {
        if (root == null)
            return 0;
        return Math.max(updateHeight(root.left), updateHeight(root.right)) + 1;
    }

    /**
     * LL型，右旋操作 

     *
     * @param root
     * @return
     */
    public Node rightRotate(Node root) {
        Node node = root.left;
        root.left = node.right;
        node.right = root;
        root.height = updateHeight(root);
        node.height = updateHeight(node);
        return node;
    }

    /**
     * RR型，左旋操作
     * @param root
     * @return
     */
    public Node leftRotate(Node root) {
        Node node = root.right;
        root.right = node.left;
        node.left = root;
        root.height = updateHeight(root);
        node.height = updateHeight(node);
        return node;
    }

    public Node insert(Node node, int data) {
        //當節點為空，直接插入
        if (node == null) {
            return (new Node(data));
        }
        //當插入元素<node.data>node.data，往node的右子樹插入
        if (node.data > data) {
            node.left = insert(node.left, data);
        } else {
            node.right = insert(node.right, data);
        }
        //更新節點的高度
        node.height = updateHeight(node);
        //獲取平衡因子(左子樹高度-右子樹高度)
        int balDiff = getBalance(node);

        // 右旋
        if (balDiff > 1 && data < node.left.data) { 

            return rightRotate(node);
        }

        // 左旋
        if (balDiff < -1 && data > node.right.data) {
            return leftRotate(node);
        }

        // 先左旋在右旋
        if (balDiff > 1 && data > node.left.data) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // 先右旋在左旋
        if (balDiff < -1 && data < node.right.data) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }

        return node;
    }

    
}

class Node {
    int data;
    Node left;
    Node right;
    int height;

    public Node(Integer data) {
        this.data = data;
        height = 1;
    }
}/<node.data>/<code>