平衡二叉树(AVL树)

2024-05-30 17:15:07 浏览数 (1)

什么是平衡二叉树？

​ 平衡二叉树 ：（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：

​ 它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

在讲解平衡二叉树之前我们先了解以下树的高度以及层的概念

查询树的高度

思路：

通过递归实现查询当前节点的左右子树的最大高度，然后再 1（加上节点本身），此时就是树的最大高度

代码语言：javascript复制
//查询树的高度
public int height(){
    return Math.max(left == null ? 0:left.height(),right == null ? 0:right.height())   1;
}

查询左右子树的高度

代码语言：javascript复制
//查询左子树的高度
public int leftHeight(){
    if(left == null){
        return 0;
    }
    return left.height();
}
//查询右子树的高度
public int rightHeight(){
    if(right == null){
        return 0;
    }
    return right.height();
}

平衡二叉树实现

左旋转

节点的左子树的高度即h(左) 和 右子树即h(右)的差值大于1 。

具体来说就是 h(右) - h(左) > 1

当满足这个情况时我们就需要进行左旋转

思路
  1. new 一个新的节点newNode ，value 为当前节点的value
  2. 设置newNode的left节点 为当前节点的left
  3. 设置newNode 的right节点 为当前节点的right的left节点
  4. 将当前节点的value设置为 当前节点的right的value
  5. 把当前节点的right 设置为 当前节点的right 的right
  6. 把当前节点的left设置为 newNode
代码语言：javascript复制
//左旋转
public void leftRotate(){
    //new 一个新的节点，值为当前节点的val
    Node newNode  = new Node(this.val);
    //将当前节点的left节点 设置为newNode的left
    newNode.left = this.left;
    //把当前节点this的right的left节点 设置为newNode的right
    newNode.right = this.right.left;
    //把当前节点的val修改成 当前节点的right的val
    this.val = this.right.val;
    //把当前节点的left设置为 newNode
    this.left = newNode;
    //把当前节点的right设置为 当前节点的right的right
    this.right = this.right.right;
}

右旋转

当前节点的左子树的高度，即h(左) 和 右子树即h(右)的差值大于1 。

具体来说就是 h(左) - h(右) > 1

当满足这个情况时我们就需要进行右旋转

思路
  1. new 一个新的节点newNode ，value 为当前节点的value
  2. 设置newNode的right节点 为当前节点的right
  3. 设置newNode 的left节点 为当前节点的left的right节点
  4. 将当前节点的value设置为 当前节点的left的value
  5. 把当前节点的left设置为 当前节点的left 的left
  6. 把当前节点的right设置为 newNode
代码语言：javascript复制
public void rightRotate(){
    //new新的节点 ，值为this.val
    Node newNode = new Node(this.val);
    //newNode 的right节点为当前节点的right节点
    newNode.right = this.right;
    //newNode 的left节点 为当前节点的left的right节点
    newNode.left = this.left.right;
    //修改当前节点的val为 当前节点的left 的val
    this.val = this.left.val;
    //修改当前节点的left 为 当前节点的left 的 left
    this.left = this.left.left;
    //修改当前节点的right 为newNode
    this.right = newNode;
}

双旋转

双旋转出现的原因

以数组【10，11，7，6，8，9】为例

如下图可以看到，以节点8为根节点的right树高度 - left树的高度 > 1

这样如果我们还是按照之前的做法势必无法得到平衡二叉树。所以我们就需要先将以节点8 为根节点的二叉树进行左旋转使它成为平衡二叉树之后，再对整棵树进行右旋转， 这样我们才能使整棵树都是平衡二叉树

解决思路

​ 如果当前树需要进行左旋转（即(rightHeight() - leftHeight() > 1)）

那么就需要判断右节点的rightHeight 是否 < rightHeight

如果满足， 那么就先将以right节点为根节点的树进行右旋转 ，然后再将整个树进行左旋转

​ 同理

​ 当前树需要进行右旋转（即(leftHeight() - rightHeight() > 1)）

那么就需要判断左节点的rightHeight 是否 > leftHeight

如果满足， 那么就先将以left节点为根节点的树进行左旋转 ，然后再将整个树进行右旋转

