二叉排序树的平均查找长度ASL_二叉排序树的平均查找长度ASL

数据结构的个人笔记
　　数据结构复习

　　扩展知识：

　　算法分析的目的是分析算法的效率以求改进

　　一、绪论

　　1、什么是数据结构？

　　数据结构包括逻辑结构，存储结构，还有数据的运算

　　（逻辑结构就是数据之间的关系，比如说线性结构就是逻辑结构的一种，线性结构就是跟一条线一样，数据之间的关系就是跟一根线一样（一根线有开始部分（头部），还有结束部分（尾部），然后中间有前后关系（也就是书中的前驱和后继））这就是逻辑结构，最后知道了数据之间的关系后，就要真正的存到内存中，这就需要存储结构了（什么是存储结构呢：就是存储数据的方式，我是按顺序存呢，还是按链条一样的方式存呢），比如说现在选择的是顺序存储结构，我们就要把带有关系（线性或其他逻辑结构）的数据按这种存储方式存到内存中）

　　线性结构就是有且只有一个开始节点和终端节点，并且其余节点有且只有一个直接前驱和直接后继，例如：线性表，典型的线性表有：顺序表，链表，栈（顺序栈，链栈）和队列（顺序队列，链队列），它们共同的特点就是数据之间的线性关系，除了头结点和尾节点之外，每个节点都有唯一的前驱和唯一的后继，也就是所谓的一对一关系。

　　二：线性表

　　线性表的定义：线性表是具有相同数据类型的n个数据元素的有限序列。n为表长，当n = 0时，为空表。 线性表公式表示：L = （a1,a2,a3…….an）, a1 为表头元素，an为表尾元素。除了第一个元素，每个元素都有且仅有一个直接前驱，除了最后一个元素，每个元素有且仅有一个直接后继。 线性表的特点：有限个数；逻辑上有顺序性；每个表元素都是单个元素；表元素类型皆相同；元素具有抽象性。

　　线性表与链表/顺序表之间的区别：线性表是一种逻辑结构，表示元素之间一一对应的关系；链表和顺序表指的是存储结构。 在计算机内，可以用不同的方式来表示线性表，最简单最常用的方式是顺序存储结构—顺序表，而链表则经常被用来表示非线性的数据结构，也是一种常用的表示线性表的方法。

　　顺序表：线性表的顺序存储被称为顺序表，它是一组地址连续的顺序存储单元，依次存储线性表中的数据元素。注意顺序存储是一种读写方式，不是存储方式，有别于顺序存储。线性表支持随机存取的顺序存储结构。

　　顺序表的优点：1：存储密度高；2：元素可以随机读取；3：存储位置可以简单的使用公式来表示。（补充：当主要操作为查找时，选用顺序表比较好）

　　链表：由于顺序表的插入删除元素操作需要移动大量的元素，影响运行效率，所以引入了链式存储，链式存储通过“链”建立起数据元素之间的逻辑关系，只需要修改指针进行插入、删除操作。分为单链表和双链表。

　　链表的优点：1：适合随机的插入和删除操作；2：存储空间大小不需要提前设定；3：可以进行动态存储。（补充：当主要操作为插入，删除时，选用链表比较好）

　　顺序表和链表的比较：

　　1：存取，链表只能从表头开始顺序存取元素；顺序表可以随机存取

　　2：存储方式，顺序表相邻存储；链表物理存储位置不一定相邻，其逻辑关系是通过指针来链接的

　　3：顺序表在静态分配时，不可改变内存大小，可能会造成溢出，动态分配时，插入和删除需要移动大量的元素，效率很低。但链表只在需要的时候申请内存，操作灵活 单链表：线性表的链式存储称为单链表，它不是连续的存储空间，元素之间是通过指针进行联系。我们通常使用“头指针”来标识一个单链表，当头指针为“NULL”时表示一个空表，此外，为了操作上的方便，在单链表第一个结点之前附加一个结点，称之为“头结点”，头结点的数据域可以不设任何信息，也可以记录表长等相关信息。但是不管带不带头结点，头指针始终指向链表的第一个结点。注意头结点不计入表长。 特点：非随机存取，不能直接从表中找到特定的结点，需要从表头开始遍历，依次查找 双链表：单链表结点中只有一个指向其后继的指针，这使得单链表只能从头到尾依次顺序的向后遍历，若要访问某个结点的前驱，只能从头开始遍历，访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)；为克服以上缺点，引入双链表，一个结点含有两个指针，分别指向其前驱结点和后继结点。

