【数据结构与算法】【15】AVL树

什么是AVL树

AVL树是一种高度平衡的二叉查找树，AVL是人名的缩写

AVL树在二叉查找树的基础上，增加了一条约束条件

任意节点的左右子树高度差不大于1

为什么要设计AVL树

AVL树的设计，是为了弥补普通二叉查找树的一些缺陷

比如我们将一堆已经按从大到小排序好的数据插入二叉树，这些数据最终会全部摆放二叉树的左子树上面

此时我们去查找二叉树中的某个元素，其查找效率和遍历数组的效率基本一样，二叉树已经完全丧失了二分查找的优势

AVL树就是要保证二叉树的绝对平衡，这样其查找效率就可以永远保持在O(log2n)

AVL树的优点在于，查询效率很高，但要维护其平衡性，在插入时需要进行一些转换，这样就会导致其插入效率比较低

因此，AVL树适合查询频繁的场景，但不适合频繁插入的场景

平衡因子

左右子树的高度差叫做平衡因子，英文术语Balance Factor，简称BF

二叉树旋转

如上图所示，以40为中心，分别将50向左旋转，将30向右旋转

仍然可以保持二叉树的大小特征，但是平衡因子却变了

利用这个特点，我们可以将不平衡的二叉树，旋转为平衡的二叉树

主要分为四种方式：左单旋，右单旋，左右双旋，右左双旋

上面的图示忽略了子节点，当被旋转的节点还有子节点时，整个旋转过程可以用下面的动画来表示

左单旋

图片较小可以右键拖拽到新页面单独查看

场景：右子树较高，新节点被插到右子树右侧

右单旋

场景：左子树较高，新节点被插到左子树左侧

左右双旋

场景：左子树较高，新节点被插到左子树右侧 右左双旋

场景：右子树较高，新节点被插到右子树左侧 更新平衡因子

当我们向AVL树中插入一个新节点时，假设新插入的节点叫做current，其父节点叫做parent

parent平衡因子的变化可分为两种情况

1. 本来就有left，插入了right，parent.bf由±1变为0，子树高度不变
2. 本来没有left和right，插入了left或right，parent.bf由0变为±1，子树高度发生变化

parent的平衡因子更新很简单，插入右侧就减1，插入左侧就加1

对于第一种情况，由于parent子树的总高度不变，因此不需要再更新parent.parent的平衡因子

对于第二种情况，则需要向上递归，更新parent的parent的平衡因子，直到某个parent的平衡因子为0

递归过程中可能还会遇到另外一种情况，就是平衡因子由±1变为±2

此时AVL树的平衡已经被打破了，需要以此节点为中心，对AVL树进行旋转

从AVL树中删除一个元素

AVL树的删除和插入基本类似，由于AVL树本来就是高度平衡的，删除一个元素只会影响到parent节点的平衡因子

判断删除后，parent节点的平衡因子是否大于1，如果大于1，按照一样的方法进行旋转即可

普通二叉树转AVL树

这其实是一个伪命题，因为它的实现方法太简单了

将普通二叉树元素按任意方式全部遍历出来，再新建一个AVL树，将元素全部插入即可

代码实现

