二叉排序树查找、插入和删除操作的时间复杂度和树的深度n有关。构建树时，当先后插入的结点按关键字有序时，二叉排序树退化为链表，插入和删除的时间都会上升到O(n)。因此需要在构建二叉排序树的过程中进行“平衡化”处理，使之成为二叉平衡树。
二叉平衡树，又称AVL树。它或者是一棵空树，或者是具有下列性质的树：
1)具备二叉排序树的所有性质；
2)左子树和右子树深度差的绝对值不超过1；
3)左子树和右子树都是二叉平衡树
以上，得出AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。
对于旋转定义可以参考链接：www.cnblogs.com/skywang12345/p/3576969.html#a1以及www.cnblogs.com/Camilo/p/3917041.html
/**
* node节点
* @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
}
/**
* 四种旋转实现（LL，LR，RL，RR）
*/
// 单右旋 LL 返回值：旋转后的根节点
// 当根结点左子树的左子树中的节点导致根结点的平衡因子为2时，采用LL型旋转进行调整。
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
// 根结点右子树的右子树中的节点导致根结点的平衡因子为-2时，采用RR型旋转进行调整。
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型(先单次左旋，再单次右旋)
// 当根结点左子树的右子树中的节点导致根结点的平衡因子为2时，采用LR型旋转进行调整。
private AVLNode lrRotate(AVLNode node){
node.left = rrRotate(node.left); // 左子树部分左旋
return llRotate(node); // 整体右旋ll
}
// RL型(先单次右旋，再单次左旋)
// 当根结点右子树的左子树中的节点导致根结点的平衡因子为-2时，采用RL型旋转进行调整。
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)，返回根节点
* 参数说明：
* val:待删除的结点
* return:
* 根节点
*/
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;
}
// 将该最大节点的值赋值给tree
node.value = x.value;
// 删除该最大节点
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节点：" + 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]
网友评论