二叉树、红黑树、B树、B+树
二叉树
一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
二叉树的特点:
- 每个结点最多有两棵子树,即二叉树不存在度大于2的结点。
- 二叉树的子树有左右之分,其子树的次序不能颠倒。
满二叉树
满二叉树:二叉树的所有叶子节点都在最后一层且总数n=2^(n-1)。

完全二叉树
完全二叉树:数据从上到下,从左到右依次进行平铺。
有序二叉树
有序二叉树:左子树上的值小于根节点的值,右子树上的值大于根节点的值。
有序二叉树的遍历:
深度优先遍历:
1、先序/前序遍历:根节点----》左子树-----》右子树
2、中序遍历:左子树----》根节点-----》右子树
3、后序遍历:左子树----》右子树-----》根节点
有序二叉树不稳定:O(logn) - O(n)
有序二叉树不稳定是因为没有任何限制,以至于在某些特殊的情况下会形成链表。
平衡二叉树
平衡二叉树是在有序二叉树的基础之上而来的,就是为了解决有序二叉树不稳定的问题。要求:一个节点的左右子树高度差的绝对值不能超过1,可以等于1。
如果插入的数据之后使得一个节点的左右子树高度差的绝对值超过了1,就要通过LL、RR、LR、RL四种旋转策略来保证平衡二叉树。
四种旋转策略
LL旋转策略:

实例:

RR旋转策略:

实例:

LR旋转策略:

实例:

RL旋转策略:

实例:

在实行旋转策略是,选择距离造成不平衡节点最近的不平衡节点作为要操作节点。
平衡二叉树特别稳定,但每次进行调整都会耗费计算机性能。
我们想既要时间复杂度在O(logn),又要十分稳定,还要不耗费计算机性能,这时,推出了红黑树。
红黑树(基于2-3-4树)
2-3-4树是从下向上构建的。节点内升序,每个节点最多有3个值,当插入第4个值时,需要在这四个之中选中间值进行升元。
实例:

然后通过2-3-4树转换 形成红黑树
转换规则如下图:

将刚刚的2-3-4树转换为红黑树:

红黑树的特点:
1、红黑树中每一个节点不是红色节点就是黑色节点。
2、红黑树当中根节点一定是黑色的。———>在转化的过程中2-3-4节点都是以黑色节点开头的
3、每一个叶子节点都是黑色的。
4、从根节点到任意一个叶子节点的路径上所走过的黑色节点的数量相同
5、如果一个节点是红色的,那么他的子节点一定是黑色
4、5条特点会导致最长的路径绝对不会超过最短路径的2倍。例如最长路径为黑红黑红黑红,最短路径为黑黑黑。
为什么红黑树是O(logn)?
2-3-4树是多叉树,如果数据相等,它的时间复杂度小于传统二叉树,2-3-4树的时间复杂度
红黑树最复杂的时候也就是变为2倍,变为2logn。这是依旧可以看成是logn。
B树
多叉树以B树为最基本点。2-3-4树来源于B树。
B树特点:
1、B树的数据存储是 key-value类型的。
2、B树有几个叉:并不确定,要看具体实现。
3、M阶B树
3.1、每个节点上最多有 M-1 个值,并且以升序排列。3阶B树每个节点最多有两个值。.....(2-3-4树属于4阶B树)
红黑树和B树如果都在内存中,内存向cpu提供数据的时间相等,由于红黑树对比次数相对较少,所以红黑树是内存最优二叉树。
为什么要有B树:
红黑树和B树如果都在磁盘中--------》数据寻址浪费时间--------》磁头移动的物理时间+平均盘面旋转半圈
B树多用于磁盘,原因是分出多个叉,降低树的高度,降低寻址次数和时间。
B树优胜于寻址,但是数据进行对比还是要在内存中。
B+树
在B树基础上改造出现的B+树,但和传统B树又不太一样。B+树是mysql数据库专用底层数据结构。
B+树的特点:
1、非叶子节点仅具有索引功能,也就是说非叶子节点只能存储key值,不能存储value值。
2、B+树的所有叶子节点会构成一个有序的链表,这样就可以根据key值遍历数据。
之所以有这两个特点就是为数据库的功能服务
B+树的构建

