平衡查找树之AVL树

一、前言

之前写过一篇二分查找树的，前面也说过，普通的二叉查找树一般情况下添加、删除查找所使用的时间复杂度是O(logN)，但在最坏的情况下，可可以会退化成一个链表，也就是每次插入节点时都比父节点大或者者小，这时查找的时间复杂度就会变成O(N)级别的，这就达不到高效了，说白了就是稳固性不高，最近花了比较多的时间在树上面，所以今天就来总结一下平衡的查找树-AVL树，AVL树就是在添加、删除节点时对二叉树进行了平衡的解决，重心就是节点的旋转操作，使得每个节点左右子树的高度差都小<=1。

二、基本实现

关于二叉查找树基本的实现，这里就不过多详情了。首先说明一下，由于要进行旋转的前提是，当前这颗树达不到平衡的要求，也就是每个节点左右子树高度差大于１，所有第一步需要做的事就是每次进行节点增加时都需要升级当前节点的高度height(默认情况下高度为0)，这里也就是取当前节点的左子树和右子树较高的那个，而后这里直接从重心入手，把一颗普通的二叉查找树变成一颗AVL树。

1.LL、RR旋转

这两种情况也就是只要进行一次旋转操作。LL旋转就是往二叉树增加或者删除元素后，当前节点的左孙子节点的子树不为空，就导致当前节点的左子树-右子树高度差(3-1)=2>1，从而平横性被破坏，这里还是拿图片来看比较形象一点

LL旋转
看看图片，就是LL旋转的例子，而后说下右旋转的过程，首先去掉节点6的右节点7并临时保存，而后把节点8和它的右子树一起旋转到节点6的右侧，最后把临时保存的节点7放到节点8的左侧，这就是LL旋转的过程，旋转后升级一下旋转后的节点的6和8的高度，而6的左子树一直都没有动，所以无需进行升级。
而后看看代码

//　右旋转 返回旋转后的根节点    private Node rightRotate(Node node) {        Node x = node.left;        Node temp = x.right;        // 向右旋转过程        x.right = node;        node.left = temp;        // 升级height        node.height = Math.max(getHeight(node.left), getHeight(node.right))+1;        x.height = Math.max(getHeight(x.left), getHeight(x.right))+1;        return x;    }

同样的道理，RR旋转就是增加后删除元素后，当前节点的右孙子节点的子树不为空，就导致当前节点的右子树-左子树高度差(3-1)=2>1，还是一样的看图说话

RR旋转
能看到左旋转和右旋转是非常相似的，以这个图为例，首先去掉节点7的左节点6并临时保存，而后把节点5和它的左子树旋转到节点7的左侧，而后把节点临时保存的6放到节点5的右边，到此，整个RR旋转就完成了，最后还是对节点5和节点7的高度进行升级。看看代码

//　左旋转 返回旋转后的根节点    private Node leftRotate(Node node) {        Node x = node.right;        Node temp = x.left;        // 向左旋转过程        x.left = node;        node.right = temp;        // 升级height        node.height = Math.max(getHeight(node.left), getHeight(node.right))+1;        x.height = Math.max(getHeight(x.left), getHeight(x.right))+1;        return x;    }

2.LR、RL旋转

之前的旋转都是单一的旋转，但实际情况中还可可以会出现其余情况，也就是产生高度差的子树不是来源于单一的方向，在进行元素的增加和删除后可可以出现，当前节点的左孩子节点的右节点出现了非空子节点，就导致左孩子节点的左子树高度小于右子树高度，这个时候就需要用LR旋转来进行平衡了，还是看图

LR旋转.png
其实LR旋转也就是先把当前节点的左孩子节点进行左旋转，旋转后就会发现此时左孩子的子树高度是左子树大于右子树，这时即可以直接进行右旋转，最终达到平衡AVL树的要求。以这个图为例，首先进行的是将根节点8的左孩子进行左旋转，也就是把节点7的左节点6去掉并临时保存，而后把节点５及其左子树旋转到节点7的左侧，最后将临时保存的节点６放到节点5的左侧，此时对于整棵树而言就满足了之前进行LL旋转所需的条件，这里能看到节点7的右侧是为空的，所以能直接把节点8右旋转到节点7的右侧，这样就完成了整个LR旋转的操作，最后也是高度的升级。

