数据结构简析:栈、队列、数组、链表、红黑树。

2021年9月2日 7点热度 0条评论 来源: JinxLin

数据结构

数据结构,直白地理解,就是研究数据的存储方式。
今天简单的分享几个最重要的数据结构方式。
1.栈
2.队列
3.数组
4.链表
5.树,红黑树

栈(Stack)

栈是一种只能从表的一端存取数据且遵循 “先进后出” 原则的线性存储结构。如图,它的这种存储结构就跟弹夹很相似,先进去的,最后出来。

队列(Queue)

队列的两端都"开口",要求数据只能从一端进,从另一端出,队列中数据的进出要遵循 “先进先出” 的原则,即最先进队列的数据元素,同样要最先出队列。

数组

数组与顺序表、链表、栈和队列一样,都用来存储具有 “一对一” 逻辑关系数据的线性存储结构。它的特点就是:查询容易,增删难。

链表

链表存储的数据元素,其物理存储位置是随机的。
链表中每个数据的存储都由以下两部分组成
数据元素本身,其所在的区域称为数据域;
指向直接后继元素的指针,所在的区域称为指针域;
一个完整的链表需要由以下几部分构成
头指针:一个普通的指针,它的特点是永远指向链表第一个节点的位置。很明显,头指针用于指明链表的位置,便于后期找到链表并使用表中的数据;
节点:链表中的节点又细分为头节点、首元节点和其他节点:
头节点:其实就是一个不存任何数据的空节点,通常作为链表的第一个节点。对于链表来说,头节点不是必须的,它的作用只是为了方便解决某些实际问题;
首元节点:由于头节点(也就是空节点)的缘故,链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓,没有实际意义;
其他节点:链表中其他的节点;
他还分为单向链表和双向链表
单向链表:是指链表中只有一条链子链接,没有顺序
双向链表:指链表中有两个链子,一个存储元素,另一个记录顺序。

将具有“一对多”关系的集合中的数据元素的形式进行存储,整个存储形状在逻辑结构上看,类似于实际生活中倒着的树,所以称这种存储结构为“树型”存储结构。
结点:使用树结构存储的每一个数据元素都被称为“结点”。
二叉树:
简单地理解,满足以下两个条件的树就是二叉树:
本身是有序树;
树中包含的各个节点的度不能超过 2,即只能是 0、1 或者 2;
二叉树具有以下几个性质:
二叉树中,第 i 层最多有 2i-1 个结点。
如果二叉树的深度为 K,那么此二叉树最多有 2K-1 个结点。
二叉树中,终端结点数(叶子结点数)为 n0,度为 2 的结点数为 n2,则 n0=n2+1。
红黑树:
红黑树(Red Black Tree) 是一种自平衡二叉查找树.它的查询速度非常的快,查询叶子节点的最大次数,不超过最小次数的2倍。
特征:
红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色. 在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:
性质1 节点是红色或黑色。
性质2 根节点是黑色。
性质3 所有叶子都是黑色。(叶子是NIL节点)
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。
是性质4导致路径上不能有两个连续的红色节点确保了这个结果。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。
因为红黑树是一种特化的二叉查找树,所以红黑树上的只读操行与普通二叉查找树相同。
树的旋转
当我们在对红黑树进行插入和删除等操作时,对树做了修改,那么可能会违背红黑树的性质。
为了保持红黑树的性质,我们可以对相关节点做一系列的调整,通过对树进行旋转。(为了保持他的五个特性)
旋转分为:左旋和右旋。
左旋:逆时针旋转两个节点,让一个节点被其右子节点取代,而该节点成为右子节点的左子节点
右旋:顺时针旋转两个节点,让一个节点被其左子节点取代,而该节点成为左子节点的右子节点
这里我们举个例子:
现在要删除这个红黑树中的17元素

由于结点17有两个孩子,子树当中仅大于17的结点是25,所以把结点25复制到17位置,保持黑色,然后将原来的25就可以删除了。

现在的这种情况的树,明显不满足红黑树中的特性,这时它就会发生右旋,进行平衡。因为16介于15与25之间所以作为分支。

    原文作者:JinxLin
    原文地址: https://blog.csdn.net/JinxLin/article/details/107892406
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。