算法--平衡二叉樹AVL原理分析以及代碼實現

前文介紹了，二叉樹、二叉排序樹，需要了解的不妨關注下小JIA。

AVL是一種高度平衡的二叉排序樹。對於任意節點左子樹與右子樹高度差不超過1，AVL的高度與節點數量為O（logn）關係。平衡因子等於左子樹高度減去右子樹高度。AVL所有節點的平衡因子只可能是-1、0、1。因此當添加元素或刪除元素時有可能會破會這種平衡，所以需要維護。失去平衡主要有四種情況，分別為LL、LR、RR和RL。

AVL 的節點定義

public class AVLTreeNode> {
 private T key; //關鍵字(鍵值)
 private int height; //高度
 private AVLTreeNode left; //左孩子
 private AVLTreeNode right; //右孩子
 public AVLTreeNode(T key, AVLTreeNode 
 left, AVLTreeNode right) {
 this.key = key;
 this.left = left;
 this.right = right;
 this.height = 0;
 }
 ......
 }

LL

LL,平衡因子大於1，左子樹平衡因子大於等於0，需要將A順時針向下右旋轉，B做為父節點

右旋轉操作，首先保存B右子樹K3，將A做為B的右子樹，K3做為A的左孩子，並更新A，B的高度值，完成旋轉。

/* LL：左旋轉 */
private AVLTreeNode leftLeftRotation(AVLTreeNode node) {
 AVLTreeNode 
 tempNode;
 
 tempNode = node.getLeft();
 node.setLeft(tempNode.getRight());
 tempNode.setRight(node);
 
 node.setHeight(max(height(node.getLeft()), height(node.getRight())) + 1);
 tempNode.setHeight(max(height(tempNode.getLeft()), node.getHeight()) + 1);
 return tempNode;
}

RR

RR，平衡因子小於-1，右子樹平衡因子小於等於0，需要將A逆時針向下左旋轉，B做為父節點

左旋轉操作，首先保存B左子樹K2，將A做為B的左子樹，K2做為B的右孩子，並更新A、B的高度值，完成旋轉

/* RR：右旋轉 */
private AVLTreeNode rightRightRotation(AVLTreeNode node) {
 AVLTreeNode 
 tempNode;
 
 tempNode = node.getRight();
 node.setRight(tempNode.getLeft());
 tempNode.setLeft(node);
 node.setHeight(max( height(node), height(node.getRight())) + 1);
 tempNode.setHeight(max( height(tempNode.getRight()), node.getHeight()) + 1);
 return tempNode;
}

LR

LR，平衡因子大於1，左子樹平衡因子小於0，首先將B進行左旋轉，在將A進行右旋轉

/* LR：左雙旋轉 */
private AVLTreeNode leftRightRotation(AVLTreeNode node) {
 node.setLeft(rightRightRotation(node.getLeft()));
 return leftLeftRotation(node);
}

RL

RL，平衡因子大於-1，右子樹平衡因子大於0，首先將B進行右旋轉，在將A進行左旋轉

/* RL：右雙旋轉 */
private AVLTreeNode rightLeftRotation(AVLTreeNode node) {
 node.setRight(leftLeftRotation(node.getRight()));
 return rightRightRotation(node);
}

插入節點

原則：根據二叉查找樹BST的規定插入數據，再來判斷是否失去平衡；若失去平衡再根據文上介紹的旋轉規則平衡數據；最後再設置樹高。

/* 將結點插入到AVL樹中 */
private AVLTreeNode insert(AVLTreeNode tree, T key) {
 if (tree == null) {
 //新建節點
 tree = new AVLTreeNode(key, null, null);
 } else {
 int cmp = key.compareTo(tree.getKey());
 if (cmp < 0) { //將key插入到tree的左子樹
 tree.setLeft(insert(tree.getLeft(), key));
 
 //插入節點後，若AVL樹失去平衡，則進行相應的調節。
 if (height(tree.getLeft()) - height(tree.getRight()) > 1) {
 if (key.compareTo(tree.getLeft().getKey()) < 0)
 tree = leftLeftRotation(tree); 

 else
 tree = leftRightRotation(tree);
 }
 } else if (cmp > 0) {//將key插入到tree的右子樹
 tree.setRight(insert(tree.getRight(), key)); 
 
 //插入節點後，若AVL樹失去平衡，則進行相應的調節。
 if (height(tree.getRight()) - height(tree.getLeft()) > 1) {
 if (key.compareTo(tree.getRight().getKey()) > 0)
 tree = rightRightRotation(tree);
 else
 tree = rightLeftRotation(tree);
 }
 }
 }
 tree.setHeight(max(height(tree.getLeft()), height(tree.getRight())) + 1);
 return tree;
}

刪除節點

同理，先找到刪除節點的位置，再進行AVL平衡調節。找到要刪除的節點Z後，如果Z的左右孩子都非空，

a)若Z的左子樹高於右子樹，找出左子樹中的最大節點K(maxNum方法)，使用K的值替換掉Z的值，並刪除K；

b)若Z的左子樹矮於或等於右子樹，找出右子樹中最小節點K(minNum方法)，使用K的值替換掉Z的值，並刪除K。

這種方式的好處是刪除後AVL樹仍然是平衡的。

/* 刪除結點 */
private AVLTreeNode remove(AVLTreeNode tree, AVLTreeNode delNode) {
 //根為空 或者 沒有要刪除的節點，直接返回null。
 if (tree == null || delNode == null)
 return null;
 int cmp = delNode.getKey().compareTo(tree.getKey());
 if (cmp < 0) { //待刪除的節點在tree的左子樹中
 tree.setLeft(remove(tree.getLeft(), delNode));
 
 // 刪除節點後，若AVL樹失去平衡，則進行相應的調節。
 if (height(tree.getRight()) - height(tree.getLeft()) > 1) {
 AVLTreeNode r = tree.getRight();
 if (height(r.getLeft()) > height(r.getRight()))
 tree = rightLeftRotation(tree);
 else
 tree = rightRightRotation(tree);
 }
 } else if (cmp > 0) { //待刪除的節點在tree的右子樹中
 tree.setRight(remove(tree.getRight(), delNode));
 
 // 刪除節點後，若AVL樹失去平衡，則進行相應的調節。
 if (height(tree.getLeft()) - height(tree.getRight()) > 1) {
 AVLTreeNode l = tree.getLeft();
 if (height(l.getRight()) > height(l.getLeft()))
 tree = leftRightRotation(tree);
 else
 tree = leftLeftRotation(tree);
 }
 } else { // tree是對應要刪除的節點。 

 // tree的左右孩子都非空
 if ((tree.getLeft() != null) && (tree.getRight() != null)) { 
 //如果tree的左子樹比右子樹高；
 if (height(tree.getLeft()) > height(tree.getRight())) { 
 AVLTreeNode max = maxNum(tree.getLeft());
 tree.setKey(max.getKey());
 tree.setLeft(remove(tree.getLeft(), max));
 //如果tree的左子樹矮於或等於右子樹
 } else {
 AVLTreeNode min = minNum(tree.getRight());
 tree.setKey(min.getKey());
 tree.setRight(remove(tree.getRight(), min));
 }
 } else {
 AVLTreeNode tmpNode = tree;
 tree = (tree.getLeft() != null) ? tree.getLeft() : tree.getRight();
 tmpNode = null;
 }
 }
 return tree;
}