常见的数据结构,附带图解

概述

数据结构是指计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。

常见数据结构:栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树...

  • 后进先出、先进后出

队列

  • 先进先出,后进后出

数组

  • 查询速度快:查询数据通过地址值和索引定位,查询任意数据耗时相同。(元素在内存中是连续存储的)
  • 删除效率低:要将原属数据删除,同时后面每个数据前移。
  • 添加效率极低:添加位置后的每个数据后移,再添加元素。

链表

  • 链表中的元素是在内存中不连续存储的,每个元素节点包含数据值以及下一个元素的地址。

  • 链表查询慢,无论查询哪个数据都要从头开始找

这其实就是一个单链表 

  • 链表增删相对较快

 

链表的种类

二叉树

  • 只能有一个根节点:每个节点最多支持2个直接子节点
  • 节点的度:节点拥有的子树的个数,二又树的度不大于2叶子节点;度为0的节点,也称之为终端结点
  • 高度:叶子结点的高度为1,叶子结点的父节点高度为2,以此类推,根节点的高度最高
  • 层:根节点在第一层,以此类推
  • 兄弟节点:拥有共同父节点的节点互称为兄弟节点

二叉树又分为普通二叉树和二叉查找树,在开发中最常用的是二叉查找树。

二叉查找树

二叉查找树又称为二叉排序树或者二叉搜索树。

特点:

  • 每一个节点上最多有两个字节点。
  • 左子树上所有节点的值都小于根节点的值。
  • 右子树上所有节点的值都大于根节点的值。

二叉查找树存在的问题:

这样就变得像链表一样,查询速度变慢了,所以引入平衡二叉树

平衡二叉树

 平衡二叉树是在满足二叉查找树得大小规则下,让树尽可能矮小,以此提高查数据的性能。

  • 任意节点的左右两个子树的高度差不超过1,任意节点的左右两棵子树都是一颗平衡二叉树

平衡二叉树在添加元素后可能导致不平衡

  • 基本策略是进行左旋或者右旋保证平衡。

平衡二叉树旋转的四种情况:左左、左右、右右、右左

  • 左左:当根节点的左子树的左子树有节点插入,导致二叉树不平衡→采用右旋

  • 左右: 当根节点的左子树的右子树有节点插入,导致二叉树不平衡→先左旋再右旋

  • 右右: 当根节点的右子树的右子树有节点插入,导致二叉树不平衡→左旋

  • 右左:当根节点的右子树的左子树有节点插入,导致二叉树不平衡→先右旋再左旋 

红黑树

  • 是一种自平衡的二叉查找树
  • 每一个节点可以是红或者黑,红黑树不是通过高度平衡的,他的平衡是通过“红黑规则”进行实现的。

红黑规则

  • 每一个节点或是红色的,或是黑色,根节点必须是黑色
  • 如果一个节点没有子节点或者父节点,则该节点相应的指针属性值为NiL,这些NiL视为叶节点,叶节点是黑色的,如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)。
  • 对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。

添加节点:

  • 添加的节点的颜色,可以是黑色也可以是红色。
  • 默认用红色效率更高。

默认用黑色:

默认用红色: 

 

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

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

相关文章

Spark01 —— Spark基础

文章目录 Spark01 —— Spark基础一、为什么选择Spark?1.1 MapReduce编程模型的局限性1.2 Spark与MR的区别1.3 版本1.4 优势1.5 Spark其他知识1、多种运行模式2、技术栈3、spark-shell:Spark自带的交互式工具4、Spark服务 二、Spark的基础配置三、Spark实…

【蓝桥杯省赛真题42】python独立海域 中小学青少年组蓝桥杯比赛 算法思维python编程省赛真题解析

目录 python独立海域 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 七、 推荐资料 1、蓝桥杯比赛 2、考级资料 3、其它资料 python独立海域 第十三届蓝桥杯青少年组python省赛真题 一、题目要求 &…

【Java--数据结构】链表经典OJ题详解(下)

前言 上一篇 欢迎关注个人主页:逸狼 创造不易,可以点点赞吗~ 如有错误,欢迎指出~ 目录 前言 链表分割 链表的回文结构 相交链表 环形链表 链表分割 编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在…

品深茶的抗癌效果怎么样?

茶叶中的一些成分,如茶多酚、儿茶素等,具有抗氧化和抗炎作用,这些作用在一定程度上可以抑制癌细胞的生长和扩散。 然而,这些成分在茶叶中的含量和生物利用率会受到多种因素的影响,如茶叶的品种、制作工艺、饮茶方式等…

【Redis 开发】Lua语言

Lua Lua语法 Lua语法 Lua是一种小巧的脚本语言,底层用C语言实现,为了嵌入式应用程序中 官网:https://www.lua.org/ 创建lua文件 touch hello.lua 运行lua文件 lua hello.lua 输出语句 print("Hello World!")数据类型 可以通过t…

