python实现二叉搜索树(AVL树)简单样例
一、二叉搜索树
class TreeNode:def __init__(self, value):self.value = valueself.left = Noneself.right = Noneclass BinarySearchTree:def __init__(self):self.root = Nonedef insert(self, value):if self.root is None:self.root = TreeNode(value)else:self._insert(self.root, value)def _insert(self, node, value):if value < node.value:if node.left is None:node.left = TreeNode(value)else:self._insert(node.left, value)else:if node.right is None:node.right = TreeNode(value)else:self._insert(node.right, value)def search(self, value):return self._search(self.root, value)def _search(self, node, value):if node is None or node.value == value:return nodeif value < node.value:return self._search(node.left, value)return self._search(node.right, value)# 使用二叉搜索树
bst = BinarySearchTree()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(2)
bst.insert(4)# 搜索节点
found_node = bst.search(4)
if found_node:print(f'Node with value {found_node.value} found')
else:print('Node not found')
二、AVL树(平衡二叉搜索树)
AVL树是一种平衡二叉搜索树,它在插入和删除节点后会自动调整树的高度以保持平衡。以下是一个简单的AVL树实现:
class TreeNode:def __init__(self, key):self.key = keyself.left = Noneself.right = Noneself.height = 1class AVLTree:def insert(self, root, key):if not root:return TreeNode(key)elif key < root.key:root.left = self.insert(root.left, key)else:root.right = self.insert(root.right, key)root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))balance = self.get_balance(root)# 左左情况if balance > 1 and key < root.left.key:return self.right_rotate(root)# 右右情况if balance < -1 and key > root.right.key:return self.left_rotate(root)# 左右情况if balance > 1 and key > root.left.key:root.left = self.left_rotate(root.left)return self.right_rotate(root)# 右左情况if balance < -1 and key < root.right.key:root.right = self.right_rotate(root.right)return self.left_rotate(root)return rootdef left_rotate(self, z):y = z.rightT2 = y.lefty.left = zz.right = T2z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))return ydef right_rotate(self, z):y = z.leftT3 = y.righty.right = zz.left = T3z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))return ydef get_height(self, root):if not root:return 0return root.heightdef get_balance(self, root):if not root:return 0return self.get_height(root.left) - self.get_height(root.right)def pre_order(self, root):if not root:returnprint("{0} ".format(root.key), end="")self.pre_order(root.left)self.pre_order(root.right)# 使用AVL树
my_tree = AVLTree()
root = None
nums = [10, 20, 30, 40, 50, 25]for num in nums:root = my_tree.insert(root, num)print("Preorder traversal of the AVL tree is:")
my_tree.pre_order(root)
相关文章:
python实现二叉搜索树(AVL树)简单样例
一、二叉搜索树 class TreeNode:def __init__(self, value):self.value valueself.left Noneself.right Noneclass BinarySearchTree:def __init__(self):self.root Nonedef insert(self, value):if self.root is None:self.root TreeNode(value)else:self._insert(self.…...
Day47 打家劫舍123
198 打家劫舍 题目链接:198.打家劫舍 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,…...
OceanBase 开源社区新进展|obdiag SIG成立
为了构建完善的 OceanBase 诊断生态系统,汇聚各方力量,形成涵盖工具、知识在内的全方位诊断生态体系,助力开发者更高效地驾驭 OceanBase,OceanBase 社区宣布成立诊断 SIG,名称:obdiag SIG。 详情参加原文链…...
React类组件生命周期详解
在React的类组件中,从组件创建到组件被挂载到页面中,这个过程react存在一系列的生命周期函数,最主要的生命周期函数是componentDidMount、componentDidUpdate、componentWillUnmount 生命周期图例如下 1. componentDidMount组件挂载 如果你…...
智能车竞赛指南:从零到一,驶向自动驾驶的未来
智能车竞赛指南:从零到一,驶向自动驾驶的未来 一、智能车竞赛概览1.1 竞赛介绍1.2 竞赛分类 二、智能车开发技术基础2.1 硬件平台2.2 软件开发 三、实战案例:循线小车开发3.1 系统架构3.2 代码示例 四、技术项目:基于ROS的视觉导航…...
微服务项目收获和总结---第2,3天(分库分表思想,文章业务)
①分库分表思想 文章表一对一为什么要拆分?因为文章的内容会非常大,查询效率会很低,我们经常操作文章的基本信息,不会很经常查询文章内容。充分发挥高频数据的操作效率。 ②freemarker和minIO 由于文章内容数据量过大,…...
【全网最全】2024电工杯数学建模A题21页初步参考论文+py代码+保奖思路等(后续会更新)
您的点赞收藏是我继续更新的最大动力! 一定要点击如下的卡片链接,那是获取资料的入口! 【全网最全】2024电工杯数学建模A题21页初步参考论文py代码保奖思路等(后续会更新成品论文)「首先来看看目前已有的资料&#x…...
怎么通过OpenAI API调用其多模态大模型(GPT-4o)
现在只要有额度,大家都可以调用OpenAI的多模态大模型了,例如GPT-4o和GPT-4 Turbo,我一年多前总结过一些OpenAI API的用法,发现现在稍微更新了一下。主要参考了这里:https://platform.openai.com/docs/guides/vision 其…...
自定义文字线性
...
robosuite导入自定义机器人
目录 目的:案例一:成果展示具体步骤:URDF文件准备xml文件生成xml修改机器人构建 目的: 实现其他标准/非标准机器人的构建 案例一: 成果展示 添加机器人JAKA ZU 7 这个模型 具体步骤: URDF文件准备 从…...
四天学会JS高阶(学好vue的关键)——构造函数数据常用函数(理论+实战)(第二天)
一、对象创建引发构造函数产生 1.1 创建对象三种方式: 利用对象字面量创建对象 const obj {name: 佩奇}注:对象字面量的由来:即它是直接由字面形式(由源代码直接)创建出来的对象,而不是通过构造函数或者…...
【Linux学习】进程地址空间与写时拷贝
文章目录 Linux进程内存布局图:内存布局的验证 进程地址空间写时拷贝 Linux进程内存布局图: 地址空间的范围,在32位机器上是2^32比特位,也就是[0,4G]。 内存布局的验证 代码验证内存布局: 验证代码: #include<s…...
Git远程控制
文章目录 1. 创建仓库1.1 Readme1.2 Issue1.3 Pull request 2. 远程仓库克隆3. 推送远程仓库4. 拉取远程仓库5. 配置Git.gitignore配置别名 使用GitHub可以,采用Gitee也行 1. 创建仓库 1.1 Readme Readme文件相当于这个仓库的说明书,gitee会初始化2两份…...
怎样从SQL中分析和提取访问的字段信息?| OceanBase实践
当执行任意一条SELECT SQL语句时,我们如何能够分析出所访问的字段信息,并进一步判断结果集中的每一列数据具体来自于哪些数据库、表以及表中的哪些字段呢?本文将会详细阐述针对此问题的技术解决方案。 应用场景 从 SQL 中解析访问的原始字段…...
MySQL 服务无法启动
常见原因: 检查端口占用: 使用命令行工具(如netstat)来检查3306端口是否已被其他程序占用,输入netstat -ano(Windows)或netstat -tulnp | grep 3306(Linux/Mac)来查找3306端口的占用情况。如果…...
Python贪心算法
贪心算法(Greedy Algorithm)是一种常见的算法设计策略,它在每一步选择当前最优解,希望通过局部最优解最终得到全局最优解。贪心算法通常适用于满足一些特定条件的问题,例如货币找零、活动选择、任务调度等。贪心算法的…...
牛客网刷题 | BC85 牛牛学数列3
目前主要分为三个专栏,后续还会添加: 专栏如下: C语言刷题解析 C语言系列文章 我的成长经历 感谢阅读! 初来乍到,如有错误请指出,感谢! 描述 牛牛准备继续进阶&…...
quartz定时任务
Quartz 数据结构 quartz采用完全二叉树:除了最后一层每一层节点都是满的,而且最后一层靠左排列。 二叉树节点个数规则:每层从左开始,第一层只有一个,就是2的0次幂,第二层两个就是2的1次幂,第三…...
Python基础学习笔记(五)——选择结构与循环结构
目录 程序的组织结构条件选择结构1. 单分支结构2. 双分支结构3. 多分支结构4. 嵌套(分支)结构5. 无内容执行6. 条件表达式 循环结构1. 可迭代对象2. range()函数3. for循环语句4. while循环语句5. 结束语句 程序的组织结构 程序的组织结构主要有以下三种…...
Vue插槽solt如何传递具名插槽的数据给子组件?
在Vue中,你可以通过作用域插槽(scoped slots)来传递数据给子组件。这同样适用于具名插槽。首先,你需要在子组件中定义一个具名插槽,并通过v-slot指令传递数据。例如: 子组件(ChildComponent.vu…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
Chapter03-Authentication vulnerabilities
文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
在 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…...
OCR MLLM Evaluation
为什么需要评测体系?——背景与矛盾 能干的事: 看清楚发票、身份证上的字(准确率>90%),速度飞快(眨眼间完成)。干不了的事: 碰到复杂表格(合并单元…...
轻量级Docker管理工具Docker Switchboard
简介 什么是 Docker Switchboard ? Docker Switchboard 是一个轻量级的 Web 应用程序,用于管理 Docker 容器。它提供了一个干净、用户友好的界面来启动、停止和监控主机上运行的容器,使其成为本地开发、家庭实验室或小型服务器设置的理想选择…...
Linux基础开发工具——vim工具
文章目录 vim工具什么是vimvim的多模式和使用vim的基础模式vim的三种基础模式三种模式的初步了解 常用模式的详细讲解插入模式命令模式模式转化光标的移动文本的编辑 底行模式替换模式视图模式总结 使用vim的小技巧vim的配置(了解) vim工具 本文章仍然是继续讲解Linux系统下的…...
