当前位置: 首页 > news >正文

Java手写AVL树

Java手写AVL树

1. AVL树实现思路原理

为了解释AVL树的实现思路原理,下面使用Mermanid代码表示该算法的思维导图:

AVL树
平衡因子
左子树
右子树
左子树高度
右子树高度
平衡因子计算
BF = 左子树高度 - 右子树高度
左子树的左子树高度
左子树的右子树高度
右子树的左子树高度
右子树的右子树高度
平衡调整
左旋转
右旋转
左子树变为根节点
原根节点变为右子节点
右子树变根节点
原根节点变左子节点

2. AVL树的手写必要性

手写AVL树的必要性主要体现在以下几个方面:

  1. 深入理解AVL树的原理和实现过程,加深对数据结构和算法的理解。
  2. 学习如何进行平衡二叉树的插入、删除和查找操作。
  3. 实际应用中可能需要自定义平衡二叉树的数据结构,手写AVL树可以满足特定需求。

3. AVL树的市场调查

市场调查显示,AVL树在各种领域都有广泛的应用。特别是在需要高效插入、删除和查找操作的场景下,AVL树具有较好的性能表现。常见的应用领域包括数据库索引、网络路由算法、编译器优化等。

4. AVL树的实现详细介绍和步骤

步骤1:定义AVL树的节点结构

首先,我们需要定义AVL树的节点结构,包括节点值、左子节点、右子节点、平衡因子等属性。

class AVLNode {int value;AVLNode left;AVLNode right;int balanceFactor;public AVLNode(int value) {this.value = value;this.left = null;this.right = null;this.balanceFactor = 0;}
}

步骤2:实现AVL树的插入操作

AVL树的插入操作是对二叉搜索树的插入操作进行了平衡调整。具体步骤如下:

  1. 在二叉搜索树中插入新节点。
  2. 更新插入路径上各节点的平衡因子。
  3. 如果某个节点的平衡因子绝对值大于1,则进行相应的平衡调整。
class AVLTree {private AVLNode root;// 插入节点public void insert(int value) {root = insertNode(root, value);}// 插入节点辅助函数private AVLNode insertNode(AVLNode node, int value) {if (node == null) {return new AVLNode(value);}if (value < node.value) {node.left = insertNode(node.left, value);} else if (value > node.value) {node.right = insertNode(node.right, value);} else {return node; // 值已存在,不插入}// 更新平衡因子node.balanceFactor = Math.max(getHeight(node.left), getHeight(node.right)) + 1;// 平衡调整int balance = getBalanceFactor(node);if (balance > 1 && value < node.left.value) {return rightRotate(node);}if (balance < -1 && value > node.right.value) {return leftRotate(node);}if (balance > 1 && value > node.left.value) {node.left = leftRotate(node.left);return rightRotate(node);}if (balance < -1 && value < node.right.value) {node.right = rightRotate(node.right);return leftRotate(node);}return node;}// 获取节点高度private int getHeight(AVLNode node) {if (node == null) {return 0;}return Math.max(getHeight(node.left), getHeight(node.right)) + 1;}// 获取节点的平衡因子private int getBalanceFactor(AVLNode node) {if (node == null) {return 0;}return getHeight(node.left) - getHeight(node.right);}// 左旋转private AVLNode leftRotate(AVLNode node) {AVLNode rightChild = node.right;AVLNode leftGrandChild = rightChild.left;rightChild.left = node;node.right = leftGrandChild;node.balanceFactor = Math.max(getHeight(node.left), getHeight(node.right)) + 1;rightChild.balanceFactor = Math.max(getHeight(rightChild.left), getHeight(rightChild.right)) + 1;return rightChild;}// 右旋转private AVLNode rightRotate(AVLNode node) {AVLNode leftChild = node.left;AVLNode rightGrandChild = leftChild.right;leftChild.right = node;node.left = rightGrandChild;node.balanceFactor = Math.max(getHeight(node.left), getHeight(node.right)) + 1;leftChild.balanceFactor = Math.max(getHeight(leftChild.left), getHeight(leftChild.right)) + 1;return leftChild;}
}

步骤3:实现AVL树的删除操作

AVL树的删除操作也是对二叉搜索树的删除操作进行了平衡调整。具体步骤如下:

  1. 在二叉搜索树中删除目标节点。
  2. 更新删除路径上各节点的平衡因子。
  3. 如果某个节点的平衡因子绝对值大于1,则进行相应的平衡调整。
