AVL Tree

AVL Tree的基本介绍

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.来自：GeeksforGeeks

在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(\log{n})。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。AVL树得名于它的发明者G. M. Adelson-Velsky和Evgenii Landis，他们在1962年的论文《An algorithm for the organization of information》中公开了这一数据结构。

节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。来自：Wikipedia

现在我们看AVL数的中文，自平衡二叉查找树，这个平衡我们从定义中看出来了：任一节点对应的两棵子树的最大高度差为1，那么二叉查找树的概念呢？似乎没有说明，其实二叉查找树(BST)也是一种独立的树结构。那么我们就先来了解一下BST

BST的基本介绍

二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（ordered binary tree）或排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

  1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  3. 任意节点的左、右子树也分别为二叉查找树；
  4. 没有键值相等的节点。

比如说上面的这棵树就是一个二叉查找树。

构造BST

那么我们该如何构造一颗BST呢？添加节点的时候，当树为空的时候就直接插入节点作为根节点。不然当小于节点且左子树不为空的递归加入左子树，大于节点且右子树不为空的时候加入右子树。左右子树为空的时候就直接插入作为左右子树。

这个思路还是特别的简单的直接按照BST的规则来就完事了。

节点代码实现

class Node{
    private int value;
    private Node left;
    private Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node [value=" + value + "]";
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public Node getLeft() {
        return left;
    }

    public void setLeft(Node left) {
        this.left = left;
    }

    public Node getRight() {
        return right;
    }

    public void setRight(Node right) {
        this.right = right;
    }

    public void add(Node node) {
        if (node.value < this.value) {
            if (this.left == null) {
                this.left = node;
                return;
            }else {
                this.left.add(node);
            }
        }else {
            if (this.right == null) {
                this.right = node;
                return;
            }else {
                this.right.add(node);
            }
        }
    }

    //：用于后面的AVT平衡二叉树的操作
    public int height() {
        return Math.max(left == null?0:left.height(), right == null?0:right.height()) +1;
    }

    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        return left.height();
    }

    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }

    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    public Node search(int value) {
        if (this.value == value) {
            return this;
        }
        if (value < this.value) {
            return this.left.search(value);
        }else {
            return this.right.search(value);
        }
    }

    public Node searchParent(int value) {
        if (this.left != null && this.left.value == value) {
            return this;
        }
        if (this.right != null && this.right.value == value) {
            return this;
        }

        if (value < this.value) {
            return this.left.searchParent(value);
        }else {
            return this.right.searchParent(value);
        }
    }

    /**
     * 找到左子树上最大的节点的父节点
     * @return 左子树上最大的节点的父节点 没有左子树就返回null
     */
    public Node findLeftMaxParentNode() {
        if (this.left == null) {
            return null;
        }
        Node temp = this.left;
        if (temp.getRight() == null) {
            return this;
        }

        if (temp.getRight() != null && temp.getRight().getRight() != null) {
            temp = temp.getRight();
        }

        return temp;
    }

    /**
     * 找到右子树上最小的节点的父节点
     * @return 右子树上最小的节点的父节点， 没有右子树就返回null
     */
    public Node findRightMinParentNode() {
        if (this.right == null) {
            return null;
        }
        Node temp = this.right;
        if (temp.getLeft() == null) {
            return this;
        }

        if (temp.getLeft() != null && temp.getLeft().getLeft() != null) {
            temp = temp.getLeft();
        }

        return temp;
    }

}

可见由一个数组构造一个BST还是非常容易的。

BST代码实现

class BinarySearchTree {
    private Node root = null;

    public BinarySearchTree(Node root) {
        this.root = root;
    }

    public BinarySearchTree() {
        this.root = null;
    }

    public Node getRoot() {
        return root;
    }

    public void setRoot(Node root) {
        this.root = root;
    }

    public void add(Node node) {
        if (root == null) {
            root = node;
            return;
        }
        this.root.add(node);
    }

    public int height() {
        return this.root.height();
    }

    public int leftHeight() {
        return this.root.leftHeight();
    }

    public int rightHeight() {
        return this.root.rightHeight();
    }

    public void infixOrder() {
        if (root == null) {
            return;
        }
        this.root.infixOrder();
    }

    /**
     * 搜索节点 缺点是重复的值会出现问题，值不能重复
     * @param value 要查询的值
     * @return 返回找到值的当前节点 找不到就返回null
     */
    public Node search(int value) {
        if (root == null) {
            return null;
        }
        return this.root.search(value);
    }