这里主要实现插入功能，删除和插入思路基本一致，其它二叉树通用功能，就不再逐个累述了

	//AVL节点
	@SuppressWarnings("all")
	public class AVLNode {
	
	    //节点值
	    T value;
	
	    //平衡因子
	    int bf;
	
	    //子节点
	    AVLNode left;
	    AVLNode right;
	
	    //父节点
	    AVLNode parent;
	
	    public int getChildCount() {
	        if (left == null && right == null)
	            return 0;
	        if (left != null && right != null)
	            return 2;
	        return 1;
	    }
	
	    @Override
	    public String toString() {
	        return String.valueOf(value + "（" + bf + "）");
	    }
	}

	//AVL树
	@SuppressWarnings("all")
	public class AVLTree {
	
	    AVLNode root;
	
	    //插入数据
	    public void Insert(T value) {
	        //树为空，直接创建根节点
	        if (root == null) {
	            AVLNode node = new AVLNode();
	            node.value = value;
	            root = node;
	            return;
	        }
	        //递归遍历所有节点，寻找插入位置
	        Insert(root, value);
	    }
	
	    //递归遍历所有节点，寻找插入位置
	    protected void Insert(AVLNode node, T value) {
	        //值等于当前节点，已存在，直接结束
	        if (value.compareTo(node.value) == 0)
	            return;
	        //值小于当前节点，插入到左子树
	        if (value.compareTo(node.value)  0) {
	            if (node.right == null) {
	                AVLNode newNode = new AVLNode();
	                newNode.value = value;
	                newNode.parent = node;
	                newNode.bf = 0;
	                node.right = newNode;
	                //递归更新平衡因子
	                UpdateBalanceFactor(node, newNode);
	                return;
	            }
	            Insert(node.right, value);
	        }
	    }
	
	    //递归更新平衡因子
	    protected void UpdateBalanceFactor(AVLNode parent, AVLNode current) {
	        if (parent == null)
	            return;
	        //更新parent的平衡因子
	        if (parent.left == current)
	            parent.bf = parent.bf + 1;
	        if (parent.right == current)
	            parent.bf = parent.bf - 1;
	        //parent子树高度不变，不需要向上递归更新
	        if (parent.bf == 0)
	            return;
	        //parent子树高度改变，但仍然保持平衡，向上递归更新
	        if (parent.bf == -1 || parent.bf == 1) {
	            UpdateBalanceFactor(parent.parent, parent);
	            return;
	        }
	        //parent子树高度改变，且打破平衡，即平衡因子由±1变为±2
	        //以parent为中心，对AVL树进行旋转
	        Rotate(parent);
	    }
	
	    //旋转AVL树
	    protected void Rotate(AVLNode parent) {
	        //右子树较高，新节点被插到右子树右侧，左单旋
	        if (parent.bf == -2 && parent.right.bf == -1) {
	            RotateL(parent);
	            return;
	        }
	        //左子树较高，新节点被插到左子树左侧，右单旋
	        if (parent.bf == 2 && parent.left.bf == 1) {
	            RotateR(parent);
	            return;
	        }
	        //左子树较高，新节点被插到左子树右侧，左右双旋
	        if (parent.bf == 2 && parent.left.bf == -1) {
	            RotateLR(parent);
	            return;
	        }
	        //右子树较高，新节点被插到右子树左侧，右左双旋
	        if (parent.bf == -2 && parent.right.bf == 1) {
	            RotateRL(parent);
	            return;
	        }
	    }
	
	    //左单旋
	    protected void RotateL(AVLNode parent) {
	        //原parent的右孩子，旋转后作为新的parent
	        AVLNode node1 = parent.right;
	        //node1的左孩子，失去parent后，移动到原parent的右节点上，可能为空
	        AVLNode node2 = parent.right.left;
	        //原parent的parent，旋转后作为新parent的parent，可能为空
	        AVLNode node3 = parent.parent;
	        //更新节点上下级关系
	        //更新node1和node3的关系
	        node1.parent = node3;
	        if (node3 != null) {
	            if (node3.left == parent)
	                node3.left = node1;
	            if (node3.right == parent)
	                node3.right = node1;
	        }
	        //更新node1和parent的关系
	        node1.left = parent;
	        parent.parent = node1;
	        //更新node2和parent的关系
	        parent.right = node2;
	        if (node2 != null)
	            node2.parent = parent;
	        if (node2 != null)
	            parent.bf = 0;
	        else
	            parent.bf = 1;
	        //更新AVL树的根节点
	        if (node3 == null) {
	            root = node1;
	            node1.parent = null;
	        }
	        //更新所有发生变化的平衡因子
	        node1.bf = 0;
	        if (node3 != null)
	            node3.bf = node3.bf - 1;
	    }
	
	    //右单旋
	    protected void RotateR(AVLNode parent) {
	        //原parent的左孩子，旋转后作为新的parent
	        AVLNode node1 = parent.left;
	        //node1的右孩子，位置被占据后，移动到原parent的左节点上，可能为空
	        AVLNode node2 = parent.left.right;
	        //原parent的parent，旋转后作为新parent的parent，可能为空
	        AVLNode node3 = parent.parent;
	        //更新节点上下级关系
	        //更新node1和node3的关系
	        node1.parent = node3;
	        if (node3 != null) {
	            if (node3.left == parent)
	                node3.left = node1;
	            if (node3.right == parent)
	                node3.right = node1;
	        }
	        //更新node1和parent的关系
	        node1.right = parent;
	        parent.parent = node1;
	        //更新node2和parent的关系
	        parent.left = node2;
	        if (node2 != null)
	            node2.parent = parent;
	        if (node2 != null)
	            parent.bf = 0;
	        else
	            parent.bf = -1;
	        //更新AVL树的根节点
	        if (node3 == null) {
	            root = node1;
	            node1.parent = null;
	        }
	        //更新所有发生变化的平衡因子
	        node1.bf = 0;
	        if (node3 != null)
	            node3.bf = node3.bf + 1;
	    }
	
	    //左右双旋
	    protected void RotateLR(AVLNode parent) {
	        RotateL(parent.left);
	        RotateR(parent);
	    }
	
	    //右左双旋
	    protected void RotateRL(AVLNode parent) {
	        RotateR(parent.right);
	        RotateL(parent);
	    }
	}

