数据结构的中文翻译

链表

在计算机科学中，链表是数据元素的线性集合，其中线性顺序不是由它们在内存中的物理位置所给出的。相反，每个元素指向下一个元素。它是由一组节点组成的数据结构，这些节点一起表示一个序列。在最简单的形式下，每个节点由数据和指向序列中下一个节点的引用(换句话说，链接)组成。这种结构允许在迭代过程中从序列的任何位置高效地插入或删除元素。更复杂的变体添加额外的链接，允许有效地插入或删除任意元素引用。链表的一个缺点是访问时间是线性的(并且很难进行流水线操作)。更快的访问，如随机访问，是不可行的。与链表相比，数组具有更好的缓存局部性。

队列

在计算机科学中,一个队列是一种特殊的抽象数据类型或集合的实体集保存在秩序和原则(或)操作集合的实体后终端位置,称为排队,从前面和删除实体终端位置,称为出列。这使队列成为先进先出(FIFO)数据结构。在FIFO数据结构中，添加到队列的第一个元素将是要删除的第一个元素。这等价于一旦添加了一个新元素，之前添加的所有元素都必须在新元素删除之前删除。通常还会输入一个peek或front操作，返回front元素的值，而不需要对其进行排序。队列是线性数据结构的一个例子，或者更抽象地说是顺序集合。

表示一个FIFO(先入先出)队列:

堆栈

在计算机科学中，堆栈是一种抽象的数据类型，作为元素的集合，有两个主要操作:

push，将元素添加到集合中

pop，它删除了尚未删除的最近添加的元素。
元素从堆栈中出来的顺序产生了它的替代名称LIFO(最后一个进入，首先退出)。此外，peek操作可以在不修改堆栈的情况下访问顶部。这种类型的结构“堆栈”这个名字来自于类比一组物理产品堆叠在彼此之上,这使得它很容易把一件事情从堆栈的顶部,在开始一个项目深入堆栈可能需要多个其他项目第一次起飞
栈运行时的简单表示，带有push和pop操作。

哈希表

在计算中，哈希表是实现关联数组抽象数据类型的数据结构，可以将键映射到值。哈希表使用哈希函数将索引计算到桶或槽数组中，从中可以找到所需的值

理想情况下，哈希函数会将每个键分配给一个唯一的桶，但是大多数哈希表设计都使用不完美的哈希函数，这可能导致哈希函数为多个键生成相同的索引，从而导致哈希冲突。这种碰撞必须以某种方式加以适应。

通过单独的链接解决哈希冲突:

堆(数据结构)

在计算机科学中,堆是专门的树型数据结构,满足堆属性:如果P是C的父节点,那么关键(P值)是大于或等于(max堆)或小于或等于(在一个最小堆)C的关键节点的“顶级”堆(没有父母)称为根节点。

优先队列

在计算机科学中，优先级队列是一种抽象数据类型，它类似于常规队列或堆栈数据结构，但是每个元素都有与之相关联的“优先级”。在优先级队列中，高优先级的元素在低优先级的元素之前被服务。如果两个元素具有相同的优先级，则根据它们在队列中的顺序提供服务。

虽然优先级队列通常使用堆实现，但它们在概念上与堆是不同的。优先队列是一个抽象概念，如“列表”或“地图”;正如可以使用链表或数组实现列表一样，可以使用堆或其他方法(如无序数组)实现优先级队列。

字典树

在计算机科学中，trie也称为数字树，有时也称为基数树或前缀树(可以用前缀搜索)，是一种搜索树——一种有序的树数据结构，用于存储动态集或关联数组，其中的键通常是字符串。与二叉搜索树不同，树中没有节点存储与该节点关联的键;相反，它在树中的位置定义了关联的键。节点的所有后代都有与该节点相关联的字符串的公共前缀，而根则与空字符串相关联。值不一定与每个节点相关联。相反，值往往只与叶子和一些与感兴趣的键相对应的内部节点相关联。有关前缀树的空间优化表示，请参见紧凑前缀树。

树

二叉搜索树
AVL树

在计算机科学中，树是一种广泛使用的抽象数据类型(ADT)——或实现此ADT的数据结构——它模拟一个层次树结构，具有根值，子树带有父节点，表示为一组链接节点。
树的数据结构可以定义递归(本地)作为节点的集合(从根节点开始),其中每个节点是一种数据结构组成的一个值,与参考节点的列表(“孩子”),与约束,没有引用是重复的,没有根。

一个简单的无序树;在这个图中，标记为7的节点有两个子节点，标记为2和6，一个父节点标记为2。顶部的根节点没有父节点。

二叉搜索树

在计算机科学中，二叉搜索树(BST)，有时被称为有序或排序的二叉树，是一种特殊类型的容器:数据结构，在内存中存储“项目”(如数字、名称等)。它们允许快速查找、添加和删除项，并且可以用于实现动态项集，或者查找表，以便按键查找项(例如，按人名查找某人的电话号码)。

