type
status
date
slug
summary
tags
category
icon
password

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

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

2、基本介绍

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

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

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

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}
notion image

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树.
notion image
int[] arr = {2,1,6,5,7,3}; // 运行原来的代码可以看到,并没有转成 AVL树
解题思路
notion image
notion image

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();       }   } }
 
普里姆算法排序算法-算法时间复杂度和空间复杂度概念 详细讲解