对于右子树，最后就是还有一种情况，也就是当前节点的右孩子节点的左节点出现了非空子节点，这就导致了
右孩子节点的左子树高度大于右子树高度,这个时候就需要用RL旋转来进行平衡了，如图

RL旋转.png
RL旋转也就是先把当前节点的右孩子节点进行右旋转，旋转后就会发现此时右孩子的子树高度是左子树高度小于右子树高度的，这时即可以进行左旋转，最终达到平衡的要求。以这个图为例，首先是将根节点5的右孩子进行右旋转，也就是把节点7的右节点8去掉并临时保存，而后把节点9旋转到节点7右侧，接下来把临时保存的节点8放到节点9的左侧，此时对于整棵树而言就满足了之前进行RR旋转所需的条件，接下来的过程就是RR旋转了，首先去掉节点7的左节点6并临时保存，而后将节点5及其左子树旋转到节点7的左侧，再将临时保存的节点6放到节点5的右侧，这样就完成了整个RL旋转的操作，最后依然是高度的升级。

其实只需了解了前面的LL和RR旋转操作，后面的组合式的LR和RL旋转自然很容易了解，其实这也正是AVL的核心，也就是这些旋转操作，使得二叉查找树总是处于平衡的状态，这样就不会像之前那样出现退化成链表的情况，而后查找所需要的时间复杂度最差情况下也是O(logN)级别，而AVL树的一个较大的缺点需要繁琐的进行旋转操作。最后附上一律的代码