　　线性表按照存储方式可分为顺序表和链表。

　　（1）顺序表。将数据元素放到一块连续的内存空间，相邻数据元素存储地址也相邻。

　　1）优点：通过下标就可访问元素，因此存取效率高。

　　2）缺点：需预分配空间，分配多了会造成浪费，分配少了会造成“溢出”，因此空间利用率低；插入和删除元素需移动元素，因此插入删除慢。

　　3）时间复杂度：访问元素是O（1），插入删除元素是O（n）。

　　（2）链表。相邻数据元素的地址可能不相邻。每个数据元素所占存储空间分成两部分，一部分存放元素值，一部分存放元素之间的关系。

　　1）优点：存储空间是动态分配的，因此没有空间限制；插入和删除元素只需要改变指针指向，因此插入删除快。

　　2）缺点：访问元素需要从开始元素一个一个去查找访问，因此存取效率低。

　　3）时间复杂度：访问元素是O（n），插入元素是O（1）。

　　为什么说顺序存储结构是随机存取的？

　　答：因为顺序存储结构存储的数据是一个挨着一个，是相邻的，也就是说访问任何一个元素的时间是相同的，因为指定了位置，比如说我要取第3个数据，我直接取序号2的的地方拿，不用说又要从0,1，到2这样就行了，所以时间复杂度是O(1)，所以说是随机存取

　　问答题：

　　一、线性表的两种存储结构各有哪些优缺点？

　　答：线性表的两种存储结构分别是：顺序存储结构和链式存储结构。顺序存储结构的优点：可以直接存取数据元素，方便灵活，效率高，但插入，和删除需要移动大量的数据元素。因而减低效率；而链式存储结构中采用动态分配，利用率较高，但需增设指示节点之间关系的指针域，存取数据元素不如顺序存储方便，但节点的插入，删除较简单。

　　二、对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素应选用那种存储结构？是说明理由？

　　答：应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是种顺序存取的存储结构。

　　三、对于一个头指针为L的带头结点的单链表，判定链表为空表的条件是（L->next==NULL;）

　　(head==NULL )不带头结点的单链表head为空的判定条件是

　　解释：带头节点的情况下，链表空时还会存在一个节点，所以head不为空，head->next为空 不带头节点的情况下，链表空时，没有任何节点，head指向null。

　　三：栈和队列

　　常见提问方式的问题：

　　数据结构（数据+结构）：是指所有数据元素以及数据元素之间的关系。这是在说数据结构是除了存放数据还有存放这些被存放的数据之间的关系是吧（这些关系可以是：逻辑结构和存储结构，

　　逻辑结构又分：集合，线性结构，树形结构，图形结构。

　　存储结构：顺序存储结构，链式存储结构，索引存储结构，哈希（或散列）存储结构

　　单链表：

　　单链表插入：先指定当前节点的后继，再指定前面节点的后继（因为单链表只有指定后继就行了）单链表的插入顺序：s-next = p->next；p->next = s;

　　这里删除指在单链表中删除节点的p的后继节点。单链表的删除顺序:q = p->next;p->next = q->next;free(q);

　　双向链表：

　　双向链表的插入顺序：先搞定插入节点的前驱和后继，在搞定其后结点的前驱，最后搞定其前结点的后继。

　　循环队列：（front:队头，rear:队尾，Maxsize:队列长度）

　　判断循环队列元素个数： (R-F+M)％M

　　判断循环队列空：R = F

　　判断循环队列满：R+1%M = F

　　往循环队列插入元素：F= (F+1)%M

　　往循环队列删除元素：R = (R+1)%M

　　双向链表的删除顺序：要删除双链表的一个结点，无非就是把要删除的结点去掉，然后重新指定前一个结点的前驱节点和后继结点，还有后面那个节点的前驱节点和后继结点。（就是修改p结点前驱结点的next指针和p结点后继结点的prior指针。）原来要删除结点的前驱节点变成原来删除结点的后继节点的前驱节点（p->next->prior = p->piror）,还有就是把原来要删除结点的后继节点变成原来删除结点的前驱节点的后继节点（p->piror-next = p->next），注意：这删除结点的顺序是有要求的，哪个先，哪个后。

