如何构建AVL树

如何构建AVL树

1.首先我们先定义AVL树的节点

class AVlNode{

    AVlNode(Integer theElement){
        this(theElement,null,null);
    }

    AVlNode(Integer theElement,AVlNodelt,AVlNode rt){
        element = theElement; left=lt; right=rt;
    }

   Integer element;//该节点存储的数据
   AVlNode left;//左儿子
   AVlNode right;//右儿子
   int height;//记录该节点的高
}

​

接着是计算节点高度的方法：在这里我们使用三元运算符替代if—else。如果T.height=-1则该节点不存在

    private int height(AVlNode T){
        return  (T==null)?-1: T.height;
    }

随后便是AVL树的插入 *** 作了.它的插入和一般的二叉查找树一样，使用递归找到插入的位置

    private AVlNode insert(Integer x,AVlNode t){
        if (t == null){
            return new AVlNode<>(x,null,null);
        }

        int compareResult = (int)x-(int)(t.element);

        if (compareResult < 0){
            t.left = insert(x,t.left);
        }else if (compareResult > 0){
            t.right = insert(x,t.right);
        }

        return balance(t);

    }

由于设置element的数据类型为Integer这时需要转换成int。与二叉查找树的插入不同的是，AVL在返回根节点之前先对树进行平衡 *** 作。

​
    private static final int ALLOWED_IMBALANCE = 1;

    private AVlNode balance(AVlNode t){
        if (t == null)
            return null;

        if (height(t.left) - height(t.right) >ALLOWED_IMBALANCE){
            if (height(t.left.left)>=height(t.left.right)){
                 t = rotateWithLeftChild(t);//左左
            }else {
                t = doubleWithLeftChild(t);//左右
            }
        }else if (height(t.right) -height(t.left) >ALLOWED_IMBALANCE){
            if (height(t.right.right)>=height(t.right.left)){
                t = rotateWithRightChild(t);//右右
            }else {
                t = doubleWithRightChild(t);//右左
            }
        }

        t.height = Math.max(height(t.right),height(t.left))+1;
        return t;
    }

​

在这里我们定义了大小为1一个全局常量.如果节点的高度差大于这个临界条件，我们对树进行平衡 *** 作。面对不同的情形进行不同的 *** 作，我们按照树结构的形状分成四种。

 左—左型、右—右型、左—右型，右—左型

其中每种情形的解决方法如下

   private AVlNode rotateWithLeftChild(AVlNode k1){
        AVlNode k2 = k1.left;
        k1.left = k2.right;
        k2.right = k1;
        k1.height = Math.max(height(k1.left),height(k1.right))+1;
        k2.height = Math.max(height(k2.left),height(k2.right))+1;

        return k2;
    }

    private AVlNode rotateWithRightChild(AVlNode k1){
        AVlNode k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        k1.height = Math.max(height(k1.left),height(k1.right));
        k2.height = Math.max(height(k2.left),height(k2.right));

        return k2;
    }

    private AVlNode doubleWithLeftChild(AVlNode k1){
        k1.left = rotateWithRightChild(k1.left);
        return rotateWithLeftChild(k1);
    }

    private AVlNode doubleWithRightChild(AVlNode k1){
        k1.right = rotateWithLeftChild(k1.right);
        return rotateWithRightChild(k1);
    }

对于不同的处理方式的记忆技巧如下：

从后往前看，左右相反，例如右—左型：

从后往前看：左对右，右对左。所以先右转再左转。

这里需注意不要和搞混，例如上面的方法rotateWithLeftChild是处理左左型所以是进行了右转。