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

这篇具有很好参考价值的文章主要介绍了Java常见的数据结构:栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、数据结构

1.数据结构概述

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

通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率

2.常见的数据结构

队列

数组

链表

二叉树

二叉查找树

平衡二叉树

红黑树...


二、栈

1.栈数据结构的执行特点

后进先出,先进后出

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

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

数据进入栈模型的过程称为:压/进栈: 

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

 数据离开栈模型的过程称为:弹/出栈:

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

 三、队列

队列的执行特点

先进先出,后进后出

例子:买票:谁先买票谁先离开队列

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

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

 数据从后端进入队列模型的过程称为:入队列

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

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

 数据从前端离开队列模型的过程称为:出队列

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

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

 四、数组

数组的特点

数组是一种查询快,增删慢的模型。

查询速度快:查询数据通过地址值和索引定位,查询任意数据耗时相同。(元素在内存中是连续存储的)

删除效率低:要将原始数据删除,同时后面每个数据前移。

添加效率极低:添加位置后的每个数据后移,再添加元素。

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

 五、链表的特点

链表的特点

链表是一种查询慢,增删快的模型(对比数组)

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

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

 添加一个链表:

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

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

  链表增删数据相对会快。

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

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

 链表的种类:

单向链表

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

 双向链表

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

六、二叉树和二叉查找树

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

A节点是BC的父节点

BC是A的子结点

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

 1.二叉树的特点

只能有一个根节点,每个节点最多支持2个直接子节点

节点的度:节点拥有的子树的个数,二叉树的度不大于2叶子节点度为0的节点,也称之为终端结点。

高度:叶子结点的高度是1,叶子结点的父节点高度为2,以此类推,根节点的高度最高。

层:根节点在第一层,以此类推

兄弟节点:拥有共用父节点的节点互称为兄弟节点

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

 2.二叉查找树

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

1.特点:

1,每一个节点上最多有两个子节点

2.左子树上所有节点的值都小于根节点的值

3.右子树上所有节点的值都大于根节点的值

二叉查找树是一种增删改查都很快的模型

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

 开发中会用二叉查找树很多,因为小的会往左边走,大的会往右边走。普通的二叉树没啥规律,不经常使用

2.二叉查找树添加节点

例子:

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

 规则:

小的存左边

大的存右边

一样的不存

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

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

 3.平衡二叉树

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

例子:

将上面的节点按照二叉查找树的规则存入

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

 得到结果:

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

 注意:这虽然还是二叉查找树,但是出现了瘸子现象,已经不能做二分算法,已经变成链表了,那么查询的速度就慢了下来

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

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

平衡二叉树的要求

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

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

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

基本策略就是进行左旋,或者右旋保持平衡

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

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

左左:

当根节点左子树的左子树有节点插入,导致二叉树不平衡

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

目前是一个正常的二叉平衡树

如果加1,就不平衡了 

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

 这个时候,就需要进行右旋操作:

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

 左右:

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

平衡的:

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

 如果加入一个6,就又不平衡了:

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

找到出问题的那条线进行左旋操作,变成左左;

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

 然后,再整体右旋,就变成平衡的了

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

  右右:

当根节点右子树的右子树右有节点插入,导致二叉树不平衡

平衡的:

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

 增加一个12,不平衡了

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

 整体左旋操作,一步到位

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

右左 :

平衡的:

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

 增加一个8,变成不平衡的:

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

先左旋:

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

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

左旋完还不够 ,以有问题的这根线进行右旋操作,变成右右

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

 整体再左旋,就平衡了

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

 七、红黑树

1.红黑树概述

红黑树是一种自平衡的二叉查找树,是计算机科学中用到的一种数据结构。

1972年出现,当时被称为平衡二叉B树。1978年被修改尾如今的红黑树;

每个节点都可以是红或者黑;红黑树不是通过高度平衡的,它的平衡是通过“红黑规则”进行实现。

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

红黑规则:

每一个节点或是红色的,或者是黑色的,根节点必须是黑色。

如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)。

对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。

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

添加节点:

添加的节点的颜色,可以说红色的,也可以是黑色的。

默认用红色效率高。

默认用黑色,插入18,比2小,插入左边,发现黑节点过多,需要调整了

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

黑色太多,调成红色 

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

 插入23,默认用黑色,插入右边,又发现黑节点过多,又需要调整

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

黑色过多,调成红色

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


插入一个20,默认用红色

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

 然后插入18和23,就会变成默认红色,18插入左子树,23插入右子树,这样发现,不需要调整了

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

红黑树增删改查的性能都很不错

总结:

各种数据结构的特点和作用是什么?

队列:

先进先出,后进后出

栈:

