package avitree;
/**
* 平衡二叉查找树类
*
* @param <T>
*/
public class AvlTree<T extends Comparable<? super T>> {
public static void main(String[] args) {
AvlTree<Integer> tree = new AvlTree<Integer>();
//第一组数据 測试 右左双旋转
// tree.insert(9);
// tree.insert(5);
// tree.insert(10);
// tree.insert(7);
// tree.insert(6);// 插这个的时候会有双旋转哦,用于測试 右左双旋转
// tree.preOrder(tree.root);
//第二组数据 測试左右双旋转
tree.insert(9);
tree.insert(5);
tree.insert(20);
tree.insert(17);
tree.insert(18);
tree.preOrder(tree.root);
}
/**
* 树的根节点
*/
public AvlNode<T> root = null;
/**
* 构造一颗空的平衡二叉树
*
*/
public AvlTree() {
}
/**
* 插入一个元素，通过这种方法来插入元素
* @param element
*/
public void insert(T element) {
if (this.root == null) {
this.root = insert(element, this.root);
} else {
insert(element, this.root);
}
}
/**
* 插入一个包括元素的新节点
*
* @param element
* @param target
* @return
*/
private AvlNode<T> insert(T element, AvlNode<T> target) {
if (target == null) {
return new AvlNode<T>(element, null, null);
}
int compareResult = element.compareTo(target.element);// 比較里面的元素大小
if (compareResult < 0) {
target.left = insert(element, target.left);
if (Math.abs(height(target.left) - height(target.right)) > 1) {// 左右子树高度差>1 打破平衡。选择单旋转或者双旋转调节平衡
if (element.compareTo(target.left.element) < 0) {//单旋转
target = rotateLeft(target);
} else {// 双旋转
target = doubleRotateLeft(target);
}
}
} else if (compareResult > 0) {
target.right = insert(element, target.right);
if (Math.abs(height(target.left) - height(target.right)) > 1) {
if (element.compareTo(target.right.element) > 0) {//单旋转
target = rotateRight(target);
} else {//双旋转
target = doubleRotateRight(target);
}
}
} else {//同样元素不予理会
}
target.height = Math.max(height(target.left), height(target.right)) + 1;
return target;
}
/**
* 单旋转 左旋转
* @param target
* @return
*/
private AvlNode<T> rotateLeft(AvlNode<T> k2) {
AvlNode<T> k1 = k2.left;
k2.left = k1.right;
k1.right = k2;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
return k1;
}
private AvlNode<T> rotateRight(AvlNode<T> k2) {
AvlNode<T> k1 = k2.right;
k2.right = k1.left;
k1.left = k2;
k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
return k1;
}
private AvlNode<T> doubleRotateLeft(AvlNode<T> k3) {
k3.left = rotateRight(k3.left);
return rotateLeft(k3);
}
private AvlNode<T> doubleRotateRight(AvlNode<T> k3) {
k3.right = rotateLeft(k3.right);
return rotateRight(k3);
}
/**
* 先序遍历測试下程序有没有bug
* @param node
*/
public void preOrder(AvlNode<T> node) {
System.out.println(node.element);
if (node.left != null) {
preOrder(node.left);
}
if (node.right != null) {
preOrder(node.right);
}
}
/**
* 获取某个节点的高度
*
* @param node
* @return
*/
public int height(AvlNode<T> node) {
return node == null ? -1 : node.height;
}
/**
* 节点类。採用静态内部类构造
*
* @param <T>
*/
private static class AvlNode<T> {
/** 节点存储的数据 。泛型类型。能够存储随意类型的元素 **/
private T element;
/** 节点的左孩子 **/
AvlNode<T> left;
/** 节点的右孩子 **/
AvlNode<T> right;
/** 节点高度。节点为null时为-1， 新插入的节点为0，插入时递归调整父节点的高度 **/
private int height;
public AvlNode(T element, AvlNode<T> leftChild, AvlNode<T> rightChild) {
this.element = element;
this.left = leftChild;
this.right = rightChild;
}
@Override
public String toString() {
return "node:" + this.element + " height:" + height;
}
}
}