当前位置： 首页 > article >正文

平衡二叉树

article 2024/11/14 14:21:23

平衡二叉树

文章目录

  • 平衡二叉树
    • 基本介绍
    • 实现平衡二叉树
      • 左旋转
      • 右旋转
      • 双旋转
    • 完整代码

平衡二叉树其实就是比排序二叉树多了旋转方法，具体实现二叉排序树，请参考：(2条消息) 二叉排序树_Land-Cruise的博客-CSDN博客

二叉排序树存在的问题

当给出一个数列{1,2,3,4,5,6}，创建一个二叉排序树，就会创建这样一棵二叉排序树

在这里插入图片描述

左边BST 存在的问题分析:

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

基本介绍

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

实现平衡二叉树

计算二叉树高度的方法

//返回以当前节点为根节点的树的高度
    public int height(){
        return Math.max(left==null?0: left.height(), right==null?0: right.height())+1;
    }

计算左子树高度的方法

//返回左子树的高度
    public int leftHeight(){
        if(left==null){
            return 0;
        }
        return left.height();
    }

计算右子树高度的方法

//返回右子树的高度
    public int rightHeight(){
        if(right==null){
            return 0;
        }
        return right.height();
    }

左旋转

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

在这里插入图片描述

具体步骤：

  1. 创建一个新的节点newNode(以4这个值创建)，创建一个新的节点，值等于当前根节点的值
  2. 把新的节点的左子树设置成当前节点的左子树
  3. 把新的节点的右子树设置成当前节点的右子树的左子树
  4. 把当前节点的值替换成右子节点的值
  5. 把当前节点的右子树替换成右子树的右子树
  6. 当前节点的左子树指向刚才创建的新的节点

代码实现

//左旋转的方法
    private void leftRotate(){
        //创建新的节点，以当前根节点的值创建的
        Node newNode = new Node(value);
        //把新的节点的左子树设置成当前节点的左子树
        newNode.left = left;
        //把新的节点的右子树设置成当前节点的右子树的左子树
        newNode.right = right.left;
        //把当前节点的值替换成右子节点的值
        value = right.value;
        //把当前节点的右子树替换成右子树的右子树
        right = right.right;
        //当前节点的左子树指向刚才创建的新的节点
        left = newNode;
    }

右旋转

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

在这里插入图片描述

具体步骤：

  1. 创建新的节点，以当前根节点的值创建
  2. 把新的节点的右子树设置成当前节点的右子树
  3. 把新的节点的左子树设置成当前节点左子树的右子树
  4. 把当前节点的值替换成左子节点的值
  5. 把当前节点的左子树替换成左子树的左子树
  6. 把当前节点的右子树指向刚才创建的新的节点

代码实现

//右旋转的方法
    private void rightRotate(){
        //创建新的节点，以当前根节点的值创建
        Node newNode = new Node(value);
        //把新的节点的右子树设置成当前节点的右子树
        newNode.right = right;
        //把新的节点的左子树设置成当前节点左子树的右子树
        newNode.left = left.right;
        //把当前节点的值替换成左子节点的值
        value = left.value;
        //把当前节点的左子树替换成左子树的左子树
        left = left.left;
        //把当前节点的右子树指向刚才创建的新的节点
        right = newNode;
    }

双旋转

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

在这里插入图片描述

具体步骤：

  1. 在加入数据后判断左子树的左子树和右子树的高度，如果左子树高度高于右子树则右旋转，否则左旋转
  2. 在加入数据后判断右子树的左子树和右子树的高度，如果左子树高度高于右子树则右旋转，否则左旋转

代码实现

在添加的方法中加入以下代码就完成了双旋转操作

//当添加完一个节点后，如果右子树的高度比左子树的高度差大于1，则右旋转
        if((rightHeight()-leftHeight())>1){
            //判断右子树的左子树的高度大于右子树的高度  满足就先右旋转
            if(right!=null&&right.leftHeight()>right.leftHeight()){
                right.rightRotate();
            }
            leftRotate();//左旋转
            return;//终端下面的执行
        }
        //当添加完一个节点后，如果左子树的高度比右子树的高度差大于1，则右旋转
        if((leftHeight()-rightHeight())>1){
            //判断左子树的右子树的高度大于右子树的高度  满足就先左旋转
            if(left!=null&&left.rightHeight()>left.leftHeight()){
                left.leftRotate();
            }
            rightRotate();//右旋转
        }