　　栈的应用

　　前缀，中缀和后缀表达式

　　中缀表达式转后缀表达式：规则：从左到右遍历中缀表达式的每个数字和运算符，是数字就直接输出，如果是运算符的话，判断当前要进栈的运算符跟栈顶的运算符比较优先级，如果栈顶运算符优先级低于当前要进栈的运算符，就不输出，直接进栈，如果栈顶运算符优先级高于当前要进栈的运算符，就输出栈顶运算符，一直遍历到表达式最后。补充说一下规则：像遇到括号了，要先左括号进栈了，然后一直遍历，再遇到右括号，就需要把出栈，直到吧左括号出栈即可（左括号输出后，栈里面还有符号就放着了，还有表达式是不用吧括号写上去的）。都是要先判断一下优先级关系，然后看要不要输出栈顶元素中缀表达式转前缀表达式：规则：从右向左遍历中缀表达式的每个数字和运算符，是数字就直接输出，如果是运算符的话，判断当前要进栈的运算符跟栈顶的运算符比较优先级，如果栈顶运算符优先级低于当前要进栈的运算符，就不输出，直接进栈，如果栈顶运算符优先级高于当前要进栈的运算符，就输出栈顶运算符一直遍历到表达式最后，如果同级就入栈。总结：就是跟中缀转后缀的遍历方向相反，中缀转后缀的遍历方向是从左往右，中缀转前缀的遍历方向是从右往左，注意写的方向也是从右往左啊！！！后缀表达式转中缀表达式：前缀表达式转中缀表达式：

　　四、串

　　常见提问方式的问题：

　　六：数组和广义表

　　数组：

　　数组的存储结构一维数组的存储结构二维数组的存储结构 按行优先存放按行优先存放，第一个元素地址为a0的话，有LOC(ai，j)=LOC(a0，0)+(i×n+j)×k；按行优先存放，第一个元素地址为a1的话，有LOC(ai，j)=LOC(a1，1)+[(i-1)×n+(j-1)]×k按列优先存放按列优先存放，第一个元素地址为a0的话，有LOC(ai，j)=LOC(a0，0)+(j×m+i)×k；按列优先存放，第一个元素地址为a1的话，有LOC(ai，j)=LOC(a1，1)+[(j-1)×n+(i-1)]×k特殊矩阵的压缩存储（什么是特殊矩阵呢？就是非零元素和零元素的分布有规律（对称,上三角，下三角，对角矩阵）的叫特殊矩阵）对称矩阵上三角矩阵下三角矩阵对角矩阵稀疏矩阵的压缩存储（上面有特殊矩阵，这个其实就跟特殊矩阵相反的吧，就是非零元素和零元素的分布没有规律），稀疏矩阵的两种压缩存储方式会使数组失去随机存储性三元组表十字链表

　　广义表

　　广义表中的数据元素是有相对次序的广义表的长度定义为最外层包含元素个数广义表的深度定义为所含括弧的重数（其实就是从左到右数左括号的数量就是深度），原子的深度为0，空表的深度为1广义表的长度，指的是广义表中所包含的数据元素的个数。由于广义表中可以同时存储原子和子表两种类型的数据，因此在计算广义表的长度时规定，广义表中存储的每个原子算作一个数据，同样每个子表也只算作是一个数据。（所以一个数据长度就为1）总结：当问到广义表长度时，看有多少个数据就好了，虽然有点说废话，但是说这话之前，我确实不知道这回事，嘻嘻​例如，在广义表 {a,{b,c,d}} 中，它包含一个原子和一个子表，因此该广义表的长度为 2。​再比如，广义表 {{a,b,c}} 中只有一个子表 {a,b,c}，因此它的长度为 1。​前面我们用 LS={a1,a2,…,an} 来表示一个广义表，其中每个 ai 都可用来表示一个原子或子表，其实它还可以表示广义表 LS 的长度为 n。广义表规定，空表 {} 的长度为 0。​广义表的深度，可以通过观察该表中所包含括号的层数间接得到。例：C = (a,(b,c,d))从C可以看到，此广义表从左往右数有两层左括号（从右往左数也是如此），因此该广义表的深度为 2。​再比如，广义表 {{1,2},{3,{4,5}}} 中，子表 {1,2} 和 {3,{4,5}} 位于同层，这里已经是两层了，然后里面还有{4,5}，所以此广义表中包含 3 层括号，因此深度为 3。广义表的存储结构只有链式存储结构

