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

查缺补漏----数据结构树高总结

① 对于平衡二叉树而言,树高的规律:

高度为h的平衡二叉树的含有的最少结点数(所有非叶节点的平衡因子均为1):

n0=1,n1=1,n2=2

n_h=n_{h-1}+n_{h-2}+1

含有的最多结点数:

2^h-1(高度为h的满二叉树含有的结点数)

② 对于折半查找判定树树高:(和完全二叉树相同)

n=\left \lfloor log_2{n} \right \rfloor+1 或者\left \lceil log_2{(n+1)} \right \rceil

③ 对于二叉排序树的树高:

最大为n,最小:\left \lceil log_2{(n+1)} \right \rceil

④ 红黑树的树高的性质:

1.从根节点到叶节点的最长路径不大于最短路径的2倍。

这是每条路径上的黑结点相同,并且不能出现相邻的红节点导致的。

2.红黑树中任何左子树和右子树的高度差,不会超过两倍。

3.若根节点黑高为h,内部结点数(关键字)最少2^h-1个。(满树的结点数)

4.若红黑树总高度=h,则根节点黑高>=h/2,因为不能出现相邻的两个红节点。又因为内部节点数n\geq 2^{\frac{h}{2}}-1,所以:h\leq 2log_{2}(n+1)

⑤ 对于B树:m表示阶数

最小高度

若要让B树的高度最小,在关键字数量不变的情况下,应该让每棵树尽可能满。对于m阶B树而言,每个结点最多有m-1个关键字以及m个分叉,则:

最大高度:

最大高度---让各层的分叉尽可能的少,即根节点只有2个分叉,其他结点只有个分叉。各层结点至少有:第一层 1、第二层 2、第三层.... 第h层,第h+1层共有叶子结点(失败结点):个(第h+1层是叶子结点,则该树有h层)。

为什么n个关键字的B树有n+1个叶子结点?因为n个关键字把(-∞,+∞)分为了n+1个区域,这n+1个区域对应n+1种失败的情况,即n+1个失败节点(叶子结点)。

相关文章:

查缺补漏----数据结构树高总结

① 对于平衡二叉树而言,树高的规律: 高度为h的平衡二叉树的含有的最少结点数(所有非叶节点的平衡因子均为1): n01,n11,n22 含有的最多结点数: (高度为h的满二叉树含有的结点数) ②…...

jenkins添加新服务