完整代码

节点类

package com.datestructures.tree.AVLTree;

public class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    //添加节点的方法  递归的形式添加  需要满足二叉排序树的要求
    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{//添加的节点的值大于当前节点的值
            //如果当前节点右子节点为null  那么就挂在右子节点上
            if(this.right==null){
                this.right = node;
            }else {
                this.right.add(node);
            }
        }
        //当添加完一个节点后，如果右子树的高度比左子树的高度差大于1，则右旋转
        if((rightHeight()-leftHeight())>1){
            //判断右子树的左子树的高度大于右子树的高度  满足就先右旋转
            if(right!=null&&right.leftHeight()>right.leftHeight()){
                right.rightRotate();
            }
            leftRotate();//左旋转
            return;//终端下面的执行
        }
        //当添加完一个节点后，如果左子树的高度比右子树的高度差大于1，则右旋转
        if((leftHeight()-rightHeight())>1){
            //判断左子树的右子树的高度大于右子树的高度  满足就先左旋转
            if(left!=null&&left.rightHeight()>left.leftHeight()){
                left.leftRotate();
            }
            rightRotate();//右旋转
        }
    }
    /**
     * 查找要删除的节点
     * @param value 希望删除的节点的值
     * @return 如果找到返回该节点，否则返回null
     */
    public Node search(int value){
      if(value==this.value){//找到就是该节点
          return this;
      }else if(value<this.value){//如果查找的值小于当前节点，向左子树递归查找
          //如果左子节点为空
          if(this.left==null){
              return null;
          }
          return this.left.search(value);
      }else{//如果查找的值不小于当前节点，向右子树递归查找
         //如果右子树为空
          if(this.right==null){
              return null;
          }
          return this.right.search(value);
      }
    }

    /**
     * 查找要删除节点的父节点
     * @param value 要删除节点的值
     * @return 返回的是要删除节点的父节点  如果没有返回null
     */
    public Node searchParent(int value){
        //如果当前节点就是要删除节点的父节点就返回
        if((this.left!=null&&this.left.value==value)||this.right!=null&&this.right.value==value){
            return this;
        }else {
            //如果查找的值小于当前节点的值并且当前节点的左子节点不为空
            if(value<this.value&&this.left!=null){
                return this.left.searchParent(value);
            }else if(value>=this.value&&this.right!=null){
                return this.right.searchParent(value);
            }else {
                return null;//没有找到父节点
            }
        }
    }
    //返回左子树的高度
    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;
    }
    //左旋转的方法
    private void leftRotate(){
        //创建新的节点，以当前根节点的值创建的
        Node newNode = new Node(value);
        //把新的节点的左子树设置成当前节点的左子树
        newNode.left = left;
        //把新的节点的右子树设置成当前节点的右子树的左子树
        newNode.right = right.left;
        //把当前节点的值替换成右子节点的值
        value = right.value;
        //把当前节点的右子树替换成右子树的右子树
        right = right.right;
        //当前节点的左子树指向刚才创建的新的节点
        left = newNode;
    }
    //右旋转的方法
    private void rightRotate(){
        //创建新的节点，以当前根节点的值创建
        Node newNode = new Node(value);
        //把新的节点的右子树设置成当前节点的右子树
        newNode.right = right;
        //把新的节点的左子树设置成当前节点左子树的右子树
        newNode.left = left.right;
        //把当前节点的值替换成左子节点的值
        value = left.value;
        //把当前节点的左子树替换成左子树的左子树
        left = left.left;
        //把当前节点的右子树指向刚才创建的新的节点
        right = newNode;
    }
    //中序遍历
    public void infixOreder(){
        if(this.left!=null){
            this.left.infixOreder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixOreder();
        }
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                '}';
    }
}

平衡二叉树的实现类

package com.datestructures.tree.AVLTree;


public class AVLTree {
    private Node root;

    public Node getRoot() {
        return root;
    }

    //添加节点的方法
    public void add(Node node) {
        if (root == null) {
            //如果root为空 则让root指向node
            root = node;
        } else {
            root.add(node);
        }
    }

    //查找要删除的节点
    public Node search(int value) {
        if (root == null) {
            return null;
        } else {
            return root.search(value);
        }
    }