插入 3 ,4


磁盘向cpu推送数据:每次需要推送一页(4kb)的数据,如两个文件 2kb+3kb,只能先推送2kb,再推送3kb。
B+树的优点:
1、非叶子节点不包含数据,只能放索引,这样每次就可以向内存当中传输更多的key值,在内存当中进行数据比对,在磁盘当中进行数据查询。
2、叶子节点是链接在一起的,这样有利于区间查询。
相关文章:
二叉树、红黑树、B树、B+树
二叉树 一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 二叉树的特点: 每个结点最多有两棵子树,即二叉树不存在度大于2的结点。二叉树的子树有左右之分…...
12,【设计模式】工厂
设计模式工厂 通过工程来构建任意参数对象&&std::forwardstd::move 在C中,“工厂”(Factory)是一种设计模式,它提供了一种创建对象的方式,将对象的创建和使用代码分离开来,提高了代码的可扩展性和可…...
mysql 8.0 窗口函数 之 分布函数 与 sql server (2017以后支持) 分布函数 一样
mysql 分布函数 percent_rank() :等级值 百分比cume_dist() :累积分布值 percent_rank() 计算方式 (rank-1)/(rows-1), 其中 rank 的值为使用RANK()函数产生的序号,rows 的值为当前…...
Python Opencv实践 - 图像直方图自适应均衡化
import cv2 as cv import numpy as np import matplotlib.pyplot as pltimg cv.imread("../SampleImages/cat.jpg", cv.IMREAD_GRAYSCALE) print(img.shape)#整幅图像做普通的直方图均衡化 img_hist_equalized cv.equalizeHist(img)#图像直方图自适应均衡化 #1. 创…...
Linux编程:在程序中异步的调用其他程序
Linux编程:execv在程序中同步调用其他程序_风静如云的博客-CSDN博客 介绍了同步的调用其他程序的方法。 有的时候我们需要异步的调用其他程序,也就是不用等待其他程序的执行结果,尤其是如果其他程序是作为守护进程运行的,也无法等待其运行的结果。 //ssss程序 #include …...
04有监督算法——支持向量机
1.支持向量机 1.1 定义 支持向量机( Support Vector Machine )要解决的问题 什么样的法策边界才是最好的呢? 特征数据本身如果就很难分,怎么办呢? 计算复杂度怎么样?能实际应用吗? 支持向量机( Support Vector Machine , SVM)是一类按监督学习( s…...
macos 使用vscode 开发python 爬虫(安装一)
使用VS Code进行Python爬虫开发是一种常见的选择,下面是一些步骤和建议: 安装VS Code:首先,确保你已经在你的macOS上安装了VS Code。你可以从官方网站(https://code.visualstudio.com/)下载并安装最新版本…...
专有网络VPC私网/公网类产品选择
私网类产品选择 VPC互连:云企业网,对等连接 VPC与本地IDC互连:VPN网关,高速通道,云企业网,智能接入网关 VPC与多站点连接:VPN网关,智能接入网关,VPN网关高速通道 远程接…...
Connect-The-Dots靶场
靶场下载 https://www.vulnhub.com/entry/connect-the-dots-1,384/ 一、信息收集 探测存活主机 netdiscover -r 192.168.16.161/24nmap -sP 192.168.16.161/24端口操作系统扫描 nmap -sV -sC -A -p 1-65535 192.168.16.159扫描发现开放端口有 21 ftp 80 http 20…...
Linux解决RocketMQ中NameServer启动问题
启动步骤可以查看官网,https://github.com/apache/rocketmq 一下说明遇到的问题。 1:ROCKETMQ_HOME问题 根据官网提示进入mq/bin目录下,可以使用./mqnamesrv进行NameServer启动,但是会遇到第一个问题,首次下载Rocket…...
js逆向实战之某书protobuf反序列化
什么是Protobuf? \qquad Protobuf(Protocol Buffer)是 Google 开发的一套数据存储传输协议,作用就是将数据进行序列化后再传输,Protobuf 编码是二进制的,它不是可读的,也不容易手动修改…...
cpolar+JuiceSSH实现手机端远程连接Linux服务器
文章目录 1. Linux安装cpolar2. 创建公网SSH连接地址3. JuiceSSH公网远程连接4. 固定连接SSH公网地址5. SSH固定地址连接测试 处于内网的虚拟机如何被外网访问呢?如何手机就能访问虚拟机呢? cpolarJuiceSSH 实现手机端远程连接Linux虚拟机(内网穿透,手机端连接Linux虚拟机) …...
[MyBatis系列②]Dao层开发的两种方式
目录 1、传统开发 1.1、代码 1.2、存在的问题 2、代理开发 2.1、开发规范 2.2、代码 ⭐mybatis系列①:增删改查 1、传统开发 传统的mybatis开发中,是在数据访问层实现相应的接口,在实现类中用"命名空间.id"的形式找到对应的映…...
言语理解-中心理解之主题词及行文脉络
例题 例题 例题 例题 例题 例题...
LeetCode 面试题 01.05. 一次编辑
文章目录 一、题目二、C# 题解法一:从第一个不同位置处判断后续相同子串法二:前后序遍历判断第一个不同字符的位置关系 优化法一法二 一、题目 字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串ÿ…...
Mybatis查询in的字段过多不走索引
mybatis查询in的字段有索引,比如说是主键查询, 但是in的字段过多导致索引失效, 这个时候可以考虑将in的数量变少, 200以内都可以, 在数据库方面采用 foreach unionall 的方式将数据集合查询出来 Service层: List<…...
封装公共el-form表单(记录)
1.公共表单组件 //commonForm.vue <script> import {TEXT,SELECT,PASSWORD,TEXTAREA,RADIO,DATE_PICKER } from /conf/uiTypes import { deepClone } from /utils export default {name: GFormCreator,props: {config: { // title/itemstype: Object,required: true}}…...
List 分批处理
1.Google Guava <dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>31.0.1-jre</version></dependency>List<String> tempList Arrays.asList("水星","金星&qu…...
SpringSession
Spring Session 是 Spring 的项目之一。Spring Session 提供了一套创建和管理 Servlet HttpSession 的方案,默认采用外置的 Redis 来存储 Session 数据,以此来解决 Session 共享的 问题。(springsession储存session数据的方式有很多,我们常…...
Python Web 开发之 JWT 简介
在之前的课程中,介绍过 Flask-Login 框架,它是基于 Session 和 Cookie 技术来实现用户授权和验证的,不过 Session 有很多的局限性,这一节介绍一种基于 token 的验证方式 —— JWT (JSON Web Token),除了对 JWT 的概念讲解之外&…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
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…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
C++使用 new 来创建动态数组
问题: 不能使用变量定义数组大小 原因: 这是因为数组在内存中是连续存储的,编译器需要在编译阶段就确定数组的大小,以便正确地分配内存空间。如果允许使用变量来定义数组的大小,那么编译器就无法在编译时确定数组的大…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
计算机基础知识解析:从应用到架构的全面拆解
目录 前言 1、 计算机的应用领域:无处不在的数字助手 2、 计算机的进化史:从算盘到量子计算 3、计算机的分类:不止 “台式机和笔记本” 4、计算机的组件:硬件与软件的协同 4.1 硬件:五大核心部件 4.2 软件&#…...
零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...
高考志愿填报管理系统---开发介绍
高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发,采用现代化的Web技术,为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## 📋 系统概述 ### 🎯 系统定…...
