Java數(shù)據(jù)結(jié)構(gòu)中關(guān)于AVL樹(shù)的實(shí)現(xiàn)方法詳解

更新時(shí)間：2024年02月11日 08:45:24 作者：小扳

這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)中關(guān)于AVL樹(shù)的實(shí)現(xiàn)方法,AVL樹(shù)是高度平衡的二叉樹(shù),它的特點(diǎn)是AVL樹(shù)中任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度最大差別為1,本文主要給大家介紹了Java語(yǔ)言如何實(shí)現(xiàn)AVL樹(shù),需要的朋友可以參考下

AVL樹(shù)的說(shuō)明

AVL樹(shù)是一種自平衡二叉搜索樹(shù)，它的名稱來(lái)源于它的發(fā)明者 Adelson-Velsky 和 Landis 。在AVL樹(shù)中，任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度最多相差 1，這使得AVL樹(shù)能夠保持相對(duì)平衡，從而保證了樹(shù)的查找、插入和刪除操作的時(shí)間復(fù)雜度都是 O(log n)。

AVL樹(shù)的平衡性是通過(guò)對(duì)節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)操作來(lái)實(shí)現(xiàn)的，包括左旋、右旋、左右旋和右左旋。當(dāng)插入或刪除節(jié)點(diǎn)后破壞了AVL樹(shù)的平衡性時(shí)，就會(huì)進(jìn)行相應(yīng)的旋轉(zhuǎn)操作來(lái)保持樹(shù)的平衡。

也就是說(shuō)， AVL 樹(shù)是一種特殊的自平衡二叉搜索樹(shù)。

AVL樹(shù)的成員變量及其構(gòu)造方法

（1）構(gòu)造 AVLNode 內(nèi)部類變量：

int key 關(guān)鍵字：通過(guò)關(guān)鍵字來(lái)比較每個(gè)節(jié)點(diǎn)的大小。
Object value 值：通過(guò)該變量存放值。
AVLNode left：引用左孩子節(jié)點(diǎn)。
AVLNode right：引用右孩子節(jié)點(diǎn)。
int height 高度：表示當(dāng)前節(jié)點(diǎn)的高度，默認(rèn)初始化為 1 。

（2）AVLNode 內(nèi)部類構(gòu)造方法：

重載兩個(gè)內(nèi)部類的構(gòu)造方法分別為：參數(shù)為 key，value 的構(gòu)造方法、參數(shù)為 key，value，left，right 的構(gòu)造方法。

（3）構(gòu)造 AVLTree 外部類：

AVLNode root：表示該樹(shù)的頭節(jié)點(diǎn)。

代碼如下：

public class AVLTree {
    AVLNode root = null;
    static class AVLNode {
        int key;
        Object value;
        AVLNode left;
        AVLNode right;
        int height = 1;
        public AVLNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }
        public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}

實(shí)現(xiàn)AVL樹(shù)的核心方法

AVL 樹(shù)的最核心的方法就是插入、更新、刪除操作，因?yàn)檫@些操作都有可能造成二叉搜索樹(shù)失去平衡。為了解決自平衡的特點(diǎn)，需要每一個(gè)插入或者更新、刪除操作之后，需要檢查是否失去平衡，若失去平衡需要通過(guò)左旋、右旋、左右旋、右左旋來(lái)重新達(dá)到平衡狀態(tài)；若沒(méi)有失去平衡，無(wú)需任何操作。

獲取當(dāng)前節(jié)點(diǎn)的高度

height(AVLNode node)

不能直接通過(guò) node.height 得到當(dāng)前節(jié)點(diǎn)的高度，是因?yàn)槟J(rèn)高度為 1，若出現(xiàn)該節(jié)點(diǎn)為 null 時(shí)，就會(huì)出現(xiàn)矛盾，因此需要先判斷該節(jié)點(diǎn)是否為 null 節(jié)點(diǎn)，若為空節(jié)點(diǎn)，返回 0 ；若不為空節(jié)點(diǎn)，則返回當(dāng)前節(jié)點(diǎn) node.height 即可。

代碼如下：

    //獲取當(dāng)前節(jié)點(diǎn)的高度
    private int height (AVLNode node) {
        return node == null ? 0 : node.height;
    }

更新當(dāng)前節(jié)點(diǎn)的高度

updateHeight(AVLNode node)

