一、数据结构
1.数据结构概述
数据结构是计算机底层存储、组织数据的方式。是指数据相互之间是以什么方式排列在一起的。
通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率
2.常见的数据结构
栈
队列
数组
链表
二叉树
二叉查找树
平衡二叉树
红黑树...
二、栈
1.栈数据结构的执行特点
后进先出,先进后出
数据进入栈模型的过程称为:压/进栈:
数据离开栈模型的过程称为:弹/出栈:
三、队列
队列的执行特点
先进先出,后进后出
例子:买票:谁先买票谁先离开队列
数据从后端进入队列模型的过程称为:入队列
数据从前端离开队列模型的过程称为:出队列
四、数组
数组的特点
数组是一种查询快,增删慢的模型。
查询速度快:查询数据通过地址值和索引定位,查询任意数据耗时相同。(元素在内存中是连续存储的)
删除效率低:要将原始数据删除,同时后面每个数据前移。
添加效率极低:添加位置后的每个数据后移,再添加元素。
五、链表的特点
链表的特点
链表是一种查询慢,增删快的模型(对比数组)
链表中的元素是在内存中不连续存储的,每个元素节点包含数据值和下一个元素的地址。
添加一个链表:
链表查询慢,无论查询哪个数据都要从头开始找。
链表增删数据相对会快。
链表的种类:
单向链表
双向链表
六、二叉树和二叉查找树
A节点是BC的父节点
BC是A的子结点
1.二叉树的特点
只能有一个根节点,每个节点最多支持2个直接子节点
节点的度:节点拥有的子树的个数,二叉树的度不大于2叶子节点度为0的节点,也称之为终端结点。
高度:叶子结点的高度是1,叶子结点的父节点高度为2,以此类推,根节点的高度最高。
层:根节点在第一层,以此类推
兄弟节点:拥有共用父节点的节点互称为兄弟节点
2.二叉查找树
二叉查找树又称二叉排序树或者二叉搜索树
1.特点:
1,每一个节点上最多有两个子节点
2.左子树上所有节点的值都小于根节点的值
3.右子树上所有节点的值都大于根节点的值
二叉查找树是一种增删改查都很快的模型
开发中会用二叉查找树很多,因为小的会往左边走,大的会往右边走。普通的二叉树没啥规律,不经常使用
2.二叉查找树添加节点
例子:
规则:
小的存左边
大的存右边
一样的不存
3.平衡二叉树
平衡二叉树是在满足查找二叉树的大小规则下,让树尽可能矮小,以此来提高查数据的性能。
例子:
将上面的节点按照二叉查找树的规则存入
得到结果:
注意:这虽然还是二叉查找树,但是出现了瘸子现象,已经不能做二分算法,已经变成链表了,那么查询的速度就慢了下来
使用平衡二叉树:
平衡二叉树是在满足查找二叉树的大小规则下,让树尽可能矮小,以此来提高查数据的性能
平衡二叉树的要求
任意节点的左右个子树的高度差不超过1,任意节点的左右两个子树都是一个平衡二叉树。
平衡二叉树在添加元素后可能导致不平衡
基本策略就是进行左旋,或者右旋保持平衡
平衡二叉树旋转的四种情况:
左左:
当根节点左子树的左子树有节点插入,导致二叉树不平衡
目前是一个正常的二叉平衡树
如果加1,就不平衡了
这个时候,就需要进行右旋操作:
左右:
当根节点左子树的右子树有节点插入,导致二叉树不平衡
平衡的:
如果加入一个6,就又不平衡了:
找到出问题的那条线进行左旋操作,变成左左;
然后,再整体右旋,就变成平衡的了
右右:
当根节点右子树的右子树右有节点插入,导致二叉树不平衡
平衡的:
增加一个12,不平衡了
整体左旋操作,一步到位
右左 :
平衡的:
增加一个8,变成不平衡的:
先左旋:
左旋完还不够 ,以有问题的这根线进行右旋操作,变成右右
整体再左旋,就平衡了
七、红黑树
1.红黑树概述
红黑树是一种自平衡的二叉查找树,是计算机科学中用到的一种数据结构。
1972年出现,当时被称为平衡二叉B树。1978年被修改尾如今的红黑树;
每个节点都可以是红或者黑;红黑树不是通过高度平衡的,它的平衡是通过“红黑规则”进行实现。
红黑规则:
每一个节点或是红色的,或者是黑色的,根节点必须是黑色。
如果某一个节点是红色,那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)。
对每一个节点,从该节点到其所有后代叶节点的简单路径上,均包含相同数目的黑色节点。
添加节点:
添加的节点的颜色,可以说红色的,也可以是黑色的。
默认用红色效率高。
默认用黑色,插入18,比2小,插入左边,发现黑节点过多,需要调整了
黑色太多,调成红色
插入23,默认用黑色,插入右边,又发现黑节点过多,又需要调整
黑色过多,调成红色
插入一个20,默认用红色
然后插入18和23,就会变成默认红色,18插入左子树,23插入右子树,这样发现,不需要调整了
红黑树增删改查的性能都很不错
总结:
各种数据结构的特点和作用是什么?
队列:
先进先出,后进后出
栈:
后进先出,先进后出
数组:
内存连续区域,根据索引查询快,增删慢
链表:
元素是游离的,查询慢,双向链表首尾操作极快
二叉树:
永远只有一个根节点,每个节点不超过2个子节点的树
二叉查找树:
小的左边,大的右边,但是可能树会变得很高,查询性能变差
平衡查找二叉树:
让树的高度差不大于1,增删改查都提高了
红黑树:文章来源:https://www.toymoban.com/news/detail-467943.html
基于红黑规则实现了自平衡的排序二叉树文章来源地址https://www.toymoban.com/news/detail-467943.html
到了这里,关于Java常见的数据结构:栈、队列、数组、链表、二叉树、二叉查找树、平衡二叉树、红黑树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!