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…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)
一、数据处理与分析实战 (一)实时滤波与参数调整 基础滤波操作 60Hz 工频滤波:勾选界面右侧 “60Hz” 复选框,可有效抑制电网干扰(适用于北美地区,欧洲用户可调整为 50Hz)。 平滑处理&…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
uniapp中使用aixos 报错
问题: 在uniapp中使用aixos,运行后报如下错误: AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计
随着大语言模型(LLM)参数规模的增长,推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长,而KV缓存的内存消耗可能高达数十GB(例如Llama2-7B处理100K token时需50GB内存&a…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
