Java數(shù)據(jù)結(jié)構(gòu)之AVL樹實(shí)例分析

這篇文章主要介紹“Java數(shù)據(jù)結(jié)構(gòu)之AVL樹實(shí)例分析”的相關(guān)知識(shí)，小編通過實(shí)際案例向大家展示操作過程，操作方法簡單快捷，實(shí)用性強(qiáng)，希望這篇“Java數(shù)據(jù)結(jié)構(gòu)之AVL樹實(shí)例分析”文章能幫助大家解決問題。

創(chuàng)新互聯(lián)服務(wù)項(xiàng)目包括龍里網(wǎng)站建設(shè)、龍里網(wǎng)站制作、龍里網(wǎng)頁制作以及龍里網(wǎng)絡(luò)營銷策劃等。多年來，我們專注于互聯(lián)網(wǎng)行業(yè)，利用自身積累的技術(shù)優(yōu)勢、行業(yè)經(jīng)驗(yàn)、深度合作伙伴關(guān)系等，向廣大中小型企業(yè)、政府機(jī)構(gòu)等提供互聯(lián)網(wǎng)行業(yè)的解決方案，龍里網(wǎng)站推廣取得了明顯的社會(huì)效益與經(jīng)濟(jì)效益。目前，我們服務(wù)的客戶以成都為中心已經(jīng)輻射到龍里省份的部分城市，未來相信會(huì)繼續(xù)擴(kuò)大服務(wù)區(qū)域并繼續(xù)獲得客戶的支持與信任！

AVL樹的引入

搜索二叉樹有著極高的搜索效率，但是搜索二叉樹會(huì)出現(xiàn)以下極端情況：
Java數(shù)據(jù)結(jié)構(gòu)之AVL樹實(shí)例分析
這樣的二叉樹搜索效率甚至比鏈表還低。在搜索二叉樹基礎(chǔ)上出現(xiàn)的平衡二叉樹(AVL樹)就解決了這樣的問題。當(dāng)平衡二叉樹(AVL樹)的某個(gè)節(jié)點(diǎn)左右子樹高度差的絕對(duì)值大于1時(shí)，就會(huì)通過旋轉(zhuǎn)操作減小它們的高度差。

基本概念

AVL樹本質(zhì)上還是一棵二叉搜索樹，它的特點(diǎn)是：

本身首先是一棵二叉搜索樹。
每個(gè)結(jié)點(diǎn)的左右子樹的高度之差的絕對(duì)值（平衡因子）最多為1。也就是說，AVL樹，本質(zhì)上是帶了平衡功能的二叉查找樹（二叉排序樹，二叉搜索樹）。
當(dāng)插入一個(gè)節(jié)點(diǎn)或者刪除一個(gè)節(jié)點(diǎn)時(shí)，導(dǎo)致某一個(gè)節(jié)點(diǎn)的左右子樹高度差的絕對(duì)值大于1，這時(shí)需要通過左旋和右旋的操作使二叉樹再次達(dá)到平衡狀態(tài)。

平衡因子(balanceFactor)

一個(gè)結(jié)點(diǎn)的左子樹與右子樹的高度之差。
AVL樹中的任意結(jié)點(diǎn)的BF只可能是-1，0和1。

基礎(chǔ)設(shè)計(jì)

下面是AVL樹需要的簡單方法和屬性：

public class AVLTree <E extends Comparable<E>>{
    class Node{
        E value;
        Node left;
        Node right;
        int height;
        public Node(){}
        public Node(E value){
            this.value = value;
            height = 1;
            left = null;
            right = null;
        }
        public void display(){
            System.out.print(this.value + " ");
        }
    }
    Node root;
    int size;
    public int size(){
        return size;
    }
    public int getHeight(Node node) {
        if(node == null) return 0;
        return node.height;
    }
    //獲取平衡因子(左右子樹的高度差，大小為1或者0是平衡的，大小大于1不平衡)
    public int getBalanceFactor(){
        return getBalanceFactor(root);
    }
    public int getBalanceFactor(Node node){
        if(node == null) return 0;
        return getHeight(node.left) - getHeight(node.right);
    }

    //判斷一個(gè)樹是否是一個(gè)平衡二叉樹
    public boolean isBalance(Node node){
        if(node == null) return true;
        int balanceFactor = Math.abs(getBalanceFactor(node.left) - getBalanceFactor(node.right));
        if(balanceFactor > 1) return false;
        return isBalance(node.left) && isBalance(node.right);
    }
    public boolean isBalance(){
        return isBalance(root);
    }

