数据结构常见问题系列(二)

柔情只为你懂 2022-11-22 10:22 185阅读 0赞

### 文章目录 ###

*   *  1. 常用数据结构
     *  2. 什么是链表、队列、栈
     *  3. 什么是树（平衡二叉树、二叉排序树、B树、B+树、R树、红黑树）

## 1. 常用数据结构 ##

1). 数组：顺序存储，随机访问。 链表：链表存储，顺序访问。  
2). 栈：分为栈顶和栈底，遵循先进后出的原则。  
3). 队列： 先进先出原则(类比成排队一样)。  
4). 树：二叉树、平衡二叉树、大、小顶堆等。  
5). 图：最短路径，关键路径。

--------------------

## 2. 什么是链表、队列、栈 ##

**链表：**

当需要存储多个相同数据类型的时候，可以使用数组存储，数组可以通过下标直接访问，但数组有个缺点就是无法动态的插入或删除其中的元素（特别是操作第一个位置上的元素），而链表弥补了这个缺陷，对于元素的插入和删除操作是很方便的，不过访问元素的“性能”就差很多了。

所谓单链表，即只有一个指针，指向下一个元素（结点）的地址，只要知道单链表的首地址，就可以遍历整个链表了。由于链表结点是在堆区动态申请的，其地址并不是连续的，因此无法进行随机访问，只有通过前一结点的next指针才能定位到下一个结点的指针。

单链表只能向后遍历，不能逆序遍历，所以有了使用更广泛的双链表。即结点多了一个存储前一个结点地址的prev指针。双链表可以双向遍历，但也只能按顺序访问。

**队列：**

队列就像我们平时排队一样，按照数据到达的顺序进行排队，每次新插入的一个结点排在队尾，删除一个结点只能从头才能出队。简言之，对元素的到达顺序，按照“先进先出”的原则。由于队列频繁的插入和删除，一般为了高效，使用固定长度的数组实现，并且可循环使用数组空间，在操作之前要判断处理的队列是否已满或为空。如果要动态长度，可以用链表实现，只要同时记住链表的首地址（队头front）和尾地址（队尾rear）。

**栈：**

栈的特点正好与队列相反，按照数据进栈的逆序出栈，即“先进后出”，每次入栈将元素放在栈顶，出栈时也只能从栈顶出栈，与队列类似，一般用定长数组存储栈元素，而不是动态的申请结点空间。进栈一般被叫做压栈，出栈被叫做弹栈。

由于压栈弹栈都在栈顶，所以只需要一个size字段存储当前栈的大小，初始化size为0，每次压栈时，size+1，注意栈是否已满,弹栈则size-1。

--------------------

## 3. 什么是树（平衡二叉树、二叉排序树、B树、B+树、R树、红黑树） ##

为什么会有树这个概念呢？因为已有的数据结构（数组、链表）不能很好的平衡静态操作和动态操作的时间开销。

<table> 
 <thead> 
  <tr> 
   <th>时间复杂度</th> 
   <th>数组</th> 
   <th>链表</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>静态操作(查找)</td> 
   <td>O(1)</td> 
   <td>O(n)</td> 
  </tr> 
  <tr> 
   <td>动态操作(插入、删除)</td> 
   <td>O(n)</td> 
   <td>O(1)</td> 
  </tr> 
 </tbody> 
</table>

对于树这种数据结构而言，最显著的特点就是有且只能有一个根节点（空树除外），每个节点可以有多个子结点，除了根结点，其他结点只能有一个父结点。树的种类繁多，一般谈论的最多的是二叉树，每个结点有不超过两个的子结点。

**平衡二叉树&二叉排序树**

二叉排序树（Binary Search Tree，BST，也叫二叉搜索树），构造一棵二叉排序树也很简单，大于根节点的放在根节点的右子树上，小于根结点的放在根结点的左子树上（等于根结点的视情况而定）。如果写程序的话，可以采用递归的方式，而且由于不存在重叠子问题的情况，因此递归的性能已经足够好(不考虑栈溢出的情况)。

