动态查找表---平衡二叉树
问题：
对于二叉排序树，假如给出一个{1，2，3，4，5，6}这样的数列，那么该树的一侧便会过长，一侧会过短，导致查询效率过低，为了解决这样的问题，提出了平衡二叉树。
平衡二叉树：
平衡二叉树也叫做平衡二叉搜索(查找)树，又被称为AVL树。具有如下性质:
(1) 它必须是二叉搜索(查找)树
(2) 它的每个节点的左右子树的高度之差都不超过1，左右子树都是一颗平衡二叉树。
平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。(这里的AVL指的是算法，AVL算法，不是AVL树的意思)
调整方式：
一、单旋 （左旋、右旋）
1、左旋
(1)创建一个新的节点newNode，创建一个新的节点，值等于当前根节点的值
(2)把新节点的左子树设置为当前节点的左子树
newNode.left = left
(3)把新节点的右子树设置为当前节点的右子树的左子树
newNode.right = right.left
(4)把当前节点的值换为右子节点的值
value = right.value
(5)把当前节点的右子树设置为右子树的右子树
right = right.right
(6)把当前节点的左子树设置为新节点
left = newNode
2、右旋
(1)创建一个新的节点newNode，创建一个新的节点，值等于当前根节
(2)把新节点的右子树设置为当前节点的右子树
newNode.right = right
(3)把新节点的左子树设置为当前节点的左子树的右子树
newNode.left = left.right
(4)把当前节点的值换为左子节点的值
value = left.value
(5)把当前节点的左子树设置为左子树的左子树
left = left.left
(6)把当前节点的右子树设置为新节点
right = newNode
二、双旋
我们会发现，对于有些树，单旋是无法解决问题的：
问题分析：
当符合右旋的条件时（左旋同理），如果它的左子树的右子树高度大于它的右子树高度，假设左子树的高度为x,右子树的高度为（x-2），左子树的左子树高度（x-2）,左子树的右子树高度（x-1）
右旋后：左子树的高度为x-2，右子树的高度x((x-1)+1=x),仍不满足平衡二叉树
解决：先对这个结点的左节点进行左旋转，再对当前结点进行右旋转即可。
代码实现：
package cn.wangqin;public class Demo {public static void main(String[] args) {int[] arr = {4,3,6,5,7,8};//int[] arr = {10,12,8,9,7,6};//int[] arr = {10,11,7,6,8,9};AVLTree at = new AVLTree();for(int i=0;i<arr.length;i++) {at.addNodeTree(new Node(arr[i]));}at.treeInOrder();System.out.println(at.getRoot().height());System.out.println(at.getRoot().leftHeight());System.out.println(at.getRoot().rightHeight());}}class AVLTree {private Node root;public Node getRoot() {return root;}public void addNodeTree(Node node) {if (root == null) {root = node;}else {root.nodeAdd(node);}}//通过中序方式遍历public void treeInOrder() {if(root == null) {return;}else {root.inOrder();}}}class Node {int value;Node left;Node right;public Node(int value) {this.value = value;}public String toString() {return "Node{" + "value=" + value + '}';}//递归形式添加节点，注意要满足二叉排序树public void nodeAdd(Node node) {if(node == null) {return;}if(node.value < this.value) {if(this.left == null) {this.left = node;}else {this.left.nodeAdd(node);}}else {if (this.right == null) {this.right = node;}else{this.right.nodeAdd(node);}}//添加节点后，判断是否需要旋转if(rightHeight()-leftHeight()>1) {//是否需要双旋进行判断if(left!=null && left.rightHeight()>left.rightHeight()) {right.leftRotate();leftRotate();}else {leftRotate();}//必须有，已经平衡后就不需要向下判断了，也防止其它情况发生return;}if(leftHeight()-rightHeight()>1) {//是否需要双旋进行判断//如果它的左子树的右子树高度大于它的左子树的高度if(left!=null && left.rightHeight()>left.rightHeight()) {//先对当前节点的左节点（左子树）-->左旋转left.leftRotate();//再对当前节点进行右旋转rightRotate();}else {//直接进行右旋转即可rightRotate();}}}public void inOrder() {if(this.left != null) {this.left.inOrder();}System.out.println(this);if (this.right != null) {this.right.inOrder();}}//返回左子树高度public int leftHeight() {if(this.left == null) {return 0;}else {return this.left.height();}}//返回右子树高度public int rightHeight() {if(this.right == null) {return 0;}else {return this.right.height();}}//返回以当前节点为根节点的树的高度：每递归一次高度加1,到最后一个叶子节点便不递归public int height() {return Math.max(this.left==null?0:this.left.height(),this.right==null?0:this.right.height())+1;}//左旋转public void leftRotate() {Node newNode = new Node(this.value);newNode.left = this.left;newNode.right = this.right.left;this.value =this.right.value;this.right = this.right.right;this.left = newNode;}//右旋转public void rightRotate() {Node newNode = new Node(this.value);newNode.right = this.right;newNode.left = this.left.right;this.value =this.left.value;this.left = this.left.left;this.right = newNode;}}
疑惑解答：递归中的this代表哪个节点？
在Node类中的addNode() 方法中，有一段左右高度判断代码：
1虽然没有加this，但是我们知道其实就是this.rightHeight()。那么递归中this代表哪个数据项呢？
以{10，12，8，9，7，6}为例，每次从根节点开始添加完节点后，其实是这样进行高度比较的，我们首先在addNode（）方法中添加代码：
System.out.println(this);然后输出：10，10，8，10，8，10，7，8，10
其实应该分割成：10，10，(8，10)，(8，10)，(7，8，10)
以添加叶子节点6为例：（输出：7，8，10）
(1) 从root开始递归，然后最后添加6，递归过程中不会执行高度判断代码，直到执行到最后叶子节点。
(2) 首先this代表7，然后才向下执行左右高度判断代码，左右子树符合平衡条件
(3) 然后返回上一级的递归，此时this代表8，也执行高度高度判断代码
(4) 然后再继续返回上一级的递归，此时thi代表10，也执行高度高度判断代码，不符合平衡条件，这时候才会进行旋转调整。
也就是添加节点后，节点从下向上开始判断左右平衡，不平衡就旋转调整
因此输出this，会出现7，8，10这种从下到上这种情况。