结果验证

现在我们以上面四种情况为例，将AVL树打印出来，验证下我们的代码是否正确

	import java.util.LinkedHashMap;
	import java.util.LinkedList;
	import java.util.List;
	import java.util.Map;
	
	//AVL树打印工具
	@SuppressWarnings("all")
	public class AVLPrinter {
	
	    AVLNode root;
	
	    //中序遍历和广度遍历结果
	    final List inorderTraverseList = new LinkedList();
	    final List breadthTraverseList = new LinkedList();
	
	    //所有节点的坐标
	    final Map xMap = new LinkedHashMap();
	    final Map yMap = new LinkedHashMap();
	
	    //整个输出矩阵中的所有字符
	    final List charForm = new LinkedList();
	
	    //下个节点的坐标
	    int nextX;
	    int nextY;
	
	    public void setRootNode(AVLNode root) {
	        this.root = root;
	    }
	
	    public void Print() {
	        //清空旧数据
	        inorderTraverseList.clear();
	        breadthTraverseList.clear();
	        xMap.clear();
	        yMap.clear();
	        charForm.clear();
	        nextX = 0;
	        nextY = 0;
	        //如果节点为空，直接结束
	        if (root == null) {
	            System.out.println("Empty Tree");
	            return;
	        }
	        //中序遍历，计算出每个节点的横向X坐标
	        InorderTraverse(root);
	        //层次遍历，计算出每个节点的纵向Y坐标
	        List levelNodeList = new LinkedList();
	        levelNodeList.add(root);
	        BreadthTraverse(levelNodeList);
	        //生成最终的二维字符数组
	        FillCharForm();
	        //打印结果
	        for (List row : charForm) {
	            for (Character cell : row)
	                System.out.print(cell);
	            System.out.println();
	        }
	    }
	
	    //中序遍历
	    private void InorderTraverse(AVLNode node) {
	        if (node.left != null)
	            InorderTraverse(node.left);
	        inorderTraverseList.add(node);
	        xMap.put(node, nextX);
	        nextX = nextX + node.toString().length() + 1;
	        if (node.right != null)
	            InorderTraverse(node.right);
	    }
	
	    //层次遍历，当前层次的所有节点
	    private void BreadthTraverse(List levelNodeList) {
	        if (levelNodeList.isEmpty())
	            return;
	        for (AVLNode node : levelNodeList)
	            yMap.put(node, nextY);
	        breadthTraverseList.addAll(levelNodeList);
	        nextY = nextY + 1;
	        List nextLevelNodeList = new LinkedList();
	        for (AVLNode node : levelNodeList) {
	            if (node.left != null)
	                nextLevelNodeList.add(node.left);
	            if (node.right != null)
	                nextLevelNodeList.add(node.right);
	        }
	        BreadthTraverse(nextLevelNodeList);
	    }
	
	    //生成最终的二维字符数组
	    private void FillCharForm() {
	        //填充占位符
	        for (int y = 0; y