圖解AVL樹
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的構造
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的左子樹進行插入；>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;
}
}
3：AVL樹的刪除
3.1：刪除葉子節點
3.2：刪除只擁有左子樹或右子樹的節點
3.3：刪除既擁有左子樹又有右子樹的節點
3.4：自測題
將上一道自測題的圖依次刪除16，15，11節點，畫出最後的結果
參考鏈接
數據可視化網站： //visualgo.net/zh
