平衡二叉树Java实现

浏览数：21 / 时间：2015年06月08日

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<T extends Comparable<? super T>> {

    public static void main(String[] args) {
        AVLTree<Integer> avlTree = new AVLTree<Integer>();
        for (int i = 0; i < 300; i++) {
            avlTree.insert(i);
        }
        avlTree.deleteKey(30);
        avlTree.deleteKey(500);
        avlTree.showTree();
    }

    private AVLTreeNode<T> root;

    public static class AVLTreeNode<T> {
        public T element;
        public AVLTreeNode<T> left;
        public AVLTreeNode<T> right;
        public int hight;

        public AVLTreeNode(T element, AVLTreeNode<T> left, AVLTreeNode<T> 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<T> insert(T element, AVLTreeNode<T> 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> 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<T> deleteKey(T key, AVLTreeNode<T> 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<T> 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<T> fixUp(AVLTreeNode<T> 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<T> T1, AVLTreeNode<T> T2) {
        if (height(T1) - height(T2) >= 0) {
            return height(T1) - height(T2);
        } else
            return height(T1) - height(T2);
    }

    public AVLTreeNode<T> singleRoateWithLeft(AVLTreeNode<T> T2) {
        AVLTreeNode<T> 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<T> singleRoateWithRight(AVLTreeNode<T> T1) {
        AVLTreeNode<T> 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<T> doubleRoateWithLeft(AVLTreeNode<T> T2) {
        T2.left = singleRoateWithRight(T2.left);
        return singleRoateWithLeft(T2);
    }

    public AVLTreeNode<T> doubleRoateWithRight(AVLTreeNode<T> T2) {
        T2.right = singleRoateWithLeft(T2.right);
        return singleRoateWithRight(T2);
    }

    public void showTree() {
        showTree(root);
    }

    public void showTree(AVLTreeNode<T> T) {
        if (T == null) {
            return;
        } else {
            showTree(T.left);
            System.out.println(T.element + "__" + T.hight);
            showTree(T.right);
        }

    }

}