【数据结构】你知道什么是二叉树的顺序存储结构吗?

在这里插入图片描述

文章目录

  • 前言
  • 1. 顺序结构
  • 2. 实现顺序结构二叉树
    • 2.1 堆的概念与结构
    • 2.2 堆的实现
      • 2.2.1 向上调整算法
      • 2.2.2 向下调整算法
  • 3. 结语

前言

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。本文将要介绍的是二叉树的顺序存储结构。

1. 顺序结构

顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费,完全二叉树更适合使用顺序结构存储。

在这里插入图片描述

现实中我们通常把(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段。

2. 实现顺序结构二叉树

一般堆使用顺序结构的数组来存储数据,堆是一种特殊的二叉树,具有二叉树的特性的同时,还具备其他的特性。

2.1 堆的概念与结构

如果有一个关键码的集合 K = { k 0 , k 1 , k 2 , . . . , k n − 1 } K = \{{k_0,k_1,k_2 , ...,k_{n−1}}\} K={k0,k1,k2,...,kn1},把它的所有元素按完全二叉树的顺序存储方式存储,在一个一维数组中,并满足: K i < = K 2 ∗ i + 1 且 K i < = K 2 ∗ i + 2 ( K i > = K 2 ∗ i + 1 且 K i > = K 2 ∗ i + 2 ) K_i <= K_{2*i+1} 且K_i <=K_{2*i+2}(K_i >=K_{2*i+1}且K_i >= K_{2*i+2}) Ki<=K2i+1Ki<=K2i+2(Ki>=K2i+1Ki>=K2i+2),$i = 0、1、2… $,则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆

在这里插入图片描述

堆具有以下性质:

  • 堆中某个结点的值总是不大于或不小于其父结点的值;

  • 堆总是一棵完全二叉树。

💡 二叉树性质

对于具有n个结点的完全二叉树,如果按照从上至下从左至右的顺序存储在数组中,并且对所有结点从0开始编号,则对于序号为 i 的结点有:

  1. i > 0 i>0 i>0 i i i位置结点的双亲序号为: ( i − 1 ) / 2 (i-1)/2 (i1)/2;若 i = 0 i=0 i=0,则 i i i根结点编号,无双亲结点
  2. 2 i + 1 < n 2i+1<n 2i+1<n,左孩子序号为: 2 i + 1 2i+1 2i+1;若 2 i + 1 > = n 2i+1>=n 2i+1>=n则无左孩子
  3. 2 i + 2 < n 2i+2<n 2i+2<n,右孩子序号为: 2 i + 2 2i+2 2i+2;若 2 i + 2 > = n 2i+2>=n 2i+2>=n则无右孩子

2.2 堆的实现

堆底层结构为数组,因此定义堆的结构为:

typedef int HPDataType;
typedef struct Heap
{HPDataType * a;int size;int capacity;
}HP;
//默认初始化堆
void HPInit(HP * php);
//利用给定数组初始化堆
void HPInitArray(HP * php, HPDataType * a, int n);
//堆的销毁
void HPDestroy(HP * php);
//堆的插入
void HPPush(HP * php, HPDataType x);
//堆的删除
HPDataType HPTop(HP * php);
// 删除堆顶的数据
void HPPop(HP * php);
// 判空
bool HPEmpty(HP * php);
//求size
int HPSize(HP * php);
//向上调整算法
void AdjustUp(HPDataType * a, int child);
//向下调整算法
void AdjustDown(HPDataType * a, int n, int parent);

上面这部分是堆实现所需要的一些方法,其中具体的方法由读者自己先来尝试实现,如有不会的可以在讨论区询问,将会由作者或者其它积极的读者来解答❤️❤️❤️

2.2.1 向上调整算法

堆的插入

将新数据插入到数组的尾上,再进行向上调整算法,直到满足堆

💡 向上调整算法

  • 先将元素插入到堆的末尾,即最后一个孩子之后

  • 插入之后如果堆的性质遭到破坏,将新插入结点顺着其双亲往上调整到合适位置即可

在这里插入图片描述

代码实现

//向上调整
void AdjustUp(HPDataType* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (parent - 1) / 2;}else{break;}}
}//插入操作,插入之后利用向上调整算法来保持堆的结构
void HPPush(HP * php, HPDataType x)
{assert(php);if (php->size == php->capacity){size_t newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDataType * tmp = realloc(php->a, sizeof(HPDataType) * newCapacity);if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newCapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}

计算向上调整算法建堆时间复杂度:

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个结点不影响最终结果)

