数据结构中的一棵树

一、树是什么?

有根有枝叶便是树!根只有一个,枝叶可以有,也可以没有,可以有一个,也可以有很多。

就像这样:
在这里插入图片描述

嗯,应该是这样:

在这里插入图片描述

二、一些概念

1、高度

树有多高,嗯,我一米八三!

树的高度怎么算?

高度是啥,就是从下往上到最顶端,从叶节点到根节点。

从每个叶节点开始,一个节点一个节点往上数,数到根节点,最长的那个数就是数的高度。叶节点起始为0.

上面这个树的高度是4。

在这里插入图片描述

2、深度

深度,顾名思义,就是从上往下到最低端,从根节点到叶节点。

从根开始,一个节点一个节点往下数,数到每个叶子节点,最长的那个数就是数的深度。根节点的起始为0.

上面这个树的深度是4。

在这里插入图片描述

对比上面的高度,看到了哈,数值是一样的,

3、层

一层是什么呢。就是横向的同一高度的所有节点凑一块儿就是一层。

像下面一条线连接了第二层所有的节点:

在这里插入图片描述

三、二叉树的遍历

二叉树是什么?

二叉树就是每个节点最多有两个分叉子节点。

遍历是什么意思?

遍历就是一个树的所有节点都点一遍,那么既然要点一遍,总归要遵循一个特定的顺序,不然,乱来的话总会可能漏一个,或者多一个。

像下面这棵树:

在这里插入图片描述

1、前序遍历

顺序:中左右

中 6 -> 左中 5 -> 左 2 -> 右 3 -> 右中 7 -> 右 8

结果就是:6、5、2、3、7、8。

2、中序遍历

顺序:左中右

左 2 -> 中 5 -> 右 3 -> 中 6 -> 右中 7 -> 右 8

结果就是: 2、5、3、6、7、8。

3、后序遍历

顺序:左右中

左 2 -> 右 3 -> 中左 5 -> 右 8 -> 中右 7 -> 中 6

结果就是:2、3、5、8、7、6.

这个顺序,其实很容易混乱。想要记得牢,只需要一点:

【前、中、后】,前为左,右为后,哪个顺序遍历,那么哪个节点就会顺序居中,其它的节点,靠左的居前。

节点的巡查是从根节点出发,从上到下,从左至右巡查,每个节点及其子点巡查完毕后,再跳出到其它节点。

4、附加:层序遍历

层序遍历很简单就是从上到下,一层一层的收拢节点。

第一层 6 -> 第二层 5、7 -> 第三层 2、3、8

结果就是:6、5、7、2、3、8.

四、树能干什么?

树能盖房子!

没错,树通常用来搭建存储数据的房子。

数据存储是对数据的持久化保存,针对数据的操作包括读和写。不过,无论是读还是写,都离不开对数据的检索操作。

1、B树

之前文章介绍过B树及在数据库存储方面的应用:

你好,我是B树

MySQL InnoDB 是怎么使用 B+ 树存数据的?

B 树,即balance tree。其结构及节点数据分布遵循特定的规则。

B 树的算法运行时间通常由它所执行的【磁盘读写操作次数】决定,所有一般会一次尽可能的读写更多的信息。一个B树节点通常和一个完整的磁盘页大小相同,所以磁盘页的大小限制了一个B树节点所能包含孩子节点的个数。

B 树每个节点会包含多少个分支,称之为分支因子。分支因子越大,B 的高度越低,查找关键字所需的磁盘存取次数越少,查询时间越短。这也是为什么会推崇使用B树结构来作为数据底层存储。

2、二叉搜索树

二叉搜索树是以一棵二叉树来组织数据存储,每个节点除了包含数据本身外,还包括指向左节点、右节点及父节点的指针,即key、left、right、p。其中存储数据需满足左中右非降序存储,即left.key <= key <= right.key。

左中右,是不是很熟悉,就是我们上面讲到过的【中序遍历】顺序。【中序遍历】输出的话,整个数列会是非降序排序数列。

搜索树结构通常支持包括查找,最大值,最小值,插入,删除等操作。嗯,这些操作是不是又很熟悉,总之就是一个【日常操作】。

二叉搜索树上的操作时间和它的高度成正比,对于n节点二叉树,通常最坏运行时间为O(lgn)(为什么是O(lgn)呢?这个需要推导,先记住就行了),这个就是树元素随机分步的情况下的结果。极端情况下,一条链从根到叶的话,时间固定就是O(n)了。就像下面这个棵树:

在这里插入图片描述

3、红黑树

红黑树也是一个二叉搜索树。那为什么会需要这么一棵树呢?

就是为了避免上面哪种极端或者接近极端情况的出现。它可以【保证最坏的情况下操作时间复杂度为O(lgn)】。

对的,是保证!那怎么保证呢?当然是通过维持红黑树本身的结构特点来实现。

