[深度优先搜索（DFS、深搜）和广度优先搜索（BFS、广搜](http://data.biancheng.net/view/39.html)





# 1 图的基本概念

图的几个应用场合：

（1）一张带权图，代表城市之间的距离。求一个城市到另一个城市的最短路径。或者说导航上用的。Dijkstra 算法。

（2）图最小生成树。城市光纤网建造，最小生成树代表了耗材最少的方法。

（3）网页排序。一个网页就是图的一个顶点，权重如何升高。

图 是一种非常重要的数据结构。树 就是一种特殊的退化的图结构。

图的生成树（也叫支撑树）通常不是唯一的。边有权重，图就是带权网络。同一网络的声称树中，总权重最小者为最小支撑树。

# 2 邻接矩阵

![在这里插入图片描述](/static/img/images/01361.png)

![在这里插入图片描述](/static/img/images/01362.png)

# 3 邻接矩阵优缺点

![在这里插入图片描述](/static/img/images/01363.png)

![在这里插入图片描述](/static/img/images/01364.png)

# 4 邻接表

![在这里插入图片描述](/static/img/images/01365.png)

![在这里插入图片描述](/static/img/images/01366.png)

# 5 广度优先搜索

![在这里插入图片描述](/static/img/images/01367.png)

![在这里插入图片描述](/static/img/images/01368.png)

# 6 深度优先搜索

![在这里插入图片描述](/static/img/images/01369.png)

# 7 遍历算法的应用

![在这里插入图片描述](/static/img/images/01370.png)

数据结构 图 图的表示 图的搜索 深度优先搜索（DFS、深搜）和广度优先搜索（BFS、广搜）

# 0 从“树”到“搜索树”





前面所说的都是线性表，基于数组实现或者基于链表实现都有优缺点，数组做查找元素快，链表做插入删除元素快。

树是半线性结构（semi-linear structure），结合了二者特点。

本书约定，仅含单个节点的树高度为0，空树高度为-1。

特别地，约定根节点的深度depth(r) = 0，故属于第0层。

特别地，不含一度节点的二叉树称作真二叉树（proper binary tree）。

有序多叉树 = 二叉树 ，在全遍历中就能看出能相互转化。

二叉树表达能力和多叉数一样的，而且得益于其定义的简洁性以及结构的规范性，所以都用二叉树。

树是怎么做到高效率的动态修改和高效率的静态查找？答案是用一些搜索树和高级搜索树。

![在这里插入图片描述](/static/img/images/01380.png)


# 1 二叉搜索树（binary search tree）

二叉搜索树的实现与分析，search()、insert()和remove()等主要接口的运行时间，均线性正比于二叉搜索树的高度。

将二分搜索树与常规二叉树分开的属性是

 - 左子树的所有节点均小于根节点 

 - 右子树的所有节点均大于根节点 

 - 每个节点的两个子树也是BST，即它们具有以上两个属性

查找、插入和删除操作 操作：

查找：从根节点出发，比较左孩子和右孩子，从而判断进入左子树递归还是进入右子数递归。（分而治之）

![在这里插入图片描述](/static/img/images/01381.png)

插入：利用查找返回大于数值一点的节点。然后把数值作为左孩子，最后更新祖先高度。

![在这里插入图片描述](/static/img/images/01382.png)

删除：利用查找找到位置后，单分支和双分支处理不一样。

![在这里插入图片描述](/static/img/images/01383.png)

# 2 平衡搜索树-AVL树

通过合理设定适度平衡的标准，并借助以上等价变换，AVL树（AVL tree）可以实现近乎理想的平衡。在渐进意义下，AVL树可始终将其高度控制在O(logn)以内，从而保证每次查找、插入或删除操作，均可在O(logn)的时间内完成。

任一节点v的平衡因子（balance factor）定义为“其左、右子树的高度差”，即balFac(v) = height(lc(v)) - height(rc(v))

插入或者删除会造成树不平衡，此时通过一些旋转操作让树重新平衡，满足AVL特点。

# 3 伸展树splay tree

[\[一个很好的介绍伸展树的博客点我\]](https://blog.csdn.net/u014634338/article/details/49586689)

伸展树也是一种平衡搜索树。

我们评估算法结构用的随机的最坏的，但实际应用场合有一定规律，如果我们适应这种规律设计算法结构，可以使得数据结构这个应用中得到更高效率。伸展树就是这么想的。

![在这里插入图片描述](/static/img/images/01384.png)

![在这里插入图片描述](/static/img/images/01385.png)

在伸展树上的一般操作都基于伸展操作：假设想要对一个二叉查找树执行一系列的查找操作，为了使整个查找时间更小，`被查频率高的那些条目就应当经常处于靠近树根的位置`。于是想到设计一个简单方法，`在每次查找之后对树进行调整，把被查找的条目搬移到离树根近一些的地方。`伸展树应运而生。伸展树是一种自调整形式的二叉查找树，它会沿着从某个节点到树根之间的路径，通过一系列的旋转把这个节点搬移到树根去。它的优势在于不需要记录用于平衡树的冗余信息。

![在这里插入图片描述](/static/img/images/01386.png)



# 4 B树 

B树

B-树结构非常适宜于在相对更小的内存中，实现对大规模数据的高效操作。

所谓m阶B-树（B-tree），即m路平衡搜索树（m >= 2），其宏观结构如图8.11所示。

![在这里插入图片描述](/static/img/images/01387.png)

> 下面来具体介绍一下B-树（Balance Tree），一个m阶的B树具有如下几个特征：

> 

> 1.根结点至少有两个子女。

> 

> 2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

> 

> 3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

> 

> 4.所有的叶子结点都位于同一层。

> 

> 5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

[\[读一下这里介绍B数和B+数的，生动形象。点我\]](https://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653190965&idx=1&sn=53f78fa037386f85531832cd5322d2a0&chksm=8c9909efbbee80f90512f0c36356c31cc74c388c46388dc2317d43c8f8597298f233ca9c29e9&scene=21#wechat_redirect)

数据库存储或者磁盘存储，读取数据还需要考虑到I/O时间，一次读取1一个数据和10个数据所花费的时间相当，但使用10次读取每次读取1个数据却是很耗时间，所以考虑使用m路平衡搜索树。

B树 查找、插入、删除操作。B树主要用于文件系统以及部分数据库索引（比如非关系型数据库MongoDB）。

大部分关系型数据库使用B+树作为索引。

# 5    B+树

大神的漫画比看书快，多看几遍后再去看书。

[还是看这里，点我](https://www.cxyxiaowu.com/3726.html)

# 6    红黑树

> 平衡二叉搜索树的形式多样，且各具特色。比如，8.1节的伸展树实现简便、无需修改节点

> 结构、分摊复杂度低，但可惜最坏情况下的单次操作需要(n)时间，故难以适用于核电站、医

> 院等对可靠性和稳定性要求极高的场合。反之，7.4节的AVL树尽管可以保证最坏情况下的单次

> 操作速度，但需在节点中嵌入平衡因子等标识；更重要的是，删除操作之后的重平衡可能需做多

> 达(logn)次旋转，从而频繁地导致全树整体拓扑结构的大幅度变化。

> 红黑树即是针对后一不足的改进。通过为节点指定颜色，并巧妙地动态调整，红黑树可保证：

> 在每次插入或删除操作之后的重平衡过程中，全树拓扑结构的更新仅涉及常数个节点。尽管最坏

> 情况下需对多达(logn)个节点重染色，但就分摊意义而言仅为O(1)个（习题[8-14]）。

> 当然，为此首先需在AVL树“适度平衡”标准的基础上，进一步放宽条件。实际上，红黑树 所采用的“适度平衡”标准，可大致表述为：

> 任一节点左、右子树的高度，相差不得超过两倍。

大神的漫画比看书快，多看几遍后再去看书。

[还是看这里，点我](https://www.cxyxiaowu.com/7374.html)

数据结构 树 树的表示（存储） 搜索树（用于高效查找）

C语言 链表 栈与队列 二叉树遍历

![在这里插入图片描述](/static/img/images/01392.png)





`1 栈的注意点`

先进后出。

递归的时候就会用到栈，把这次结果压入栈，去计算下一次的。

题外话：算法中避免用递归。不断压入栈有时会导致过多占用内存，

`2 栈的典型应用`

可线性描述、逆序输出、大小规模不确定。

递归嵌套：具有自相似性的问题多可嵌套地递归描述。

栈混洗（stack permutation）、括号匹配、

![在这里插入图片描述](/static/img/images/01393.png)

逆波兰表达式



`3  试探回溯法  高效地实现试探回溯策略`

n皇后问题

迷宫路径问题




`4 栈与队列`

都是一种数据结构，应用场合不定，作用广泛。

数据结构 笔记 --栈与队列 C++ 语言版 邓俊辉老师

![在这里插入图片描述](/static/img/images/01401.png)





![在这里插入图片描述](/static/img/images/01402.png)


`1 链表 列表`

链表不是列表。我们所谈的列表更倾向于是针对对象而言的。

或许应该说列表是链表的扩展。他们的物理存储结构都不是连续的，而是依赖于节点指针指向的。所以链表里面的很多算法拿到列表对象上来说，都差不多。

`2 向量 列表`

向量在物理存储上地址是连续的。所以get()、size()这类静态方法效率高。但是insert()和remove()等动态操作需要线性时间。

列表则相反。

数据结构 笔记--列表 循位置访问 C++ 语言版 邓俊辉老师

我是一个专注技术分享的博主,尤其爱搞深度学习和单片机电子。你现在看到的是我的个人博客网站。