由于通過(guò)刪除、插入、旋轉(zhuǎn)都有可能導(dǎo)致當(dāng)前節(jié)點(diǎn)的高度發(fā)生改變，所以需要更新高度。實(shí)現(xiàn)該方法也很簡(jiǎn)單，判斷當(dāng)前節(jié)點(diǎn)的左右節(jié)點(diǎn)的高度，取最大的高度 + 1 就是為當(dāng)前節(jié)點(diǎn)的高度。

代碼如下：

    //更新當(dāng)前的高度
    private void updateHeight (AVLNode node) {
        node.height = Integer.max(height(node.left),height(node.right)) + 1;
    }

平衡因子

bf(AVLNode node)

判斷當(dāng)前節(jié)點(diǎn)是否失去平衡，當(dāng)該節(jié)點(diǎn)的左子樹(shù)的高度 - 右子樹(shù)的高度 > 1或者 < -1 即失去平衡了。若差值為 1、0、-1，表示沒(méi)有失去平衡。

代碼如下：

    //平衡因子
    private int bf (AVLNode node) {
        return  height(node.left) - height(node.right);
    }

對(duì)失衡節(jié)點(diǎn)旋轉(zhuǎn)

rotate(AVLNode node)

有四種情況：左旋、右旋、左右旋、右左旋

左旋：需要先拿到失衡節(jié)點(diǎn) node 的右孩子節(jié)點(diǎn) node.right ,將 r = node.right 賦值給 r 。先將 r.left 賦值給 node.right ，即 node.right = r.left 進(jìn)行 "換爹" 操作，然后再 "上位" r.left = node 。最后，因?yàn)樾D(zhuǎn)會(huì)導(dǎo)致當(dāng)前 node 的節(jié)點(diǎn)與上位后的節(jié)點(diǎn) r 的高度都有可能會(huì)改變，所以需要及時(shí)更新高度，通過(guò) updateHeight(node)，updateHeight(r)，需要注意的是，更新的順序不能改變。

右旋：跟左旋的原理是一樣的，需要先拿到失衡節(jié)點(diǎn) node 的左孩子節(jié)點(diǎn) node.left ,將 l= node.left賦值給 l。先將 l.right賦值給 node.left，即 node.left= l.right進(jìn)行 "換爹" 操作，然后再 "上位" l.right= node 。最后，因?yàn)樾D(zhuǎn)會(huì)導(dǎo)致當(dāng)前 node 的節(jié)點(diǎn)與上位后的節(jié)點(diǎn) r 的高度都有可能會(huì)改變，所以需要及時(shí)更新高度，通過(guò) updateHeight(node)，updateHeight(l)，需要注意的是，更新的順序不能改變。

左右旋：通過(guò)結(jié)合左旋、右旋實(shí)現(xiàn)左右旋。先拿到當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn) l = node.left，對(duì)于 l 節(jié)點(diǎn)需要用到左旋的方法進(jìn)行旋轉(zhuǎn) leftRotate(l)，旋轉(zhuǎn)后需要重新賦值 node.left = leftRotate(l) 。接著對(duì)于 node 節(jié)點(diǎn)需用用到右旋方法進(jìn)行旋轉(zhuǎn) rightRotate(node) 。最后返回rightRotate(node) 節(jié)點(diǎn)即可。

右左旋：通過(guò)結(jié)合右旋、左旋實(shí)現(xiàn)右左旋。先拿到當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn) r = node.right，對(duì)于 r 節(jié)點(diǎn)需要用到右旋的方法進(jìn)行旋轉(zhuǎn) rightRotate(r) ，旋轉(zhuǎn)后需要重新賦值 node.right = rightRotate(r) 。接著對(duì)于 node 節(jié)點(diǎn)需要用到左旋方法 leftRotate(node) 。最后返回 leftRotate(node) 節(jié)點(diǎn)即可。

代碼如下：

    //左旋
    private AVLNode leftRotate (AVLNode node) {
        AVLNode r = node.right;
        node.right = r.left;
        r.left = node;
        updateHeight(node);
        updateHeight(r);
        return r;
    }
    //右旋
    private AVLNode rightRotate (AVLNode node) {
        AVLNode l = node.left;
        node.left = l.right;
        l.right = node;
        updateHeight(node);
        updateHeight(l);
        return l;
    }
    //左右旋
    private AVLNode leftRightRotate (AVLNode node) {
        AVLNode l = node.left;
        node.left = leftRotate(l);
        return rightRotate(node);
    }
    //右左旋
    private AVLNode rightLeftRotate (AVLNode node) {
        AVLNode r = node.right;
        node.right = rightRotate(r);
        return leftRotate(node);
    }

