1、看一个案例(说明二叉排序树可能的问题)

给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST), 并分析问题所在.

左边BST 存在的问题分析:
1.左子树全部为空，从形式上看，更像一个单链表.
2.插入速度没有影响 查询速度明显降低(因为需要依次比较),
3.不能发挥BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢
4.解决方案-平衡二叉树(AVL)

2、基本介绍

平衡二叉树也叫平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树， 可以保证查询效率较高。
具有以下特点：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、伸展树等。
举例说明, 看看下面哪些AVL树, 为什么?

①②都是AVL树，③不是

3、应用案例-单旋转(左旋转)

要求: 给你一个数列，创建出对应的平衡二叉树.数列 {4,3,6,5,7,8}

3.1、左旋转代码实现

//add(Node node) 左旋转[单旋转]if (rightHeight() - leftHeight() > 1) {leftRotate();}

  public void leftRoate(){ //创建一个新的节点newNode，值等于当前节点的值 Node newNode=new Node(this.value); //把新的节点的左子树设置为当前节点的左子树 newNode.left=left; //把新的节点的右子树设置为当前节点的右子树的左子树 newNode.right=right.left; //把当前节点的值替换为右子节点的值 this.value=right.value; //把当前节点的右子树设置为右子树的右子树 this.right=right.right; //把当前节点的左子树设置为新节点 this.left=newNode;    }

4、应用案例-单旋转(右旋转)

要求: 给你一个数列，创建出对应的平衡二叉树.数列 {10,12, 8, 9, 7, 6}

4.1、右旋转代码实现

//add(Node node) 右旋转[单旋转]if (leftHeight() - rightHeight() > 1) {rightRotate();}

  public void rightRoate(){ //创建一个新的节点newNode，值等于当前节点的值 Node newNode=new Node(this.value); //把新的节点的左子树设置为当前节点的左子树 newNode.right=right; //把新的节点的右子树设置为当前节点的右子树的左子树 newNode.left=left.right; //把当前节点的值替换为右子节点的值 this.value=left.value; //把当前节点的右子树设置为右子树的右子树 this.left=left.left; //把当前节点的左子树设置为新节点 this.right=newNode;    }

5、应用案例-双旋转

前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列
int[] arr = { 10, 11, 7, 6, 8, 9 }; 运行原来的代码可以看到，并没有转成 AVL树.

int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到，并没有转成 AVL树

解题思路

5.1、双旋转代码实现

   if (rightHeight()-leftHeight()>1){     if(right!=null&&right.leftHeight()>right.rightHeight()){  right.rightRoate();  leftRoate();     }else {  leftRoate();     }     return; } if (leftHeight()-rightHeight()>1){     if(left!=null&&left.rightHeight()>left.leftHeight()){  left.leftRoate();  rightRoate();     }else{  rightRoate();     } }

6、代码整合

package com.qf.avltree;import java.util.Map;public class AVLTreeDemo {    public static void main(String[] args) { int[] arr = { 10, 11, 7, 6, 8, 9 }; AVLTree binarySortTree=new AVLTree(); for (int i : arr) {     binarySortTree.add(new Node(i)); } int height = binarySortTree.root.height(); int leftHeight = binarySortTree.root.leftHeight(); int rightHeight = binarySortTree.root.rightHeight(); System.out.println("树的高度为："+height); System.out.println("左子树的高度为："+leftHeight); System.out.println("右子树的高度为："+rightHeight); System.out.println(binarySortTree.root.value); binarySortTree.midOrder();    }}class AVLTree{    public Node root;    public void add(Node node){ if (root==null){     root=node; }else{     root.add(node); }    }    public void midOrder(){ if (root==null){     System.out.println("树为空~~~"); }else{     root.midOrder(); }    }}class Node{    public int value;    public Node left;    public Node right;    public Node(int value){ this.value=value;    }    @Override    public String toString() { return "Node{" +  "value=" + value +  '}';    }    public void add(Node node){ if (this==null){     return; } if (this.value>node.value){     if (this.left==null){  this.left=node;     }else{  this.left.add(node);     } }else{     if (this.right==null){  this.right=node;     }else{  this.right.add(node);     } } if (rightHeight()-leftHeight()>1){     if(right!=null&&right.leftHeight()>right.rightHeight()){  right.rightRoate();  leftRoate();     }else {  leftRoate();     }     return; } if (leftHeight()-rightHeight()>1){     if(left!=null&&left.rightHeight()>left.leftHeight()){  left.leftRoate();  rightRoate();     }else{  rightRoate();     } }    }    public int leftHeight(){ if (left==null){     return 0; }else {     return left.height(); }    }    public int rightHeight(){ if (right==null){     return 0; }else {     return right.height(); }    }    public void leftRoate(){ //创建一个新的节点newNode，值等于当前节点的值 Node newNode=new Node(this.value); //把新的节点的左子树设置为当前节点的左子树 newNode.left=left; //把新的节点的右子树设置为当前节点的右子树的左子树 newNode.right=right.left; //把当前节点的值替换为右子节点的值 this.value=right.value; //把当前节点的右子树设置为右子树的右子树 this.right=right.right; //把当前节点的左子树设置为新节点 this.left=newNode;    }    public void rightRoate(){ //创建一个新的节点newNode，值等于当前节点的值 Node newNode=new Node(this.value); //把新的节点的左子树设置为当前节点的左子树 newNode.right=right; //把新的节点的右子树设置为当前节点的右子树的左子树 newNode.left=left.right; //把当前节点的值替换为右子节点的值 this.value=left.value; //把当前节点的右子树设置为右子树的右子树 this.left=left.left; //把当前节点的左子树设置为新节点 this.right=newNode;    }    public int height(){ return Math.max(left==null?0:left.height(),right==null?0:right.height())+1;    }    public void midOrder(){ if (this.left!=null){     this.left.midOrder(); } System.out.println(this); if (this.right!=null){     this.right.midOrder(); }    }}