数据结构篇

常见数据结构

• 栈：先进后出。
• 队列：先进先出。
• 数组：查改快，增删慢
• 链表：查改慢，增删快。分为单向链表和双向链表；单向链表结点只记录其后驱结点，双向链表记录其前端和后续结点。
• 二叉树：分支不超过两个的有序树。
• 排序树/查找树：在二叉树的基础上，元素是有大小顺序的，左子树小，右子树大。
• 平衡树：左孩子和右孩子数量相等，查询速度非常快。
• 不平衡树：左孩子和右孩子数量不相等。
• 红黑树：趋近于平衡树，查询的速度非常的快，查询叶子结点最大次数和最小次数不能超过2倍。

栈

栈：stack,又称堆栈，它是运算受限的线性表，其限制是仅允许在表的一端进行插入和删除操作，不允许在其他任何位置进行添加、查找、删除等操作。

图示

特点

• 先进后出（存进去的元素，要在它后面的元素依次取出之后，才能取出改元素）。就好比弹夹，子弹压进弹夹，先压进去的子弹在下面，后压进来的子弹在上面，在开枪时，先弹出最上面的子弹，然后才能弹出下面的子弹。
• 栈的顶端位置是入口、出口。

队列

队列：queue,简称队，它同堆栈一样，也是一种运算受限的线性表，其限制是仅允许在表的一段进行插入，而在表的另一端进行删除。左进右出、右进左出、头进尾出、尾进头出等。

图示

特点

• 先进先出（存进去的元素，要在它前面的元素依次取出后，才能取出该元素）。就好比排队买票，先排队（入队列），后面的人需要等前面的人依次买完票（出队列），才能轮到后面的人，不允许插队。
• 队列的入口、出口各占一侧。

数组

数组：array,是有序的元素序列，数组是在内存中开辟一段连续的空间，并在此空间存放元素。就像是宿舍，有100间房间，从001到100依次给每个房间打上固定编号，通过编号就能快速找到对应的宿舍。

图示

特点

• 查找元素快：通过索引，可以快速访问指定位置的元素。
• 增删元素慢：

  • **指定索引位置增加元素：**需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根据索引，复制到新数据对应索引的位置。

    • 创建新数组，复制原数组中元素到新数组，新元素添加至末尾。

- 创建新数组，将新元素添加到指定位置，复制原数组中元素数据。

• **指定索引位置删除元素：**需要创建一个新数组，把原数组元素根据索引，复制到新数组对应索引的位置，原数组中指定索引位置元素不复制到新数组中。

  • 创建新数组，删除指定位置元素，复制其他元素到新数组。

链表

链表：linked list,由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。链表结构有单向链表和双向链表。
单向链表：每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
双向链表：每个结点包含三个部分：一个是存储数据元素的数据域，一个是存储下一个结点地址的指针域，最后一个是存储上一个结点地址的指针域。

图示

特点

• 多个结点之间，通过地址进行连接。例如，多个人手拉手，每个人使用自己的右手拉住下个人的左手，依次类推，这样多个人就连在一起了。
• 查找元素慢：想要查找某个元素，需要通过连接的结点，依次向后查找指定元素。
• 增删元素快：
  • 增加元素：只需要修改连接下个元素的地址即可。
    • 起始位置增加元素：

- 中间位置增加元素：

- 末尾位置增加元素：

• 删除元素：只需要修改连接下个元素的地址即可。

  • 起始位置删除元素

- 中间位置删除元素：

- 末尾位置删除元素：

二叉树

二叉树：binary tree,是每个节点不超过2的有序树（tree）。
类似于我们生活中树的结构，只不过每个结点上都最多只能有两个子结点，且根节点从顶部开始。
二叉树是每个结点最多有两个子树的树结构。顶上的叫根节点，两边被称为“左子树”和“右子树”。

图示

特点

• 每个结点最多有两个子树的树结构。

排序树/查找树

排序树/查找树：Binary Sort Tree/Binary Search Tree在二叉树的基础上，元素是有大小排序的，查询效率比链表结构要高。。
左子树小，右子树大

图示

特点

• 元素是有大小排序的。
• 左、右子树也分别为二叉排序树。
• 左子树小，右子树大。
• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
• 若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
• 没有键值相等的结点。

平衡树

平衡树：Balance Tree,左孩子数量和右孩子数量相等。

图示

特点

• 左孩子数量和右孩子数量相等。

不平衡树

不平衡树：Unbalance Tree,跟平衡树相对，左孩子数量和右孩子数量不相等。

图示

特点

• 左孩子数量和右孩子数量不相等。

红黑树

红黑树：Red Black Tree,是一种特化的AVL树（平衡二叉树）,本身就是一颗二叉查找树，树的键值依然是有序的。
对于红黑树有一定的约束：
1.节点可以是红色的或者是黑色的
2.根节点是黑色的
3.叶子节点（空节点）是黑色的（NIL）
4.每个红色节点的子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）
5.任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

图示

特点

• 速度特别快,趋近平衡树。

• 查找叶子元素最少和最多次数不多于二倍（从根到叶子的最长路径不会超过最短路径得当2倍）。

• 当插入或删除节点时，往往会打破这种规则，为了保持这种平衡通常需要一些调整，调整有两种方法：[变色]和[旋转]。而旋转又分为两种形式：[左旋转]和[右旋转]

  • 变色：为了重新复核红黑树的规则，尝试把红色节点变为黑色，或者把黑色节点变为红色。

    • 出现连续红色，需要变色调整，但往往变色都是一系列连锁变色的，如下图

• 旋转：

  • 左旋转：连续两个红色，但是因为13为黑色，所以17无法变成黑色，因此需要进行左旋转，再进行变色
    
    

  • 右旋：因为上面左旋转完之后,其中（17 -> 8 ->6 ->NIL）的黑色节点个数是4，不符合（任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同），这时需要把13进行右旋转，再进行变色。