代码语言：javascript复制
    if (rightHeight() - leftHeight() > 1){
        //当前节点的右子树的右子树高度 < 当前节点的右子树的左子树高度
        if (right != null && right.rightHeight() < right.leftHeight()){
            //先将右子树进行右旋转 ，然后再将所有的树进行左旋转
            right.rightRotate();
            leftRotate();
        }else {
            leftRotate();
        }
    }
    else if (leftHeight() - rightHeight() > 1){
        //当前节点的左子树的右子树高度 > 当前节点的左子树的左子树高度
        if (left != null && left.leftHeight() < left.rightHeight()){
            //先将左子树进行左旋转 ，然后再将整棵树进行右旋转
            left.leftRotate();
            rightRotate();
        }else {
            rightRotate();
        }
    }
}

代码实现

代码语言：javascript复制
public class Node {
    public int val;
    public Node right;
    public Node left;

    //左旋转
    public void leftRotate(){
        //new 一个新的节点，值为当前节点的val
        Node newNode  = new Node(this.val);
        //将当前节点的left节点 设置为newNode的left
        newNode.left = this.left;
        //把当前节点this的right的left节点 设置为newNode的right
        newNode.right = this.right.left;
        //把当前节点的val修改成 当前节点的right的val
        this.val = this.right.val;
        //把当前节点的left设置为 newNode
        this.left = newNode;
        //把当前节点的right设置为 当前节点的right的right
        this.right = this.right.right;
    }

    public void rightRotate(){
        //new新的节点 ，值为this.val
        Node newNode = new Node(this.val);
        //newNode 的right节点为当前节点的right节点
        newNode.right = this.right;
        //newNode 的left节点 为当前节点的left的right节点
        newNode.left = this.left.right;
        //修改当前节点的val为 当前节点的left 的val
        this.val = this.left.val;
        //修改当前节点的left 为 当前节点的left 的 left
        this.left = this.left.left;
        //修改当前节点的right 为newNode
        this.right = newNode;
    }
    //添加树
    public void add(Node node){
        if(node == null){
            return;
        }
        if(node.val < this.val){
            if(this.left == null){
                this.left = node;
            }else{
                this.left.add(node);
            }
        }else{
            //node.val >= this.val
            if(this.right == null){
                this.right = node;
            }else{
                this.right.add(node);
            }
        }


        if (rightHeight() - leftHeight() > 1){
            //当前节点的右子树的右子树高度 < 当前节点的右子树的左子树高度
            if (right != null && right.rightHeight() < right.leftHeight()){
                //先将右子树进行右旋转 ，然后再将所有的树进行左旋转
                right.rightRotate();
                leftRotate();
            }else {
                leftRotate();
            }
        }
        else if (leftHeight() - rightHeight() > 1){
            //当前节点的左子树的右子树高度 > 当前节点的左子树的左子树高度
            if (left != null && left.leftHeight() < left.rightHeight()){
                //先将左子树进行左旋转 ，然后再将整棵树进行右旋转
                left.leftRotate();
                rightRotate();
            }else {
                rightRotate();
            }
        }
    }
    //查询左子树的高度
    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;
    }
    
    //中序遍历二叉树
    public void infix(){
        if(this.left != null){
            this.left.infix();
        }
        System.out.println(this);

        if (this.right != null){
            this.right.infix();
        }
    }
    public Node(int val) {
        this.val = val;
    }
    @Override
    public String toString() {
        return "Node["  
                "val="   val  
                ']';
    }
}
代码语言：javascript复制
public class AVLTree {
    public Node root;
    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,12,33,14,1,22,0,3,33,23,44,55,54,34};
        AVLTree avl  = new AVLTree();
        for (int i=0;i<arr.length;i  ){
                avl.add(new Node(arr[i]));
        }
        avl.root.infix();
        System.out.println("树的高度 :"   avl.root.height());
        System.out.println("树的左子树高度 :"   avl.root.leftHeight());
        System.out.println("树的右子树高度 :"   avl.root.rightHeight());
    }

    public void add(Node node){
        if (root == null){
            root = node;

        }else{
             root.add(node);
        }
    }
}

运行结果

Node[val=0] Node[val=1] Node[val=3] Node[val=6] Node[val=7] Node[val=8] Node[val=9] Node[val=10] Node[val=11] Node[val=12] Node[val=14] Node[val=22] Node[val=23] Node[val=33] Node[val=33] Node[val=34] Node[val=44] Node[val=54] Node[val=55] 树的高度 :5 树的左子树高度 :3 树的右子树高度 :4 进程已结束,退出代码0

int null public return 二叉树

0 人点赞