class AVLTree {// ...// 删除节点public void delete(int value) {root = deleteNode(root, value);}// 删除节点辅助函数private AVLNode deleteNode(AVLNode node, int value) {if (node == null) {return null;}if (value < node.value) {node.left = deleteNode(node.left, value);} else if (value > node.value) {node.right = deleteNode(node.right, value);} else {if (node.left == null || node.right == null) {node = (node.left != null) ? node.left :node.right;} else {AVLNode minNode = findMin(node.right);node.value = minNode.value;node.right = deleteNode(node.right, minNode.value);}}if (node == null) {return null;}// 更新平衡因子node.balanceFactor = Math.max(getHeight(node.left), getHeight(node.right)) + 1;// 平衡调整int balance = getBalanceFactor(node);if (balance > 1 && getBalanceFactor(node.left) >= 0) {return rightRotate(node);}if (balance > 1 && getBalanceFactor(node.left) < 0) {node.left = leftRotate(node.left);return rightRotate(node);}if (balance < -1 && getBalanceFactor(node.right) <= 0) {return leftRotate(node);}if (balance < -1 && getBalanceFactor(node.right) > 0) {node.right = rightRotate(node.right);return leftRotate(node);}return node;}// 查找最小节点private AVLNode findMin(AVLNode node) {while (node.left != null) {node = node.left;}return node;}
}

步骤4:实现AVL树的查找操作

AVL树的查找操作与二叉搜索树的查找操作相同,不需要进行平衡调整。

class AVLTree {// ...// 查找节点public boolean search(int value) {return searchNode(root, value);}// 查找节点辅助函数private boolean searchNode(AVLNode node, int value) {if (node == null) {return false;}if (value < node.value) {return searchNode(node.left, value);} else if (value > node.value) {return searchNode(node.right, value);} else {return true;}}
}

步骤5:测试AVL树的各个操作

