AVL樹(三)之 Java的實(shí)現(xiàn)【轉(zhuǎn)】

2019-11-06 08:41:38

字體：大中小

供稿：網(wǎng)友

本文轉(zhuǎn)自：http://www.cnblogs.com/skywang12345/p/3577479.html

1. AVL樹的介紹2. AVL樹的java實(shí)現(xiàn)3. AVL樹的Java測試程序

AVL樹的介紹

AVL樹是高度平衡的而二叉樹。它的特點(diǎn)是：AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為1。

上面的兩張圖片，左邊的是AVL樹，它的任何節(jié)點(diǎn)的兩個(gè)子樹的高度差別都<=1；而右邊的不是AVL樹，因?yàn)?的兩顆子樹的高度相差為2(以2為根節(jié)點(diǎn)的樹的高度是3，而以8為根節(jié)點(diǎn)的樹的高度是1)。

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

1. 節(jié)點(diǎn)

1.1 節(jié)點(diǎn)定義

public class AVLTree<T extends Comparable<T>> {    PRivate AVLTreeNode<T> mRoot;    // 根結(jié)點(diǎn)    // AVL樹的節(jié)點(diǎn)(內(nèi)部類)    class AVLTreeNode<T extends Comparable<T>> {        T key;                // 關(guān)鍵字(鍵值)        int height;         // 高度        AVLTreeNode<T> left;    // 左孩子        AVLTreeNode<T> right;    // 右孩子        public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {            this.key = key;            this.left = left;            this.right = right;            this.height = 0;        }    }        ......}AVLTree是AVL樹對應(yīng)的類，而AVLTreeNode是AVL樹節(jié)點(diǎn)，它是AVLTree的內(nèi)部類。AVLTree包含了AVL樹的根節(jié)點(diǎn)，AVL樹的基本操作也定義在AVL樹中。AVLTreeNode包括的幾個(gè)組成對象:(01) key -- 是關(guān)鍵字，是用來對AVL樹的節(jié)點(diǎn)進(jìn)行排序的。(02) left -- 是左孩子。(03) right -- 是右孩子。(04) height -- 是高度。
 
1.2 樹的高度
/* * 獲取樹的高度 */private int height(AVLTreeNode<T> tree) {    if (tree != null)        return tree.height;    return 0;}public int height() {    return height(mRoot);}關(guān)于高度，有的地方將"空二叉樹的高度是-1"，而本文采用維基百科上的定義：樹的高度為最大層次。即空的二叉樹的高度是0，非空樹的高度等于它的最大層次(根的層次為1，根的子節(jié)點(diǎn)為第2層，依次類推)。
 
1.3 比較大小
/* * 比較兩個(gè)值的大小 */private int max(int a, int b) {    return a>b ? a : b;} 
2. 旋轉(zhuǎn)
如果在AVL樹中進(jìn)行插入或刪除節(jié)點(diǎn)后，可能導(dǎo)致AVL樹失去平衡。這種失去平衡的可以概括為4種姿態(tài)：LL(左左)，LR(左右)，RR(右右)和RL(右左)。下面給出它們的示意圖：
上圖中的4棵樹都是"失去平衡的AVL樹"，從左往右的情況依次是：LL、LR、RL、RR。除了上面的情況之外，還有其它的失去平衡的AVL樹，如下圖：
上面的兩張圖都是為了便于理解，而列舉的關(guān)于"失去平衡的AVL樹"的例子。總的來說，AVL樹失去平衡時(shí)的情況一定是LL、LR、RL、RR這4種之一，它們都由各自的定義：
(1) LL：LeftLeft，也稱為"左左"。插入或刪除一個(gè)節(jié)點(diǎn)后，根節(jié)點(diǎn)的左子樹的左子樹還有非空子節(jié)點(diǎn)，導(dǎo)致"根的左子樹的高度"比"根的右子樹的高度"大2，導(dǎo)致AVL樹失去了平衡。     例如，在上面LL情況中，由于"根節(jié)點(diǎn)(8)的左子樹(4)的左子樹(2)還有非空子節(jié)點(diǎn)"，而"根節(jié)點(diǎn)(8)的右子樹(12)沒有子節(jié)點(diǎn)"；導(dǎo)致"根節(jié)點(diǎn)(8)的左子樹(4)高度"比"根節(jié)點(diǎn)(8)的右子樹(12)"高2。
 
(2) LR：LeftRight，也稱為"左右"。插入或刪除一個(gè)節(jié)點(diǎn)后，根節(jié)點(diǎn)的左子樹的右子樹還有非空子節(jié)點(diǎn)，導(dǎo)致"根的左子樹的高度"比"根的右子樹的高度"大2，導(dǎo)致AVL樹失去了平衡。     例如，在上面LR情況中，由于"根節(jié)點(diǎn)(8)的左子樹(4)的左子樹(6)還有非空子節(jié)點(diǎn)"，而"根節(jié)點(diǎn)(8)的右子樹(12)沒有子節(jié)點(diǎn)"；導(dǎo)致"根節(jié)點(diǎn)(8)的左子樹(4)高度"比"根節(jié)點(diǎn)(8)的右子樹(12)"高2。
 
(3) RL：RightLeft，稱為"右左"。插入或刪除一個(gè)節(jié)點(diǎn)后，根節(jié)點(diǎn)的右子樹的左子樹還有非空子節(jié)點(diǎn)，導(dǎo)致"根的右子樹的高度"比"根的左子樹的高度"大2，導(dǎo)致AVL樹失去了平衡。     例如，在上面RL情況中，由于"根節(jié)點(diǎn)(8)的右子樹(12)的左子樹(10)還有非空子節(jié)點(diǎn)"，而"根節(jié)點(diǎn)(8)的左子樹(4)沒有子節(jié)點(diǎn)"；導(dǎo)致"根節(jié)點(diǎn)(8)的右子樹(12)高度"比"根節(jié)點(diǎn)(8)的左子樹(4)"高2。
 
(4) RR：RightRight，稱為"右右"。插入或刪除一個(gè)節(jié)點(diǎn)后，根節(jié)點(diǎn)的右子樹的右子樹還有非空子節(jié)點(diǎn)，導(dǎo)致"根的右子樹的高度"比"根的左子樹的高度"大2，導(dǎo)致AVL樹失去了平衡。     例如，在上面RR情況中，由于"根節(jié)點(diǎn)(8)的右子樹(12)的右子樹(14)還有非空子節(jié)點(diǎn)"，而"根節(jié)點(diǎn)(8)的左子樹(4)沒有子節(jié)點(diǎn)"；導(dǎo)致"根節(jié)點(diǎn)(8)的右子樹(12)高度"比"根節(jié)點(diǎn)(8)的左子樹(4)"高2。
如果在AVL樹中進(jìn)行插入或刪除節(jié)點(diǎn)后，可能導(dǎo)致AVL樹失去平衡。AVL失去平衡之后，可以通過旋轉(zhuǎn)使其恢復(fù)平衡，下面分別介紹"LL(左左)，LR(左右)，RR(右右)和RL(右左)"這4種情況對應(yīng)的旋轉(zhuǎn)方法。
 
2.1 LL的旋轉(zhuǎn)
LL失去平衡的情況，可以通過一次旋轉(zhuǎn)讓AVL樹恢復(fù)平衡。如下圖：
圖中左邊是旋轉(zhuǎn)之前的樹，右邊是旋轉(zhuǎn)之后的樹。從中可以發(fā)現(xiàn)，旋轉(zhuǎn)之后的樹又變成了AVL樹，而且該旋轉(zhuǎn)只需要一次即可完成。對于LL旋轉(zhuǎn)，你可以這樣理解為：LL旋轉(zhuǎn)是圍繞"失去平衡的AVL根節(jié)點(diǎn)"進(jìn)行的，也就是節(jié)點(diǎn)k2；而且由于是LL情況，即左左情況，就用手抓著"左孩子，即k1"使勁搖。將k1變成根節(jié)點(diǎn)，k2變成k1的右子樹，"k1的右子樹"變成"k2的左子樹"。
 
LL的旋轉(zhuǎn)代碼
/* * LL：左左對應(yīng)的情況(左單旋轉(zhuǎn))。 * * 返回值：旋轉(zhuǎn)后的根節(jié)點(diǎn) */private AVLTreeNode<T> leftLeftRotation(AVLTreeNode<T> k2) {    AVLTreeNode<T> k1;    k1 = k2.left;    k2.left = k1.right;    k1.right = k2;    k2.height = max( height(k2.left), height(k2.right)) + 1;    k1.height = max( height(k1.left), k2.height) + 1;    return k1;} 
2.2 RR的旋轉(zhuǎn)
理解了LL之后，RR就相當(dāng)容易理解了。RR是與LL對稱的情況！RR恢復(fù)平衡的旋轉(zhuǎn)方法如下：
圖中左邊是旋轉(zhuǎn)之前的樹，右邊是旋轉(zhuǎn)之后的樹。RR旋轉(zhuǎn)也只需要一次即可完成。
RR的旋轉(zhuǎn)代碼
/* * RR：右右對應(yīng)的情況(右單旋轉(zhuǎn))。 * * 返回值：旋轉(zhuǎn)后的根節(jié)點(diǎn) */private AVLTreeNode<T> rightRightRotation(AVLTreeNode<T> k1) {    AVLTreeNode<T> k2;    k2 = k1.right;    k1.right = k2.left;    k2.left = k1;    k1.height = max( height(k1.left), height(k1.right)) + 1;    k2.height = max( height(k2.right), k1.height) + 1;    return k2;} 
2.3 LR的旋轉(zhuǎn)
LR失去平衡的情況，需要經(jīng)過兩次旋轉(zhuǎn)才能讓AVL樹恢復(fù)平衡。如下圖：
第一次旋轉(zhuǎn)是圍繞"k1"進(jìn)行的"RR旋轉(zhuǎn)"，第二次是圍繞"k3"進(jìn)行的"LL旋轉(zhuǎn)"。
 
LR的旋轉(zhuǎn)代碼
/* * LR：左右對應(yīng)的情況(左雙旋轉(zhuǎn))。 * * 返回值：旋轉(zhuǎn)后的根節(jié)點(diǎn) */private AVLTreeNode<T> leftRightRotation(AVLTreeNode<T> k3) {    k3.left = rightRightRotation(k3.left);    return leftLeftRotation(k3);} 
2.4 RL的旋轉(zhuǎn)
RL是與LR的對稱情況！RL恢復(fù)平衡的旋轉(zhuǎn)方法如下：
第一次旋轉(zhuǎn)是圍繞"k3"進(jìn)行的"LL旋轉(zhuǎn)"，第二次是圍繞"k1"進(jìn)行的"RR旋轉(zhuǎn)"。
 
RL的旋轉(zhuǎn)代碼
/* * RL：右左對應(yīng)的情況(右雙旋轉(zhuǎn))。 * * 返回值：旋轉(zhuǎn)后的根節(jié)點(diǎn) */private AVLTreeNode<T> rightLeftRotation(AVLTreeNode<T> k1) {    k1.right = leftLeftRotation(k1.right);    return rightRightRotation(k1);} 
3. 插入
插入節(jié)點(diǎn)的代碼
/*  * 將結(jié)點(diǎn)插入到AVL樹中，并返回根節(jié)點(diǎn) * * 參數(shù)說明： *     tree AVL樹的根結(jié)點(diǎn) *     key 插入的結(jié)點(diǎn)的鍵值 * 返回值： *     根節(jié)點(diǎn) */private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {    if (tree == null) {        // 新建節(jié)點(diǎn)        tree = new AVLTreeNode<T>(key, null, null);        if (tree==null) {            System.out.println("ERROR: create avltree node failed!");            return null;        }    } else {        int cmp = key.compareTo(tree.key);           if (cmp < 0) {    // 應(yīng)該將key插入到"tree的左子樹"的情況            tree.left = insert(tree.left, key);            // 插入節(jié)點(diǎn)后，若AVL樹失去平衡，則進(jìn)行相應(yīng)的調(diào)節(jié)。            if (height(tree.left) - height(tree.right) == 2) {                if (key.compareTo(tree.left.key) < 0)                    tree = leftLeftRotation(tree);                else                    tree = leftRightRotation(tree);            }        } else if (cmp > 0) {    // 應(yīng)該將key插入到"tree的右子樹"的情況            tree.right = insert(tree.right, key);            // 插入節(jié)點(diǎn)后，若AVL樹失去平衡，則進(jìn)行相應(yīng)的調(diào)節(jié)。            if (height(tree.right) - height(tree.left) == 2) {                if (key.compareTo(tree.right.key) > 0)                    tree = rightRightRotation(tree);                else                    tree = rightLeftRotation(tree);            }        } else {    // cmp==0            System.out.println("添加失敗：不允許添加相同的節(jié)點(diǎn)！");        }    }    tree.height = max( height(tree.left), height(tree.right)) + 1;    return tree;}public void insert(T key) {    mRoot = insert(mRoot, key);} 
4. 刪除
刪除節(jié)點(diǎn)的代碼
/*  * 刪除結(jié)點(diǎn)(z)，返回根節(jié)點(diǎn) * * 參數(shù)說明： *     tree AVL樹的根結(jié)點(diǎn) *     z 待刪除的結(jié)點(diǎn) * 返回值： *     根節(jié)點(diǎn) */private AVLTreeNode<T> remove(AVLTreeNode<T> tree, AVLTreeNode<T> z) {    // 根為空 或者 沒有要?jiǎng)h除的節(jié)點(diǎn)，直接返回null。    if (tree==null || z==null)        return null;    int cmp = z.key.compareTo(tree.key);    if (cmp < 0) {        // 待刪除的節(jié)點(diǎn)在"tree的左子樹"中        tree.left = remove(tree.left, z);        // 刪除節(jié)點(diǎn)后，若AVL樹失去平衡，則進(jìn)行相應(yīng)的調(diào)節(jié)。        if (height(tree.right) - height(tree.left) == 2) {            AVLTreeNode<T> r =  tree.right;            if (height(r.left) > height(r.right))                tree = rightLeftRotation(tree);            else                tree = rightRightRotation(tree);        }    } else if (cmp > 0) {    // 待刪除的節(jié)點(diǎn)在"tree的右子樹"中        tree.right = remove(tree.right, z);        // 刪除節(jié)點(diǎn)后，若AVL樹失去平衡，則進(jìn)行相應(yīng)的調(diào)節(jié)。        if (height(tree.left) - height(tree.right) == 2) {            AVLTreeNode<T> l =  tree.left;            if (height(l.right) > height(l.left))                tree = leftRightRotation(tree);            else                tree = leftLeftRotation(tree);        }    } else {    // tree是對應(yīng)要?jiǎng)h除的節(jié)點(diǎn)。        // tree的左右孩子都非空        if ((tree.left!=null) && (tree.right!=null)) {            if (height(tree.left) > height(tree.right)) {                // 如果tree的左子樹比右子樹高；                // 則(01)找出tree的左子樹中的最大節(jié)點(diǎn)                //   (02)將該最大節(jié)點(diǎn)的值賦值給tree。                //   (03)刪除該最大節(jié)點(diǎn)。                // 這類似于用"tree的左子樹中最大節(jié)點(diǎn)"做"tree"的替身；                // 采用這種方式的好處是：刪除"tree的左子樹中最大節(jié)點(diǎn)"之后，AVL樹仍然是平衡的。                AVLTreeNode<T> max = maximum(tree.left);                tree.key = max.key;                tree.left = remove(tree.left, max);            } else {                // 如果tree的左子樹不比右子樹高(即它們相等，或右子樹比左子樹高1)                // 則(01)找出tree的右子樹中的最小節(jié)點(diǎn)                //   (02)將該最小節(jié)點(diǎn)的值賦值給tree。                //   (03)刪除該最小節(jié)點(diǎn)。                // 這類似于用"tree的右子樹中最小節(jié)點(diǎn)"做"tree"的替身；                // 采用這種方式的好處是：刪除"tree的右子樹中最小節(jié)點(diǎn)"之后，AVL樹仍然是平衡的。                AVLTreeNode<T> min = maximum(tree.right);                tree.key = min.key;                tree.right = remove(tree.right, min);            }        } else {            AVLTreeNode<T> tmp = tree;            tree = (tree.left!=null) ? tree.left : tree.right;            tmp = null;        }    }    return tree;}public void remove(T key) {    AVLTreeNode<T> z;     if ((z = search(mRoot, key)) != null)        mRoot = remove(mRoot, z);} 
完整的實(shí)現(xiàn)代碼AVL樹的實(shí)現(xiàn)文件(AVRTree.java)
 View CodeAVL樹的測試程序(AVLTreeTest.java)
 View Code 
AVL樹的Java測試程序
AVL樹的測試程序運(yùn)行結(jié)果如下：
== 依次添加: 3 2 1 4 5 6 7 16 15 14 13 12 11 10 8 9 == 前序遍歷: 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16 == 中序遍歷: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 == 后序遍歷: 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7 == 高度: 5== 最小值: 1== 最大值: 16== 樹的詳細(xì)信息:  7 is root 4 is  7's   left child 2 is  4's   left child 1 is  2's   left child 3 is  2's  right child 6 is  4's  right child 5 is  6's   left child13 is  7's  right child11 is 13's   left child 9 is 11's   left child 8 is  9's   left child10 is  9's  right child12 is 11's  right child15 is 13's  right child14 is 15's   left child16 is 15's  right child== 刪除根節(jié)點(diǎn): 8== 高度: 5== 中序遍歷: 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16 == 樹的詳細(xì)信息:  7 is root 4 is  7's   left child 2 is  4's   left child 1 is  2's   left child 3 is  2's  right child 6 is  4's  right child 5 is  6's   left child13 is  7's  right child11 is 13's   left child 9 is 11's   left child10 is  9's  right child12 is 11's  right child15 is 13's  right child14 is 15's   left child16 is 15's  right child 
下面，我們對測試程序的流程進(jìn)行分析！
1. 新建AVL樹
2. 依次添加"3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9" 到AVL樹中。
2.01 添加3,2添加3,2都不會(huì)破壞AVL樹的平衡性。
 
2.02 添加1添加1之后，AVL樹失去平衡(LL)，此時(shí)需要對AVL樹進(jìn)行旋轉(zhuǎn)(LL旋轉(zhuǎn))。旋轉(zhuǎn)過程如下：
 
2.03 添加4添加4不會(huì)破壞AVL樹的平衡性。
 
2.04 添加5添加5之后，AVL樹失去平衡(RR)，此時(shí)需要對AVL樹進(jìn)行旋轉(zhuǎn)(RR旋轉(zhuǎn))。旋轉(zhuǎn)過程如下：
 
2.05 添加6添加6之后，AVL樹失去平衡(RR)，此時(shí)需要對AVL樹進(jìn)行旋轉(zhuǎn)(RR旋轉(zhuǎn))。旋轉(zhuǎn)過程如下：
 
2.06 添加7添加7之后，AVL樹失去平衡(RR)，此時(shí)需要對AVL樹進(jìn)行旋轉(zhuǎn)(RR旋轉(zhuǎn))。旋轉(zhuǎn)過程如下：
 
2.07 添加16添加16不會(huì)破壞AVL樹的平衡性。
 
2.08 添加15添加15之后，AVL樹失去平衡(RR)，此時(shí)需要對AVL樹進(jìn)行旋轉(zhuǎn)(RR旋轉(zhuǎn))。旋轉(zhuǎn)過程如下：
 
2.09 添加14添加14之后，AVL樹失去平衡(RL)，此時(shí)需要對AVL樹進(jìn)行旋轉(zhuǎn)(RL旋轉(zhuǎn))。旋轉(zhuǎn)過程如下：
 
2.10 添加13添加13之后，AVL樹失去平衡(RR)，此時(shí)需要對AVL樹進(jìn)行旋轉(zhuǎn)(RR旋轉(zhuǎn))。旋轉(zhuǎn)過程如下：
 
2.11 添加12添加12之后，AVL樹失去平衡(LL)，此時(shí)需要對AVL樹進(jìn)行旋轉(zhuǎn)(LL旋轉(zhuǎn))。旋轉(zhuǎn)過程如下：
 
2.12 添加11添加11之后，AVL樹失去平衡(LL)，此時(shí)需要對AVL樹進(jìn)行旋轉(zhuǎn)(LL旋轉(zhuǎn))。旋轉(zhuǎn)過程如下：
 
2.13 添加10添加10之后，AVL樹失去平衡(LL)，此時(shí)需要對AVL樹進(jìn)行旋轉(zhuǎn)(LL旋轉(zhuǎn))。旋轉(zhuǎn)過程如下：
 
2.14 添加8添加8不會(huì)破壞AVL樹的平衡性。
 
2.15 添加9但是添加9之后，AVL樹失去平衡(LR)，此時(shí)需要對AVL樹進(jìn)行旋轉(zhuǎn)(LR旋轉(zhuǎn))。旋轉(zhuǎn)過程如下：
 
3. 打印樹的信息
輸出下面樹的信息：
前序遍歷: 7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16 中序遍歷: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 后序遍歷: 1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7 高度: 5最小值: 1最大值: 16
 
4. 刪除節(jié)點(diǎn)8
刪除操作并不會(huì)造成AVL樹的不平衡。
刪除節(jié)點(diǎn)8之后，再打印該AVL樹的信息。高度: 5中序遍歷: 1 2 3 4 5 6 7 9 10 11 12 13 14 15 16