2-3、avl树
avl树，又叫平衡二叉搜索树，是在二叉搜索树的基础上建立的一种树，它相比bst，多了一个特性，就是任意一棵子树根节点的左右子树的高度差的绝对值不超过1，这是为了防止bst中最坏情况的出现，一棵avl树的深度为o(logN)。
对于节点的插入，有可能会导致树平衡条件被打破，因此，在插入时，需要对树进行结构调整，以重新满足平衡条件。
我们假设某棵子树的根节点为r，导致r的平衡条件被打破的可能性有以下四种：
1、往r的左儿子的左子树进行插入
2、往r的右儿子的右子树进行插入
3、往r的左儿子的右子树进行插入
4、往r的右儿子的左子树进行插入
可以看出，1与2是对称类似的，只需要进行一次旋转就行，3与4同样对称类似，但是需要进行两次旋转。
一、但旋转
对于1和2这两种情况，我们讨论第1种，也就是对r的左儿子的左子树进行插入操作
图 1
由图1可以看出，当插入到子树X中时，导致k2的左子树比右子树的高度高2，导致不平衡，需要进行旋转，将k1和k2进行旋转，然后把k1的子树Y挂接为k2的左子树，可以看出，在这种情况下，只需要进行一次旋转就行了。
我们注意到，在调整的时候，k1和k2的子树也发生了变化，Y变成了k2的左子树，的确，因为k2变成了k1的右子树，导致k1变成了三叉树，所以必须对k1的某棵子树重新调整父节点，考虑到bst的特点，发现Y中的节点树都大于k1，同时也小于k2，而此时k2的左子树原来是k1，经过调整后k2的左子树正好空缺，所以可以把k2的左子树设为Y，至此，我们完美的完成了单旋转调整。
二、双旋转
当第三种情况出现时，会略微复杂，我们先看下面这个例子。
图2
很明显，进行一次单旋转操作后仍然无法满足平衡条件，因此，我们需要对Y树进行改造。将其拆为根节点r和两颗子树Y1，Y2。其中，假设是因为Y2导致树平衡条件被打破
图3
先对k1和r进行旋转，然后在对r和k2进行旋转，就可以重新满足平衡条件了。
ok，是不是觉得很简单呢？既然思路已经理清了，那代码就可以信手拈来了，下面是基于递归的实现，avl树的平衡调整还是有些复杂的，基于递归的实现要容易理解一些，下次我会补全没有采用递归的实现。
package avl;/** * avl树的实现 * * @author 梅东 * * @param <E> */public class AvlTree<E extends Comparable<? super E>> {private AvlNode<E> root;public void insert(E e) {this.root = insert(e, root);}public int height(AvlNode<E> r) {if (r == null)return -1;elsereturn r.height;}/** * 前序输出每个节点的值 */@Overridepublic String toString() {StringBuilder result = new StringBuilder();return DLR(result, this.root);}/** * 插入节点 * * @param e * @param r * @return */public AvlNode<E> insert(E e, AvlNode<E> r) {// 根节点为空，返回一个新节点if (r == null)return new AvlNode<E>(e);// 该节点和根节点的比较结果int compareResult = e.compareTo(r.element);// 小于0，说明是插入到根节点的左子树中去了if (compareResult < 0) {r.leftChild = insert(e, r.leftChild);// 左子树与右子树的高相差2，打破了平衡if (height(r.leftChild) - height(r.rightChild) == 2) {if (e.compareTo(r.leftChild.element) < 0)// 插入到左子树根节点的左子树中，是第一种情况，左旋转r = rotateWithLeftChild(r);else// 插入到左子树根节点的右子树中，是第三种情况，左-右旋转r = doubleWithLeftChild(r);}} else if (compareResult > 0) {// 大于0，说明是插入到根节点的右子树中去了r.rightChild = insert(e, r.rightChild);// 右子树与左子树高度差为2，打破了平衡if (height(r.rightChild) - height(r.leftChild) == 2) {if (e.compareTo(r.rightChild.element) > 0)// 插入到了右子树根节点的右子树中区，第二种情况，右旋转r = rotateWithRightChild(r);else// 插入到右子树根节点的左子树中，是第四种情况，右-左旋转r = doubleWithRightChild(r);}} else;r.height = Math.max(height(r.leftChild), height(r.rightChild)) + 1;return r;}/** * 左旋转 * * @param r * @return */private AvlNode<E> rotateWithLeftChild(AvlNode<E> r) {AvlNode<E> root = r.leftChild;r.leftChild = root.rightChild;root.rightChild = r;r.height = Math.max(height(r.leftChild), height(r.rightChild)) + 1;root.height = Math.max(height(root.leftChild), r.height) + 1;return root;}/** * 右旋转 * * @param r * @return */private AvlNode<E> rotateWithRightChild(AvlNode<E> r) {AvlNode<E> root = r.rightChild;r.rightChild = root.leftChild;root.leftChild = r;r.height = Math.max(height(r.leftChild), height(r.rightChild)) + 1;root.height = Math.max(height(root.rightChild), r.height) + 1;return root;}/** * 左-右旋转 * * @param r * @return */private AvlNode<E> doubleWithLeftChild(AvlNode<E> r) {r.leftChild = rotateWithRightChild(r.leftChild);return rotateWithLeftChild(r);}/** * 右-左旋转 * * @param r * @return */private AvlNode<E> doubleWithRightChild(AvlNode<E> r) {r.rightChild = rotateWithLeftChild(r.rightChild);return rotateWithRightChild(r);}/** * 前序遍历 * * @param result * @param root * @return */private String DLR(StringBuilder result, AvlNode<E> root) {if (root != null) {result.append(root.element);result.append(" ");DLR(result, root.leftChild);DLR(result, root.rightChild);}return result.toString();}/** * 树节点实现 * * @author 梅东 * * @param <E> */private static class AvlNode<E> {E element;AvlNode<E> leftChild;AvlNode<E> rightChild;int height;public AvlNode(E element) {this(element, null, null);}public AvlNode(E element, AvlNode<E> leftChild, AvlNode<E> rightChild) {this.element = element;this.leftChild = leftChild;this.rightChild = rightChild;this.height = 0;}}}