public class Main {public static void main(String[] args) {AVLTree tree = new AVLTree();tree.insert(10);tree.insert(20);tree.insert(30);tree.insert(40);tree.insert(50);tree.insert(25);System.out.println("AVL树是否包含值30:" + tree.search(30)); // 输出:truetree.delete(30);System.out.println("AVL树是否包含值30:" + tree.search(30)); // 输出:false}
}

相关文章:

Java手写AVL树

Java手写AVL树 1. AVL树实现思路原理 为了解释AVL树的实现思路原理&#xff0c;下面使用Mermanid代码表示该算法的思维导图&#xff1a; #mermaid-svg-ycH8kKpzVk2HWEby {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid…...

运维自动化:提高效率的秘诀

&#x1f337;&#x1f341; 博主猫头虎&#xff08;&#x1f405;&#x1f43e;&#xff09;带您 Go to New World✨&#x1f341; &#x1f984; 博客首页——&#x1f405;&#x1f43e;猫头虎的博客&#x1f390; &#x1f433; 《面试题大全专栏》 &#x1f995; 文章图文…...

C++设计模式_05_Observer 观察者模式

接上篇&#xff0c;本篇将会介绍C设计模式中的Observer 观察者模式&#xff0c;和前2篇模板方法Template Method及Strategy 策略模式一样&#xff0c;仍属于“组件协作”模式。Observer 在某些领域也叫做 Event 。 文章目录 1. 动机&#xff08; Motivation&#xff09;2. 代码…...

github网站打不开,hosts文件配置

首先获取github官网的ip地址&#xff0c; 打开cmd&#xff0c;输入ping github.com 配置&#xff1a; #github 140.82.114.4 github.com 199.232.69.194 github.global.ssl.fastly.net 185.199.108.153 assets-cdn.github.com 185.199.110.153 assets-cdn.github.com 185.199…...

总结PCB设计的经验

一般PCB基本设计流程如下&#xff1a;前期准备->PCB结构设计->PCB布局->布线->布线优化和丝印->网络和DRC检查和结构检查->制版。: :   第一&#xff1a;前期准备。这包括准备元件库和原理图。“工欲善其事&#xff0c;必先利其器”&#xff0c;要做出一…...

HCIE-HCS规划设计搭建

1、相关术语 1、等价路由 等价路由&#xff08;Equal-cost routing&#xff09;是一种网络路由策略&#xff0c;用于在网络中选择多个具有相同路由度量&#xff08;路由距离或成本&#xff09;的最佳路径之一来转发数据流量。 当存在多个路径具有相同的路由度量时&#xff0c;…...

c语言输出杨辉三角

#include<stdio.h> int main() {int x 0; //表示杨辉三角的的大小int y 1;printf("请输入x的值: ");scanf("%d", &x);for (int i 0; i < x; i) {for (int j 0; j < i; j) {if (j 0 || i 0) {y 1;}else {y y * (i - j 1) / j;}pri…...

性能测试-持续测试及性能测试建设(22)

什么是持续测试? 持续测试定义为:在软件交付流水线中执行自动化测试的过程,目的是获得关于预发布软件业务风险的即时反馈。 完成持续测试,我们还是需要回到定义中,它有3个关键词:软件交付流水线、自动化测试、即时反馈。 首先,持续测试需要具备一条完整的流水线,其代表…...

嵌入式C 语言中的三块技术难点

​ C 语言在嵌入式学习中是必备的知识&#xff0c;甚至大部分操作系统都要围绕 C 语言进行&#xff0c;而其中有三块技术难点&#xff0c;几乎是公认级别的“难啃的硬骨头”。 今天就来带你将这三块硬骨头细细拆解开来&#xff0c;一定让你看明白了。 0x01 指针 指针是公认…...

【斗破年番】紫研新形象,萧炎终成翻海印,救援月媚,三宗决战

Hello,小伙伴们&#xff0c;我是小郑继续为大家深度解析斗破年番。 斗破苍穹年番动画更新了&#xff0c;小医仙帅气回归&#xff0c;萧炎紫妍成功进入山谷闭关苦修&#xff0c;美杜莎女王守护没多久&#xff0c;就因蛇人族求救离开。从官方公布的最新预告来看&#xff0c;萧炎紫…...

差分方程模型:国民总收入(GDP)的乘数-加速数模型

【背景知识-凯恩斯经济增长模型】 凯恩斯(John M.Keynes)建立了著名的国民经济增长模型。令Y表示国民总收入&#xff0c;C表示总消费&#xff0c;E为总支出&#xff0c;I表示投资&#xff0c;G为政府的投入&#xff08;如基建等&#xff09;。那么有 【6.1】 其中&#xff0…...

【C语言】指针和数组笔试题解析(1)

指针是C语言的灵魂&#xff0c;他的玩法多种多样&#xff0c;这篇文章带来指针的笔试题详解&#xff0c;可以帮助我们更好的理解与巩固指针的知识 目录 预备知识&#xff1a;题目&#xff1a;一维数组&#xff1a;二维数组&#xff1a; 题目比较多&#xff0c;但切记戒骄戒躁&a…...

Vue中组件的三种注册方式

组件的注册 1.全局注册&#xff1a; 在全局注册中&#xff0c;你需要确保在 Vue 根实例之前导入并注册组件。通常&#xff0c;你会在入口文件&#xff08;例如 main.js&#xff09;中执行这些操作。 // main.jsimport Vue from vue; import App from ./App.vue;// 导入全局组…...

docker 和k8s 入门

docker 和k8s 入门 本文是云原生的学习记录&#xff0c;可以参考以下文档 k8s https://www.yuque.com/leifengyang/oncloud 相关视频教程可参考如下 https://www.bilibili.com/video/BV13Q4y1C7hS?p2&vd_source0882f549dac54045384d4a921596e234 相对于公有云&#x…...

基于Yolov8的交通标志牌(TT100K)识别检测系统

1.Yolov8介绍 Ultralytics YOLOv8是Ultralytics公司开发的YOLO目标检测和图像分割模型的最新版本。YOLOv8是一种尖端的、最先进的&#xff08;SOTA&#xff09;模型&#xff0c;它建立在先前YOLO成功基础上&#xff0c;并引入了新功能和改进&#xff0c;以进一步提升性能和灵活…...

使用Python编写一个多线程的12306抢票程序

国庆长假即将到来&#xff0c;大家纷纷计划着自己的旅行行程。然而&#xff0c;对于很多人来说&#xff0c;抢购火车票人们成了一个令人头疼的问题。12306网站的服务器经常因为流量高而崩溃&#xff0c;导致抢票变得越来越严重异常困难。 首先&#xff0c;让我们来了解一下1230…...

DT Paint Effects工具(三)

管 分支 使用细枝 叶 力 使用湍流 流动画 渲染全局参数 建造盆栽植物...

SpringBoot整合Mybatis

目录 &#xff08;1&#xff09;引入依赖 &#xff08;2&#xff09;编写Mapper接口 &#xff08;3&#xff09;编写Mapper映射文件 &#xff08;4&#xff09;编写yml配置文件 &#xff08;5&#xff09;编写测试类 &#xff08;1&#xff09;引入依赖 <dependency>…...

Java后端使用POST请求向mysql中插入Json数据的问题

1.后端请求正常 但数据表中value没有值 原因 json数据属性不符合spring解析格式&#xff0c;json属性名称的大写字母不符合spring要求 以下为为错误示范 1 Test 以大写字母开头&#xff0c; 2 tTest 小写字母开头&#xff0c;但是第二个字母是大写解决方案 实体类属性加上Jso…...

豆瓣图书评分数据的可视化分析

导语 豆瓣是一个提供图书、电影、音乐等文化产品的社区平台&#xff0c;用户可以在上面发表自己的评价和评论&#xff0c;形成一个丰富的文化数据库。本文将介绍如何使用爬虫技术获取豆瓣图书的评分数据&#xff0c;并进行可视化分析&#xff0c;探索不同类型、不同年代、不同…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

LangChain 中的文档加载器(Loader)与文本切分器(Splitter)详解《二》

&#x1f9e0; LangChain 中 TextSplitter 的使用详解&#xff1a;从基础到进阶&#xff08;附代码&#xff09; 一、前言 在处理大规模文本数据时&#xff0c;特别是在构建知识库或进行大模型训练与推理时&#xff0c;文本切分&#xff08;Text Splitting&#xff09; 是一个…...

Python常用模块:time、os、shutil与flask初探

一、Flask初探 & PyCharm终端配置 目的: 快速搭建小型Web服务器以提供数据。 工具: 第三方Web框架 Flask (需 pip install flask 安装)。 安装 Flask: 建议: 使用 PyCharm 内置的 Terminal (模拟命令行) 进行安装,避免频繁切换。 PyCharm Terminal 配置建议: 打开 Py…...

Redis上篇--知识点总结

Redis上篇–解析 本文大部分知识整理自网上&#xff0c;在正文结束后都会附上参考地址。如果想要深入或者详细学习可以通过文末链接跳转学习。 1. 基本介绍 Redis 是一个开源的、高性能的 内存键值数据库&#xff0c;Redis 的键值对中的 key 就是字符串对象&#xff0c;而 val…...

从0开始学习R语言--Day17--Cox回归

Cox回归 在用医疗数据作分析时&#xff0c;最常见的是去预测某类病的患者的死亡率或预测他们的结局。但是我们得到的病人数据&#xff0c;往往会有很多的协变量&#xff0c;即使我们通过计算来减少指标对结果的影响&#xff0c;我们的数据中依然会有很多的协变量&#xff0c;且…...

关于疲劳分析的各种方法

疲劳寿命预测方法很多。按疲劳裂纹形成寿命预测的基本假定和控制参数&#xff0c;可分为名义应力法、局部应力一应变法、能量法、场强法等。 1名义应力法 名义应力法是以结构的名义应力为试验和寿命估算的基础&#xff0c;采用雨流法取出一个个相互独立、互不相关的应力循环&…...

开源 vGPU 方案:HAMi,实现细粒度 GPU 切分

本文主要分享一个开源的 GPU 虚拟化方案&#xff1a;HAMi&#xff0c;包括如何安装、配置以及使用。 相比于上一篇分享的 TimeSlicing 方案&#xff0c;HAMi 除了 GPU 共享之外还可以实现 GPU core、memory 得限制&#xff0c;保证共享同一 GPU 的各个 Pod 都能拿到足够的资源。…...

暴雨新专利解决服务器噪音与性能悖论

6月1日&#xff0c;我国首部数据中心绿色化评价方面国家标准《绿色数据中心评价》正式实施&#xff0c;为我国数据中心的绿色低碳建设提供了明确指引。《评价》首次将噪音控制纳入国家级绿色评价体系&#xff0c;要求从设计隔声结构到运维定期监测实现闭环管控&#xff0c;加速…...