　　常见提问方式的问题：

　　七：树和二叉树

　　对于二叉树构造和遍历，我另外有介绍：

　　https://zhuanlan.zhihu.com/p/134071439

　　常见提问方式的问题：

　　一、二叉树遍历

　　二叉树遍历案例一:

　　记住超重要的一句话：比如说后序遍历是左右根的顺序，开始是F，后面本应该是G的，但是因为G是H和I的根节点，先不能写，也是先把左右结点先写，然后根结点.

　　还有像中序遍历是左根右的顺序，开始F,D，后面本应该是G，但是因为G是H和I的根节点，先不能写，（重新把GHI这颗树单独当做一颗新的树）先把H,然后G，后面是I

　　前序遍历：ABDFGHIEC

　　中序遍历：FDHGIBEAC（有点像从下往上的感觉）

　　后序遍历：FHIGDEBCA二叉树遍历案例二：

　　二叉树遍历案例三：

　　前序遍历：ABDEHCFI

　　中序遍历：DBHEACIF

　　后序遍历：DHEBIFCA

　　二、会经常考查树和二叉树的性质

　　三、树的存储结构

　　双亲表示法孩子表示法孩子兄弟表示法

　　四、二叉树的存储结构

　　顺序存储结构可以用数组表示，下标存储对应编号的结点，如果是空的结点，可以用#表示，链式存储结构二叉树的每个结点用链表中的一个结点来存储，二叉链存储结构为：下图。data表示值域，用于存储对应的数据元素，lchild和rchild分别表示左指针域和右指针域，分别用于存储左孩子结点和右孩子结点的存储地址

　　五、二叉树与树，森林之间的转换

　　树转换为二叉树1、树中所有相邻兄弟之间加一条连线2、对树中每个节点只保留跟第一个孩子之间的连线，删除与其他孩子之间的连线3、以树的根节点为轴心，将整棵树顺时针旋转45度森林转换为二叉树1、将森林中的每棵树都转换成相应的二叉树2、第一课二叉树不动，从第二颗二叉树开始，依次把后一颗二叉树的根结点作为前一颗二叉树根结点的右孩子结点。当所有二叉树连在一起后，此时得到的二叉树就是有森林转换得到的二叉树

　　二叉树转换为树1、若某结点是其双亲结点的左孩子，则把该孩子的右孩子，右孩子的右孩子等都与该结点的双亲结点用连线连起来2、删除原二叉树中所有双亲结点与右孩子结点之间的连线3、整理由前面两步得到的树，即以根节点为轴心，逆时针旋转45度

　　二叉树转换为森林

　　六、线索二叉树

　　线索二叉树就是比二叉链多加了前驱和后继。

　　七、二叉树的构造

　　回答第一个问题：根据先序确定下一个根节点是谁，中序确定该根节点的左右孩子，具体案例，可到：https://zhuanlan.zhihu.com/p/73438175，这篇文章对二叉树构造有比较详细的讲解。

　　上述图片例子讲解一下：A结点后，1、左孩子剩下先序遍历为BDG,中序遍历为DGB，B就是我们新的根节点，从中序遍历中得出DG是在B的左边，右边为空。2、然后剩下的先序遍历为DG，中序遍历为DG，D作为新的根节点，从中序遍历中得出G在D的右边，左边为空。

　　A结点的右孩子也是这样去构造

　　由中序和后序构造二叉树：

　　例如给定结点的中序序列(D,B,G,E,A,C,F)和后序序列(D,G,E,B,F,C,A)

　　八、哈夫曼树和哈弗曼编码

　　八、图

　　基本术语

　　出度：表示有多少条边是以这个为起点指向其它顶点的（该顶点有多少条边指向其它顶点）入度：有多少条边指向该顶点顶点的度：跟该顶点相连接的边的条数（跟该顶点连接有多少条边）无向图连通：就是比如说两个顶点A跟B，A去B家有路线，但是B去A家没有连通图：任意两个顶点都是连通的图连通分图

