二叉排序樹查找、插入和刪除操作的時間復雜度和樹的深度n有關。構建樹時穿剖，當先后插入的結點按關鍵字有序時，二叉排序樹退化為鏈表卦溢，插入和刪除的時間都會上升到O(n)糊余。因此需要在構建二叉排序樹的過程中進行“平衡化”處理秀又，使之成為二叉平衡樹。
二叉平衡樹贬芥，又稱AVL樹吐辙。它或者是一棵空樹，或者是具有下列性質(zhì)的樹：
1)具備二叉排序樹的所有性質(zhì)蘸劈；
2)左子樹和右子樹深度差的絕對值不超過1昏苏；
3)左子樹和右子樹都是二叉平衡樹
以上，得出AVL樹的查找威沫、插入和刪除在平均和最壞情況下都是O(logn)贤惯。
對于旋轉(zhuǎn)定義可以參考鏈接：www.cnblogs.com/skywang12345/p/3576969.html#a1以及www.cnblogs.com/Camilo/p/3917041.html
/**
* node節(jié)點
* @author SUJiannan
*/
class AVLNode {
// 單node 高度為0 ；
// 空樹 高度為 -1
public int value; //值棒掠；為簡化操作
public AVLNode left; //左孩子結點
public AVLNode right; //右孩子結點
public int height; //樹的高度
public AVLNode(int value) {
this.value = value;
this.height = 0; // 樹的init高度為0
}
public AVLNode() {
}
}
package tree;
import java.util.ArrayList;
import java.util.List;
/**
* 二叉平衡樹
* @author SUJiannan
* @see 下午8:26:31
* 圖例參考：http://www.cnblogs.com/Camilo/p/3917041.html
*/
public class AVLTree {
private AVLNode root; // 根結點
/**
* 計算樹的高度
*/
public int height(AVLNode node){
return node == null ? -1 : node.height; // 空樹高度為-1
}
/**
* 四種旋轉(zhuǎn)實現(xiàn)（LL救巷，LR，RL句柠，RR）
*/
// 單右旋 LL 返回值：旋轉(zhuǎn)后的根節(jié)點
// 當根結點左子樹的左子樹中的節(jié)點導致根結點的平衡因子為2時浦译，采用LL型旋轉(zhuǎn)進行調(diào)整。
private AVLNode llRotate(AVLNode node){
AVLNode x = node.left;
node.left = x.right;
x.right = node;
node.height = Math.max(this.height(node.right),this.height(node.left)) + 1;
x.height = Math.max(this.height(x.left), node.height) + 1;
return x;
}
// 單左旋 RR
// 根結點右子樹的右子樹中的節(jié)點導致根結點的平衡因子為-2時溯职，采用RR型旋轉(zhuǎn)進行調(diào)整精盅。
private AVLNode rrRotate(AVLNode node){
AVLNode x = node.right;
node.right = x.left;
x.left = node;
node.height = Math.max(this.height(node.right),this.height(node.left)) + 1;
x.height = Math.max(this.height(x.right), node.height) + 1;
return x;
}
// LR型(先單次左旋，再單次右旋)
// 當根結點左子樹的右子樹中的節(jié)點導致根結點的平衡因子為2時谜酒，采用LR型旋轉(zhuǎn)進行調(diào)整叹俏。
private AVLNode lrRotate(AVLNode node){
node.left = rrRotate(node.left); // 左子樹部分左旋
return llRotate(node); // 整體右旋ll
}
// RL型(先單次右旋，再單次左旋)
// 當根結點右子樹的左子樹中的節(jié)點導致根結點的平衡因子為-2時僻族，采用RL型旋轉(zhuǎn)進行調(diào)整粘驰。
private AVLNode rlRotate(AVLNode node){
node.right = llRotate(node.right); // 右子樹部分右旋
return rrRotate(node);
}
/**
* 插入操作
*/
public void insert(int val) {
this.root = insert(root,val);
}
public AVLNode insert(AVLNode node, int val){
if(node == null) {
return new AVLNode(val);
}
int cmp = node.value - val;
if(cmp > 0) {
node.left = insert(node.left,val);
if(height(node.left) - height(node.right) == 2) {
if(node.left.value > val) {
// ll
node = llRotate(node);
} else {
// lr
node = lrRotate(node);
}
}
} else if(cmp < 0) {
node.right = insert( node.right,val);
if(height(node.left) - height(node.right) == -2) {
if(val > node.right.value) {
// rr
node = rrRotate(node);
} else {
//rl
node = rlRotate(node);
}
}
} else {
// 相等 無操作
return null;
}
// 插入后 樹的高度
node.height = Math.max(height(node.left), height(node.right)) + 1;
return node;
}
/**
* 刪除結點(z)，返回根節(jié)點
* 參數(shù)說明：
* val:待刪除的結點
* return:
* 根節(jié)點
*/
public AVLNode remove(int val) {
AVLNode root = remove(this.root , val);
return root;
}
private AVLNode remove(AVLNode node, int val) {
if(node == null) {
// System.out.println("not find");
return null;
}
// find value
int cmp = node.value - val;
if(cmp > 0) {
node.left = remove(node.left,val);
if(this.height(node.left) - height(node.right) == -2) {
AVLNode tmpNode = node.right;
if(height(tmpNode.left) > height(tmpNode.right)) {
//rl
node = this.rlRotate(node);
} else {
//rr
node = this.rrRotate(node);
}
}
} else if (cmp < 0) {
node.right = remove(node.right,val);
if ( height(node.left ) - height(node.right) == 2) {
AVLNode tmpNode = node.left;
if(height(tmpNode.left) < height(tmpNode.right)) {
// lr
node = lrRotate(node);
} else {
// ll
node = llRotate(node);
}
}
} else {
// find it and delete it
if(node.left == null && node.right == null) {
node = null;
} else if(node.left != null && node.right == null ) {
node = node.left;
// delete后 樹的高度
node.height = Math.max(height(node.left), height(node.right)) + 1;
} else if(node.left == null && node.right != null) {
node = node.right;
// delete后 樹的高度
node.height = Math.max(height(node.left), height(node.right)) + 1;
} else {
// 獲取左子樹最大的node
AVLNode x = node.left;
while(x.right != null) {
x = x.right;
}
// 將該最大節(jié)點的值賦值給tree
node.value = x.value;
// 刪除該最大節(jié)點
node.left = remove(node.left , x.value);
// delete后 樹的高度
node.height = Math.max(height(node.left), height(node.right)) + 1;
}
}
return node;
}
/**
* 查找當前value對應的node
*/
public AVLNode get(int value) {
AVLNode avlNode = get(value,this.root);
// 利用int最小值代表未找到
return avlNode == null ? new AVLNode(Integer.MIN_VALUE) : avlNode;
}
private AVLNode get(int value,AVLNode node) {
if(node == null) {
return null; // not find
}
int cmp = value - node.value;
if(cmp > 0) {
return get(value , node.right);
} else if(cmp < 0) {
return get(value , node.left);
} else {
// find it
return node;
}
}
/**
* 中序遍歷
*/
public void printZhong(){
List list = new ArrayList();
printZ(this.root , list);
System.out.println("中序遍歷：" + list);
}
private void printZ(AVLNode node, List list) {
if(node != null) {
printZ(node.left ,list) ;
list.add(node.value);
printZ(node.right ,list) ;
}
}
/**
* 先序遍歷
*/
public void printXian(){
List list = new ArrayList();
printX(this.root , list);
System.out.println("先序遍歷：" + list);
}
private void printX(AVLNode node, List list) {
if(node != null) {
list.add(node.value);
printX(node.left ,list) ;
printX(node.right ,list) ;
}
}
}
測試代碼：
public static void main(String[] args) {
int arr[]= {3,2,1,4,5,6,7,16,15,14,13,12,11,10,8,9};
AVLTree a = new AVLTree();
for (int i : arr) {
a.insert(i);
}
a.remove(5);
a.remove(6);
a.printXian();
a.printZhong();
AVLNode avlNode = a.get(900);
System.out.println("尋找9的node節(jié)點：" + avlNode.value);
}
運行結果：
先序遍歷：[7, 2, 1, 4, 3, 13, 11, 9, 8, 10, 12, 15, 14, 16]
中序遍歷：[1, 2, 3, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
