Python | Leetcode Python题解之第230题二叉搜索树中第K小的元素
题目:
题解:
class AVL:"""平衡二叉搜索树(AVL树):允许重复值"""class Node:"""平衡二叉搜索树结点"""__slots__ = ("val", "parent", "left", "right", "size", "height")def __init__(self, val, parent=None, left=None, right=None):self.val = valself.parent = parentself.left = leftself.right = rightself.height = 0 # 结点高度:以node为根节点的子树的高度(高度定义:叶结点的高度是0)self.size = 1 # 结点元素数:以node为根节点的子树的节点总数def __init__(self, vals):self.root = self._build(vals, 0, len(vals) - 1, None) if vals else Nonedef _build(self, vals, l, r, parent):"""根据vals[l:r]构造平衡二叉搜索树 -> 返回根结点"""m = (l + r) // 2node = self.Node(vals[m], parent=parent)if l <= m - 1:node.left = self._build(vals, l, m - 1, parent=node)if m + 1 <= r:node.right = self._build(vals, m + 1, r, parent=node)self._recompute(node)return nodedef kth_smallest(self, k: int) -> int:"""返回二叉搜索树中第k小的元素"""node = self.rootwhile node:left = self._get_size(node.left)if left < k - 1:node = node.rightk -= left + 1elif left == k - 1:return node.valelse:node = node.leftdef insert(self, v):"""插入值为v的新结点"""if self.root is None:self.root = self.Node(v)else:# 计算新结点的添加位置node = self._subtree_search(self.root, v)is_add_left = (v <= node.val) # 是否将新结点添加到node的左子结点if node.val == v: # 如果值为v的结点已存在if node.left: # 值为v的结点存在左子结点,则添加到其左子树的最右侧node = self._subtree_last(node.left)is_add_left = Falseelse: # 值为v的结点不存在左子结点,则添加到其左子结点is_add_left = True# 添加新结点leaf = self.Node(v, parent=node)if is_add_left:node.left = leafelse:node.right = leafself._rebalance(leaf)def delete(self, v) -> bool:"""删除值为v的结点 -> 返回是否成功删除结点"""if self.root is None:return Falsenode = self._subtree_search(self.root, v)if node.val != v: # 没有找到需要删除的结点return False# 处理当前结点既有左子树也有右子树的情况# 若左子树比右子树高度低,则将当前结点替换为右子树最左侧的结点,并移除右子树最左侧的结点# 若右子树比左子树高度低,则将当前结点替换为左子树最右侧的结点,并移除左子树最右侧的结点if node.left and node.right:if node.left.height <= node.right.height:replacement = self._subtree_first(node.right)else:replacement = self._subtree_last(node.left)node.val = replacement.valnode = replacementparent = node.parentself._delete(node)self._rebalance(parent)return Truedef _delete(self, node):"""删除结点p并用它的子结点代替它,结点p至多只能有1个子结点"""if node.left and node.right:raise ValueError('node has two children')child = node.left if node.left else node.rightif child is not None:child.parent = node.parentif node is self.root:self.root = childelse:parent = node.parentif node is parent.left:parent.left = childelse:parent.right = childnode.parent = nodedef _subtree_search(self, node, v):"""在以node为根结点的子树中搜索值为v的结点,如果没有值为v的结点,则返回值为v的结点应该在的位置的父结点"""if node.val < v and node.right is not None:return self._subtree_search(node.right, v)elif node.val > v and node.left is not None:return self._subtree_search(node.left, v)else:return nodedef _recompute(self, node):"""重新计算node结点的高度和元素数"""node.height = 1 + max(self._get_height(node.left), self._get_height(node.right))node.size = 1 + self._get_size(node.left) + self._get_size(node.right)def _rebalance(self, node):"""从node结点开始(含node结点)逐个向上重新平衡二叉树,并更新结点高度和元素数"""while node is not None:old_height, old_size = node.height, node.sizeif not self._is_balanced(node):node = self._restructure(self._tall_grandchild(node))self._recompute(node.left)self._recompute(node.right)self._recompute(node)if node.height == old_height and node.size == old_size:node = None # 如果结点高度和元素数都没有变化则不需要再继续向上调整else:node = node.parentdef _is_balanced(self, node):"""判断node结点是否平衡"""return abs(self._get_height(node.left) - self._get_height(node.right)) <= 1def _tall_child(self, node):"""获取node结点更高的子树"""if self._get_height(node.left) > self._get_height(node.right):return node.leftelse:return node.rightdef _tall_grandchild(self, node):"""获取node结点更高的子树中的更高的子树"""child = self._tall_child(node)return self._tall_child(child)@staticmethoddef _relink(parent, child, is_left):"""重新连接父结点和子结点(子结点允许为空)"""if is_left:parent.left = childelse:parent.right = childif child is not None:child.parent = parentdef _rotate(self, node):"""旋转操作"""parent = node.parentgrandparent = parent.parentif grandparent is None:self.root = nodenode.parent = Noneelse:self._relink(grandparent, node, parent == grandparent.left)if node == parent.left:self._relink(parent, node.right, True)self._relink(node, parent, False)else:self._relink(parent, node.left, False)self._relink(node, parent, True)def _restructure(self, node):"""trinode操作"""parent = node.parentgrandparent = parent.parentif (node == parent.right) == (parent == grandparent.right): # 处理需要一次旋转的情况self._rotate(parent)return parentelse: # 处理需要两次旋转的情况:第1次旋转后即成为需要一次旋转的情况self._rotate(node)self._rotate(node)return node@staticmethoddef _subtree_first(node):"""返回以node为根结点的子树的第1个元素"""while node.left is not None:node = node.leftreturn node@staticmethoddef _subtree_last(node):"""返回以node为根结点的子树的最后1个元素"""while node.right is not None:node = node.rightreturn node@staticmethoddef _get_height(node) -> int:"""获取以node为根结点的子树的高度"""return node.height if node is not None else 0@staticmethoddef _get_size(node) -> int:"""获取以node为根结点的子树的结点数"""return node.size if node is not None else 0class Solution:def kthSmallest(self, root: TreeNode, k: int) -> int:def inorder(node):if node.left:inorder(node.left)inorder_lst.append(node.val)if node.right:inorder(node.right)# 中序遍历生成数值列表inorder_lst = []inorder(root)# 构造平衡二叉搜索树avl = AVL(inorder_lst)# 模拟1000次插入和删除操作random_nums = [random.randint(0, 10001) for _ in range(1000)]for num in random_nums:avl.insert(num)random.shuffle(random_nums) # 列表乱序for num in random_nums:avl.delete(num)return avl.kth_smallest(k)
相关文章:

