remove
remove分成三种情况，没有孩子节点的节点(即页子),单个孩子节点的节点，两个孩子节点的节点
1)页子节点可以直接删除
2)单个孩子节点的节点删除了，让其下的孩子节点直接和其父亲节点相连(就是孩子节点和祖父节点相连)
3)两个孩子节点的节点，为了保持排序状态，需要拿到这个节点的左子树的最大节点或者右子树的最小节点，得到这个节点的数据代替要删除的节点，
然后删除这个左子树的最大节点或者右子树的最小节点，因为左子树的最大节点没有右节点(有右节点的话，他就不是最大的了),同理，右子树的最小节点
没有左节点，所以要删除的这个节点只有一个或者没有孩子节点，只需要进行1)或者2)就完成了。
AVL树
在插入节点时通过旋转(rotation)解决问题:
/**
* 插入一个元素到树里面，可能破坏了高度差，需要找到一个节点a，该节点左子树和右子树被破坏了，则需要对这个节点(平衡因子)
*
* 树进行平衡，有四种情况:
*
* 1.a节点的左儿子的左子树插入
*
* 2.a节点的左儿子的右子树插入
*
* 3.a节点的右儿子的左子树插入
*
* 4.a节点的右儿子的右子树插入
*
*
* 1.4两种情况需要进行一次旋转
*
* 2.3两种情况需要进行两次旋转
*
* 旋转的目的是为了使插入节点的树的高度降低1，所以只要求旋转平衡因子为根的树就可以了
*/
在删除节点的时候：
/**
* 删除一个节点，找到平衡因子，他的左子树高度和右子树高度如果相差2的话，就需要旋转，而且旋转后，平衡因子的节点为根的树的高度肯定会
*
* 下降1，这样平衡因子所在的树的高度下降1，也有可能需要进行旋转调整，这样调整一直到根节点
*
*/
代码如下：
package struct;
/**
* @author chenxiaohui
* @version 创建时间：2011-8-26
*
*
*/
public class AvlTree {
/**
*
* avl树:树中每个节点的左子树和右子树的高度最多差1的二叉查找树
*
*
*
*/
public int height(AvlNode node) {
return node != null ? node.height : -1;
}
/**
*
*
* 插入一个元素到树里面，可能破坏了高度差，需要找到一个节点a，该节点左子树和右子树被破坏了，则需要对这个节点(平衡因子)
*
* 树进行平衡，有四种情况:
*
* 1.a节点的左儿子的左子树插入
*
* 2.a节点的左儿子的右子树插入
*
* 3.a节点的右儿子的左子树插入
*
* 4.a节点的右儿子的右子树插入
*
*
* 1.4两种情况需要进行一次旋转
*
* 2.3两种情况需要进行两次旋转
*
* @param t
* @param tree
* @return
*/
public AvlNode insert(int t, AvlNode tree) {
if (tree == null)
return new AvlNode(t);
int cmp = compare(t, tree.element);
if (cmp < 0) {
// 左子树
tree.leftChild = insert(t, tree.leftChild);
// 因为左子树插入了节点，那么左子树比右子树高,根据avl树的性质，插入了节点
// 要么高度差为1，要么高度差为2，所以当相差为2时，需要进行树的调整
if ((height(tree.leftChild) - height(tree.reightChild)) == 2) {
// 当t比树左子树的元素还小的话，就是在树的左子树的左边插入节点，成为左子树的左子树，需要一次旋转
if (compare(t, tree.leftChild.element) < 0) {
tree = rotateLeftChild(tree);
} else {
// 当t比树左子树的元素还大的话，就是在树的左子树的右边插入节点，成为左子树的右子树，需要两次旋转
tree = doubleRotateLeftChild(tree);
}
}
} else if (cmp > 0) {
// 右子树
tree.reightChild = insert(t, tree.reightChild);
if ((height(tree.reightChild) - height(tree.leftChild)) == 2) {
// 当t比树右子树的元素还大的话，就是在树的右子树的右边插入节点，成为右子树的右子树，需要一次旋转
if (compare(t, tree.reightChild.element) > 0) {
tree = rotateRightChild(tree);
} else {
// 当t比树右子树的元素还小的话，就是在树的右子树的左边插入节点，成为右子树的左子树，需要两次旋转
tree = doubleRotateRightChild(tree);
}
}
} else {
// 树里面有这个树
}
tree.height = Math
.max(height(tree.leftChild), height(tree.reightChild)) + 1;
return tree;
}
/**
* 第1种情况需要进行顺时针旋转(右旋转)
*
* @param k2
* @return
*/
private AvlNode rotateLeftChild(AvlNode k2) {
AvlNode k1 = k2.leftChild;
k2.leftChild = k1.reightChild;
k1.reightChild = k2;
k2.height = Math.max(height(k2.leftChild), height(k2.reightChild)) + 1;
k1.height = Math.max(height(k1.leftChild), height(k2)) + 1;
return k1;
}
/**
*
* 第4种情况需要进行逆时针旋转(左旋转)
*
* @param k2
* @return
*/
private AvlNode rotateRightChild(AvlNode k2) {
AvlNode k1 = k2.reightChild;
k2.reightChild = k1.leftChild;
k1.leftChild = k2;
k2.height = Math.max(height(k2.leftChild), height(k2.reightChild)) + 1;
k1.height = Math.max(height(k1.reightChild), height(k2)) + 1;
return k1;
}
/**
* 第2种情况需要进行(右-左旋转)
*
* @param k3
* @return
*/
private AvlNode doubleRotateLeftChild(AvlNode k3) {
AvlNode k1 = k3.leftChild;
k3.leftChild = rotateRightChild(k1);
return rotateLeftChild(k3);
}
/**
* 第3种情况需要进行(左-右旋转)
*
* @param k3
* @return
*/
private AvlNode doubleRotateRightChild(AvlNode k3) {
AvlNode k1 = k3.reightChild;
k3.reightChild = rotateLeftChild(k1);
return rotateRightChild(k3);
}
public int compare(int a, int b) {
return a - b;
}
static class AvlNode {
private int element;
private int height;
private AvlNode leftChild;
private AvlNode reightChild;
AvlNode(int element) {
this(element, null, null);
}
AvlNode(int element, AvlNode left, AvlNode right) {
this.element = element;
this.leftChild = left;
this.reightChild = right;
}
}
public void sysout(AvlNode node) {
if (node != null) {
AvlNode a = node.leftChild;
sysout(a);
for (int i = 0; i < node.height; i++) {
System.out.print(" ");
}
System.out.print(node.element);
System.out.print("\n");
AvlNode b = node.reightChild;
sysout(b);
}
}
/**
* 删除一个节点，找到平衡因子，他的左子树高度和右子树高度如果相差2的话，就需要旋转，而且旋转后，平衡因子的节点为根的树的高度肯定会
*
* 下降1，这样平衡因子所在的树的高度下降1，也有可能需要进行旋转调整，这样调整一直到根节点
*
* @param t
* @param tree
* @return
*/
public AvlNode delete(int t, AvlNode tree) {
if (tree == null)
return null;
int cmp = compare(t, tree.element);
if (cmp < 0) {
tree.leftChild = delete(t, tree.leftChild);
if ((height(tree.reightChild) - height(tree.leftChild)) == 2) {
if (tree.leftChild == null) {
tree = rotateRightChild(tree);
} else {
tree = doubleRotateRightChild(tree);
}
}
} else if (cmp > 0) {
tree.reightChild = delete(t, tree.reightChild);
if ((height(tree.leftChild) - height(tree.reightChild)) == 2) {
if (tree.reightChild == null) {
tree = rotateLeftChild(tree);
} else {
tree = doubleRotateLeftChild(tree);
}
}
} else if (cmp == 0) {
tree = null;
}
if (tree != null) {
tree.height = Math.max(height(tree.leftChild),
height(tree.reightChild)) + 1;
}
return tree;
}
public static void main(String[] args) {
AvlTree avlTree = new AvlTree();
AvlNode node = new AvlNode(20);
/*
* Random random = new Random(); for (int i = 0; i < 10; i++) { int y =
* random.nextInt(100) + 1; node = avlTree.insert(y, node); }
*/
node = avlTree.insert(8, node);
node = avlTree.insert(3, node);
node = avlTree.insert(10, node);
node = avlTree.insert(2, node);
node = avlTree.insert(5, node);
node = avlTree.insert(30, node);
node = avlTree.insert(50, node);
node = avlTree.insert(6, node);
node = avlTree.insert(20, node);
node = avlTree.insert(35, node);
node = avlTree.insert(43, node);
node = avlTree.insert(60, node);
node = avlTree.insert(18, node);
node = avlTree.insert(26, node);
node = avlTree.insert(33, node);
node = avlTree.insert(40, node);
node = avlTree.insert(45, node);
node = avlTree.insert(62, node);
// avlTree.sysout(node);
node = avlTree.delete(2, node);
avlTree.sysout(node);
}
}