数据结构速成--查找

        由于是速成专题，因此内容不会十分全面，只会涵盖考试重点，各学校课程要求不同 ，大家可以按照考纲复习，不全面的内容，可以看一下小编主页数据结构初阶的内容，找到对应专题详细学习一下。  

目录

一、顺序查找

二、折半查找

三、平衡二叉树（AVL树）

四、散列查找

---

一、顺序查找

         顺序查找，主要用于线性表中进行查找。

二、折半查找

        折半查找（二分查找），仅适用于有序的顺序表。

         这里涉及到了二叉排序树，注意左子树都小于根，右子树都大于根。树是递归定义的，所以记住左孩子<父结点，右孩子>父结点。

三、平衡二叉树（AVL树）

        平衡二叉树就是左右子树高度之差的绝对值不超过1，就是说高度差=左子树高度-右子树高度=0、1、-1。

        当树不平衡时，我们就需要调整，我们要分清是什么结点导致了树的不平衡，比如左子树多了个左孩子，右子树多了个左孩子等等。

        网上有很多调整平衡二叉树的教程，无非就是左旋和右旋。实际上我们只需要找到第一个不平衡结点，向下找两个连续的结点进行调整即可。

        插入了90导致了66不平衡，就向下找两个连续的结点，一定要在66到90的路上找，所以找到了68、70，所以我们只需要对66、68、70三个结点进行调整，让这三个结点变成平衡二叉树，再把剩下的结点按性质插回去。

四、散列查找