/** * @author Legend * @data by on 18-6-24. * @description */public class AVLTree<K extends Comparable<K>, V> {    private class Node {        public K key;        public V value;        public Node left, right;        public int height;        public Node(K key, V value) {            this.key = key;            this.value = value;            left = right = null;            height = 1;        }    }    private Node root;    private int size;    public AVLTree() {        root = null;        size = 0;    }    public void add(K key, V value) {        root = add(root, key, value);    }    private Node add(Node node, K key, V value) {        if (node == null) {            size++;            return new Node(key, value);        }        if (key.compareTo(node.key)<0) {            node.left = add(node.left, key, value);        } else if (key.compareTo(node.key)>0) {            node.right = add(node.right, key, value);        } else {            node.value = value;        }        // 升级Height        node.height = 1+Math.max(getHeight(node.left), getHeight(node.right));        // 计算平衡因子        int balanceFactor = getBalanceFactor(node);        if (Math.abs(balanceFactor)>1) {            System.out.println("unbalanced: "+balanceFactor);        }        // 平衡维护        //　LL        if (balanceFactor>1 && getBalanceFactor(node.left)>=0) {            return rightRotate(node);        }        //RR        if (balanceFactor<-1 && getBalanceFactor(node.right)<=0) {            return leftRotate(node);        }        // LR        if (balanceFactor>1 && getBalanceFactor(node.left)<0) {            node.left = leftRotate(node);            return rightRotate(node);        }        // RL        if (balanceFactor<-1 && getBalanceFactor(node.right)>0) {            node.right = rightRotate(node);            return leftRotate(node);        }        return node;    }    private Node getNode(Node node, K key) {        if (node == null) {            return null;        }        if (key.compareTo(node.key)==0) {            return node;        } else if (key.compareTo(node.key)<0) {            return getNode(node.left, key);        } else {            return getNode(node.right, key);        }    }    public V remove(K key) {        Node node = getNode(root, key);        if (node != null) {            root = remove(root, key);            return node.value;        }        return null;    }    private Node remove(Node node, K key) {        if (node == null) {            return null;        }        Node retNode;        if (key.compareTo(node.key)<0) {            node.left = remove(node.left, key);            retNode = node;        } else if (key.compareTo(node.key)>0) {            node.right = remove(node.right, key);            retNode =  node;        } else {            if (node.left == null) {                Node rightNode = node.right;                node.right = null;                size--;                retNode = rightNode;            } else if (node.right == null) {                Node leftNode = node.left;                node.left = null;                size--;                retNode = leftNode;            } else {                Node successor = miniMum(node.right);                successor.left = node.left;                successor.right = remove(node.right, successor.key);                node.left = node.right = null;                retNode = successor;            }        }        if (retNode == null) return null;        retNode.height = Math.max(getHeight(retNode.left), getHeight(retNode.right))+1;        int balanceFactor = getBalanceFactor(retNode);        // LL        if (balanceFactor>1 && getBalanceFactor(retNode.left)<=0) {            return rightRotate(retNode);        }        // RR        if (balanceFactor<-1 && getBalanceFactor(retNode.right)>=0) {            return leftRotate(retNode);        }        // LR        if (balanceFactor>1 && getBalanceFactor(retNode.left)>0) {            retNode.left = leftRotate(retNode);            return rightRotate(retNode);        }        // RL        if (balanceFactor<-1 && getBalanceFactor(retNode.right)<0) {            retNode.right = rightRotate(retNode);            return leftRotate(retNode);        }        return retNode;    }    private Node miniMum(Node node) {        if (node.left == null) {            return node;        }        return miniMum(node.left);    }    public boolean contains(K key) {        return getNode(root, key) != null;    }    public V get(K key) {        Node node = getNode(root, key);        return node == null?null: node.value;    }    public void set(K key, V newValue) {        Node node = getNode(root, key);        if (node == null) {            throw new IllegalArgumentException(key+" doesn't exits!");        }        node.value = newValue;    }    public int getSize() {        return size;    }    public boolean isEmpty() {        return size == 0;    }    //　获取节点的高度    private int getHeight(Node node) {        if (node == null) return 0;        return node.height;    }    //　取得节点node的平衡因子    private int getBalanceFactor(Node node) {        if (node == null) return 0;        return getHeight(node.left)-getHeight(node.right);    }    //　右旋转 返回旋转后的根节点    private Node rightRotate(Node node) {        Node x = node.left;        Node temp = x.right;        // 向右旋转过程        x.right = node;        node.left = temp;        // 升级height        node.height = Math.max(getHeight(node.left), getHeight(node.right))+1;        x.height = Math.max(getHeight(x.left), getHeight(x.right))+1;        return x;    }    //　左旋转 返回旋转后的根节点    private Node leftRotate(Node node) {        Node x = node.right;        Node temp = x.left;        // 向左旋转过程        x.left = node;        node.right = temp;        // 升级height        node.height = Math.max(getHeight(node.left), getHeight(node.right))+1;        x.height = Math.max(getHeight(x.left), getHeight(x.right))+1;        return x;    }    // 判断二叉树能否是一颗平衡二叉树    public boolean isBalanced() {        return isBalanced(root);    }    private boolean isBalanced(Node node) {        if (node == null) return true;        int balanceFactor = getBalanceFactor(node);        if (balanceFactor>1) return false;        return isBalanced(node.left) && isBalanced(node.right);    }    // 判断二叉树能否是一颗二叉搜索树    public boolean inBST() {        ArrayList<K> keys = new ArrayList<>();        inOrder(root, keys);        for (int i=1;i<keys.size();i++) {            if (keys.get(i-1).compareTo(keys.get(i))>0) {                return false;            }        }        return true;    }    private void inOrder(Node node, ArrayList<K> keys) {        if (node == null) return;        inOrder(node.left, keys);        keys.add(node.key);        inOrder(node.right, keys);    }}

三、总结

这篇尽管没把AVL树的整个构建流程写清楚，但是写了AVL树的核心操作，这也是了解为什么会要对二叉查找树进行优化的关键，这篇博客暂时就到这里了。