idea常用知识点随记

idea常用知识点随记 1. 打开idea隐藏的commit窗口2. idea中拉取Git分支代码3. idea提示代码报错,项目编译没有报错4. idea中实体类自动生成序列号5. idea隐藏当前分支未commit代码6. idea拉取新建分支的方法 1. 打开idea隐藏的commit窗口 idea左上角File→Settings…

java连锁美业收银系统源码-美业SaaS系统【微信小程序端】功能及应用场景介绍

博弈美业管理系统源码 连锁多门店美业收银系统源码 多门店管理 / 会员管理 / 预约管理 / 排班管理 / 商品管理 / 促销活动 PC管理后台、手机APP、iPad APP、微信小程序 ( 需要系统演示视频可联系观看 ) ▶ 顾客微信小程序端: 场景名称 场…

React配置@别名路径配置

1. 背景知识 路径解析配置(webpack),把 / 解析为 src/路径联想配置(VsCode),VsCode 在输入 / 时,自动联想出来对应的 src/下的子级目录 2. 路径解析配置 配置步骤: 安装craco npm …

利用Seaborn实现高级统计图表—python可视化

👽发现宝藏 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。【点击进入巨牛的人工智能学习网站】。 利用 Seaborn 实现高级统计图表 在数据可视化领域,Seaborn 是 Python 中一个备…

ArcGIS小技巧—坐标系匹配

坐标系:(Coordinate System):在一些书籍和软件中也叫做空间参考,简单来说,有了坐标系,我们才能够用一个或多个“坐标值”来表达和确定空间位置。没有坐标系,坐标值就无从谈起&#x…

c#数据库:1.c#创建并连接数据库

安装软件:SQL Server Management Studio Management Studio Visual Studio 2022 启动服务: 打开SQL Server Management Studio Management Studio ,连接到服务器(GUANZU是我的计算机名) 新建数据库,随便起个名字叫aq: c#代码: using System; using System.Collections.Gener…

Detla lake with Java--在spark集群上运行程序

昨天写了第一篇入门,今天看见有人收藏,继续努力学习下去。今天要实现的内容是如何将昨天的HelloDetlaLake 在spark集群上运行,。具体步骤如下 1、安装spark,我使用的是 spark-3.5.1-bin-hadoop3-scala2.13,去官网下载&#xff0c…

C++ 如何实现原子性

1.操作系统如何实现原子性 在单处理器,单核,运行多线程的情况下,我们不使用线程同步工具, 我们会出现,线程之间会互相抢夺,临界区的资源,造成数据不符合我们预期的结果, 后面再说解决办法,那么我们怎么帮助实现原子性 1 屏蔽中断,不让线程之间切换,让它完成再切换 2 底层硬…

Android CalendarView助你打造精美的Android日历应用

Android CalendarView助你打造精美的Android日历应用 1. 引言 移动应用中的日历功能对于用户来说至关重要,它不仅是时间管理的工具,还能帮助用户记录重要事件和安排活动。因此,一个高效、易用的日历控件对于移动应用的成功至关重要。 传统…

PaddlePaddle与OpenMMLab

产品全景_飞桨产品-飞桨PaddlePaddle OpenMMLab算法应用平台

windows平台安装labelme

之前写过一篇文章也是关于在windows平台安装labelme的:《windows平台python版labelme安装与使用_labelme下载-CSDN博客》,随着软件与工具的更新换代,按照同样的方法最近在使用的时候出现了错误,出现创建虚拟环境失败,具…

运维的利器–监控–zabbix–第二步:建设–部署zabbix agent--windows server系统--agent客户端安装部署

第一步:下载windows agent软件 第一点:zabbix官网针对linux和window系统有两种不同的安装方式,其中:windows为tar压缩包,根据你zabbix server安装的版本,在官网下载同样版本的agent软件。 amd64&#xff…

漂亮自适应APP下载页源码

漂亮自适应APP下载页源码,源码由HTMLCSSJS组成,记事本打开源码文件可以进行内容文字之类的修改,双击html文件可以本地运行效果,也可以上传到服务器里面 漂亮自适应APP下载页源码

公链系统开发全指南: 从规划到实施

在区块链技术的迅速发展和应用推广下,公链系统的开发成为了当前数字资产领域的热门话题。从规划到实施,公链系统的开发过程需要经历多个步骤,下文将详细介绍每个步骤。 第一步: 规划和设计 市场调研: 分析市场需求和竞争情况,确定…

preg_match详解(反向引用和捕获组)

在讲preg_match函数之前,我们先了解一下什么是php可变变量 php可变变量 在PHP中双引号包裹的字符串中可以解析变量,而单引号则不行 也就是在php中,双引号里面如果包含有变量,php解释器会将其替换为变量解释后的结果&#xff1b…