jenkins添加新服务 新建item 添加流水线 node{def envname "ENVIRONMENT:1234-dev"def projectGitUrl http://xxxxx/xxxxxx/12345.gitdef imageServer harbor.xxxxx.com //镜像仓库地址def projectAppName 12345-applicationdef projectGitBranch dev//git分…...

网络连接设备的功能与应用概述

目录 一、集线器 二、交换机 三、网桥 四、路由器 五、集线器、交换机、网桥与路由器的比较 备注 一、集线器 定义: 集线器(Hub)是一种物理层设备,它提供多个端口,用于将多个计算机或其他网络设备连接在一起&am…...

【SpringCloud】04-Gateway网关登录校验

1. 网关请求处理流程 2. 网关过滤器 3. 网关实现登录校验 Component // 参数构造器 RequiredArgsConstructor public class AuthGlobalFilter implements GlobalFilter, Ordered {private final AuthProperties authProperties;private final JwtTool jwtTool;private final A…...

FFmpeg 库的简要说明

FFmpeg 库的简要说明: libavutil 功能:提供一系列通用工具函数,旨在简化开发流程。 主要用途: 随机数生成器:用于生成随机数,适用于各种应用。 数据结构:提供常用的数据结构(如链表…...

Go:error处理机制

文章目录 本篇总结的是Go中对于错误的处理机制 Go 语言的函数经常使用两个返回值来表示执行是否成功:返回某个值以及 true 表示成功;返回零值(或 nil)和 false 表示失败 而实际上来说,是需要对于第二个参数进行判断的…...

Python机器学习中的主成分分析(PCA)全面解析与应用

🎯 Python机器学习中的主成分分析(PCA)全面解析与应用 📖 目录 🌟 主成分分析 (PCA) 的概念和原理🔎 PCA的数学基础🛠 Python 实现 PCA 的步骤详解📊 如何选择适合的主成分数量⚙️…...

MySQL 安装和基本使用

MySQL 介绍 MySQL 的特性 MySQL 是基于开源协议发布的,可以免费使用,也可以基于源码进行二次开发。 MySQL 使用标准 SQL 语言进行管理。 MySQL 可以运行于多个系统上,具有跨平台特性,并且支持多种语言。 MySQL 使用插件式存储…...

RequestBody接收参数报错com.fasterxml.jackson.databind.exc.MismatchedInputException

目录: 1、错误现象2、解决办法3、最终验证 1、错误现象 报错的现象和代码如下: 2、解决办法 查了很多都说参数类型对不上,最后只有换接收方式后验证是可以的;最终想了一下,觉得是请求的是json,需要用json接…...

大数据治理的关键技术:构建稳固的数据基石

在这个信息爆炸的时代,数据已经成为企业最宝贵的资产之一。然而,随着数据量的爆炸性增长,如何有效治理这些数据成为了一个巨大的挑战。今天,我们就来聊聊大数据治理的关键技术,看看如何构建一个稳固的数据基石&#xf…...

OS管理和进程的学习

1.冯诺依曼体系结构 1.1 输入设备:键盘,鼠标,键盘,网卡(网络接受),磁盘... 输出设备:显示器,磁盘,网卡(网络发送) .... 存储器&…...

Linux 部署 Harbor 镜像仓库详解

文章目录 安装 Docker安装 Harbor访问 Harbor 安装 Docker 本次部署流程使用的是1台阿里云ECS,Ubuntu 22.04,2核4G。 首先需要做的是在当前服务器上,安装好 Docker,参考链接如下: https://blog.csdn.net/weixin_4659…...

怎么把flv格式转换成mp4?将flv格式换成MP4格式的简单方法

怎么把flv格式转换成mp4?flv这一昔日网络视频领域的璀璨明星,凭借其小巧的文件体积与卓越的流媒体传输性能,曾在网络视频时代初期大放异彩,成为无数网络视频爱好者的首选。然而,随着科技的日新月异与多媒体设备的多元化…...

原型模式和建造模式的区别

原型模式(Prototype Pattern)和建造者模式(Builder Pattern)虽然都是创建型设计模式,但它们的应用场景和实现方式有着显著的区别。以下是二者的详细对比: 1. 意图和应用场景 原型模式: 意图&a…...

最新 client-java 调用 k8s ApiServer

创建权限绑定 sa-role.yaml apiVersion: v1 kind: ServiceAccount metadata:name: my-admin #账号名namespace: kube-system--- apiVersion: rbac.authorization.k8s.io/v1 kind: ClusterRole metadata:annotations:rbac.authorization.kubernetes.io/autoupdate: "true…...

TCP单包数据大于1460字节会被拆包的问题

关于TCP单包数据大于1460字节会被拆包的问题 1、问题背景: 最近在用STM32W5500做项目,需要STM32通过TCP协议发送数据到上位机并显示。当数据量小的时候上位机显示正常,一旦数据量大过大上位机就会出现数据丢失的情况,甚至数据直接…...

苏宁关键字搜索接口技术解析与实战

在当今的电商领域,搜索功能无疑是用户寻找心仪商品的最重要途径之一。苏宁作为国内知名的电商平台,其提供的API接口服务为开发者提供了丰富的商品数据。本文将详细介绍如何使用苏宁的关键字搜索接口,通过编写代码实现商品搜索功能。 接口概述…...

Java学习教程,从入门到精通,Java 基本数据类型详解(5)

Java 基本数据类型详解 Java是一种强类型语言,这意味着在Java程序中,每个变量都必须明确声明其数据类型。Java提供了八种基本数据类型(Primitive Data Types),这些类型都是预先定义好的,并且每种类型都占用…...

使用Flask实现本机的模型部署

前言 模型部署是指将大模型运行在专属的计算资源上,使模型在独立的运行环境中高效、可靠地运行,并为业务应用提供推理服务。其目标是将机器学习模型应用于实际业务中,使最终用户或系统能够利用模型的输出,从而发挥其作用。 一、设…...

基于SSM的校园跑腿网站的设计与实现

文未可获取一份本项目的java源码和数据库参考。 课题来源及研究的目的和意义 随着网络技术的不断完善与发展,各种互联网公司不断如雨后春笋般不断涌现,丰富了人们生活的各个方面。近年来由于 Online To 0ffline即线上到线下(020)模式的发展和兴起&…...

基于FPGA的PID算法学习———实现PID比例控制算法

基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...

HTML 列表、表格、表单

1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

反射获取方法和属性

Java反射获取方法 在Java中,反射(Reflection)是一种强大的机制,允许程序在运行时访问和操作类的内部属性和方法。通过反射,可以动态地创建对象、调用方法、改变属性值,这在很多Java框架中如Spring和Hiberna…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...

短视频矩阵系统文案创作功能开发实践,定制化开发

在短视频行业迅猛发展的当下&#xff0c;企业和个人创作者为了扩大影响力、提升传播效果&#xff0c;纷纷采用短视频矩阵运营策略&#xff0c;同时管理多个平台、多个账号的内容发布。然而&#xff0c;频繁的文案创作需求让运营者疲于应对&#xff0c;如何高效产出高质量文案成…...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...