# 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++ 语言版 邓俊辉老师

邓俊辉老师的书。





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

`1 有数组为什么还需要向量？`

几乎所有程序设计语言中都会有数组，程序设计语言的开发者将数组作为一种内置的数据类型。

数组在刚开始初始化的时候就已经固定了长度，也可以依照下标查找，但还有很多种特性数组是不含有的。

向量这种抽象数据类型，它是一种利用程序设计语言抽象出来的一种数据类型。我们可以在运行时开辟一块空间来放一段数据，它就是一个对象。我们可以轻易的利用操作接口方法来对这些数据进行获取、插入、删除、查找、排序、集合化。可以看到如果拥有这些方法可以对数据进行更好的处理，是数组不能替代的。

还有一点是非常重要的，无论我们基于什么语言设计了一个抽象数据类型，在内部的实现方法可能就是使用的数组，我们只是做了将数组抽象化为更普遍的数据类型，并把这种数据类型取名为向量，因为这种数据类型和向量的很多特性都很相似。

`2 什么是抽象数据类型？什么是数据结构？`

抽象数据类型=数据模型+定义在该模型上的一组操作

数据结构=基于某种特定语言，实现抽象数据类型adt的一整套算法。

数据类型就是指 Int x，我们抽象数据类型的目的就是 vector x。

抽象数据类型是一种抽象定义、要考虑操作语义、不涉及数据的存储方式。

数据结构是一种具体的实践方法，要注重内部的实现算法，要考虑数据的具体存储机制。


`3 在这一章中主要讲的内容是什么？`

假如我们用c语言写了一个队列数据结构。我们应该讲一下队列这种数据结构的特性，所需要的方法（从对象的角度来看，就是我们应该讲一下队列这种对象应该有哪些行为和属性），同时我们也应该考虑去实现这些方法的时候我们的程序应该怎么写才能使得对象用起来更加顺手，去实现这些方法我们有不同的程序写法（每一种写法都是一种算法），如何使这些算法更加低成本和高效率也是我们应该考虑的。

这一章的内容就是在讲向量这个数据结构应该具有的行为方法，以及我们应该怎么用程序去实现这些行为方法，并且使得程序是高效率和低成本兼顾着的。

`4 有序向量和无序向量有什么区别？`

由于这两者表达数据的方法不一样，所以这两者的数据结构实现算法也不一样。有序向量可以很方便的进行查找操作，如果我们在给一堆数据建模，然后查找操作非常频繁的话就可以优先使用有序向量。

`5 总结`

如果我们是在用c语言学习数据结构这门课，那么内容将会有线性表（数组、链表）、队列与栈（特殊线性表）、串、树、图，在这些内容中又会详细的了解到查找与排序。

现在我们用c++语言学习数据结构这门课，要将关注点放在对象上来。

向量是`寻秩访问`，内部是由数组实现的，在物理空间上一个向量对象里的数据是连续存储的。

数据结构 笔记--向量 C++ 语言版 邓俊辉老师

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