简介
均衡二叉搜寻树是一种非凡的二叉搜寻树。为什么会有均衡二叉搜寻树呢？
考虑一下二叉搜寻树的非凡状况，如果一个二叉搜寻树所有的节点都是右节点，那么这个二叉搜寻树将会进化成为链表。从而导致搜寻的工夫复杂度变为O(n),其中n是二叉搜寻树的节点个数。
而均衡二叉搜寻树正是为了解决这个问题而产生的，它通过限度树的高度，从而将工夫复杂度升高为O(logn)。
AVL的个性
在探讨AVL的个性之前，咱们先介绍一个概念叫做均衡因子，均衡因子示意的是左子树和右子树的高度差。
如果均衡因子=0，示意这是一个齐全均衡二叉树。
如果均衡因子=1，那么这棵树就是均衡二叉树AVL。
也就是是说AVL的均衡因子不可能大于1。
先看一个AVL的例子：
总结一下，AVL首先是一个二叉搜寻树，而后又是一个二叉均衡树。
AVL的构建
有了AVL的个性之后，咱们看下AVL是怎么构建的。
public class AVLTree { //根节点 Node root; class Node { int data; //节点的数据 int height; //节点的高度 Node left; Node right; public Node(int data) { this.data = data; left = right = null; } }同样的，AVL也是由各个节点形成的，每个节点领有data，left和right几个属性。
因为是二叉均衡树，节点是否均衡还跟节点的高度无关，所以咱们还须要定义一个height作为节点的高度。
在来两个辅助的办法，一个是获取给定的节点高度：
//获取给定节点的高度 int height(Node node) { if (node == null) return 0; return node.height; }和获取均衡因子：
//获取均衡因子 int getBalance(Node node) { if (node == null) return 0; return height(node.left) - height(node.right); }AVL的搜寻
AVL的搜寻和二叉搜寻树的搜寻形式是统一的。
先看一个直观的例子，怎么在AVL中搜寻到7这个节点：
搜寻的根本步骤是：
- 从根节点15登程，比拟根节点和搜寻值的大小
- 如果搜寻值小于节点值，那么递归搜寻左侧树
- 如果搜寻值大于节点值，那么递归搜寻右侧树
- 如果节点匹配，则间接返回即可。
相应的java代码如下：
//搜寻办法，默认从根节点搜寻 public Node search(int data){ return search(root,data); } //递归搜寻节点 private Node search(Node node, int data) { // 如果节点匹配，则返回节点 if (node==null || node.data==data) return node; // 节点数据大于要搜寻的数据，则持续搜寻右边节点 if (node.data > data) return search(node.left, data); // 如果节点数据小于要搜素的数据，则持续搜寻左边节点 return search(node.right, data); }AVL的插入
AVL的插入和BST的插入是一样的，不过插入之后有可能会导致树不再均衡，所以咱们须要做一个再均衡的步骤。
看一个直观的动画：
插入的逻辑是这样的：
- 从根节点登程，比拟节点数据和要插入的数据
- 如果要插入的数据小于节点数据，则递归左子树插入
- 如果要插入的数据大于节点数据，则递归右子树插入
- 如果根节点为空，则插入以后数据作为根节点
插入数据之后，咱们须要做再均衡。
再均衡的逻辑是这样的：
- 从插入的节点向上找出第一个未均衡的节点，这个节点咱们记为z
- 对z为根节点的子树进行旋转，失去一个均衡树。
依据以z为根节点的树的不同，咱们有四种旋转形式：
- left-left：
如果是left left的树，那么进行一次右旋就够了。
右旋的步骤是怎么样的呢？
- 找到z节点的左节点y
- 将y作为旋转后的根节点
- z作为y的右节点
- y的右节点作为z的左节点
- 更新z的高度
相应的代码如下：
Node rightRotate(Node node) { Node x = node.left; Node y = x.right; // 右旋 x.right = node; node.left = y; // 更新node和x的高度 node.height = max(height(node.left), height(node.right)) + 1; x.height = max(height(x.left), height(x.right)) + 1; // 返回新的x节点 return x; }- right-right:
如果是right-right模式的树，须要通过一次左旋：
左旋的步骤正好和右旋的步骤相同：
- 找到z节点的右节点y
- 将y作为旋转后的根节点
- z作为y的左节点
- y的左节点作为z的右节点
- 更新z的高度
相应的代码如下：
//左旋 Node leftRotate(Node node) { Node x = node.right; Node y = x.left; //左旋操作 x.left = node; node.right = y; // 更新node和x的高度 node.height = max(height(node.left), height(node.right)) + 1; x.height = max(height(x.left), height(x.right)) + 1; // 返回新的x节点 return x; }- left-right：
如果是left right的状况，须要先进行一次左旋将树转变成left left格局，而后再进行一次右旋，失去最终后果。
- right-left：
如果是right left格局，须要先进行一次右旋，转换成为right right格局，而后再进行一次左旋即可。
当初问题来了，怎么判断一个树到底是哪种格局呢？咱们能够通过获取均衡因子和新插入的数据比拟来判断：
如果balance>1,那么咱们在Left Left或者left Right的状况，这时候咱们须要比拟新插入的data和node.left.data的大小
如果data < node.left.data，示意是left left的状况，只须要一次右旋即可
如果data > node.left.data，示意是left right的状况，则须要将node.left进行一次左旋，而后将node进行一次右旋
如果balance<-1,那么咱们在Right Right或者Right Left的状况，这时候咱们须要比拟新插入的data和node.right.data的大小
如果data > node.right.data，示意是Right Right的状况，只须要一次左旋即可如果data < node.left.data，示意是Right left的状况，则须要将node.right进行一次右旋，而后将node进行一次左旋
插入节点的最终代码如下：
//插入新节点，从root开始 public void insert(int data){ root=insert(root, data); } //遍历插入新节点 Node insert(Node node, int data) { //先依照一般的BST办法插入节点 if (node == null) return (new Node(data)); if (data < node.data) node.left = insert(node.left, data); else if (data > node.data) node.right = insert(node.right, data); else return node; //更新节点的高度 node.height = max(height(node.left), height(node.right)) + 1; //判断节点是否均衡 int balance = getBalance(node); //节点不均衡有四种状况 //1.如果balance>1,那么咱们在Left Left或者left Right的状况，这时候咱们须要比拟新插入的data和node.left.data的大小 //如果data < node.left.data，示意是left left的状况，只须要一次右旋即可 //如果data > node.left.data，示意是left right的状况，则须要将node.left进行一次左旋，而后将node进行一次右旋 //2.如果balance<-1,那么咱们在Right Right或者Right Left的状况，这时候咱们须要比拟新插入的data和node.right.data的大小 //如果data > node.right.data，示意是Right Right的状况，只须要一次左旋即可 //如果data < node.left.data，示意是Right left的状况，则须要将node.right进行一次右旋，而后将node进行一次左旋 //left left if (balance > 1 && data < node.left.data) return rightRotate(node); // Right Right if (balance < -1 && data > node.right.data) return leftRotate(node); // Left Right if (balance > 1 && data > node.left.data) { node.left = leftRotate(node.left); return rightRotate(node); } // Right Left if (balance < -1 && data < node.right.data) { node.right = rightRotate(node.right); return leftRotate(node); } //返回插入后的节点 return node; }AVL的删除
AVL的删除和插入相似。
首先依照一般的BST删除，而后也须要做再均衡。
看一个直观的动画：
删除之后，节点再均衡也有4种状况：
如果balance>1,那么咱们在Left Left或者left Right的状况，这时候咱们须要比拟左节点的均衡因子
如果左节点的均衡因子>=0，示意是left left的状况，只须要一次右旋即可
如果左节点的均衡因<0，示意是left right的状况，则须要将node.left进行一次左旋，而后将node进行一次右旋
如果balance<-1,那么咱们在Right Right或者Right Left的状况，这时候咱们须要比拟右节点的均衡因子
如果右节点的均衡因子<=0，示意是Right Right的状况，只须要一次左旋即可
如果右节点的均衡因子>0，示意是Right left的状况，则须要将node.right进行一次右旋，而后将node进行一次左旋
相应的代码如下：
Node delete(Node node, int data) { //Step 1. 一般BST节点删除 // 如果节点为空，间接返回 if (node == null) return node; // 如果值小于以后节点，那么持续左节点删除 if (data < node.data) node.left = delete(node.left, data); //如果值大于以后节点，那么持续右节点删除 else if (data > node.data) node.right = delete(node.right, data); //如果值雷同，那么就是要删除的节点 else { // 如果是单边节点的状况 if ((node.left == null) || (node.right == null)) { Node temp = null; if (temp == node.left) temp = node.right; else temp = node.left; //没有子节点的状况 if (temp == null) { node = null; } else // 单边节点的状况 node = temp; } else { //非单边节点的状况 //拿到右侧节点的最小值 Node temp = minValueNode(node.right); //将最小值作为以后的节点值 node.data = temp.data; // 将该值从右侧节点删除 node.right = delete(node.right, temp.data); } } // 如果节点为空，间接返回 if (node == null) return node; // step 2: 更新以后节点的高度 node.height = max(height(node.left), height(node.right)) + 1; // step 3: 获取以后节点的均衡因子 int balance = getBalance(node); // 如果节点不再均衡，那么有4种状况 //1.如果balance>1,那么咱们在Left Left或者left Right的状况，这时候咱们须要比拟左节点的均衡因子 //如果左节点的均衡因子>=0，示意是left left的状况，只须要一次右旋即可 //如果左节点的均衡因<0，示意是left right的状况，则须要将node.left进行一次左旋，而后将node进行一次右旋 //2.如果balance<-1,那么咱们在Right Right或者Right Left的状况，这时候咱们须要比拟右节点的均衡因子 //如果右节点的均衡因子<=0，示意是Right Right的状况，只须要一次左旋即可 //如果右节点的均衡因子>0，示意是Right left的状况，则须要将node.right进行一次右旋，而后将node进行一次左旋 // Left Left Case if (balance > 1 && getBalance(node.left) >= 0) return rightRotate(node); // Left Right Case if (balance > 1 && getBalance(node.left) < 0) { node.left = leftRotate(node.left); return rightRotate(node); } // Right Right Case if (balance < -1 && getBalance(node.right) <= 0) return leftRotate(node); // Right Left Case if (balance < -1 && getBalance(node.right) > 0) { node.right = rightRotate(node.right); return leftRotate(node); } return node; }本文的代码地址：
learn-algorithm
本文收录于 http://www.flydean.com/11-algorithm-avl-tree/
最艰深的解读，最粗浅的干货，最简洁的教程，泛滥你不晓得的小技巧等你来发现！
欢送关注我的公众号:「程序那些事」,懂技术，更懂你！