二叉搜索树保持键排序顺序,以便查找和其他操作可以使用二分查找的原则:在寻找钥匙在树上(或插入一个新的密钥)的地方,他们遍历这棵树从根到叶,使比较键存储在树的节点和决定,比较的基础上,继续向左或向右子树中搜索。平均而言，这意味着每次比较都允许操作跳过树的大约一半，因此每次查找、插入或删除所花费的时间与树中存储的项的数量的对数成正比。这比在一个(未排序的)数组中按键查找项所需的线性时间要好得多，但比在哈希表上对应的操作要慢。

一个大小为9和深度为3的二叉搜索树，根为8。树叶没有被画出来。

AVL树

在计算机科学中，AVL树(以发明者Adelson-Velsky和Landis命名)是一种自平衡的二叉搜索树。这是第一个被发明的数据结构。在AVL树中，任何节点的两个子树的高度在最多的时候是不同的;如果在任何时候，它们之间的差异不止一个，那么重新平衡就是为了恢复这一资产。查找、插入和删除在平均和最坏的情况下都需要O(log n)时间，其中n是操作之前树中的节点数。插入和删除可能需要树被一个或多个树旋转重新平衡。

显示在AVL树中插入几个元素的动画。它包括左、右、左、右和左旋转。

AVL树平衡因子(绿色)

AVL树旋转

Left-Left Rotation

Right-Right Rotation

Left-Right Rotation

Right-Left Rotation

红黑树

红黑树是计算机科学中的一种自平衡二叉搜索树。
二叉树的每个节点都有一个额外的位，这个位通常被解释为节点的颜色(红色或黑色)。
这些颜色位用于确保树在插入和删除过程中保持近似平衡。

平衡是通过用两种颜色中的一种来绘制树的每个节点，以满足某些属性，这些属性共同限制了树在最坏情况下的不平衡程度。
当修改树时，新树随后被重新排列并重新绘制，以恢复着色属性。
这些属性的设计方式使重新排列和重新上色能够有效地进行。

树的平衡并不完美，但是它足够好，可以保证在O(log n)时间内进行搜索，其中n是树中元素的总数。
插入和删除操作以及树的重新排列和重新上色也在O(log n)时间内执行。

红黑树的一个例子:

属性

除了对二叉搜索树施加的要求之外，红黑树还必须满足以下条件:

每个节点要么是红色的，要么是黑色的。
根是黑色的。这条规则有时被省略。因为根总是可以从红色变为黑色，但也不一定相反，这个规则对分析没有什么影响。
所有的叶子(NIL)都是黑色的。
如果一个节点是红色的，那么它的子节点都是黑色的。
从给定节点到其任何子代NIL节点的每条路径都包含相同数量的黑节点。

一些定义:从根节点到节点的黑节点数是节点的黑深度;
从根到叶的所有路径中黑色节点的统一数量称为红黑树的黑高度。

这些约束强化了红黑树的一个关键属性:从根到最远叶子的路径不超过从根到最近叶子的路径的两倍。
结果是，这棵树大概是高度平衡的。
由于插入、删除和查找值等操作需要最坏情况下的时间与树的高度成正比，因此在最坏情况下，与普通的二叉搜索树不同，红黑树在树的高度上的理论上界允许红黑树高效工作。

平衡插入

If uncle is RED

If uncle is BLACK

Left Left Case (p is left child of g and x is left child of p)
Left Right Case (p is left child of g and x is right child of p)
Right Right Case (p is right child of g and x is right child of p)
Right Left Case (p is right child of g and x is left child of p)

– Left Left Case (See g, p and x)

– Left Right Case (See g, p and x)

– Right Right Case (See g, p and x)

– Right Left Case (See g, p and x)

图(有向图与无向图)

在计算机科学中，图是一种抽象的数据类型，用于实现数学中的无向图和有向图概念，特别是图论领域

图数据结构由一个有限的(且可能是可变的)顶点或节点或点集组成，以及一组非向图或一组有向图的有序对。
这些对称为无向图的边、弧或线，以及有向图的箭头、有向边、有向弧或有向线。
顶点可以是图结构的一部分，也可以是由整数索引或引用表示的外部实体。

并查集

非联合集数据结构(也称为单点查找数据结构或合并查找集)是一种数据结构，它跟踪一组划分为若干不相交(不重叠)子集的元素。
它提供near-constant-time操作(由阿克曼的逆函数有界)添加新的集,合并现有集,并确定是否在同一组元素。除了许多其他用途(请参见应用部分),分离集扮演着一个关键角色,克鲁斯卡算法寻找图的最小生成树。

MakeSet创建8单例

在联合的一些操作之后，一些集合被分组在一起。