　　有向图连通：就是比如说两个顶点A跟B，A去B家有路线，但是B去A家没有强连通图：任意两个顶点都是连通的，还有就是A跟B两个家伙，现在是A可以去B家，B也可以去A家，两个条件强连通分量

　　图的存储结构

　　邻接矩阵：用一个二维数组表示顶点之间相邻关系的邻接矩阵的0,1，无穷的意思？不带权时，（无向图和有向图）1表示两个点是连通的，0表示不连通的带权的时候，连通的两点，矩阵中的值为两点间的权值，点和点自身标为0；不连通的两点的值为无穷

　　邻接表：我觉得是表示出度，用链表的方式表示该顶点能去哪对于无向图，邻接矩阵数组的第i行或第i列非零元素，非无穷元素的个数正好是顶点i的度对于有向图，邻接矩阵数组的第i行或（第i列）非零元素，非无穷元素的个数正好是顶点i的出度（或入度）1、已知一个有向图的邻接矩阵表示，计算第i个结点的出度的方法是（求第i行的非零元素个数之和） 2、已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是（求第i列的非零元素个数之和）

　　逆邻接表：我觉得是表示入度，用链表的方式表示有多少顶点能到该顶点邻接表的特点对于有n个顶点和e条边的无向图，其邻接表有n个头结点和2e个边结点，对于有n个顶点和e条边的有向图其邻接表有n个头结点和e个边结点。显然，对于边数目较少的稀疏图，邻接表比邻接矩阵更节省存储空间。

　　图的遍历方式：

　　深度优先遍历：就我感觉像：我先选一个没访问的点，然后再接着去遍历相邻的未被访问过的点，就这样一直去访问相邻而未被访问过的，如果一条路线的顶点都访问完后，然后还有其它条顶点没被访问过，则接着选一个没访问过的顶点开始，继续做上面的事情。总的来说，就是在找没被访问过的点。如上图8.4的深度优先遍历结果为:我们选0作为初始点，然后有：0,1,2,4,3；0,3,2,4,1,广度优先遍历：如上图8.4的广度优先遍历结果为:我们选0作为初始点，然后有：01,3,2,4；0,3,1,2,4

　　上方这图我们当作是图8.5深度优先遍历（DFS）：广度优先遍历（BFS）:(入队的所有序列就是BFS遍历的结果)步骤： (1)从某个顶点V出发，访问该顶点的所有邻接点V1，V2..VN (2)从邻接点V1，V2…VN出发，再访问他们各自的所有邻接点 (3)重复上述步骤，直到所有的顶点都被访问过(1)从顶点V1出发，v1入队，访问V1，V1的邻接点有V2 V3 V4，将它们入队,v1出队队列：V2 V3 V4 (2)访问队头V2，V2的邻接点为V1(已访问过，忽略)和V5，将V5入队，V2出队队列：V3 V4 V5 (3)访问V3，V3的邻接点为V1(访问过忽略) V4（已在队列忽略） V6 V5（已在队列，忽略），V6入队，V3出队 队列：V4 V5 V6 ……

　　图的应用

　　最小生成树：边上的权值之和最小的树称图的最小生成树例子三：像上图，有如下题目：设有无向图G，要求给出用普里姆算法构造最小生成树所走过的边的集合。答案： E={(1，3)，(1，2)，这里也是有点疑问，1,3连接完后，换边，又选取1,2，因为这里2,5权值太大了，就换边。换边的时候，但是不能断开原有连接的边，需要从已访问的顶点中，再选取一个权值最小的那条边才行，像这里，前面1,3和1,2都走过了，(3，5)，(5，6)，(6，4)}。还有一个答案应该也可以，这是我自己觉得的啊： E={(1，3)，(3，2)，(3，5)，(5，6)，(6，4)}普利姆最小生成树总结：你换边的时候，要找已连接的顶点，不能断开，然后再从已连接的顶点中找到最小权值的那条边，一直这样找下去即可。这两个算法就是帮我们从一个图中找出权值最小的边的工具普利姆算法：选定以某个顶点开始，去找各顶点上最小权值的边来构建最小生成树。选取A为起点，最小生成树序列应该是这样的：<A,B>,<B,C>,<C,E>,到这里是怎样，是接着从E这个顶点出发，选取E邻边权值最小的边，还是直接选取另外一个顶点作为起点开始？克鲁斯卡尔算法：直接去找最小的那条边，不用连着去找，拓补排序：在一个有向图中找一个拓扑序列的过程叫拓扑排序步骤：每次找一个没有前驱结点的顶点，并删除它，重复做这件事，如果有删除不了的顶点，表明有回路（就是找不到没有前驱结点的结点）关键路径：在AOE网中，从源点到汇点的所有路径中具有最大路径长度的路径称为关键路径AOE：源点：入度为0的顶点（我理解为像线性表的表头结点，没有前驱结点的结点）汇点：出度为0的顶点（没有后继的结点）最短路径：不带权图：经过的边数最少的路径称为最短路径。带权图：所经过的边权值之和最小的路径称为最短路径