在这里插入图片描述

分析:

第1层, 2 0 2^0 20个结点,需要向上移动0层

第2层, 2 1 2^1 21个结点,需要向上移动1层

第3层, 2 2 2^2 22个结点,需要向上移动2层

第4层, 2 3 2^3 23个结点,需要向上移动3层

第h层, 2 h − 1 2^{h-1} 2h1个结点,需要向上移动h-1层

则需要移动结的总移动步数为:每层结点个数 * 向上调整次数(第一层调整次数为0)

T ( h ) = 2 1 ∗ 1 + 2 2 ∗ 2 + 2 3 ∗ 3 + . . + 2 h − 2 ∗ ( h − 2 ) + 2 h − 1 ∗ ( h − 1 ) T(h) = 2^1∗1+2^2∗2+2^3∗3+..+2^{h−2}∗(h−2)+2^{h−1}∗(h−1) T(h)=211+222+233+..+2h2(h2)+2h1(h1)

2 ∗ T ( h ) = 2 2 ∗ 1 + 2 3 ∗ 2 + 2 4 ∗ 3 + . . + 2 h − 1 ∗ ( h − 2 ) + 2 h ∗ ( h − 1 ) 2*T(h) = 2^2∗1+2^3∗2+2^4∗3+..+2^{h−1}∗(h−2)+2^h∗(h−1) 2T(h)=221+232+243+..+2h1(h2)+2h(h1)

② — ① 错位相减:

T ( h ) = − 2 1 ∗ 1 − ( 2 2 + 2 3 + . . + 2 h − 2 + 2 h − 1 ) + 2 h ∗ ( h − 1 ) T(h) = −2^1∗1−(2^2+2^3+..+2^{h−2}+2^{h−1})+2^h∗(h−1) T(h)=211(22+23+..+2h2+2h1)+2h(h1)

T ( h ) = − 2 0 − 2 1 ∗ 1 − ( 2 2 + 2 3 + . . + 2 h − 2 + 2 h − 1 ) + 2 h ∗ ( h − 1 ) + 2 0 T(h)=-2^0−2^1∗1−(2^2+2^3+..+2^{h−2}+2^{h−1})+2^h∗(h−1)+2^0 T(h)=20211(22+23+..+2h2+2h1)+2h(h1)+20

T ( h ) = − ( 2 0 + 2 1 ∗ 1 + 2 2 + 2 3 + . . + 2 h − 2 + 2 h − 1 ) + 2 h ∗ ( h − 1 ) + 2 0 T(h)=-(2^0+2^1∗1+2^2+2^3+..+2^{h−2}+2^{h−1})+2^h∗(h−1)+2^0 T(h)=(20+211+22+23+..+2h2+2h1)+2h(h1)+20

T ( h ) = − ( 2 h − 1 ) + 2 h ∗ ( h − 1 ) + 2 0 T(h)=-(2^h-1)+2^h∗(h−1)+2^0 T(h)=(2h1)+2h(h1)+20

T ( h ) = 2 h ∗ ( h − 2 ) + 2 T(h)=2^h*(h−2)+2 T(h)=2h(h2)+2

然后根据二叉树的性质: n = 2 h − 1 n=2^h−1 n=2h1 h = l o g 2 ( n + 1 ) h=log_2(n+1) h=log2(n+1)

T ( n ) = ( n + 1 ) ( l o g 2 ( n + 1 ) − 2 ) + 2 T(n)=(n+1)(log_2(n+1)−2)+2 T(n)=(n+1)(log2(n+1)2)+2