    //查找要删除节点的父节点
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        } else {
            return root.searchParent(value);
        }
    }

    //删除节点
    public void delNode(int value) {
        if (root == null) {
            return;
        } else {
            //1.需求先去找到要删除的节点 targetNode
            Node targetNode = search(value);
            if (targetNode == null) {//如果没有找到要删除的节点
                return;
            }
            //如果发现当前这棵二叉树只有一个节点
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            //2.找到要删除的节点的父节点 parentNode
            Node parentNode = searchParent(value);
            //如果要删除的节点时叶子结点
            if (targetNode.left == null & targetNode.right == null) {//要删除的节点没有左子树和右子树
                //判断targetNode是父节点的左子节点还是右子节点
                if (parentNode.left != null && parentNode.left.value == value) {
                    parentNode.left = null;//左子节点
                } else if (parentNode.right != null && parentNode.right.value == value) {
                    parentNode.right = null;//右子节点.
                }
            } else if (targetNode.left != null && targetNode.right != null) {//要删除的节点有左子树和右子树
                int minVal = delRightTreeMin(targetNode.right);
                targetNode.value = minVal;
            } else {//要删除的节点有一棵子树
                if (parentNode != null) {
                    //如果要删除的节点有左子节点
                    if (targetNode.left != null) {
                        if (parentNode.left.value == value) {//如果targetNode是parent的左子节点
                            parentNode.left = targetNode.left;
                        } else {//如果targetNode是parent的右子节点
                            parentNode.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else {
                    if (parentNode != null) {
                        if (parentNode.left.value == value) {//如果targetNode是parent的左子节点
                            parentNode.left = targetNode.right;
                        } else {//如果targetNode是parent的右子节点
                            parentNode.right = targetNode.right;
                        }
                    } else {
                        root = targetNode.right;
                    }
                }
            }
        }
    }

    /**
     * 1.返回最小值  2.删除以node为根节点的最小值的那个节点
     *
     * @param node 传入的节点   当做新的二叉排序树的根节点
     * @return 返回以node 为根节点的二叉排序树的最小节点的值
     */
    public int delRightTreeMin(Node node) {
        Node target = node;
        //循环的查找左节点，就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        //这时target就指向了最小值的节点
        delNode((target.value));
        return target.value;
    }

    //中序遍历
    public void infixOrder() {
        if (root != null) {
            root.infixOreder();
        } else {
            System.out.println("当前二叉排序树为空 不能遍历");
        }
    }
}

测试类

package com.datestructures.tree.AVLTree;

public class AVLTreeDemo {
    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};//左右旋转的问题数列  双旋转
        //创建一个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());
        System.out.println(avlTree.getRoot());
    }
}

http://www.kler.cn/a/18185.html

相关文章：

  • 软件工程概论项目(二)，node.js的配置，npm的使用与vue的安装
  • Vue 项目打包后环境变量丢失问题（清除缓存），区分.env和.env.*文件
  • mac终端使用pytest执行iOS UI自动化测试方法
  • vue3+element-plus==＞ el-form输入响应式失效踩坑!!!!!!!!!!
  • 【mySql 语句使用】
  • 重构代码之内联临时变量
  • C++知识点 -- 特殊类设计
  • 【Java】面试常问知识点（Java基础—2）
  • Word下划线怎么打？速速get这5个实用方法！
  • 将webrtc的音频模式改为共享模式
  • SEO优化新手必须掌握的10个技巧和工具
  • 点成分享丨细胞培养三步骤——复苏、传代、冻存
  • Java并发编程实践学习笔记（三）——共享对象之可见性
  • Dart语法下
  • 基于springboot的私人健身与教练预约管理系统
  • 散列查找实验（开散列） 题目编号:583
  • Python小姿势 - # Python相关技术知识点
  • 右值引用和移动构造函数
  • 网络机顶盒哪个牌子好？资深数码粉分享网络电视机顶盒排名
  • WRF模式
  • 如何建设智慧档案馆
  • 【Leetcode 161】【GO】相隔为 1 的编辑距离
  • @Async异步线程：Spring 自带的异步解决方案
  • 同步辐射散射数据处理：从测量到分析的全流程解析
  • Ubuntu18.04系统及相关软件安装恢复过程
  • MG100-Hi3798MV100-当贝纯净桌面卡刷固件包