檢查節(jié)點(diǎn)是否平衡與重新平衡

balance(AVLNode node)

介紹四種失衡狀態(tài)的樹(shù)

LL : 當(dāng)前節(jié)點(diǎn) node 的左子樹(shù)的高度 - 右子樹(shù)的高度 > 1，且 node.left 的左子樹(shù)的高度 - node.left 的右子樹(shù)的高度 >= 0 。實(shí)現(xiàn)該情況重新平衡，只需要當(dāng)前節(jié)點(diǎn)進(jìn)行右旋操作即可。
LR：當(dāng)前節(jié)點(diǎn) node 的左子樹(shù)的高度 - 右子樹(shù)的高度 > 1，且 node.left 的左子樹(shù)的高度 - node.left 的右子樹(shù)的高度 < 0 。實(shí)現(xiàn)該情況重新平衡，需要進(jìn)行先將 node.left 節(jié)點(diǎn)進(jìn)行左旋，重新 node.left = leftRotate(node.left)，接著對(duì)于 node 進(jìn)行右旋即可，也就是上面已經(jīng)實(shí)現(xiàn)的左右旋方法。
RL：當(dāng)前節(jié)點(diǎn) node 的左子樹(shù)的高度 - 右子樹(shù)的高度 < -1 ，且 node.right 的左子樹(shù)的高度 - node.right的右子樹(shù)的高度 >0 。實(shí)現(xiàn)該情況重新平衡，需要用到上面實(shí)現(xiàn)了的右左旋方法。
RR：當(dāng)前節(jié)點(diǎn) node 的左子樹(shù)的高度 - 右子樹(shù)的高度 < -1 ，且 node.right 的左子樹(shù)的高度 - node.right 的右子樹(shù)的高度 <= 0 。實(shí)現(xiàn)該情況重新平衡，只需要左旋一次操作即可。

四種失衡狀態(tài)圖：

代碼如下：

    //檢查節(jié)點(diǎn)是否失衡，重新平衡代碼
    private AVLNode balance (AVLNode node) {
        if(node == null) {
            return  null;
        }
        if (bf(node) > 1 && bf(node.left) >= 0) {
            return rightRotate(node);
        } else if (bf(node) > 1 && bf(node.left) < 0) {
            return leftRightRotate(node);
        } else if (bf(node) < -1 && bf(node.right) <= 0) {
            return leftRotate(node);
        }else if (bf(node) < -1 && bf(node.right) > 0) {
            return rightLeftRotate(node);
        }
        return node;
    }

當(dāng) node == null 時(shí)，返回 null 即可。

插入與更新節(jié)點(diǎn)

put(int key, Object value)

使用遞歸實(shí)現(xiàn)插入、更新節(jié)點(diǎn)。兩種情況，若沒(méi)有找到 key 關(guān)鍵字時(shí)，而找到空位的地方插入新節(jié)點(diǎn)；若找到 key 關(guān)鍵字時(shí)，更新該節(jié)點(diǎn)的值即可。區(qū)別于一般的二叉搜索樹(shù)，自平衡的二叉搜索樹(shù)，需要在插入節(jié)點(diǎn)后更新當(dāng)前節(jié)點(diǎn)的高度和通過(guò)旋轉(zhuǎn)來(lái)重新達(dá)到平衡。需要注意的是，更新節(jié)點(diǎn)的操作是不會(huì)改變高度還有破壞平衡。

代碼如下：

    //更新
    public AVLNode put (int key, Object value) {
        return doPut(root,key,value);
    }
    private AVLNode doPut(AVLNode node, int key, Object value) {
        if (node == null) {
            return new AVLNode(key,value);
        }
        if (node.key == key) {
            node.value = value;
            return node;
        }
        if (node.key > key) {
            node.left = doPut(node.left,key,value);
        }else {
            node.right = doPut(node.right,key,value);
        }
        updateHeight(node);
        return balance(node);
    }

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

remove(AVLNode node)

使用遞歸實(shí)現(xiàn)刪除節(jié)點(diǎn)思路：

（1）node == null

（2）沒(méi)有找到 key

（3）找到 key 1) 沒(méi)有 2）只有一個(gè)孩子 3）有兩個(gè)孩子

（4）更新高度

（5）balance