由此可得:

💡 向上调整算法建堆时间复杂度为 O ( n ∗ l o g 2 n ) O(n∗log_2n) O(nlog2n)

2.2.2 向下调整算法

堆的删除

删除堆是删除堆顶的数据,将堆顶的数据和最后一个数据交换,然后删除数组最后一个数据,再进行向下调整算法。

在这里插入图片描述

💡 向下调整算法

  • 将堆顶元素与堆中最后一个元素进行交换

  • 删除堆中最后一个元素

  • 将堆顶元素向下调整到满足堆的特性为止

在这里插入图片描述

代码实现

//向下调整算法
void AdjustDown(HPDataType* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){// 假设法,选出左右孩⼦中⼩的那个孩⼦if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//删除操作,删除之后利用向下调整算法来保持堆的结构
void HPPop(HP * php)
{assert(php);assert(php->size > 0);Swap(&php->a[0], &php->a[php->size - 1]);php->size--;AdjustDown(php->a, php->size, 0);
}

计算向下调整算法建堆时间复杂度

在这里插入图片描述

分析:

第1层, 2 0 2^0 20个结点,需要向下移动h-1层

第2层, 2 1 2^1 21个结点,需要向下移动h-2层

第3层, 2 2 2^2 22个结点,需要向下移动h-3层

第4层, 2 3 2^3 23个结点,需要向下移动h-4层

第h-1层, 2 h − 2 2^{h-2} 2h2个结点,需要向下移动1层

则需要移动结点的总移动步数为:每层结点个数 * 向下调整次数

T ( h ) = 2 0 ∗ ( h − 1 ) + 2 1 ∗ ( h − 2 ) + 2 2 ∗ ( h − 3 ) + 2 3 ∗ ( h − 4 ) . . + 2 h − 3 ∗ 2 + 2 h − 2 ∗ 1 T(h)=2^0∗(h-1)+2^1∗(h-2)+2^2∗(h-3)+2^3*(h-4)..+2^{h−3}∗2+2^{h−2}∗1 T(h)=20(h1)+21(h2)+22(h3)+23(h4)..+2h32+2h21

2 ∗ T ( h ) = 2 1 ∗ ( h − 1 ) + 2 2 ∗ ( h − 2 ) + 2 3 ∗ ( h − 3 ) + 2 4 ∗ ( h − 4 ) . . + 2 h − 2 ∗ 2 + 2 h − 1 ∗ 1 2*T(h)=2^1∗(h-1)+2^2∗(h-2)+2^3∗(h-3)+2^4*(h-4)..+2^{h−2}∗2+2^{h−1}∗1 2T(h)=21(h1)+22(h2)+23(h3)+24(h4)..+2h22+2h11

② — ① 错位相减:

T ( h ) = 1 − h + 2 1 + 2 2 + 2 3 + 2 4 + . . + 2 h − 2 + 2 h − 1 T(h)=1-h+2^1+2^2+2^3+2^4+..+2^{h-2}+2^{h-1} T(h)=1h+21+22+23+24+..+2h2+2h1

T ( h ) = 2 0 + 2 1 + 2 2 + 2 3 + 2 4 + . . + 2 h − 2 + 2 h − 1 − h T(h)=2^0+2^1+2^2+2^3+2^4+..+2^{h-2}+2^{h-1}-h T(h)=20+21+22+23+24+..+2h2+2h1h

T ( h ) = 2 h − 1 − h T(h)=2^h−1−h T(h)=2h1h

然后根据二叉树的性质: n = 2 h − 1 n= 2^h−1 n=2h1 h = l o g 2 ( n + 1 ) h=log_2(n+1) h=log2(n+1)

T ( n ) = n − l o g 2 ( n + 1 ) ≈ n T(n)=n−log_2(n+1)≈n T(n)=nlog2(n+1)n

由此可得:

💡 向下调整算法建堆时间复杂度为 O ( n ) O(n) O(n)

3. 结语

今天的分享到这里就结束啦!如果觉得文章还不错的话,可以三连支持一下。

也可以点点关注,避免以后找不到我哦!

Crossoads主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是作者前进的动力!

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/419110.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

python安装以及访问openAI API

安装python 我是python小白&#xff0c;所以需要一步一步来&#xff0c;先安装。 一口吃不成胖子&#xff0c;记住。 从官网下载python&#xff0c;目前最新版本是3.12&#xff0c;但是据说稳定版3.11更好一点&#xff0c;所以&#xff0c;下载3.11&#xff0c;注意不要下载…

stm32的内部时钟源 | RC震荡电路

文章目录 前言学习了解 前言 了解到 内部高速RC振荡器&#xff08;HSI&#xff09;就是RC震荡器实现的&#xff0c;故想对RC震荡做些了解与分析。 学习了解 【不需要晶振&#xff0c;也可产生时钟脉冲&#xff01;RC振荡器的工作原理&#xff0c;维恩电桥振荡器&#xff01;…

string字符会调用new分配堆内存吗

gcc的string默认大小是32个字节&#xff0c;字符串小于等于15直接保存在栈上&#xff0c;超过之后才会使用new分配。

Kafka 分布式消息系统详细介绍

Kafka 分布式消息系统 一、Kafka 概述1.1 Kafka 定义1.2 Kafka 设计目标1.3 Kafka 特点 二、Kafka 架构设计2.1 基本架构2.2 Topic 和 Partition2.3 消费者和消费者组2.4 Replica 副本 三、Kafka 分布式集群搭建3.1 下载解压3.1.1 上传解压 3.2 修改 Kafka 配置文件3.2.1 修改z…

axure之变量

一、设置我们的第一个变量 1、点击axure上方设置一个全局变量a 3 2、加入按钮、文本框元件点击按钮文档框展示变量值。 交互选择【单击时】【设置文本】再点击函数。 点击插入变量和函数直接选择刚刚定义的全局变量&#xff0c;也可以直接手动写入函数(注意写入格式。) 这…

Gitflow基础知识

0.理想状态 现状 听完后的理想状态 没使用过 git 知道 git 是什么&#xff0c;会用 git 基础流程命令 用过 git&#xff0c;但只通过图形化界面操作 脱离图形化界面操作&#xff0c;通过 git 命令操作 会 git 命令 掌握 gitflow 规范&#xff0c;合理使用 rebase 和解决…

spark sql 优化

1. 配置 比例内存 : core 1:2 2. 增加 core 数可以增加 执行任务的 线程数 3. 计算有大表&#xff0c;并发生shuffle 时&#xff0c;生成的任务数是由spark.sql.shuffle.partitions 决定的&#xff0c;所以针对大表shuffle &#xff0c;要增加spark.sql.shuffle.partitio…

C++笔记20•数据结构:哈希(Hash)•

哈希 1.无序的关联式容器&#xff08;unordered_map&unordered_set&#xff09; unordered_map与unordered_set几乎与map与set是一样的&#xff0c;只是性能unordered_map与unordered_set比map与set更优一些。还有就是unordered_map与unordered_set是无序的&#xff0c;…

差异基因富集分析(R语言——GOKEGGGSEA)

接着上次的内容&#xff0c;上篇内容给大家分享了基因表达量怎么做分组差异分析&#xff0c;从而获得差异基因集&#xff0c;想了解的可以去看一下&#xff0c;这篇主要给大家分享一下得到显著差异基因集后怎么做一下通路富集。 1.准备差异基因集 我就直接把上次分享的拿到这…

服务器流量监控工具vnStat的简单使用以及关于Linux的软中断信号(signal)的一点内容

一、服务器流量监控工具vnStat的简单使用 vnStat是为Linux和BSD设计的基于控制台的网络流量监控工具&#xff0c;通过它可以非常方便在命令行查看流量统计情况。它可以保留某个或多个所选择的网络接口的网络流量日志。为了生成日志&#xff0c;vnStat使用内核提供的信息。换句话…

misc流量分析

一、wireshark语法 1、wireshark过滤语法 &#xff08;1&#xff09;过滤IP地址 ip.srcx.x..x.x 过滤源IP地址 ip.dstx.x.x.x 过滤目的IP ip.addrx.x.x.x 过滤某个IP &#xff08;2&#xff09;过滤端口号 tcp.port80tcp.srcport80 显示TCP的源端口80tcp.dstport80 显示…

Python和C++多尺度导图

&#x1f3af;要点 热化学属性观测蒙特卡罗似然比灵敏度分析时间尺度上动力学化学催化反应动力学建模自动微分电化学分析模型反应动力学数学模型渔业生态不确定性模型敏感性分析空间统计地理模型分析技术多维数据表征实现生成艺术图案流苏物体长度比&#xff0c;面积比和复杂度…

深度学习实战:如何利用CNN实现人脸识别考勤系统

1. 何为CNN及其在人脸识别中的应用 卷积神经网络&#xff08;CNN&#xff09;是深度学习中的核心技术之一&#xff0c;擅长处理图像数据。CNN通过卷积层提取图像的局部特征&#xff0c;在人脸识别领域尤其适用。CNN的多个层次可以逐步提取面部的特征&#xff0c;最终实现精确的…

Django+Vue3前后端分离学习(二)(重写User类)

一、重写User类&#xff1a; 1、首先导入User类&#xff1a; from django.contrib.auth.models import User 2、然后点在User上&#xff0c;按住ctrl 点进去&#xff0c;发现 User类继承AbstractUser Ctrl点进去AbstractUser&#xff0c;然后将此方法全部复制到自己APP的mo…

3 html5之css新选择器和属性

要说css的变化那是发展比较快的&#xff0c;新增的选择器也很多&#xff0c;而且还有很多都是比较实用的。这里举出一些案例&#xff0c;看看你平时都是否用过。 1 新增的一些写法&#xff1a; 1.1 导入css 这个是非常好的一个变化。这样可以让我们将css拆分成公共部分或者多…

WebDriver与Chrome DevTools Protocol:如何在浏览器自动化中提升效率

介绍 随着互联网数据的爆炸式增长&#xff0c;爬虫技术成为了获取信息的重要工具。在实际应用中&#xff0c;如何提升浏览器自动化的效率是开发者常常面临的挑战。Chrome DevTools Protocol&#xff08;CDP&#xff09;与Selenium WebDriver相结合&#xff0c;为浏览器自动化提…

还不会剪音乐?试试这四款在线音频剪辑

音频剪辑很多人都没有接触过。其实这并不是一个难事&#xff0c;我们甚至可以用一些简单的工具来给自己做个简单的BGM&#xff0c;最近我尝试了几款不同的音频剪辑工具。今天就来跟大家分享一下我的使用体验&#xff0c;看看哪款工具更适合你的需求。 一、福昕音频剪辑 网址&…

Oracle rman 没有0级时1级备份和0级大小一样,可以用来做恢复 resetlogs后也可以

文档说了 full backup 不能 用于后续的level 1&#xff0c;没说level 1没有level 0 是不是level 1就是level 0&#xff1f; GOAL What are incremental backups? Why are archivelogs still required to recover a database from an online incremental backup? Discuss th…

python学习13:对excel格式文件进行读写操作

读取excel的话需要下载第三方库&#xff1a; 常用的库:xlrd(读),xlwt(写),xlutils,openpyxl[-----pip install xxx-------] 这里推荐openpyxl pip install openpyxl excel读取的基本操作 # 2)基本操作: # 2.1)打开文件,获取工作簿 filename rD:\stdutyZiLiao\pythoneProje…

动态化-鸿蒙跨端方案介绍

一、背景 &#x1f449; 华为在2023.9.25官方发布会上宣布&#xff0c;新的鸿蒙系统将不再兼容安卓应用&#xff0c;这意味着&#xff0c;包括京东金融APP在内的所有安卓应用&#xff0c;在新的鸿蒙系统上将无法运行&#xff0c;需要重新开发专门适用于新鸿蒙系统的专版APP。 …