    /**
     * 搜索父节点 缺点是值不能重复
     * @param value
     * @return 返回找到值的父节点， 找不到就返回null
     */
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        }
        if (root.getValue() == value) {
            return null;
        }
        return this.root.searchParent(value);
    }


    public Node findLeftMaxParentNode() {
        return root.findLeftMaxParentNode();
    }

    public Node findRightMinParentNode() {
        return root.findRightMinParentNode();
    }
    /**
     * 删除节点
     * @param value
     * @return
     */
    public boolean delNode(int value) {
        Node node = search(value);
        Node parent = searchParent(value);
        if (node == null) {
            return false;
        }

        if (parent == null) {
            if (root == null) {
                return true;
            }else { //：要删除的节点就是根节点
                Node leftMaxParentNode = findLeftMaxParentNode();
//                System.out.println(leftMaxParentNode.getRight().getValue());
                if (leftMaxParentNode == null) {
                    root = root.getRight();
                    return true;
                }else {
                    if (leftMaxParentNode == root) {
                        this.root.setValue(this.root.getLeft().getValue());
                        this.root.setLeft(null);
                        return true;
                    }else {
                        this.root.setValue(leftMaxParentNode.getRight().getValue());
                        leftMaxParentNode.setRight(leftMaxParentNode.getRight().getLeft());
                        return true;
                    }
                }
            }
        }
        // 是一个叶子节点
        if (node.getLeft() == null && node.getRight() == null) {
            if (parent.getLeft() == node) {
                parent.setLeft(null);
            }else {
                parent.setRight(null);
            }
            return true;
        }

        // 只有一个右子节点
        if (node.getLeft() == null) {
            if (parent.getRight() ==node) {
                parent.setRight(node.getRight());
                return true;
            }else {
                parent.setLeft(node.getRight());
                return true;
            }
        }

        if (node.getRight() == null) {
            if (parent.getRight() == node) {
                parent.setRight(node.getLeft());
                return true;
            }else {
                parent.setLeft(node.getLeft());
                return true;
            }
        }

        // 有两个节点的
        Node leftMaxParentNode = node.findLeftMaxParentNode();
        if (leftMaxParentNode == node) {
            node.setValue(node.getLeft().getValue());
            node.setLeft(null);
            return true;
        }else {
            node.setValue(leftMaxParentNode.getRight().getValue());
            leftMaxParentNode.setRight(leftMaxParentNode.getRight().getLeft());
            return true;
        }
    }
}

可以看到上面的代码还是特别的多的，因为这个代码都是我学习的时候写的，这里就直接复制过来了。里面很多的方法都是为了AVL来写的。其实里面有几个函数还是比较难写的，比如那个删除节点的那个函数我就写了不少的时间，不过，这里这个问题都不是重点了。我们主要说的是AVL树。

从BST到AVL

虽然说BST是蛮好的，中序遍历一个BST我们就能得到一个有序的数组，这个是多么的方便。但是BST也存在了一些问题。比如说我给定的数组是1 2 3 4 5 6使用这个数组构造BST的时候，我们发现构造出来一个非常奇怪的树。

1
  2
    3
      4
        5
           6

一个如同单链表的BST，但是效率比单链表还要低。有些人会说，我们可以使用中位数作为节点来构造二叉树，但是这个依然是有问题的。

    4
   3  5
 2      6
1         7

这棵树是效率高的吗？童谣也不是，效率和单链表其实也差不多。

是什么导致这些BST的效率很低的？因为这些树不平衡，这就可以联系到上面的AVL中关于平衡的定义了。左右子树的高度差不大于1。而且是所有的子树的左右子树的高度差都不大于1。所以说上面的两棵树都不是AVL。

An Example Tree that is an AVL Tree

The above tree is AVL because differences between heights of left and right subtrees for every node is less than or equal to 1.

An Example Tree that is NOT an AVL Tree

The above tree is not AVL because differences between heights of left and right subtrees for 8 and 18 is greater than 1.

Insertion Examples:

AVL代码实现

class AVLTree extends BinarySearchTree {

    public AVLTree() {
        this.setRoot(null);
    }

    public AVLTree(Node rootNode) {
        this.setRoot(rootNode);
    }
    public void createAVLTree() {
        while ((leftHeight() - rightHeight() !=1 && leftHeight() -rightHeight() !=0) && 
                (rightHeight() - leftHeight() != 1 && rightHeight() - leftHeight() !=0)) {
            createAVLTreeOneTime();
        }
    }
    //：左旋转， 当左子树的高度小于右子树的高度时候可以降低两者之间的差值，使之成为平衡树
    public void createAVLTreeOneTime() {
        if (leftHeight() - rightHeight() > 1) {
            //：进行双旋转， 如果这个左子树的右节点的高度大于右子树先对左子树进行左旋转
            if (this.getRoot().getLeft().leftHeight() <
                    this.getRoot().getLeft().rightHeight()) {
                new AVLTree(this.getRoot().getLeft()).leftRotate();
            }
            this.rightRotate();

        } else if (rightHeight() - leftHeight() >1) {
            if (this.getRoot().getRight().rightHeight() <
                    this.getRoot().getRight().leftHeight()) {
                new AVLTree(this.getRoot().getRight()).rightRotate();
            }
            this.leftRotate();

        } else return;
    }

    public void leftRotate() {
        Node newNode = new Node(this.getRoot().getValue());
        newNode.setLeft(this.getRoot().getLeft());
        newNode.setRight(this.getRoot().getRight().getLeft());
        this.getRoot().setLeft(newNode);
        this.getRoot().setValue(this.getRoot().getRight().getValue());
        this.getRoot().setRight(this.getRoot().getRight().getRight());
    }

