type
status
date
slug
summary
tags
category
icon
password
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(); } } }
- 作者:程序员小舟
- 链接:https://codezhou.top/article/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91(AVL%E6%A0%91)
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。