索引的细节

目录

什么是线性 搜索算法？

算法：二进制搜索算法

二进制搜索如何工作？

什么是二叉排序树？

构建二叉排序树

什么是AVL树？

AVL树的性能分析

---

什么是线性 搜索算法？

线性搜索是一种非常简单的搜索算法。在这种类型的搜索中，逐个对所有项目进行顺序搜索。检查每个项目，如果找到匹配项，则返回该特定项目，否则搜索将继续，直到数据收集结束。

算法：二进制搜索算法

二进制搜索是一种快速搜索算法，运行时复杂度为Ο(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处。

二进制搜索将可搜索项目减半，从而减少了对更少数字进行比较的次数。

 

什么是二叉排序树？

我们直接看它的性质：

• 若它的左子树不空，则左子树上所有结点的值均小于它根结点的值。
• 若它的右子树不空，则右子树上所有结点的值均大于它根结点的值。
• 它的左、右树又分为⼆叉排序树

显然，二叉排序树与二叉树一样，也是通过递归的形式定义的。因此，它的操作也都是基于递归的方式。 

二叉排序树也叫二叉查找树、二叉搜索树，既然名字都不一般，那它显然和普通的二叉树不同。那到底有什么不同，它的特点或者优点在哪里呢？不妨，我们来构建一棵二叉树。

构建二叉排序树

假设我们有以下数据，我们按从左到右的顺序来构建二叉排序树：

1. 首先，将8作为根节点
2. 插入3，由于3小于8，作为8的左子树
3. 插入10，由于10大于8，作为8的右子树
4. 插入1，由于1小于8，进入左子树3，1又小于3，则1为3的左子树
5. 插入6，由于6小于8，进入左子树3，6又大于3，则6为3的右子树
6. 插入14，由于14大于8，进入右子树10，14又大于10，则14为10的右子树
7. 插入4，由于4小于8，进入左子树3，4又大于3，进入右子树6，4还小于6，则4为6的左子树
8. 插入7，由于7小于8，进入左子树3，7又大于3，进入右子树6，7还大于于6，则7为6的右子树
9. 插入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树或者是空树，或者是具有以下性质的二叉搜索树：

1. 它的左右子树都是AVL树
2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O（log2N） ，搜索时间复杂度O( log2N)。
 

AVL树的性能分析

AVL树是一棵绝对平衡的二叉搜索树,因为每个节点的平衡因子gap不超过1;这样可以保证查询时高效的时间复杂度，即log2(N) ;

但是:如果要对AVL树做一些结构修改的操作，性能非常低下:

比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。

因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(不改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。