    //中序遍歷樹
    private  void inPrevOrder(Node root){
        if(root == null) return;
        inPrevOrder(root.left);
        root.display();
        inPrevOrder(root.right);
    }
    public void inPrevOrder(){
        System.out.print("中序遍歷：");
        inPrevOrder(root);
    }}

RR(左旋)

往一個(gè)樹右子樹的右子樹上插入一個(gè)節(jié)點(diǎn)，導(dǎo)致二叉樹變得不在平衡，如下圖，往平衡二叉樹中插入5，導(dǎo)致這個(gè)樹變得不再平衡，此時(shí)需要左旋操作，如下：
Java數(shù)據(jù)結(jié)構(gòu)之AVL樹實(shí)例分析
代碼如下：

//左旋,并且返回新的根節(jié)點(diǎn)
    public Node leftRotate(Node node){
        System.out.println("leftRotate");
       Node cur = node.right;
       node.right = cur.left;
       cur.left = node;
       //跟新node和cur的高度
        node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
        cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1;
        return cur;
    }

LL(右旋)

往一個(gè)AVL樹左子樹的左子樹上插入一個(gè)節(jié)點(diǎn)，導(dǎo)致二叉樹變得不在平衡，如下圖，往平衡二叉樹中插入2，導(dǎo)致這個(gè)樹變得不再平衡，此時(shí)需要左旋操作，如下：
Java數(shù)據(jù)結(jié)構(gòu)之AVL樹實(shí)例分析
代碼如下：

 //右旋，并且返回新的根節(jié)點(diǎn)
    public Node rightRotate(Node node){
        System.out.println("rightRotate");
        Node cur = node.left;
        node.left = cur.right;
        cur.right = node;
        //跟新node和cur的高度
        node.height = Math.max(getHeight(node.left),getHeight(node.right)) + 1;
        cur.height = Math.max(getHeight(cur.left),getHeight(cur.right)) + 1;
        return cur;
    }

LR(先左旋再右旋)

往AVL樹左子樹的右子樹上插入一個(gè)節(jié)點(diǎn)，導(dǎo)致該樹不再平衡，需要先對(duì)左子樹進(jìn)行左旋，再對(duì)整棵樹右旋，如下圖所示，插入節(jié)點(diǎn)為5.
Java數(shù)據(jù)結(jié)構(gòu)之AVL樹實(shí)例分析

RL(先右旋再左旋)

往AVL樹右子樹的左子樹上插入一個(gè)節(jié)點(diǎn)，導(dǎo)致該樹不再平衡，需要先對(duì)右子樹進(jìn)行右旋，再對(duì)整棵樹左旋，如下圖所示，插入節(jié)點(diǎn)為2.
Java數(shù)據(jù)結(jié)構(gòu)之AVL樹實(shí)例分析

添加節(jié)點(diǎn)

//添加元素
    public  void add(E e){
        root = add(root,e);
    }
    public Node add(Node node, E value) {
        if (node == null) {
            size++;
            return new Node(value);
        }
        if (value.compareTo(node.value) > 0) {
            node.right = add(node.right, value);
        } else if (value.compareTo(node.value) < 0) {
            node.left = add(node.left, value);
        }
        //跟新節(jié)點(diǎn)高度
        node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;
        //獲取當(dāng)前節(jié)點(diǎn)的平衡因子
        int balanceFactor = getBalanceFactor(node);
        //該子樹不平衡且新插入節(jié)點(diǎn)(導(dǎo)致不平衡的節(jié)點(diǎn))在左子樹的左子樹上，此時(shí)需要進(jìn)行右旋
        if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
            return rightRotate(node);
        }
        //該子樹不平衡且新插入節(jié)點(diǎn)(導(dǎo)致不平衡的節(jié)點(diǎn))在右子樹子樹的右子樹上，此時(shí)需要進(jìn)行左旋
        else if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
            return leftRotate(node);
        }
        //該子樹不平衡且新插入節(jié)點(diǎn)(導(dǎo)致不平衡的節(jié)點(diǎn))在左子樹的右子樹上，此時(shí)需要先對(duì)左子樹左旋，在整個(gè)樹右旋
        else if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }
        //balanceFactor < -1 && getBalanceFactor(node.left) > 0
        //該子樹不平衡且新插入節(jié)點(diǎn)(導(dǎo)致不平衡的節(jié)點(diǎn))在右子樹的左子樹上，此時(shí)需要先對(duì)右子樹右旋，再整個(gè)樹左旋
        else if(balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
            node.right = rightRotate(node.right);
            return leftRotate(node);
        }
        return node;
    }

