2014-06-12 15:00:14
主要内容为：
AVL树的插入操作；
AVL树的删除操作；
AVL树的插入操作主要参考<<数据结构与算法分析>>Java语言描述(Mark Allen Weiss)这个博客写的也挺好，可以看下http://dongxicheng.org/structure/avl/
AVL树的删除操作看了http://blog.chinaunix.net/uid-28852942-id-4035450.html写的，思路很清晰，做了改进，变成了一个函数。
AVL树插入操作和删除操作应该先看一下二叉查找树的插入和删除操作。
先说插入操作：
插入操作直接看书上的，第一开始觉得书上代码有问题。即经过旋转操作，没有及时调整各子树的高度，其实递归过程都调整了。
通过递归，找到一个叶子节点，此时，生成一个新节点，然后插入到此叶子节点之下。由于是递归过程，所以相当于从当前的插入节点开始，往上到树的root节点开始进行平衡判定，旋转操作。并在每一步进行节点的高度计算。
删除操作也和这个差不多，只是找到删除的节点，接着递归删除右子树最左边的节点。
同时，从下往上开始调整，用fixup函数对平衡二叉树进行旋转操作。
public class AVLTree> { public static void main(String[] args) { AVLTree avlTree = new AVLTree (); for (int i = 0; i < 300; i++) { avlTree.insert(i); } avlTree.deleteKey(30); avlTree.deleteKey(500); avlTree.showTree(); } private AVLTreeNode root; public static class AVLTreeNode { public T element; public AVLTreeNode left; public AVLTreeNode right; public int hight; public AVLTreeNode(T element, AVLTreeNode left, AVLTreeNode right) { this.element = element; this.left = left; this.right = right; this.hight = 0; } public AVLTreeNode(T theElement) { element = theElement; } } public void insert(T element) { root = insert(element, root); } public AVLTreeNode insert(T element, AVLTreeNode root) { if (root == null) { return new AVLTreeNode(element, null, null); } int compareResult = compare(element, root.element); if (compareResult < 0) { root.left = insert(element, root.left); if (height(root.left) - height(root.right) == 2) { if (compare(element, root.left.element) < 0) { root = singleRoateWithLeft(root); } else { root = doubleRoateWithLeft(root); } } } else if (compareResult > 0) { root.right = insert(element, root.right); if (height(root.right) - height(root.left) == 2) { if (compare(element, root.right.element) > 0) { root = singleRoateWithRight(root); } else { root = doubleRoateWithRight(root); } } } else ; root.hight = Math.max(height(root.left), height(root.right)) + 1; return root; } private int height(AVLTreeNode T) { // TODO Auto-generated method stub if (T == null) { return -1; } else return T.hight; } private int compare(T element, T element2) { return element.compareTo(element2); } public void deleteKey(T key) { deleteKey(key, root); } public AVLTreeNode deleteKey(T key, AVLTreeNode root) { if (root != null && root.element == key) { // 要删除的节点是当前root节点 if (root.left == null) { // 左节点为空，或者两个子节点都为空 root = root.right; } else if (root.right == null) { // 右节点为空，即是只有左节点 root = root.left; } else { // 第三种情况，即是此节点有两个孩子 AVLTreeNode temp = root.right; while (temp.left != null) { temp = temp.left; } root.element = temp.element; root.right = deleteKey(temp.element, root.right); } if (root != null) { root.hight = Math.max(height(root.left), height(root.right)) + 1; if (numOfUnbalance(root.left, root.right) >= 2) { fixUp(root); } } return root; } else if (root != null) { // 当前节点非空，且当前节点值不为key if (key.compareTo(root.element) < 0) { root.left = deleteKey(key, root.left); } else { root.right = deleteKey(key, root.right); } root.hight = Math.max(height(root.left), height(root.right)) + 1; if (numOfUnbalance(root.left, root.right) >= 2) { fixUp(root); } return root; } System.out.println("没有找到节点__" + key);// 最后是没有此节点情况 return null; } public AVLTreeNode fixUp(AVLTreeNode root) { if (height(root.left) > height(root.right)) { if (height(root.left.left) >= height(root.left.right)) { root = singleRoateWithRight(root); } else { root = doubleRoateWithRight(root); } } else if (height(root.left) < height(root.right)) { if (height(root.left.left) >= height(root.left.right)) { root = singleRoateWithLeft(root); } else { root = doubleRoateWithLeft(root); } } return root; } public int numOfUnbalance(AVLTreeNode T1, AVLTreeNode T2) { if (height(T1) - height(T2) >= 0) { return height(T1) - height(T2); } else return height(T1) - height(T2); } public AVLTreeNode singleRoateWithLeft(AVLTreeNode T2) { AVLTreeNode T1; T1 = T2.left; T2.left = T1.right; T1.right = T2; T2.hight = Math.max(height(T2.left), height(T2.right)) + 1; T1.hight = Math.max(height(T1.left), height(T2)) + 1; return T1; } public AVLTreeNode singleRoateWithRight(AVLTreeNode T1) { AVLTreeNode T2; T2 = T1.right; T1.right = T2.left; T2.left = T1; T1.hight = Math.max(height(T1.left), height(T1.right)) + 1; T2.hight = Math.max(height(T1), height(T2.right)) + 1; return T2; } public AVLTreeNode doubleRoateWithLeft(AVLTreeNode T2) { T2.left = singleRoateWithRight(T2.left); return singleRoateWithLeft(T2); } public AVLTreeNode doubleRoateWithRight(AVLTreeNode T2) { T2.right = singleRoateWithLeft(T2.right); return singleRoateWithRight(T2); } public void showTree() { showTree(root); } public void showTree(AVLTreeNode T) { if (T == null) { return; } else { showTree(T.left); System.out.println(T.element + "__" + T.hight); showTree(T.right); } }}
看教材，加上给出的一个删除操作的博客地址，就没问题了。