我们上面及到过二叉搜索树节点包含的数据,红黑树会在其基础上增加一个存储位来表示节点的颜色(红或者黑)。通过【对任何一条从根到叶子节点的简单路径上的各个节点颜色进行约束】来确保【没有一路径会比其它路径长2倍】。

红黑树的特点:

  • a)【节点要么红,要么黑】

  • b)【根节点是黑的】

  • c)【叶节点是黑的】

  • d)【如果一个节点是红色的,那么它的子节点是黑色的】

  • e)【对任何一个节点,从该节点到其所有后代叶节点的简单路径上的黑节点数据是相同的】

这里有个点需要强调一下,红黑树里所说的叶子节点指的是【外部节点】,也就是不包含 key 的节点。

黑高:从某个节点到达其叶节点的【任何一个(参考e】简单路径上的黑色节点个数称之为黑高。红黑树的黑高即为其根节点的黑高。

一颗有 n 个内部节点的红黑树的高度至多为 2lg(n+1),也即我们前面说的能够保证最坏的情况下操作时间复杂度为O(lgn)。

红黑树有哪些应用呢?

最常见的就是 HashMap了,用于解决存储元素哈希冲突,当链表元素个数超过8时,即转为红黑树。

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

正点原子imx6ull网络环境配置:开发板和电脑通过网线直连、电脑WiFi上网

1.硬件连接 开发板通过网线连接电脑。电脑连接wifi 2.VMware设置 2.1添加桥接模式和NAT模式 1&#xff09;打开vm设置 2&#xff09;设置网络适配器为桥接模式&#xff0c;不要勾选 “赋值物理网络连接状态” 3&#xff09; 添加一个网络适配器并设置成NAT模式&#xff0c;…

力扣hot100 颜色分类 双指针 滚动赋值

Problem: 75. 颜色分类 文章目录 思路解题方法复杂度Code&#x1f496; 超简洁版 思路 解题方法 描述你的解题方法 复杂度 时间复杂度: O ( n ) O(n) O(n) 空间复杂度: O ( 1 ) O(1) O(1) Code class Solution { public void sortColors(int[] nums){int n nums.length…

QGroundControl Qt安卓环境搭建及编译出现的问题

记录Qt 5.15.2搭建安卓环境出现的各种问题。 zipalign tool not found: D:/JavaAndroid/Android/sdk/build-tools//zipalign.exe&#xff1f; 答&#xff1a;需要将DANDROID_PLATFORM升级到已下载的版本. bin/llvm-readobj.exe: error: unknown argument ‘–libs’ 答&…

社交媒体数据分析:解读Facebook用户行为

在当今数字化时代&#xff0c;社交媒体已经成为人们生活不可或缺的一部分&#xff0c;而Facebook作为这个领域的巨头&#xff0c;承载了数十亿用户的社交活动。这庞大的用户群体产生了海量的数据&#xff0c;通过深度数据分析&#xff0c;我们能够深入解读用户行为&#xff0c;…

乐鑫科技业绩超预期修复,Wi-Fi芯片龙头走出“V底”了?

2024年伊始&#xff0c;又到了A股开始业绩披露的时间节点。 尽管A股业绩预告序幕刚刚拉开&#xff0c;但为数不多的企业预告似乎还是透露出某些信号&#xff1a;2023年国内半导体企业的业绩或许并没有想象中的“差”&#xff0c;相反正在逐渐改善。 通过同花顺问财进行筛选发…

php反序列化漏洞基础

一、序列化 serialize(): 序列化是将对象或类转换为字符串的过程,以便在程序运行过程中对其进行持久化存储或传输的操作。在PHP中,序列化主要用于将类对象或数组转换成字节流的形式,以便于存储在磁盘或传输到其他系统。 通过序列化,可以将对象或类转换成一串字符串,然后可…

PPO 跑CartPole-v1

gym-0.26.2 cartPole-v1 参考动手学强化学习书中的代码,并做了一些修改 代码 import gym import torch import torch.nn as nn import torch.nn.functional as F import numpy as np import matplotlib.pyplot as plt from tqdm import tqdmclass PolicyNet(nn.Module):def __…

2024最新PyQt5及其工具(Qt Designer、PyUIC、PyRcc)手把手操作实践指南

2024最新PyQt5及其工具&#xff08;Qt Designer、PyUIC、PyRcc&#xff09;手把手操作实践指南 前言 最近做了一些个人项目&#xff0c;内部逻辑还是挺多的&#xff0c;而且也有想要开源的想法&#xff0c;但是总不能直接把源码端给大家直接运行&#xff0c;有一些需求还有萌…

ubuntu设置每天定时关机

ubuntu设置每天定时关机 终端输入命令&#xff1a; sudo crontab -e输入密码&#xff0c;回车。 我这里使用nano作为编辑器&#xff0c;你可以选择vim。 在末尾输入以下命令&#xff1a; 59 23 * * * sudo -u root shutdown now设置&#xff1a;每天23:59分&#xff0c;电脑…

中科院自动化所:基于关系图深度强化学习的机器人多目标包围问题新算法

摘要&#xff1a;中科院自动化所蒲志强教授团队&#xff0c;提出一种基于关系图的深度强化学习方法&#xff0c;应用于多目标避碰包围(MECA)问题&#xff0c;使用NOKOV度量动作捕捉系统获取多机器人位置信息&#xff0c;验证了方法的有效性和适应性。研究成果在2022年ICRA大会发…

HarmonyOS应用开发者初级认证试题库(鸿蒙)

目录 考试链接&#xff1a; 流程&#xff1a; 选择&#xff1a; 判断&#xff1a; 单选&#xff1a; 多选&#xff1a; 考试链接&#xff1a; 开发者能力认证-职业认证-鸿蒙能力认证-华为开发者学堂 (huawei.com)https://developer.huawei.com/consumer/cn/training/dev-…

计算机导论06-人机交互

文章目录 人机交互基础人机交互概述人机交互及其发展人机交互方式人机界面 新型人机交互技术显示屏技术跟踪与识别&#xff08;技术&#xff09;脑-机接口 多媒体技术多媒体技术基础多媒体的概念多媒体技术及其特性多媒体技术的应用多媒体技术发展趋势 多媒体应用技术文字&…

高斯Hack算法

背景 刷leetcode时&#xff0c;碰到一题需要求解n个bit中选择m个bit的所有组合集&#xff0c;我只想到了递归求解&#xff0c;没啥问题&#xff0c;但是在官方题解中看到了牛逼的方法(Gospers Hack)&#xff0c;故记录一下。 4bit中2个1的情况 0011b0101b0110b1001b1010b1100b…

ASP.NET Core SingleR:初次体验和简单项目搭建

文章目录 前言应用场景SignalR 网站长什么样&#xff1f;第一个ASP.NET core SignalR程序确定SignalR版本新建MVC项目添加unpkg管理器添加客户端添加ChatHub文件添加SignalR服务添加网页运行测试浏览器Websocket调试type1type6Type为其它时 总结 前言 平常的网页通讯都是基于H…

苹果要在iPhone上运行AI大模型?

近两年&#xff0c;人工智能&#xff08;AI&#xff09;技术已经成为各大科技公司的重点研究领域&#xff0c;苹果公司自然也不甘落后。最新消息称&#xff0c;苹果甚至打算在iPhone上直接运行AI大模型... 据苹果AI研究人员表示&#xff0c;他们发明了一种创新的闪存利用技术&a…

Intel开发环境Quartus、Eclipse与WSL的安装

PC &#xff1a;win10 64bit 安装顺序&#xff1a;先安装Quartus 21.4&#xff0c;接着Eclipse或者WSL&#xff08;Windows Subsystem for Linux&#xff09;&#xff0c;Eclipse与WSL的安装不分先后。 为什么要安装Eclipse&#xff1f; 因为Eclipse可以开发基于Nios II的C/…

【上分日记】第380场周赛(数位dp+ KMP + 位运算 + 二分 + 双指针 )

文章目录 前言正文1.3005. 最大频率元素计数2.3007.价值和小于等于 K 的最大数字3.3008. 找出数组中的美丽下标 II 总结尾序 前言 本场周赛&#xff0c;博主也只写出两道题(前两道, hhh菜鸡勿喷)&#xff0c;第三道涉及位运算 &#xff0c;数位dp&#xff0c;第四道涉及KMP。 下…

Mac系统下,保姆级Jenkins自动化部署Android

一、Jenkins自动化部署 1、安装jenkins 官网&#xff1a;macOS Installers for Jenkins LTS 选择macOS brew install jenkins-lts 安装最新: brew install jenkins-lts 启动jenkins服务: brew services start jenkins-lts 重启jenkins服务: brew services restart jenkin…

Angular系列教程之变更检测与性能优化

文章目录 前言变更检测的原理脏检查OnPush策略 示例代码总结 前言 Angular 除了默认的变化检测机制&#xff0c;也提供了ChangeDetectionStrategy.OnPush&#xff0c;用 OnPush 可以跳过某个组件或者某个父组件以及它下面所有子组件的变化检测。 在本文中&#xff0c;我们将探…

grep 在运维中的常用可选项

一、对比两个文件 vim -d <filename1> <filename2> 演示&#xff1a; 需求&#xff1a;&#xff5e;目录下有两个文件一个test.txt 以及 text2.txt,需求对比两个文件的内容。 执行后会显示如图&#xff0c;不同会高亮。 二、两次过滤 场景&#xff1a;当需要多…