　　常见提问方式的问题：

　　第九章：查找

　　平均查找长度

　　平均查找长度ASL的计算（请看这篇文章：https://www.cnblogs.com/ygsworld/p/10238729.html）总结：二叉排序树的ASL成功：（比较次数*不为空的结点数) * (比较次数*不为空的结点数）……/不为空的总结点数不成功：到为空结点比较次数（不包括为空结点的比较次数，因为已经是空了，不需要在比较了）*为空的结点数/不为空的总结点数+1

　　哈希表的ASL成功：所有探测次数相加/元素个数不成功：（如下图），什么时候才是不成功呢？待查关键字不在散列表中，要一直找到空元素才算查找失败。比如说一个不在哈希表中的关键字21，首先从第一个关键字14开始比较，直到找到空元素也就是散列地址为0的时候才算失败，这里探测次数是13次，然后关键字1开始，探测次数为12，……总结：所有不成功的探测次数相加/元素个数+1。不成功的探测次数：上面也有解释了，其实也就是从自身开始比较，直到找到为空的，或者整个哈希表中找完都没有的探测次数，（别忘了，自身开始也算比较了一次，中间比较……次，然后到空的也算比较了一次），

　　静态查找表顺序表有序表（折半查找）静态树表（分块查找）索引顺序表动态查找表二叉排序树概念：若根结点的左子树非空，则左子树的所有结点关键字均小于根节点的关键字，若根结点的右子树非空，则右子树的关键字的所有结点关键字均大于根节点的关键字根结点的左右子树本身又各是一个二叉排序树实现：

　　//二叉排序树查找关键字BiTree Search_BST(BitTree T,DataType x)///二叉树查找关健字非递归版：{ BiTree *p = T; while (p) { if (p->data == x) return p; p = (x < p->data) ? p->lchild : p->rchild; } return NULL;}1、（中序）遍历二叉排序树中的结点可以得到一个递增的关键字序列解释：二叉排序树特点：根节点大于左子树，小于右子树，中序遍历：左根右，不就是递增了吗2、中序遍历二叉排序树所得到的序列是（有序）序列（填有序或无序）。平衡二叉树（AVL树）一般情况下，一颗平衡二叉树总是二叉排序树，脱离二叉排序树来讨论平衡二叉树是没有意义的概念：若一颗二叉树中每个结点的左，右子树的高度最多相差1，由平衡因子决定是否为平衡二叉树，这个平衡因子怎么算呢？该结点左子树的高度减去右子树的高度（或者该结点右子树的高度减去左子树的高度），然后平衡因子绝对值小于等于1，即平衡因子为-1,0,1的时候，表示该结点是平衡的，当一颗二叉树的所有结点都是平衡的，就是一颗平衡二叉树一棵AVL树有如下必要条件：条件一：它必须是二叉查找树。条件二：每个节点的左子树和右子树的高度差至多为1。AVL树的查找、插入、删除操作在平均和最坏的情况下都是O（logn）平衡二叉树的构造（补充一下：要时刻要去注意每个节点的平衡因子了，每次插入一个结点的时候要注意，你要算哪个结点的平衡因子，就要以哪个结点作为根节点去算平衡因子）每个结点（每个结点的平衡因子）的左右子树的高度最多相差1（左子树高度不包括根结点-右子树不包括根结点），这样的二叉树叫做平衡二叉树总结：当平衡因子为正2顺时针旋转，当平衡因子为-2时，逆时针旋转，旋转的时候，还要考虑二叉排序树的要求B树B+树

　　哈希表的查找