Python | Leetcode Python题解之第230题二叉搜索树中第K小的元素
题目: 题解: class AVL:"""平衡二叉搜索树(AVL树):允许重复值"""class Node:"""平衡二叉搜索树结点"""__slots__ ("val", "parent&quo…...

Python酷库之旅-第三方库Pandas(018)
目录 一、用法精讲 44、pandas.crosstab函数 44-1、语法 44-2、参数 44-3、功能 44-4、返回值 44-5、说明 44-6、用法 44-6-1、数据准备 44-6-2、代码示例 44-6-3、结果输出 45、pandas.cut函数 45-1、语法 45-2、参数 45-3、功能 45-4、返回值 45-5、说明 4…...

九科bit-Worker RPA 内容学习
入门阶段, 花时间学习和记忆细枝末节,可能会反而分散新手去理解核心逻辑的精力,并且不常用的知识也很容易被遗忘。 简介: 什么是RPA? RPA(Robotic Process Automation,机器人流程自动化&#x…...

vscode编译环境配置-golang
1. 支持跳转 如果单测函数上方不显示run test | debug test,需要安装Code Debugger(因为以前的go Test Explorer不再被维护了) 2. 单测 指定单个用例测试 go test -v run TestXXXdlv 调试 需要安装匹配的go版本和delve版本(如…...

【JavaEE】网络编程——UDP
🤡🤡🤡个人主页🤡🤡🤡 🤡🤡🤡JavaEE专栏🤡🤡🤡 文章目录 1.数据报套接字(UDP)1.1特点1.2编码1.2.1DatagramSocket1.2.2DatagramPacket…...

JAVA毕业设计147—基于Java+Springboot的手机维修管理系统(源代码+数据库)
基于JavaSpringboot的手机维修管理系统(源代码数据库)147 一、系统介绍 本项目分为用户、管理员、维修员三种角色 1、用户: 注册、登录、新闻公告、售后申请、申请列表、意见反馈、个人信息、密码修改 2、管理员: 用户管理、用户管理、栏目管理、网…...
力扣第228题“汇总区间”
在本篇文章中,我们将详细解读力扣第228题“汇总区间”。通过学习本篇文章,读者将掌握如何遍历和汇总区间,并了解相关的复杂度分析和模拟面试问答。每种方法都将配以详细的解释,以便于理解。 问题描述 力扣第228题“汇总区间”描…...

部署大语言模型并对话
在阿里云的https://developer.aliyun.com/adc/scenario/b105013328814fe995c0f091d708d67d 选择函数计算 设置服务器配置 复制公网地址 这个地址不能直接 在返回应用,创建应用LLM 对话页面 Open WebUI 点击下面的创建应用 部署完成后访问域名 打开访问地址...
WebSocket、socket.io-client
WebSocket WebSocket 是一种网络通信协议,它提供了一个在单个长期持久的 TCP 连接上进行全双工(full-duplex)通信的通道。 WebSocket 允许客户端和服务器之间进行双向的数据交换,这意味着服务器可以主动向客户端推送数据&#x…...
Maven 仓库
在 Maven 世界中,任何一个依赖、插件或者项目构建的输出,都可以称为 构件 。 坐标和依赖是构件在 Maven 世界中的逻辑表示方式,构件的物理表示方式是文件,Maven 通过仓库来统一管理这些文件。 任何一个构件都有一组坐标唯一标识。…...

给后台写了一个优雅的自定义风格的数据日志上报页面
highlight: atelier-cave-dark 查看后台数据日志是非常常见的场景,经常看到后台的小伙伴从服务器日志复制一段json数据字符串,然后找一个JSON工具网页打开,在线JSON格式化校验。有的时候,一些业务需要展示mqtt或者socket的实时信息展示,如果不做任何修改直接展示一串字符…...

【React Native优质开源项目】
🌈个人主页: 程序员不想敲代码啊 🏆CSDN优质创作者,CSDN实力新星,CSDN博客专家 👍点赞⭐评论⭐收藏 🤝希望本文对您有所裨益,如有不足之处,欢迎在评论区提出指正,让我们共…...

Android 自动更新时间的数字时钟 TextClock
TextClock 继承 TextView ,使用方法和 TextView 一样。 它专门用于显示数字时钟,可以自定义显示格式。 只要在布局文件里添加,它会自动更新时间,不需要添加刷新逻辑。 布局文件, <?xml version"1.0"…...
【Linux Git入门】Git的介绍
文章目录 前言git简介git是什么git的作用为什么要学习git安装git总结前言 在现代软件开发中,版本控制系统已经成为了不可或缺的工具。其中,Git是最受欢迎的版本控制系统之一。Git是由Linux的创造者Linus Torvalds在2005年创建的,用于管理Linux内核的开发。Git是一个分布式版…...
kafka面试题(基础-进阶-高阶)
目录 Kafka 基础篇 1.Kafka 的用途有哪些?使用场景如何? 2.Kafka 中的ISR、AR 又代表什么?ISR 的伸缩又指什么 3.Kafka 中的 HW、LEO、LSO、LW 等分别代表什么? 4.Kafka 中是怎么体现消息顺序性的? 5.Kafka 中的分区器、序列化器、拦截器是否了解?它们之间的处理顺序…...

《系统架构设计师教程(第2版)》第11章-未来信息综合技术-07-大数据技术概述
文章目录 1. 大数据的定义2. 大数据的研究内容2.1 面临的问题2.2 面临的挑战2.3 分析步骤2.3.1 数据获取和记录2.3.2 信息抽取和清洗2.3.3 数据集成、聚集和表示2.3.4 查询处理、数据建模和分析2.3.5 解释 3.大数据的应用领域3.1 制造业的应用3.2 服务业的应用3.3 交通行业的应…...

前端面试题54(断点续传讲解)
断点续传是一种在上传或下载大文件时,如果因为网络问题中断,可以从已经上传或下载的部分继续,而不是重新开始的技术。这对于提高用户体验和节省带宽非常有帮助。下面我将分别从HTTP协议层面、前端实现思路以及一个简单的前端实现示例来讲解断…...

YOLOv10改进 | Conv篇 | RCS-OSA替换C2f实现暴力涨点(减少通道的空间对象注意力机制)
一、本文介绍 本文给大家带来的改进机制是RCS-YOLO提出的RCS-OSA模块,其全称是"Reduced Channel Spatial Object Attention",意即"减少通道的空间对象注意力"。这个模块的主要功能是通过减少特征图的通道数量,同时关注空…...

【C++BFS】690. 员工的重要性
本文涉及知识点 CBFS算法 LeetCode690. 员工的重要性 你有一个保存员工信息的数据结构,它包含了员工唯一的 id ,重要度和直系下属的 id 。 给定一个员工数组 employees,其中: employees[i].id 是第 i 个员工的 ID。 employees[…...
视频调整帧率、分辨率+音画同步
# python data_utils/pre_video/multi_fps_crop_sync.pyimport cv2 import os from tqdm import tqdm import subprocess# 加载人脸检测模型 face_cascade cv2.CascadeClassifier(cv2.data.haarcascades haarcascade_frontalface_default.xml)def contains_face(frame):gray …...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互
引擎版本: 3.8.1 语言: JavaScript/TypeScript、C、Java 环境:Window 参考:Java原生反射机制 您好,我是鹤九日! 回顾 在上篇文章中:CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...
OpenLayers 分屏对比(地图联动)
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能,和卷帘图层不一样的是,分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。
1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj,再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...

初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
JavaScript基础-API 和 Web API
在学习JavaScript的过程中,理解API(应用程序接口)和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能,使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

C++ 设计模式 《小明的奶茶加料风波》
👨🎓 模式名称:装饰器模式(Decorator Pattern) 👦 小明最近上线了校园奶茶配送功能,业务火爆,大家都在加料: 有的同学要加波霸 🟤,有的要加椰果…...

在 Spring Boot 中使用 JSP
jsp? 好多年没用了。重新整一下 还费了点时间,记录一下。 项目结构: pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...