数据结构和算法

数据结构的特征

形成原因：二分法。为了提升查找效率。思路为：1、对数据集进行排序；2、找到数据中间节点；3、对比，相等则返回，否则根据大小找中间往前或往后的节点再次二分查找

平衡因子等于左儿子高度减去右儿子高度

为了有效的管理数据的中间节点，对数据集进行存储的时候就形成适合二分查找的数据结构，这就演化出了树和跳表两种数据结构。适用于小量数据插入、删除频率低的场景

二叉查找树充分利用了二分法的思维，但是构建的时候为了保证层数的稳定，防止退化成链表，这时我们就需要利用平衡算法形成的平衡二叉树来保证树形结构的平衡，保证左右子树的层级不会大于1

分支主题

构建原则：1、非叶子节点只允许两个节点的存在；2、每个节点的值左边小于当节点，右边大于当前节点（这里的值时基于自己的算法实现的，可以是数值或hash值）；3、通过平衡算法（Treap、AVL、红黑树），保证左右节点的高度相差不超过1（树的左旋和右旋）

平衡二叉树AVL树

由于AVL树的左右子树层高严格相差1，导致删除和杀入需要复杂的旋转来保持平衡，红黑树通过降低对平衡性的要求，来提升插入和删除效率。红黑树在插入、删除节点时会通过变色、左旋、右旋来调整节点，但旋转次数不会超过3次，整体性能好于AVL树，是一种自平衡的二叉查找树

红黑树需要满足的要求：1、所有节点分为红或黑，并且根节点是黑色，且叶子节点是空的黑色节点；2、红色节点不能相邻；3、每个节点从它本身到每一个叶子节点所经过的路径中，黑色节点的数量都是相同的

红黑树

B树属于多叉树（而AVL树是二叉树），又称平衡多路查找树，即查找路径多于2。数据库索引技术大量使用B树和B+树的数据结构

特点：充分利用了每个节点的空间，通过每个节点保存多个数据的形式减少了树的高度提升了查找性能

构建原则：1、排序，关键字递增序列和左小右大的原则；2、非叶子节点的节点数大于1；3、每个节点除了保存关键字和记录关键字的指针外，还保存指向其它几点的指针（最底层的指针指向null）

B树

B+树是在B树的基础上再次做改进，一方面是查询的稳定性（降低树的层级）；另外一方面是优化了数据排序

构建原则：1、非叶子几点不保存数据，只保存关键字的索引；2、左边的叶子节点的值小于根节点，右边的叶子节点是值大于根节点；3、最后一层是叶子节点，节点之间有指针相连

B+树

树

基本概念：1、稳定与不稳定排序：相同的大小数字，排序后相对位置不变。稳定适用于相同值先来后到场景。2、内排序和外排序：内排序指排序过程都在内存中完成。外排序需要用到外部设备。3、常见的排序方法分类：1）、插入类排序：直接插入排序、希尔排序；2）、交换类排序：冒泡排序、快速排序；3）、选择类排序：简单选择排序、堆排序；4）、归并排序5）、基数排序

记当插入第i个记录时，R1，R2，。。。Ri-1均是有序的，将第i个记录Ri依次与Ri-1、R。。。R2，R1进行比较，找到合适的地方插入。优势：简单明了；劣势：速度很慢。 默认从下标1开始，也就是第二个元素。因为只有一个元素默认是有序的

1、直接插入排序

实际上是一个分组插入的方法，选取一个小于数组长度n的树d1作为第一个增量，把记录分层d1组。所有距离为d1的记录放置在同一组中，进行组内直接插入排序。然后不断缩小增量到d = 1，排序完毕。经过分组，一步步减少问题规模，能减少移动的次数和对比的次数。

2、希尔排序

在所有记录中选出最小的记录，放到第一个位置交换；然后选择出第二小的记录，放到第二个位置交换。以此类推，直到排序完成

3、直接选择排序

通过循环比较，相邻元素的交换，将较小的元素逐渐从底部移动到顶部。

4、冒泡排序

分治法，选取一个基准元素，大于基准的放在右边，小于的放在左边。重复上述步骤，完成排序。类似于二分思想。相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了

5、快速排序

排序

带权图总权值最小的树，针对的是带权无向连通图。可能存在多个树形，但只有一个节点序列

基本思想：选定一个点，确定这个点能到达的其它顶点，选择最小的连线值，连接；然后查找已连接的点到未连接的点中，选择一个最小的连续进行相连，直到所有的点都被连起来。注意，不能形成环路。

普利姆算法

基本思想：选择一个最小的边，连接，再次寻找第二小的边，连接。重复以上过程，直到所有的点都能有直接或间接的路径联通。注意不能形成环路

克鲁斯卡尔算法

图的最小生成树算法

指一种通过重复将问题分解为同类的子问题而解决问题的方法。一般通过函数的自我调用，语言中函数可以通过调用自身来进行递归实现

常见的递归算法：汉诺塔移盘算法、阶乘求解、欧几里得最大公约数算法、斐波那契数列

递归算法

穷举法

贪心算法：背包算法、普利姆算法

分治法：快速排序

动态规划算法：最长公用因子序列

回溯法：八皇后问题求解

算法类型总结

数据结构和算法