二叉排序树在通常情况下可以达到O(lgn)的静态、动态操作的时间复杂度，但是存在一种特殊情况，若输入的本来就是有序的，这时二叉树就退化成了链表。为了消除二叉树对于输入的敏感特性，引入了平衡二叉树（AVL），事实上平衡二叉树应该叫平衡二叉排序树也合理。平衡二叉树只要保证每个节点左子树和右子树的高度差小于等于1就可以了。

**B树 & B+树**

操作系统中，寄存器的访问速度和容量是此消彼涨的，速度最快的当属CPU上的寄存器，然后就是cache（高速缓存），然后是内存，再就是外部磁盘等，当两个处在不同层级的存储器（比如内存和外部磁盘）交换数据时，我们称之为I/O。而I/O相当耗时，要尽量避免使用。

B树（B-Tree，“B-树”这种翻译我不是很认同）的出现就是为了解决这个问题。B树由于是多路二叉树（根结点有两个子结点，其他结点子结点不止两个），它的高度要远低于平衡二叉树，一般来讲，二叉平衡树每下降一层就执行一次磁盘I/O操作，以1GB数据为例，平均需要30次磁盘I/O才能读取到数据，而B树每下降一层，每个结点都会读入多个关键码，因此B树适用于实现磁盘的读写逻辑。

B 树是为了磁盘或其它存储设备而设计的一种多叉（相对于二叉树，B树每个内结点有多个分支，即多叉平衡排序树。与下面要介绍的红黑树很相似，但在降低磁盘I/O操作方面要更好一些。许多数据库系统都一般使用B树或者B树的变形结构（如B+树）来存储信息。

**R树**

处理空间存储问题，R树在数据库等领域做出的功绩是非常显著的。它很好的解决了在高维空间搜索等问题。举个R树在现实领域中能够解决的例子：查找20英里以内所有的餐厅。如果没有R树你会怎么解决？一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中，一个字段记录经度，另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息，然后计算是否满足要求。如果一个地区有100家餐厅的话，我们就要进行100次位置计算操作了，如果应用到谷歌地图这种超大数据库中，这种方法便必定不可行了。

R树就很好的解决了这种高维空间搜索问题。它把B树的思想很好的扩展到了多维空间，采用了B树分割空间的思想，并在添加、删除操作时采用合并、分解结点的方法，保证树的平衡性。因此，R树就是一棵用来存储高维数据的平衡树。

每个R树的叶子结点包含了多个指向不同数据的指针，这些数据可以是存放在硬盘中的，也可以是存在内存中。根据R树的这种数据结构，当我们需要进行一个高维空间查询时，我们只需要遍历少数几个叶子结点所包含的指针，查看这些指针指向的数据是否满足要求即可。这种方式使我们不必遍历所有数据即可获得答案，效率显著提高。

**红黑树**

R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红(Red)或黑(Black)。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]  
  红黑树的应用比较广泛，主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。例如，Java集合中的TreeSet和TreeMap，C++ STL中的set、map，需要使用动态规则的防火墙系统，使用红黑树而不是散列表被实践证明具有更好的伸缩性。Linux内核在管理vm\_area\_struct（虚拟内存）时就是采用了红黑树来维护内存块的。

对于链表、数组、树和图来说，它们每次的动态操作都会完全遗忘之前的状态，转而到达全新的状态，这种数据结构称为ephemeral structure。另一种数据结构可以记录某一历史时刻的状态，在访问时可以根据版本好+目标数据进行访问，这种数据结构称为persistent structure。事实上，红黑树可以实现这种对历史版本的记录。

B树与红黑树最大的不同在于，B树的结点可以有许多子女，从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样，一棵含n个结点的B树的高度也为O（lgn），但可能比一棵红黑树的高度小许多，因为它的分支因子比较大。所以，B树可以在O（logn）时间内，实现各种如插入（insert），删除（delete）等动态集合操作。

--------------------

**什么是堆（大根堆、小根堆）**

这里说的“堆”是一种数据结构，注意与jvm中的堆内存分开。堆必须满足以下两个条件：（1）是完全二叉树 （2）heap中存储的值是偏序（偏序只对部分元素成立关系R,全序对集合中任意两个元素都有关系R）。

大根堆：父结点的值大于等于其子结点的值；小根堆：父结点的值小于等于其子节点的值。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzI4MzM5Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/eb5fabc4328e480ead9df4b14135b15c.png