　　哈希表（存放键值（地址）和数值的存储结构）哈希函数（把数值映射（帮这个数值找一个地址）到地址的函数） 为了能有效运用查找技术，必须解决的问题是：构造一个好的哈希函数，确定一个解决冲突的方法哈希函数的构造方法：直接定址法：直接以关键字（本身数值）或关键字加上某个常量作为地址好处：计算简单缺点：关键字不连续的时候会造成内存浪费（）就比如说：12跟134除留余数法：关键字除以一个整数p所得余数作为哈希地址（p小于等于哈希表长度m，但p最好小于m的素数，这种效果最好）数字分析法：提取关键字中取值较均匀的数字作为哈希地址哈希冲突的解决方法开放定址法（就是这个位置用不了，那我就去找用得了的位置）然后找用空闲位置的方法又有：线性探测法（就是这个位置用不了，那就从后面的位置依次寻找空闲的位置）缺点：容易发生堆聚现象；堆聚就是存入哈希表的若干个同义词（产生地址冲突的数据）在表中连成一片，占用了其他关键字的映射位置。平方探测法拉链法（把产生冲突的位置放在一个单链表里）

　　​！！！注意：二分法查找，low以0开始，high以n-1结束，例如：总共13个待排序的数，low就是0，high就是12,

　　第十章：内排序

　　口诀：希快选堆不稳定，二路归并空杂n，快堆归时杂都一样，除快时杂最坏

　　插入排序

　　直接插入排序（分两个区（有序区，无序区）把第一个元素当做已排序好的，放入有序区，然后后面待排序的（无序区），依次跟有序区的比较，找到插入的位置插入）

　　直接插入排序折半排序：希尔排序（分组排序）

　　交换排序

　　冒泡排序（N个数字要排序完成，总共进行N-1趟排序，每i趟的排序次数为(N-i)次，所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数）：基本思想是通过无序区中相邻元素关键字（关键字指的就是该元素的值）之间比较和位置的交换使关键字最小的元素如气泡一般逐渐往上漂浮，直至水面。这里对冒泡排序书上的和百度有个疑问，书上的按照定义，是把最小的漂浮到最上面，书上的例子对（9,8,7,6,5,4,3,2,1,0）进行排序，第一趟进行了9次比较，排序好的序列为（0,9,8,7,6,5,4,3,2,1）,但按照百度的话，是经过一趟排序后，最大的沉到了序列末尾，即（8,7,6,5,4,3,2,1,9），我是觉得书上的比较正确，也符合定义，但是百度的因为看多了，习惯了百度的这种说法，这两种都没问题吧，都可以用吧？快速排序：基本思想是在待排序的n个元素中任取一个元素（通常取第一个元素）作为基准，把该元素放入适当的位置，比它小的元素放在基准元素的左边，比它大的元素放在基准元素的右边。快速排序的划分过程：从两头向中间扫描。例如：（6,8,7,9,0,1,3,2,4,5），我们选6作为基准元素，然后从两头向中间扫描，这里只有6的右边这一头，反正从边向中间扫描，第一趟得出两个子区间（5,4,2,3,0,1）和（9,7,8），于是第一趟得到的序列就是（5,4,2,3,0,1,6,9,7,8），注意0和1，按道理是得到（5,4,2,3,1,0）的，但看书上都是倒数第一个和倒数第二个会换位置的。

　　选择排序

　　首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。最好，最坏，平均时间复杂度都为O(n*log2n)简单选择排序（在待排序找出最小的元素，放到有序区，然后）

　　堆排序小根堆排序

　　归并排序：

　　基数排序：

　　第一步以LSD为例，假设原来有一串数值如下所示：73, 22, 93, 43, 55, 14, 28, 65, 39, 81首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：01 812 223 73 93 434 145 55 65678 289 39第二步接下来将这些桶子中的数值重新串接起来，成为以下的数列：81, 22, 73, 93, 43, 14, 55, 65, 28, 39接着再进行一次分配，这次是根据十位数来分配：01 142 22 283 394 435 556 657 738 819 93第三步接下来将这些桶子中的数值重新串接起来，成为以下的数列：14, 22, 28, 39, 43, 55, 65, 73, 81, 93这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好。MSD的方式与LSD相反，是由高位数为基底开始进行分配，但在分配之后并不马上合并回一个数组中，而是在每个“桶子”中建立“子桶”，将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

　　常见提问方式的问题：