那年夏十七

234 树一、引入​ 在二叉树中，每个节点有一个数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树（multiway tree）。​ 2-3-4树，就是多叉树，它的每个节点最多有四个子节点和三个数据项。首先，2-3-4树像红黑树一样是平衡树。它的效率比红黑树稍差，但是编程容易。 · 上图展示的就是一棵2-3-4树，每个节点可以保存一个、两个或者三个数据项。· 上图中上面三个节点有子节点，底层的六个节点都是叶节点，没有子节点。2-3-4树中所有的叶节点都是在一层上的。 二、2-3-4树名字的含义与特性2-3-4树中的2、3、4的含义指的是一个节点可能含有的子节点数。对非子叶节点有三种可能的情况： ​ · 有一个数据项的节点总是有两个子节点​ · 有两个数据项的节点总是有三个子节点​ ·...

...

[TOC] 平衡二叉树 参考：https://blog.csdn.net/jyy305/article/details/70949010 一、定义平衡二叉树，是一种二叉排序树，其中每个节点的左子树和右子树相差的高度不超过1 （左子树的高度 - 右子树的高度 <= |1|）。它是一种高度平衡的二叉排序树。高度平衡：意思是说，要么它是一颗空树，要么它的左子树和右子树都是平衡二叉树。 平衡二叉树的出现是为了优化二叉顺序树的查找效率，你可以想象下，二叉顺序树如果顺序添加一个这样的数据｛5，4，3，2，1｝,那么树成了一个链表，查找效率显然不高 。 平衡二叉树首先是一个二叉顺序树，只不过他在每次添加数据的时候会进行自我平衡，来优化查找的效率。 二、术语最小不平衡子树：指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。...

...

[TOC] 二叉树参考文档: 百度百科 https://www.jianshu.com/p/bf73c8d50dc2 在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。 1、定义二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点之后，每个顶点定义了唯一的父结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。如果不考虑连通性，允许图中有多个连通分量，这样的结构叫做森林。 [1] 2、特点 每个节点最多有两棵子树，即两个子节点。 左子树和右子树是有顺序的，次序不能任意颠倒 即使树中某节点只有一颗子树，也要区分他是左子树还是右子树 3、性质 在二叉树的第i层上最多有 2的（i-1）次方个节点 。 （i>=1） 二叉树中如果深度为k，那么最多有2的k次方-1个节点 （i>=1） n0 = n2 + 1 ...

[TOC] 数据结构-树1、介绍：树是一种数据结构，它是由n（n>=1 ， n=0...

排序(七)希尔排序一、描述希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。 希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率； 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位； 希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。 直接插入排序 http://xia17.chukongxiang.top:8017/articles/2021/02/26/1614334116912.html 二、步骤选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1； 按增量序列个数 k，对序列进行 k 趟排序； 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1...

排序(六)直接插入排序描述直接插入排序的基本操作是将一个记录插入到已经排好序的有序表中，总而得到一个新的，记录数增1的有序表。 将n个待排序的元素看成一个有序表和无序表，开始时有序表只有一个元素，无序表中有 n-1个元素，排序过程中每次去除无序表的一个元素，插入到有序表指定位置中，使之成为一个新的有序表，重复 n-1次可完成排序过程 流程从第二个数开始循环，当循环数小于前面的数时，将循环数插入到小于数的位置，小于数到循环数的数组元素后移。 实例步骤 数组 ： 4 6 5 2 6 与前面的4 比较 。 发现6比4大 ，不执行后移 5 与前面得 4 6 比较 ， 发现比6小 ，将5插入到6的位置 ，然后6后移一位。 2与前面的 4 5 6 比较 发现比4小 ，将2插入到 4的 位置 然后 4 5 6 后移 得到 2 4 5 6 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344/** * 将 j 插入到 i 的位置 ，且 i 到 j -1 的元素后移一位...

排序(五)快速排序一、定义百科中的快速排序的介绍是： 快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。 二、实现思路从数据中选择一个基准数，将整个数据中比基准数小的放到基准数的左边，比基准数大的数放到右边。这样整个数据就分成了两个部分，再将两个部分的数据通过递归在执行前面的操作，重复即可完成排序。 整个算法中基准数的选择绝定了算法的效率一般有三种方式。 1》将数据中的第一个数作为基准数，在随机的数据中效率还行，但在反序的数据中效率低下。 2》随机选择一个数为基准数，因为每次都要随机产生基准数效率有所降低。 ...

排序(三)归并排序1 描述归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。– 百度百科 2 步骤 将数组分成两个部分，一般是取中值分成大小相差不大于1的两个数组 左右两边数组继续执行步骤一，直至数组长度变为1 （递归）结束条件是数组大小为1 将左右两边排过序的数组进行合并（数组里只有一个数自然就是有序的了） 3 图示过程引用自 ： https://www.jianshu.com/p/33cffa1ce613 3.1 流程 3.2 合并两个有序数据的流程 4 复杂度 时间复杂度：O(nlogn) **空间复杂度：O(N)**，归并排序需要一个与原数组相同长度的数组做辅助来排序 稳定性：归并排序是稳定的排序算法 5...