索引的细节
目录
什么是线性 搜索算法？
线性搜索是一种非常简单的搜索算法。在这种类型的搜索中，逐个对所有项目进行顺序搜索。检查每个项目，如果找到匹配项，则返回该特定项目，否则搜索将继续，直到数据收集结束。
算法：二进制搜索算法
二进制搜索是一种快速搜索算法，运行时复杂度为Ο(log n)。这种搜索算法的工作原则是分而治之。为使此算法正常工作，数据收集应采用排序形式。
二进制搜索通过比较集合的最中间项来查找特定项。如果匹配发生，则返回项目的索引。如果中间项大于项，则在中间项左侧的子阵列中搜索项。否则，在中间项右侧的子阵列中搜索项。该过程也在子阵列上继续，直到子阵列的大小减小到零。
二进制搜索如何工作？
要使二进制搜索起作用，必须对目标数组进行排序。我们将通过一个图例来学习二元搜索的过程。以下是我们的排序数组，让我们假设我们需要使用二进制搜索来搜索值31的位置。
首先，我们将使用此公式确定数组的一半
mid = low + (high - low) / 2
这里，0 +(9-0)/ 2 = 4(整数值为4.5)。所以，4是数组的中间位置。
现在我们将存储在位置4的值与搜索的值进行比较，即31.我们发现位置4的值是27，这不匹配。由于值大于27并且我们有一个排序数组，因此我们也知道目标值必须位于数组的上半部分。
我们将低点改为+1，再次找到新的中值。
low = mid + 1
mid = low + (high - low) / 2
我们新的中期现在是7。我们将位置7处存储的值与目标值31进行比较。
存储在位置7的值不匹配，而是比我们正在寻找的值更多。因此，该值必须位于此位置的下半部分。
因此，我们再次计算中期。这次是5。
我们将位置5处存储的值与目标值进行比较。我们发现这是一场比赛。
我们得出结论，目标值31存储在位置5处。
二进制搜索将可搜索项目减半，从而减少了对更少数字进行比较的次数。
什么是二叉排序树？
我们直接看它的性质：
- 若它的左子树不空，则左子树上所有结点的值均小于它根结点的值。
- 若它的右子树不空，则右子树上所有结点的值均大于它根结点的值。
- 它的左、右树又分为⼆叉排序树
显然，二叉排序树与二叉树一样，也是通过递归的形式定义的。因此，它的操作也都是基于递归的方式。
二叉排序树也叫二叉查找树、二叉搜索树，既然名字都不一般，那它显然和普通的二叉树不同。那到底有什么不同，它的特点或者优点在哪里呢？不妨，我们来构建一棵二叉树。
构建二叉排序树
假设我们有以下数据，我们按从左到右的顺序来构建二叉排序树：
- 首先，将8作为根节点
- 插入3，由于3小于8，作为8的左子树
- 插入10，由于10大于8，作为8的右子树
- 插入1，由于1小于8，进入左子树3，1又小于3，则1为3的左子树
- 插入6，由于6小于8，进入左子树3，6又大于3，则6为3的右子树
- 插入14，由于14大于8，进入右子树10，14又大于10，则14为10的右子树
- 插入4，由于4小于8，进入左子树3，4又大于3，进入右子树6，4还小于6，则4为6的左子树
- 插入7，由于7小于8，进入左子树3，7又大于3，进入右子树6，7还大于于6，则7为6的右子树
- 插入13，由于13大于8，进入右子树10，又13大于10，进入右子树14,13小于14，则13为14的左子树
经过以上的逻辑，这棵二叉排序树构建完成。 接下来是构建过程：
我们可以看出：
- 只要左子树为空，就把小于父节点的数插入作为左子树
- 只要右子树为空，就把大于父节点的数插入作为右子树
- 如果不为空，就一直往下去搜索，直到找到合适的插入位置
了解了如何构建后，我们不禁要问，这有啥用呀？感觉没啥特别的地方呢？别急！我们马上揭晓！
我们对这棵二叉树进行中序遍历，看看会发生什么？你自己试一试！
没错，这棵二叉树中序遍历结果为：
根据以上思路，我们其实就可以写出代码了，构建的过程其实就是插入的过程：
void insert(int key)
{
//定义一个临时指针 用于移动
Node* temp = root;//方便移动 以及 跳出循环
Node* prev = NULL;//定位到待插入位置的前一个结点
while (temp != NULL)
{
prev = temp;
if (key < temp->data)
{
temp = temp->left;
}
else if(key > temp->data)
{
temp = temp->right;
}
else
{
return;
}
}
if (key < prev->data)
{
prev->left = (Node*)malloc(sizeof(Node));
prev->left->data = key;
prev->left->left = NULL;
prev->left->right = NULL;
}
else
{
prev->right = (Node*)malloc(sizeof(Node));
prev->right->data = key;
prev->right->left = NULL;
prev->right->right = NULL;
}
}什么是AVL树？
当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O（log2N） ，搜索时间复杂度O( log2N)。
AVL树的性能分析
AVL树是一棵绝对平衡的二叉搜索树,因为每个节点的平衡因子gap不超过1;这样可以保证查询时高效的时间复杂度，即log2(N) ;
但是:如果要对AVL树做一些结构修改的操作，性能非常低下:
比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(不改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
原文地址：https://blog.csdn.net/whs_8792/article/details/143669134
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！