java avl_Java底层实现AVL 平衡二叉树
1、為什么要有AVL平衡二叉樹
我們之前寫過文章叫做BST二分搜索樹，這種數據結構有一個缺點就是會退化為鏈表形式，到這導致了我們的樹結構發揮不出來它應有的優勢。
從上圖可以發現如果按照順序進行添加操作，那么二分搜索樹就會退化為鏈表形式，樹結構也就失去了它的意義。
AVL(Adelson-Velsky-Landis Tree)是以創造者的名字命名的。這種樹結構就是一種平衡二叉樹。它是最早的認為可以自平衡的一種樹結構。
2、什么是AVL平衡二叉樹
我們之前寫過的滿二叉樹、完全二叉樹、線段樹、最大堆等等都是一種平衡樹的例子(葉子節點的高度差不會大于 1 )。其實上面的平衡二叉樹都是比較理想的例子。但是在AVL樹中維護的平衡二叉樹有所不同。對于任意一個節點，左子樹和右子樹的高度差不能超過 1
上面的規則相對來說更加寬松一些。比如下面這張圖：
這個結構并不滿足我們之前的平衡二叉樹的規則，根節點的左右子樹高度差不大于 1 。卻滿足我們上面的規則(對于任意節點)。
對于時間復雜度方面，平衡二叉樹的高度和節點數量之間也是O(log (N) )。
3、AVL樹的基本實現
3.1、實現的方法
首先，我們需要標注每個節點的高度信息和平衡因子，平衡因子的計算就是左子樹的高度減去右子樹的高度的絕對值。這樣我們就可以依靠平衡因子來維護的AVL樹結構。
3.2、構造函數
我們首先需要構造一個節點信息作為內部類，主要包含我們要存儲的內容，左右子樹的指針，還有高度信息。對于平衡因子我們可以使用左右子樹的差來進行計算。 節點信息：
private class Node{ //內部類 public K key;
public V value;
public Node left, right;
public int height;
public Node(K key, V value){
this.key = key;
this.value = value;
left = null;
right = null;
height = 1; //新節點高度為 1 }
構造函數：
private Node root;
private int size;
public AVLTree(){
root = null;
size = 0;
}
3.3、基本成員函數
首先我們需要獲取樹結構的大小信息getSize()方法和判斷是否為空isEmpty()方法。
程序實現：
public int getSize() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
因為我們需要高度信息來判斷樹結構，所以引入getHeight()方法。
程序實現：
private int getHeight(Node node) {
if (node == null)
return 0;
return node.height;
}
為了方便我們后續的操作，我們引入getNode()方法，通過索引key值來獲得節點。
程序實現：
private Node getNode(K key) {
return getNode(root, key);
}
private Node getNode(Node node, K key) {
if (node == null)
return null;
if (node.key.compareTo(key) < 0)
return getNode(node.left, key);
else if (node.key.compareTo(key) > 0)
return getNode(node.right, key);
else
return node;
}
在添加操作的時候，我們需要根據高度信息來獲得平衡因子，進而判斷樹結構是否滿足平衡樹的性質。大于0：偏左，小于0：偏右
程序實現：
private int getBalanceFactor(Node node){
if (node == null)
return 0;
return getHeight(node.left) - getHeight(node.right);
}
4、左旋轉和右旋轉
我們知道原來平衡的樹變成不平衡會是在添加元素的時候，所以在添加元素的時候我們需要維護平衡性。下面就分四種情況分別討論：
4.1、LL 右旋轉
有一種添加元素后的情況是這樣的。
可以認為添加的元素在節點的左邊(L)的右邊(L)。 在添加元素2，后會導致樹結構的平衡性破壞，對于這種情況的判斷就是當前節點的平衡因子大于1(向左偏斜)，并且左節點的平衡因子大于0(向左偏斜)，這樣就保證了這種情況的出現，向左偏斜。if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
那么我們就需要對上面的結構進行維護。進行右旋轉操作。
為了不失一般性，我們引入更復雜的情況，如下圖：
按照平衡二叉樹的排序規則，對元素進行右旋轉(類似于 y 繞 x 右旋轉)，相當于降低樹的高度。旋轉后仍然滿足二叉樹的排序規則。我們可以發現相對位置發生改變的就是節點 y 和 x 的右子樹 T3 。最后更新高度信息，高度發生變化的只有節點 x , y 。 程序實現：
private Node rightRotate(Node y) {
Node x = y.left; //獲得旋轉中心 Node T3 = x.right;
x.right = y; //進行旋轉操作 y.left = T3;
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1; //重新更新高度信息 x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
4.2、RR 左旋轉
我們有了上面的右旋轉的概念，那么左旋轉就變得簡單多了，左旋轉的發生的前提就是節點的平衡因子小于-1(偏右)，右子樹的平衡因子小于0(偏右)，也就是類似于下面的結構。 可以認為添加的元素在節點的右邊(R)的右邊(R)。if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
下面就是對結構進行左旋轉操作，維護平衡性。
以x為中心，進行左旋轉操作(類似于 y 繞 x 左旋轉)，需要轉移的分別是 x 的左子樹 T2 和節點 y 。 程序實現：
private Node leftRotate(Node y) {
Node x = y.right;
Node T2 = x.left;
x.left = y; //需要轉移的元素 y.right = T2;
y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1; // 更新高度信息 x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;
return x;
}
4.3、LR 左右旋轉
這種情況就是添加元素在節點的左邊的右邊，左右旋轉指的是先進行左旋轉，后進行右旋轉。類似于下面這種情況。
具體細節的旋轉如下：
先進行左旋轉操作，結構就會變成我們之前LL的形式，然后對其進行右旋轉操作即可。
4.4、RL 右左旋轉
這種情況就是添加元素在節點的右邊的左邊，右左旋轉指的是先進行右旋轉，后進行左旋轉。類似于下面這種情況。
具體細節的旋轉如下： 先進行左旋轉操作，結構就會變成我們之前LL的形式，然后對其進行右旋轉操作即可。
4.5、四種情況總結
上面的四種情況完全包含了添加元素所需要的情況。
// LLif (balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
return rightRotate(node);
// RRif (balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
return leftRotate(node);
// LRif (balanceFactor > 1 && getBalanceFactor(node.left) < 0){
node.left = leftRotate(node.left);
return rightRotate(node);
}
// RLif (balanceFactor < -1 && getBalanceFactor(node.right) > 0){
node.right = rightRotate(node.right);
return leftRotate(node);
}
5、增刪改查操作的實現
5.1、添加操縱
步驟：遞歸到底的時候添加元素，否則就更新元素
更新每個節點的高度信息 + 對結構進行平衡處理
private Node add(Node node, K key, V value) {
/** BST 的源代碼片段 ····*/
node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
int balanceFactor = getBalanceFactor(node);
// LL if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0)
return rightRotate(node);
// RR if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0)
return leftRotate(node);
// LR if (balanceFactor > 1 && getBalanceFactor(node.left) < 0){
node.left = leftRotate(node.left);
return rightRotate(node);
}
// RL if (balanceFactor < -1 && getBalanceFactor(node.right) > 0){
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
5.2、刪除操作
這里的刪除操作，在原本BST二分搜索樹的基礎上進行改變，增加刪除元素后對節點進行平衡后的處理，同添加操作基本相同，這里只對增加的程序片段進行展示。
private Node remove(Node node, K key) {
/** BST 的源代碼片段 ····*/
if (retNode == null)
return null;
retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right)); //更新高度值 int balanceFactor = getBalanceFactor(retNode);
// LL if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0)
return rightRotate(retNode);
// RR if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0)
return leftRotate(retNode);
// LR if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0){
retNode.left = leftRotate(retNode.left);
return rightRotate(retNode);
}
// RL if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0){
retNode.right = rightRotate(retNode.right);
return leftRotate(retNode);
}
return retNode;
}
5.3、查詢操作
查詢操作主要包含查看元素是否在樹結構中，另一個就是通過key值查找對應的 value 值。兩者均是借助getNode方法進行實現。 程序實現：
public boolean contains(K key) {
return getNode(key) != null;
}
public V get(K key) {
Node node = getNode(key);
return node == null ? null : node.value;
}
5.4、更改操作
更改操作也是借助getNode方法進行更改。
public void set(K key, V newValue) {
Node node = getNode(key);
if (node != null)
node.value = newValue;
else
throw new IllegalArgumentException(key + "doesn't exist");
}
最后
更多精彩內容，大家可以轉到我的主頁：源碼地址在主頁內哦~~首頁 | 曲怪曲怪?quguai.cn
總結
以上是生活随笔為你收集整理的java avl_Java底层实现AVL 平衡二叉树的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： java 注解继承注解_Java注解合并
- 下一篇： java 宽字节_宽字节注入