查找的基本概念和顺序查找
- 查找定义：在数据集合中寻找满足某种条件的数据元素的过程称为查找
- 关键字：数据元素中某个可以以唯一标识该元素的数据项
- 平均查找长度（ASL：Average Search Length）:在查找的过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值
顺序查找(线性查找)，主要用于在线性表中进行查找。从查找表的一端开始，顺序扫描查找表，依次将扫描到的关键字和待查找的值key进行比较。如果相等，则查找成功。如果扫描结束仍然没有发现相等的数据元素，则查找失败。
- 时间复杂度为O(n)
折半查找
算法思路：
- 首先将给定值key与表中中间位置元素的关键字比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分中。然后在缩小的范围内继续进行同样的查找，如此重复直到找到为止，或者确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。
折半查找分析
折半查找判定树
- 对于折半查找，查找的比较次数就是从根结点到该结点经历的结点数
- 时间复杂度为O(logn)
- 概要: 具有N个（N>0）结点的完全二叉树的高度为 [log2(N+1)] 或 [log2N] +1。
分块查找
- 分块查找又称为索引顺序查找
分块查找思想：
- ①确定待查找值在哪个块（折半查找）
②在确定的块中查找待查找值（顺序查找）
分块查找分析
- 由于分块查找实际是进行两次查找，所以整个算法的平均查找长度是两次查找的平均查找长度之和。
即ASL分块=ASL折半+ASL顺序
二叉排序树
- 二叉排序树(Binary Search Tree 也叫二叉搜索树)或者是一棵空树，或者是具有以下性质的二叉树
①若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
②若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
③它的左右子树也是一棵二叉排序树。
算法思想
- 由于二叉排序树的特点(左子树<根结点<右子树),所以每次查找一个关键字，需要先和根结点进行比较：
如果这个关键字小于根结点的值，则再到这个根结点的左子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。
如果这个关键字大于根结点的值，则再到这个根结点的右子树进行同样的比较操作一直进行下去直到找到该关键字，表示查找成功，或者是空指针，表示查找失败。
* 查找关键字代码
* 1
* 2
* 插入关键字代码
* 1)空树：直接插入新结点返回成功2)树不空：检查是否存在关键字重复的结点：
①存在：返回插入失败
②不存在：检查根结点的值和待插入关键字值的大小关系递归插入左右子树
*
* 构造代码
*
* 删除结点
* ①删除的是叶子结点
* 方法：直接删去该结点即可
* ②删除的是仅有左子树或者右子树的结点
* 方法：“子承父业”
* ③删除的是左右子树都有的结点
* 仿照②类型，先将一个孩子“继承父业”，另一个孩子“归顺”于这个孩子方法：找到待删除结点的直接前驱或者直接后继结点，用该结点来替换待删除结点，再删除该结点。
二叉排序树分析
- 查找时间复杂度是O(n)
- 概要: “左小右大”
平衡二叉树(AVL树)
- 平衡二叉树(AVL树)是特殊的二叉排序树，特殊的地方在于左右子树的高度之差绝对值不超过1，而且左右子树又是一棵平衡二叉树。
平衡因子
- 定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是−1、0或1。
平衡调整
平衡二叉树的建立过程和二叉排序树的建立过程是相似的，都是从一棵空树开始陆续插入结点。不同的地方在于对于平衡二叉树的建立过程中，由于插入结点可能会破坏结点的平衡性，所以需要进行平衡调整。
LL调整(左孩子的左子树上插入结点导致)
- 最小不平衡子树根结点的平衡因子为2>0
它的左孩子结点平衡因子为1>0
两个都大于0，所以直接右旋就可以调整
* 概要: “正则右旋”
* RR调整(右孩子的右子树上插入结点导致)
* 最小不平衡子树根结点的平衡因子为-2<0它的右孩子结点平衡因子为-1<0
两个都小于0，所以直接左旋就可以调整
* 概要: “负则左旋”
* LR调整(左孩子的右子树上插入结点导致)
* RL调整(右孩子的左子树上插入结点导致)
* 概要: 先局部转换为LL或RR，最后进行调整分析
- 含有n个结点平衡二叉树的最大深度为O(log2n)，因此，平衡二叉树的平均查找长度为O(log2n)
平衡二叉树
题目: 给出一个二叉树,判断是否是平衡二叉树.
一棵高度平衡的二叉树的定义是：一棵二叉树中每个节点的两个子树的深度相差不会超过1。
扩展: 二叉树的最大高度, 也是使用类似的递归思想, 二叉树的最大宽度是使用层次遍历,
// 二叉树的最大高度
int getHeight(TreeNode *root) {
if(root == NULL) return 0;
return max(getHeight(root->left),getHeight(root->right))+1;
}
bool isBalanced(TreeNode *root) {
if(root == NULL) return true;
if(abs(getHeight(root->left) - getHeight(root->right))>1){
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}B树和B+树
2-3树
2-3树是一种多路查找树：2和3的意思就是2-3树包含两种结点
- 1)2结点包含一个元素和两个孩子(或者没有孩子)。
①左子树包含的元素小于该结点的元素值，右子树包含的元素大于该结点的元素值
②2结点要不有两个孩子，要不就没有孩子，不允许有一个孩子* 2)3结点包含一大一小两个元素和三个孩子(或者没有孩子)。(两个元素按大小顺序排列好)①左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。
②3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子* 3)2-3树所有叶子结点都在同一层次2-3-4树
2-3-4树也是一种多路查找树：2和3和4的意思就是2-3-4树包含三种结点
- 1)2结点包含一个元素和两个孩子(或者没有孩子)。
①左子树包含的元素小于该结点的元素值，右子树包含的元素大于该结点的元素值
②2结点要不有两个孩子，要不就没有孩子，不允许有一个孩子* 2)3结点包含一大一小两个元素和三个孩子(或者没有孩子)。①左子树包含的元素小于该结点较小的元素值，右子树包含的元素大于该结点较大的元素值，中间子树包含的元素介于这两个元素值之间。
②3结点要不有三个孩子，要不就没有孩子，不允许有一个或两个孩子* 3)4结点包含小中大三个元素和四个孩子(或者没有孩子)。①左子树包含的元素小于该结点最小的元素值，第二个子树包含大于最小的元素值小于中间元素值的元素，第三个子树包含大于中间元素值小于最大元素值的元素，右子树包含的元素大于该结点最大的元素值。
②4结点要不有四个孩子，要不就没有孩子，不允许有一个或两个或三个孩子* 4)2-3-4树所有叶子结点都在同一层次B树
- B树也是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例，我们把树中结点最大的孩子数目称为B树的阶。通常记为m。
一棵m阶B树或为空树，或为满足如下特性的m叉树：
* 1）树中每个结点至多有m棵子树。（即至多含有m-1个关键字) ("两棵子树指针夹着一个关键字")
* 2）若根结点不是终端结点，则至少有两棵子树。(至少一个关键字)
* 3）除根结点外的所有非叶结点至少有 ⌈m/2⌉棵子树。（即至少含有⌈m/2⌉-1个关键字）
* 4）所有非叶结点的结构如下：
* 5）所有的叶子结点出现在同一层次上，不带信息。(就像是折半查找判断树中查找失败的结点)
* 1.B树的查找操作
* 查找过程：①先让待查找关键字key和结点的中的关键字比较，如果等于其中某个关键字，则查找成功。
②如果和所有关键字都不相等，则看key处在哪个范围内，然后去对应的指针所指向的子树中查找。
Eg:如果Key比第一个关键字K1还小，则去P0指针所指向的子树中查找，如果比最后一个关键字Kn还大，则去Pn指针所指向的子树中查找。
* 2.B树的插入操作
* 分裂的方法：取这个关键字数组中的中间关键字(⌈n/2⌉)作为新的结点，然后其他关键字形成两个结点作为新结点的左右孩子。
* 3.B树的删除操作
* B树中的删除操作与插入操作类似，但要稍微复杂些，要使得删除后的结点中的关键字个数≥⌈m/2⌉-1 ，因此将涉及结点的“合并”问题。由于删除的关键字位置不同，可以分为关键字在终端结点和不在终端结点上两种情况。
* 1）如果删除的关键字在终端结点上（最底层非叶子结点）：
①结点内关键字数量大于⌈m/2⌉-1 ，这时删除这个关键字不会破坏B树的定义要求。所以直接删除。
②结点内关键字数量等于⌈m/2⌉-1 ，并且其左右兄弟结点中存在关键字数量大于⌈m/2⌉-1 的结点，则去兄弟阶段中借关键字。
③结点内关键字数量等于⌈m/2⌉-1 ，并且其左右兄弟结点中不存在关键字数量大于⌈m/2⌉-1 的结点，则需要进行结点合并。
* 2）如果删除的关键字不在终端结点上（最底层非叶子结点）：需要先转换成在终端结点上，再按照在终端结点 上的情况来分别考虑对应的方法。
* 相邻关键字：对于不在终端结点上的关键字,它的相邻关键字是其左子树中值最大的关键字或者右子树中值最小的关键字。
* 第一种情况：存在关键字数量大于⌈m/2⌉-1 的左子树或者右子树，在对应子树上找到该关键字的相邻关键字，然后将相邻关键字替换待删除的关键字。
* 第二种情况：左右子树的关键字数量均等于⌈m/2⌉-1 ，则将这两个左右子树结点合并，然后删除待删除关键字。B+树
- B+树是常用于数据库和操作系统的文件系统中的一种用于查找的数据结构
- m阶的B+树与m阶的B树的主要差异在于：
1）在B+树中，具有n个关键字的结点只含有n棵子树，即每个关键字对应一棵子树；而在B树中，具有n个关键字的结点含有(n+1)棵子树。
2）在B+树中，每个结点（非根内部结点）关键字个数n的范围是 ⌈m/2⌉≤n≤m（根结点1≤n≤m），在B树中，每个结点（非根内部结点）关键字个数n的范围是⌈m/2⌉ -1≤n≤m-1（根结点：1≤n≤m-1）。
3）在B+树中，叶结点包含信息，所有非叶结点仅起到索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
4）在B+树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。