后进先出,先进后出

数组:

内存连续区域,根据索引查询快,增删慢

链表:

元素是游离的,查询慢,双向链表首尾操作极快

二叉树:

永远只有一个根节点,每个节点不超过2个子节点的树

二叉查找树:

小的左边,大的右边,但是可能树会变得很高,查询性能变差

平衡查找二叉树:

让树的高度差不大于1,增删改查都提高了

红黑树:

基于红黑规则实现了自平衡的排序二叉树文章来源地址https://www.toymoban.com/news/detail-467943.html

到了这里,关于Java常见的数据结构:栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 常见的数据结构(顺序表、顺序表、链表、栈、队列、二叉树)

    线性表(Linear List)     1.什么是线性表     2.线性表的特点     3.线性表的基本运算 顺序表     1.什么是顺序表     2.时间复杂度: 链表     1.什么是链表     2.单向链表     3. 双向链表     4.ArrayList和LinkedList的使用 栈Stack     1.什么是栈     2.栈的基本方法 队列Queue

    2024年02月13日
    浏览(35)
  • 数据结构之线性表的类型运用Linear Lists: 数组,栈,队列,链表

    定义 一个最简单,最基本的数据结构。一个线性表由多个相同类型的元素穿在一次,并且每一个元素都一个前驱(前一个元素)和后继(后一个元素)。 线性表的类型 常见的类型:数组、栈、队列、链表 这些不同数据结构的特性可以解决不同种类的问题 题面 题目描述 有

    2024年02月12日
    浏览(44)
  • 【Java数据结构】顺序表、队列、栈、链表、哈希表

    是一个有类型参数(type parameter)的范型表(generic class) 能够自动调整容量,并且不需要写额外的代码 存放数据使用数组但是可以编写一些额外的操作来强化为线性表,底层依然采用顺序存储实现的线性表,称为顺序表 创建 常见操作 一旦确认数组列表大小恒定,不再发生

    2024年02月02日
    浏览(41)
  • Java 数据结构篇-用链表、数组实现栈

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 栈的说明         2.0 用链表来实现栈         2.1 实现栈 - 入栈方法(push)         2.2 实现栈 - 出栈(pop)         2.3 实现栈 - 查看栈顶元素(peek)         2.4 实

    2024年02月05日
    浏览(56)
  • Java 数据结构篇-用数组、堆实现优先级队列

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍    文章目录         1.0 优先级队列说明         2.0 用数组实现优先级队列         3.0 无序数组实现优先级队列         3.1 无序数组实现优先级队列 - 入队列 offer(E value)         3.2 无序数组实现优先

    2024年02月04日
    浏览(43)
  • 数据结构01-线性结构-链表栈队列-队列篇

    本系列为C++数据结构系列,会介绍 线性结构,简单树,特殊树,简单图等。本文为线性结构部分。 线性结构 【 3 】链表:单链表、双向链表、循环链表 【 3 】栈 【 3 】队列 队列(Queue)与栈一样,是一种线性存储结构,它具有如下特点: (1)队列中的数据元素遵循“先进

    2024年02月16日
    浏览(36)
  • 数据结构,队列,顺序表队列,链表队列

            队列是一种常见的数据结构,它具有先进先出(First-In-First-Out,FIFO)的特性,类似于排队等候的场景。以下是队列的要点: 1. 定义:队列是一种线性数据结构,由一系列元素组成,可以进行插入和删除操作。插入操作(称为入队)只能在队列的末尾进行,删除操

    2024年02月11日
    浏览(38)
  • 【数据结构】栈和队列(链表模拟队列)

      学习本章节必须具备 单链表的前置知识, 建议提前学习:点击链接学习:单链表各种功能函数 细节 详解 本章节是学习用 单链表模拟队列 1. 单链表实现队列 思路如下 队列:只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先 进先出

    2024年04月27日
    浏览(42)
  • 数据结构01-线性结构-链表栈队列-栈篇

    线性结构-栈 本系列为C++数据结构系列,会介绍 线性结构,简单树,特殊树,简单图等。本文为线性结构部分。 线性结构 【 3 】链表:单链表、双向链表、循环链表 【 3 】栈 【 3 】队列 栈是Stack一个后进先出Last In First Out,LIFO的线性表,他要求只在表尾对数据执行删除和插

    2024年02月16日
    浏览(38)
  • Python数据结构与算法-数据结构(列表、栈、队列、链表)

    数据结构是指相互之间存在这一种或者多种关系的数据元素的集合和该集合中元素之间的关系组成。 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字典等都是一种数据结构。 N.Wirth:“程序=数据结构+算法” 数据结构按照其 逻辑结

    2024年02月08日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包