平衡二叉树 AVL树
- 给你一个数列{1,2,3,4,5,6}，要求创建一颗二叉排序树(BST) 并分析问题所在.
左边BST存在的问题分析:
1)左子树全部为空，从形式上看，更像- -个单链表.
2)插入速度没有影响
3)查询速度明显降低(因为需要依次比较),不能发挥BST的优势，因为每次还需要比较左子树，其查询速度比单链表还慢
4）解决方案-平衡二叉树(AVL)
- 基本介绍
1)平衡二叉树也叫平衡二叉搜索树(Self- balancing binarysearch tree)又被称为AVL树， 可以保证查询效率较高。
2)具有以下特点:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用实现方法有红黑树、AVL、替罪羊树、Treap、 伸展树等。
应用案例-单旋转（左旋转）
- 要求:给你一个数列，创建出对应的平衡二叉树数列{4,3,6,5,7,8}
思路分析
问题:当插入8时rightHeight()- leftHeight()>1成立，此时，不再是一颗avl树了.
怎么处理--进行左旋转:
-
创建一个新的节点newNode (以4这个值创建)，创建一个新的节点，值等于当前根节点的值
-
newNode.left = left； //把新节点的左子树设置了当前节点的左子树
-
newNode.right =right.left; //把新节点的右子树设置为当前节点的右子树的左子树
-
value=right.value; //把当前节点的值换为右子节点的值
-
right=right.right; //把当前节点的右子树设置成右子树的右子树
-
left=newLeft; //把当前节点的左子树设置为新节点
代码实现
AVL树高度求解
定义一个Class Node，并在类中写求解树高度的方法
//返回左子树的高度
public int leftHeight() {
if (left == null) {
return 0;
}
return left.height();
}
//返回右子树的高度
public int rightHeight() {
if (right == null) {
return 0;
}
return right.height();
}
//返回以该节点为根节点的树的高度
public int height() {
return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}
递归思想解释：以根结点左结点和右节点为初始递归条件，一直往下递归到叶子结点，往上每返回一层递归函数高度加一，比较左右结点路径的深度，得到最大深度
测试代码：
int[] arr={4,3,6,5,7,8};
//创建一个AVLTree对象
AVLTree avlTree = new AVLTree();
//添加结点
for (int i=0;i< arr.length;i++){
avlTree.add(new Node(arr[i]));
}
//遍历
System.out.println("中序遍历");
avlTree.infixOrder();
System.out.println("在没有平衡处理前~~");
System.out.println("树的高度="+avlTree.getRoot().height());
左旋转代码
Class Node类中写左旋转代码
//左旋转方法
private void leftRotate(){
//创建新的结点，以当前根节点的值
Node newNode = new Node(value);
//把新的结点的左子树设置为当前结点的左子树
newNode.left=left;
//把新结点的右子树结点设置为当前结点右子树的左子树结点
newNode.right=right.left;
//把当前节点与当前节点的右子树结点进行交换
value=right.value;
//把当前节点的右子树设置为与当前节点的右子树的右子树
right=right.right;
//把当前结点的左子树（结点）设置为新的结点
left=newNode;
}
并修改Class Node类中的add方法
当添加完一个节点，如果：（右子树高度-左子树高度）>1,左旋转
//添加结点
//递归的形式添加节点，注意需要满足二叉排序树的要求
public void add(Node node) {
if (node == null) {
return;
}
//判断传入的结点的值，和当前子树的根节点的值关系
if (node.value < this.value) {
//如果当前节点左子节点为null
if (this.left == null) {
this.left = node;
} else {
//递归的向左子树添加
this.left.add(node);
}
} else { //添加的结点的值大于当前结点的值
//如果当前节点y右子节点为null
if (this.right == null) {
this.right = node;
} else {
//递归的向左子树添加
this.right.add(node);
}
}
//当添加完一个节点，如果：（右子树高度-左子树高度）>1,左旋转
if (rightHeight()-leftHeight()>1){
leftRotate();//左旋转
}
}
测试代码
int[] arr={4,3,6,5,7,8};
//创建一个AVLTree对象
AVLTree avlTree = new AVLTree();
//添加结点
for (int i=0;i< arr.length;i++){
avlTree.add(new Node(arr[i]));
}
//遍历
System.out.println("中序遍历");
avlTree.infixOrder();
System.out.println("平衡处理~~");
System.out.println("树的高度="+avlTree.getRoot().height());
System.out.println("左子树的高度="+avlTree.getRoot().leftHeight());
System.out.println("右子树的高度="+avlTree.getRoot().rightHeight());
应用案例-单旋转（左旋转）
思路分析
问题:当插入6时 leftHeight -rightHeightO >1成立，此时，不再是一颗avl树了。
怎么处理-进行右旋转[就是降低左子树的高度1，这里是将9这个节点，通过右旋转，到右子树
-
创建一个新的节点newNode(以10这个值创建),创建一个新的节点，值等于当前根节点的值
-
newNode.right = right //把新节点的右子树设置了当前节点的右子树
-
newNode.left =left.right; //把新节点的左子树设置为当前节点的左子树的右子树
-
value=left.value;//把当前节点的值换为左子节点的值
-
left=left.left;//把当前节点的左子树设置成左子树的左子树
-
right=newNode;//把当前节点的右子树设置为新节点
代码实现
Class Node类中写右旋转代码
//右旋转方法
private void rightRotate(){
//创建新的结点，以当前根节点的值
Node newNode = new Node(value);
newNode.right=right;
newNode.left=left.right;
value=left.value;
left=left.left;
right=newNode;
}
并修改Class Node类中的add方法
当添加完一个节点，如果：（右子树高度-左子树高度）>1,左旋转
//添加结点
//递归的形式添加节点，注意需要满足二叉排序树的要求
public void add(Node node) {
if (node == null) {
return;
}
//判断传入的结点的值，和当前子树的根节点的值关系
if (node.value < this.value) {
//如果当前节点左子节点为null
if (this.left == null) {
this.left = node;
} else {
//递归的向左子树添加
this.left.add(node);
}
} else { //添加的结点的值大于当前结点的值
//如果当前节点y右子节点为null
if (this.right == null) {
this.right = node;
} else {
//递归的向左子树添加
this.right.add(node);
}
}
//当添加完一个节点，如果：
if (rightHeight()-leftHeight()>1){//（右子树高度-左子树高度）>1,左旋转
leftRotate();//左旋转
}else if (leftHeight()-rightHeight()>1){//（左子树高度-右子树高度）>1,右旋转
rightRotate();//右旋转
}
}
测试代码
public static void main(String[] args) {
//int[] arr={4,3,6,5,7,8};
int[] arr={10,12,8,9,7,6};
//创建一个AVLTree对象
AVLTree avlTree = new AVLTree();
//添加结点
for (int i=0;i< arr.length;i++){
avlTree.add(new Node(arr[i]));
}
//遍历
System.out.println("中序遍历");
avlTree.infixOrder();
System.out.println("平衡处理~~");
System.out.println("树的高度="+avlTree.getRoot().height());
System.out.println("左子树的高度="+avlTree.getRoot().leftHeight());
System.out.println("右子树的高度="+avlTree.getRoot().rightHeight());
}
应用案例-双旋转
前面的两个数列，进行单旋转(即一次旋转)就可以将非平衡二叉树转成平衡二叉树,但是在某些情况下，单旋转不能完成平衡二叉树的转换。比如数列：
int[]arr={10, 11,7,6,8,9};//运行原来的代码可以看到，并没有转成AVL树.
int[] arr = {2,1,6,5,7,3}; //运行原来的代码可以看到，并没有转成AVL树
问题分析
所以提出解决措施
问题分析
1.当符号右旋转的条件时
2.如果它的左子树的右子树高度大于它的左子树的高度
3.先对当前这个结点的左节点进行左旋转
4.在对当前结点进行右旋转的操作即可
代码实现
修改Class Node类中的add方法
public void add(Node node) {
if (node == null) {
return;
}
//判断传入的结点的值，和当前子树的根节点的值关系
if (node.value < this.value) {
//如果当前节点左子节点为null
if (this.left == null) {
this.left = node;
} else {
//递归的向左子树添加
this.left.add(node);
}
} else { //添加的结点的值大于当前结点的值
//如果当前节点y右子节点为null
if (this.right == null) {
this.right = node;
} else {
//递归的向左子树添加
this.right.add(node);
}
}
//当添加完一个节点，如果：（右子树高度-左子树高度）>1,左旋转
if (rightHeight()-leftHeight()>1) {//左旋转
//如果它的右子树的左子树高度大于它的右子树的高度
//先对右子节点进行右旋转
//然后在对当前节点进行左旋转
if (right != null && right.leftHeight() > right.rightHeight()) {
//先对右子节点进行右旋转
right.rightRotate();
//然后在对当前结点进行左旋转
leftRotate();
} else {
leftRotate();
}
return;//必须要！！！
}
if (leftHeight()-rightHeight()>1){//右旋转
//如果它的左子树的右子树高度大于它的左子树的高度
if(left!=null&&left.rightHeight()>left.leftHeight()){
//先对当前结点的左节点（左子树）-》进行左旋转
left.leftRotate();
//再对当前节点进行右旋转
rightRotate();//右旋转
}else{//直接进行右旋转
rightRotate();//右旋转
}
}
}
测试：
public static void main(String[] args) {
//int[] arr={4,3,6,5,7,8};
int[] arr={10,11,7,6,8,9};
//创建一个AVLTree对象
AVLTree avlTree = new AVLTree();
//添加结点
for (int i=0;i< arr.length;i++){
avlTree.add(new Node(arr[i]));
}
//遍历
System.out.println("中序遍历");
avlTree.infixOrder();
System.out.println("平衡处理~~");
System.out.println("树的高度="+avlTree.getRoot().height());
System.out.println("左子树的高度="+avlTree.getRoot().leftHeight());
System.out.println("右子树的高度="+avlTree.getRoot().rightHeight());
}