刪除節(jié)點(diǎn)

 //刪除節(jié)點(diǎn)
    public E remove(E value){
        root = remove(root,value);
        if(root == null){
            return null;
        }
        return root.value;
    }
    public Node remove(Node node, E value){
        Node retNode = null;
        if(node == null)
            return retNode;
        if(value.compareTo(node.value) > 0){
            node.right = remove(node.right,value);
            retNode = node;
        }
        else if(value.compareTo(node.value) < 0){
            node.left = remove(node.left,value);
            retNode = node;
        }
        //value.compareTo(node.value) = 0
        else{
            //左右節(jié)點(diǎn)都為空，或者左節(jié)點(diǎn)為空
            if(node.left == null){
                size--;
                retNode = node.right;
            }
            //右節(jié)點(diǎn)為空
            else if(node.right == null){
                size--;
                retNode = node.left;
            }
            //左右節(jié)點(diǎn)都不為空
            else{
                Node successor = new Node();
                //尋找右子樹最小的節(jié)點(diǎn)
                Node cur = node.right;
                while(cur.left != null){
                    cur = cur.left;
                }
                successor.value  = cur.value;
                successor.right = remove(node.right,value);
                successor.left = node.left;
                node.left =  node.right = null;
                retNode = successor;
            }
            if(retNode == null)
                return null;
            //維護(hù)二叉樹平衡
            //跟新height
            retNode.height = Math.max(getHeight(retNode.left),getHeight(retNode.right));
        }
        int balanceFactor = getBalanceFactor(retNode);
        //該子樹不平衡且新插入節(jié)點(diǎn)(導(dǎo)致不平衡的節(jié)點(diǎn))在左子樹的左子樹上，此時(shí)需要進(jìn)行右旋
        if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
            return rightRotate(retNode);
        }
        //該子樹不平衡且新插入節(jié)點(diǎn)(導(dǎo)致不平衡的節(jié)點(diǎn))在右子樹子樹的右子樹上，此時(shí)需要進(jìn)行左旋
        else if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
            return leftRotate(retNode);
        }
        //該子樹不平衡且新插入節(jié)點(diǎn)(導(dǎo)致不平衡的節(jié)點(diǎn))在左子樹的右子樹上，此時(shí)需要先對(duì)左子樹左旋，在整個(gè)樹右旋
        else if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
            retNode.left = leftRotate(retNode.left);
            return rightRotate(retNode);
        }
        //該子樹不平衡且新插入節(jié)點(diǎn)(導(dǎo)致不平衡的節(jié)點(diǎn))在右子樹的左子樹上，此時(shí)需要先對(duì)右子樹右旋，再整個(gè)樹左旋
        else if(balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
            retNode.right = rightRotate(retNode.right);
            return leftRotate(retNode);
        }
        return  retNode;
    }

關(guān)于“Java數(shù)據(jù)結(jié)構(gòu)之AVL樹實(shí)例分析”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)，可以關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，小編每天都會(huì)為大家更新不同的知識(shí)點(diǎn)。

名稱欄目：Java數(shù)據(jù)結(jié)構(gòu)之AVL樹實(shí)例分析
當(dāng)前路徑：http://aaarwkj.com/article46/jjggeg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、建站公司、外貿(mào)建站、企業(yè)網(wǎng)站制作、全網(wǎng)營銷推廣、企業(yè)建站

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

欧美一级特黄大片做受成人-亚洲成人一区二区电影-激情熟女一区二区三区-日韩专区欧美专区国产专区

Java數(shù)據(jù)結(jié)構(gòu)之AVL樹實(shí)例分析

AVL樹的引入

基本概念

基礎(chǔ)設(shè)計(jì)

RR(左旋)

LL(右旋)

LR(先左旋再右旋)

RL(先右旋再左旋)

添加節(jié)點(diǎn)

刪除節(jié)點(diǎn)