    //：右旋转 与上面的左旋转是类似的  旋转不一定是有用的我发现，，，这个1 3 变成了 3 1 可见单旋转并不能将所有的树转换成平衡二叉树
    public void rightRotate() {
        Node newNode = new Node(this.getRoot().getValue());
        newNode.setRight(this.getRoot().getRight());
        newNode.setLeft(this.getRoot().getLeft().getRight());
        this.getRoot().setValue(this.getRoot().getLeft().getValue());
        this.getRoot().setRight(newNode);
        this.getRoot().setLeft(this.getRoot().getLeft().getLeft());
    }
}

旋转 由BST到AVL

左旋转

public void leftRotate() {
    Node newNode = new Node(this.getRoot().getValue());
    newNode.setLeft(this.getRoot().getLeft());
    newNode.setRight(this.getRoot().getRight().getLeft());
    this.getRoot().setLeft(newNode);
    this.getRoot().setValue(this.getRoot().getRight().getValue());
    this.getRoot().setRight(this.getRoot().getRight().getRight());
}

左旋转是非常的形象的。当右子树的高度大于左子树的高度的时候，我们将树进行左旋转这样就可以平衡左右子树之间的高度之差。

如何左旋转：

  1. 以当前节点（根节点）值构造一个新的节点。
  2. 新节点的左指针指向根节点的左子树
  3. 新节点的右指针指向根节点的右子树的左子树。
  4. 根节点的左子树指向新节点。
  5. 将根节点的右子树的值赋给根节点
  6. 根节点的右指针指向根节点的右子树的右子树

这个看起来可能很懵逼，不过看着下面的图基本上就可以理解了。理解之后你也会发现这个这个左旋转会存在一些问题。

右旋转

//：右旋转 与上面的左旋转是类似的  旋转不一定是有用的我发现，，，这个1 3 变成了 3 1 可见单旋转并不能将所有的树转换成平衡二叉树
public void rightRotate() {
    Node newNode = new Node(this.getRoot().getValue());
    newNode.setRight(this.getRoot().getRight());
    newNode.setLeft(this.getRoot().getLeft().getRight());
    this.getRoot().setValue(this.getRoot().getLeft().getValue());
    this.getRoot().setRight(newNode);
    this.getRoot().setLeft(this.getRoot().getLeft().getLeft());
}

右旋转与左旋转类似，这里不再赘述、

恐怕你已经发现了问题，就是原本是1 3的树经过左旋转之后会变成 3 1。

这是如果再使用右旋转又会变成1 3。这个是非常有问题的。那么问题出在了那么了呢？

我当我们进行右旋转的时候，们将根节点的右子树树指向的是新的节点，新节点的左子树指向的是根节点的左子树的右子树，那么如果根节点的左子树的左子树的高度小于其左子树的右子树的高度上呢？这时就会引发这个问题。此时我们虽然是想右选择的。但是右子树上的新的节点的左子树连接这那个比较大的根节点的左子树的右子树，这时旋转之后右子树就会变得高，不会形成一个AVL。此时需要平衡一下根节点的左子树，使左子树先来一次左旋转

左旋转也是类似的道理。因此需要将左右旋转结合起来写一个新的函数。

左右旋转结合

public void createAVLTreeOneTime() {
    if (leftHeight() - rightHeight() > 1) {
        //：进行双旋转， 如果这个左子树的右节点的高度大于右子树先对左子树进行左旋转
        if (this.getRoot().getLeft().leftHeight() <
            this.getRoot().getLeft().rightHeight()) {
            new AVLTree(this.getRoot().getLeft()).leftRotate();
        }
        this.rightRotate();

    } else if (rightHeight() - leftHeight() >1) {
        if (this.getRoot().getRight().rightHeight() <
            this.getRoot().getRight().leftHeight()) {
            new AVLTree(this.getRoot().getRight()).rightRotate();
        }
        this.leftRotate();

    } else return;
}

public void createAVLTree() {
    while ((leftHeight() - rightHeight() !=1 && leftHeight() -rightHeight() !=0) && 
           (rightHeight() - leftHeight() != 1 && rightHeight() - leftHeight() !=0)) {
        createAVLTreeOneTime();
    }
}

这样我们的AVL就完成了，上面的代码都已经做了说明，不想说了。而且这种二叉树的问题，说明是真的难说，还是自己拿一个笔多画一画就完事了，画着画着就可以理解其中的大智慧了。

上面的图可能看起来有点儿懵逼，不过我感觉画的特别的形象。主要讲了旋转的事情。要结合上面的代码一起进行消化理解吸收。

总结

这个讲的稍微的敷衍，不过也没有办法，我主要想说的就是AVL的旋转而已，但是又是用语言难以理解的，于是上外网盗了一些图片过来辅助理解，不知道下次这些图片会不会么得了，嘤嘤嘤~~

赏

一枚小菜鸡