Python算法——平衡二叉树(AVL)
Python中的平衡二叉搜索树(AVL树)算法详解
平衡二叉搜索树(AVL树)是一种自平衡的二叉搜索树,它通过在插入或删除节点时进行旋转操作来保持树的平衡性。在AVL树中,任何节点的两个子树的高度差(平衡因子)最多为1。这种平衡性质确保了AVL树的高度始终是对数级别,使得查找、插入和删除等操作的时间复杂度保持在O(log n)。在本文中,我们将深入讨论AVL树的原理,并提供Python代码实现。
AVL树的节点定义
首先,我们定义AVL树的节点类:
class AVLNode:def __init__(self, key):self.key = keyself.height = 1self.left = Noneself.right = None
AVL树的节点除了包含值之外,还记录了节点的高度。这个高度信息是维持平衡的关键。
插入操作
插入操作是在AVL树中插入新节点的过程,同时需要保持树的平衡。插入后,我们需要更新节点的高度,并进行旋转操作来恢复平衡。
def insert(root, key):if root is None:return AVLNode(key)if key < root.key:root.left = insert(root.left, key)elif key > root.key:root.right = insert(root.right, key)# 更新节点的高度root.height = 1 + max(get_height(root.left), get_height(root.right))# 获取平衡因子balance = get_balance(root)# 进行旋转操作来恢复平衡# 左旋if balance > 1 and key < root.left.key:return rotate_right(root)# 右旋if balance < -1 and key > root.right.key:return rotate_left(root)# 左右双旋if balance > 1 and key > root.left.key:root.left = rotate_left(root.left)return rotate_right(root)# 右左双旋if balance < -1 and key < root.right.key:root.right = rotate_right(root.right)return rotate_left(root)return root
删除操作
删除操作是在AVL树中删除节点的过程,同时需要保持树的平衡。删除后,我们需要更新节点的高度,并进行旋转操作来恢复平衡。
def delete(root, key):if root is None:return rootif key < root.key:root.left = delete(root.left, key)elif key > root.key:root.right = delete(root.right, key)else:# 节点有一个或没有子节点if root.left is None:return root.rightelif root.right is None:return root.left# 节点有两个子节点,找到右子树的最小节点root.key = find_min(root.right).key# 删除右子树的最小节点root.right = delete(root.right, root.key)# 更新节点的高度root.height = 1 + max(get_height(root.left), get_height(root.right))# 获取平衡因子balance = get_balance(root)# 进行旋转操作来恢复平衡# 左旋if balance > 1 and get_balance(root.left) >= 0:return rotate_right(root)# 右旋if balance < -1 and get_balance(root.right) <= 0:return rotate_left(root)# 左右双旋if balance > 1 and get_balance(root.left) < 0:root.left = rotate_left(root.left)return rotate_right(root)# 右左双旋if balance < -1 and get_balance(root.right) > 0:root.right = rotate_right(root.right)return rotate_left(root)return root
辅助函数
为了实现插入和删除操作,我们需要一些辅助函数:
def get_height(node):if node is None:return 0return node.heightdef get_balance(node):if node is None:return 0return get_height(node.left) - get_height(node.right)def rotate_left(z):y = z.rightT2 = y.left# 执行左旋y.left = zz.right = T2# 更新节点的高度z.height = 1 + max(get_height(z.left), get_height(z.right))y.height = 1 + max(get_height(y.left), get_height(y.right))return ydef rotate_right(y):x = y.leftT2 = x.right# 执行右旋x.right = yy.left = T2# 更新节点的高度y.height = 1 + max(get_height(y.left), get_height(y.right))x.height = 1 + max(get_height(x.left), get_height(x.right))return x
示例
创建一个AVL树并演示插入和删除操作:
# 创建空树
avl_root = None# 插入操作
keys_to_insert = [50, 30, 70, 20, 40, 60, 80]
for key in keys_to_insert:avl_root = insert(avl_root, key)# 中序遍历查看结果
def inorder_traversal_avl(root):if root is not None:inorder_traversal_avl(root.left)print(f"({root.key}, {get_balance(root)})", end=" ")inorder_traversal_avl(root.right)print("中序遍历结果:", end=" ")
inorder_traversal_avl(avl_root)# 删除操作
delete_key = 30
avl_root = delete(avl_root, delete_key)print("\n删除节点 30 后中序遍历结果:", end=" ")
inorder_traversal_avl(avl_root)
输出结果:
中序遍历结果: (20, 1) (30, 0) (40, 0) (50, -1) (60, 0) (70, 0) (80, 0)
删除节点 30 后中序遍历结果: (20, 1) (40, 0) (50, 0) (60, 0) (70, 0) (80, 0)
这表示插入和删除操作都能够保持AVL树的平衡。AVL树通过自平衡的方式,保证了树的高度始终是对数级别,使得查找、插入和删除等操作的时间复杂度保持在O(log n)。通过理解其原理和实现,您将能够更好地应用AVL树解决实际问题。
相关文章:
Python算法——平衡二叉树(AVL)
Python中的平衡二叉搜索树(AVL树)算法详解 平衡二叉搜索树(AVL树)是一种自平衡的二叉搜索树,它通过在插入或删除节点时进行旋转操作来保持树的平衡性。在AVL树中,任何节点的两个子树的高度差(平…...
公开可用的API 合集
这是一个开源项目列表,收录了一些公开可用、无需注册或认证即可使用的API接口。 这个项目解决了开发者们在寻找合适的API时遇到的各种困难,如无法快速定位、难以筛选等问题,为他们提供了便捷的一站式查询服务。 项目是“public-apis”&…...
单片机编程原则
多任务编程的概念 方式一:实时操作系统(不建议新手使用) 方式二 :裸机多任务模型 逻辑多任务的基本原理 把三个任务分别分为一个一个的片段 然后先执行任务一的第一个切片 执行第二个任务的第一个片段 执行第三个任务的第一个片…...
开源短剧付费变现小程序源码系统+在线开通会员+在线充值 带完整的搭建教程
说起微短剧,相信大家都不会陌生。相比传统网剧冗长的剧情,微短剧最大的看点,是时长短、高浓缩,顺应了当下用户娱乐时间碎片化趋势。其故事题材多为赘婿、霸道总裁、穿越、重生等看似夸张、无厘头,但却非常“上头”的虚…...
基于Python机器学习、深度学习技术提升气象、海洋、水文领域实践应用能力
Python是功能强大、免费、开源,实现面向对象的编程语言,能够在不同操作系统和平台使用,简洁的语法和解释性语言使其成为理想的脚本语言。除了标准库,还有丰富的第三方库,Python在数据处理、科学计算、数学建模、数据挖…...
电商平台为什么需要及时部署ssl证书?
电商平台为什么需要及时部署ssl证书? 21世纪以来,互联网技术得到了快速的发展和应用上的普及,为生活、工作、学习都带来了巨大的变化。现代社会中,快节奏的生活让人们的购物方式也发生了极大的转变,逐渐由线下转为了线…...
卡码网语言基础课 | 12. 位置互换
通过本次练习,将要学习到以下C知识点: 位置互换交换变量字符串 题目:给定一个长度为偶数位的字符串,请编程实现字符串的奇偶位互换。 奇偶位互换是指字符串的奇数位和偶数位相互交换位置 即:第一位和第二位交换&…...
用DOM来读取XML时要注意的一些概念
2023年11月15日,周三下午 在 DOM(文档对象模型)中,有一些重要的概念和术语: 文档对象(Document Object):表示整个 XML 文档的根节点,它是 DOM 树的入口点。元素节点&…...
openresty安装配置,执行shell脚本
下载并解压 OpenResty 源代码: bashCopy code wget https://openresty.org/download/openresty-1.19.9.1.tar.gz tar -zxvf openresty-1.19.9.1.tar.gz cd openresty-1.19.9.1 运行 ./configure 并指定安装路径: bashCopy code ./configure --prefix…...
解决Dockerfile中 Could not initialize class sun.awt.X11FontManager错误
Dockerfile中增加命令 RUN yum install dejavu-sans-fonts fontconfig -y如果您使用的是基于Alpine Linux的发行版,可以使用apk命令来安装DejaVu Sans字体和fontconfig工具 RUN apk update RUN apk add ttf-dejavu fontconfig...
Kubernetes(k8s)进阶
文章目录 Kubernetes进阶一、Namespace(名称空间)1.namespace介绍2.管理namespace查看namespace创建namespaceyaml文件配置namespace 二、Pod(最小基本部署单元)1.pod介绍2.管理pod创建并运行pod查看pod信息访问pod删除podyaml文件…...
[Vue 配置] Vite + Vue3 项目配置和使用 NProgress
文章归档:https://www.yuque.com/u27599042/coding_star/mfmsrf9tz98ox3qg 安装 pnpm i nprogress配置 NProgress 其他更多可参考,仓库地址:https://github.com/rstacruz/nprogress 在 src/config/nprogress.js 中进行配置 是否展示右上角圆…...
Android MQTT开发之 Hivemq MQTT Client
使用一个开源库:hivemq-mqtt-client,这是Java生态的一个MQTT客户端框架,需要Java 8,Android上使用的话问题不大,需要一些额外的配置,下面列出了相关的配置,尤其是 packagingOptions,…...
【Maven教程】(十一):使用 Maven 构建 Web应用 —— 使用 jetty-maven-plugin 进行测试、使用 Cargo 实现自动化部署~
Maven 使用 Maven 构建 Web应用 1️⃣ Web 项目的目录结构2️⃣ account-service2.1 account-service的 POM2.2 account-service 的主代码 3️⃣ account-web3.1 account-web 的POM3.2 account-web 的主代码 4️⃣ 使用 jetty-maven-plugin 进行测试5️⃣ 使用 Cargo 实现自动…...
番外 2 : LoadRunner 的安装以及配置
LoadRunner 的安装以及配置教程 一 . 配置 IE 浏览器二 . 安装 LoadRunner 工具三 . 修改默认浏览器的配置四 . 设置 LoadRunner 能够获取本地资源 Hello , 大家好 , 又给大家带来新的专栏喽 ~ 这个专栏是专门为零基础小白从 0 到 1 了解软件测试基础理论设计的 , 虽然还不足以…...
win10正确配置tensorRT环境
目的 使用tensorRT进行网络模型部署,加快推理速度 方法 安装tensorRT的过程需要对各种组件的版本进行匹配 前置安装套件有: 1、CUDA 2、cuDNN 3、pyCUDA 4、tensorflow或pytorch 主要记录tensorRT安装: tensorRT安装配置查询 步骤: 1、去tensorRT官网…...
C++初阶-模板初阶
模板初阶 一、泛型编程二、函数模板2.1函数模板概念2.2函数模板格式2.3函数模板的原理2.4函数模板的原理2.5模板参数的匹配原则 三、类模板3.1类模板的定义格式3.2类模板的实例化 一、泛型编程 如何实现一个通用的交换函数呢? void Swap(int& left, int& …...
基于Python实现汽车销售数据可视化【500010086】
导入模块 import numpy as np import pandas as pd import plotly.graph_objects as go import plotly.express as px获取数据 df1 pd.read_excel(r"./data/中国汽车总体销量.xlsx") print(df1.head(5))df1.info()df1[年份] df1[时间].dt.year df1[月份] df1[时…...
dist.init_process_group() 卡住超时导致报错
在跑模型是遇到一个问题: import torch.distributed as dist dist.init_process_group(backend"nccl", init_methodtcp://localhost:%d % tcp_port, ranklocal_rank, world_sizenum_gpus)程序卡在这一步一动不动。. 解决办法一: 我看网上有人…...
RESTFul API:真是让人又爱又恨
RESTFul API是一种广泛使用的Web服务设计风格,它以资源为中心,通过HTTP方法来操作这些资源。然而,尽管RESTFul架构风格在许多情况下都非常有用,但在实际应用中,我们也发现了一些不足之处。本文将详细阐述这些问题&…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
大型活动交通拥堵治理的视觉算法应用
大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动(如演唱会、马拉松赛事、高考中考等)期间,城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例,暖城商圈曾因观众集中离场导致周边…...
visual studio 2022更改主题为深色
visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中,选择 环境 -> 常规 ,将其中的颜色主题改成深色 点击确定,更改完成...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