代碼如下：

    //刪除
    public AVLNode remove (int key) {
        return doRemove(root,key);
    }
    private AVLNode doRemove (AVLNode node,int key) {
        if (node == null) {
            return null;
        }
        if (node.key > key) {
            node.left = doRemove(node.left,key);
        } else if (node.key < key) {
            node.right = doRemove(node.right,key);
        }else {
            if (node.left == null && node.right == null) {
                return null;
            } else if (node.right == null) {
                node = node.left;
            } else if (node.left == null) {
                node = node.right;
            }else {
                AVLNode p = node.right;
                while (p.left != null) {
                    p = p.left;
                }
                p.right = doRemove(node.right,p.key);
                p.left = node.left;
                node = p;
            }
        }
        updateHeight(node);
        return balance(node);
    }

實(shí)現(xiàn)AVLTree核心方法的完整代碼

public class AVLTree {
    AVLNode root = null;
    static class AVLNode {
        int key;
        Object value;
        AVLNode left;
        AVLNode right;
        int height = 1;
        public AVLNode(int key, Object value) {
            this.key = key;
            this.value = value;
        }
        public AVLNode(int key, Object value, AVLNode left, AVLNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
    //獲取當(dāng)前節(jié)點(diǎn)的高度
    private int height (AVLNode node) {
        return node == null ? 0 : node.height;
    }
    //更新當(dāng)前的高度
    private void updateHeight (AVLNode node) {
        node.height = Integer.max(height(node.left),height(node.right)) + 1;
    }
    //平衡因子
    private int bf (AVLNode node) {
        return  height(node.left) - height(node.right);
    }
    //左旋
    private AVLNode leftRotate (AVLNode node) {
        AVLNode r = node.right;
        node.right = r.left;
        r.left = node;
        updateHeight(node);
        updateHeight(r);
        return r;
    }
    //右旋
    private AVLNode rightRotate (AVLNode node) {
        AVLNode l = node.left;
        node.left = l.right;
        l.right = node;
        updateHeight(node);
        updateHeight(l);
        return l;
    }
    //左右旋
    private AVLNode leftRightRotate (AVLNode node) {
        AVLNode l = node.left;
        node.left = leftRotate(l);
        return rightRotate(node);
    }
    //右左旋
    private AVLNode rightLeftRotate (AVLNode node) {
        AVLNode r = node.right;
        node.right = rightRotate(r);
        return leftRotate(node);
    }
    //檢查節(jié)點(diǎn)是否失衡，重新平衡代碼
    private AVLNode balance (AVLNode node) {
        if(node == null) {
            return  null;
        }
        if (bf(node) > 1 && bf(node.left) >= 0) {
            return rightRotate(node);
        } else if (bf(node) > 1 && bf(node.left) < 0) {
            return leftRightRotate(node);
        } else if (bf(node) < -1 && bf(node.right) <= 0) {
            return leftRotate(node);
        }else if (bf(node) < -1 && bf(node.right) > 0) {
            return rightLeftRotate(node);
        }
        return node;
    }
    //更新
    public AVLNode put (int key, Object value) {
        return doPut(root,key,value);
    }
    private AVLNode doPut(AVLNode node, int key, Object value) {
        if (node == null) {
            return new AVLNode(key,value);
        }
        if (node.key == key) {
            node.value = value;
            return node;
        }
        if (node.key > key) {
            node.left = doPut(node.left,key,value);
        }else {
            node.right = doPut(node.right,key,value);
        }
        updateHeight(node);
        return balance(node);
    }
    //刪除
    public AVLNode remove (int key) {
        return doRemove(root,key);
    }
    private AVLNode doRemove (AVLNode node,int key) {
        if (node == null) {
            return null;
        }
        if (node.key > key) {
            node.left = doRemove(node.left,key);
        } else if (node.key < key) {
            node.right = doRemove(node.right,key);
        }else {
            if (node.left == null && node.right == null) {
                return null;
            } else if (node.right == null) {
                node = node.left;
            } else if (node.left == null) {
                node = node.right;
            }else {
                AVLNode p = node.right;
                while (p.left != null) {
                    p = p.left;
                }
                p.right = doRemove(node.right,p.key);
                p.left = node.left;
                node = p;
            }
        }
        updateHeight(node);
        return balance(node);
    }
}

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)中關(guān)于AVL樹(shù)的實(shí)現(xiàn)方法詳解的文章就介紹到這了,更多相關(guān)Java AVL樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: