AVL树Java实现，包括删除

现在的位置: 首页 > 综合 > 正文

AVL树Java实现，包括删除

2013年10月11日 ⁄ 综合 ⁄ 共 3120字 ⁄ 字号小中大 ⁄ 评论关闭

文章来自于此，经过各种查询资料，纠结了好久的AVL树实现总算搞定了，以下是一个动态演示的动画avl，来源不记得了。看代码之前务必把算法描述看懂了，还有几种旋转方法（很重要，插入和删除的平衡都靠这几步），具体的可以看下严蔚敏的《数据结构与算法》，C语言描述，里面除了删除没有讲，其余的讲的挺细的。这里给的参考是wiki的。

建议看该结构的时候掌握对BST的基本操作（插入删除）。这样理解起来就不会怎么吃力

package com.mars.datastructure;

/**
 * http://dongxicheng.org/structure/avl/
 * http://www.asiteof.me/2010/06/avl/
 * @author hoot
 * 
 */
public class AVLTree4 {
    private static class Node {
        Node left;
        Node right;
        int height;
        int data;
    }

    private int heigth(Node t) {
        if(t == null){
            return 0;
        }
        return t.height;
    }

    // LL
    private Node rightRotate(Node a) {
        Node b = a.left;
        a.left = b.right;
        b.right = a;
        a.height = max(heigth(a.left), heigth(a.right));
        b.height = max(heigth(b.left), heigth(b.right));
        return b;
    }

    // RR
    private Node leftRotate(Node a) {
        Node b = a.right;
        a.right = b.left;
        b.left = a;
        a.height = max(heigth(a.left), heigth(a.right));
        b.height = max(heigth(b.left), heigth(b.right));
        return b;
    }

    //LR
  private  Node leftRightRotate(Node a){
        a.left = leftRotate(a.left);
        return rightRotate(a);
    }

    //RL
  private Node rightLeftRotate(Node a){
        a.right = rightRotate(a.right);
        return leftRotate(a);
    }

    //insert
   public Node insert(int data, Node t){
        if(t == null){
            t = newNode(data);
        }else if(data < t.data){
            t.left = insert(data, t.left);
            if(heigth(t.left) - heigth(t.right) == 2){
                if(data < t.left.data){
                    t = rightRotate(t);
                }else{
                    t = leftRightRotate(t);
                }
            }
        }else{
            t.right = insert(data, t.right);
            if(heigth(t.right) - heigth(t.left) == 2){
                if(data > t.right.data){
                    t = leftRotate(t);
                }else{
                    t = rightLeftRotate(t);
                }
            }
        }
        t.height = max(heigth(t.left), heigth(t.right));
        return t;
    }

    //delete
   public Node delete(int data, Node t){
        if(t == null){
            return null;
        }
        if(t.data == data){
            if(t.right == null){ 
                t = t.left; 
            }else{
                Node head = t.right;
                while(head.left != null){
                    head = head.left;
                }
                t.data = head.data;
                //还记得BST树删除节点吧
                t.right = delete(t.data, t.right);
                t.height = max(heigth(t.left), heigth(t.right)) + 1;
            }
            return t;
        }else if(t.data > data){
            t.left = delete(data, t.left);
        }else{
            t.right = delete(data, t.right);
        }
        t.height = max(heigth(t.left), heigth(t.right));

        //以上只是删除节点，但是需要保持平衡，所以还需旋转让其平衡以满足AVL的性质。
        //看下
        if(t.left != null){
            t.left = rotate(t.left);
        }
        if(t.right != null){
            t.right = rotate(t.right);
        }
        return rotate(t);
    }
    private Node newNode(int data){
        Node a = new Node();
        a.left = a.right = null;
        a.height = 0;
        a.data = data;
        return a;
    }
    private int max(int heigth, int heigth2) {

        return heigth > heigth2 ? heigth : heigth2;
    }

    public void travel(Node root) {
        Node node = root;
        if (node == null) {
            return;
        }
        travel(node.left);
        System.out.print(node.data + " ");
        travel(node.right);
    }

    private Node rotate(Node t){              /*对于单个节点进行的AVL调整*/
        if(heigth(t.left) - heigth(t.right) == 2){
            if(heigth(t.left.left) >= heigth(t.left.right)){
                t = rightRotate(t);
            }
            else{
                t = leftRightRotate(t);
            }
        }
        if(heigth(t.right) - heigth(t.left) ==2){
            if(heigth(t.right.right) >= heigth(t.right.left)){
                t = leftRotate(t);
            }
            else{
                t = rightLeftRotate(t);
            }
        }
        return t;
    }

    public static void main(String[] args) {
        int[] a = {0, 1, 4, 3, 8, 9, 2, 5, 7, 6, -10};
        Node root = null;
        AVLTree4 avl = new AVLTree4();
        for(int b : a){
         //   System.out.println("for:" + root);
            root = avl.insert(b, root);
        }
        System.out.println(root);
        avl.travel(root);

        avl.delete(9, root);
        System.out.println();
        avl.travel(root);
    }
}

鉴于旋转的方式和名字千奇百怪，这里给出了算法中描述的旋转方法和对应的名字