2023计算机考研初试在即，在最后阶段建议各位同学将知识点再系统复习一遍，以免有所遗漏！2022计算机考研数据结构第六单元知识点包含二分搜索、二叉搜索树、平衡二叉树等内容。高顿考研为大家整理了2022计算机考研数据结构第六单元知识点的详细内容，供大家参考复习！
二分搜索
关键字：用来标识一个数据元素的某个数据项。
主关键字：可以唯一标识一个数据元素的关键字。
次关键字：不能唯一标识一个数据元素的关键字。
搜索：在数据结构中寻找关键字等于给定值的元素。
平均搜索长度：搜索过程中关键字值之间的平均比较次数。
二分搜索
将中间位置上的元素的关键字与待搜索元素的关键字相比较
若相等：搜索成功。
若较小：在中间元素的左边的表中进行二分搜索，若较大则在右边进行。
实现：用low和high分别指示表的两端，m为中间元素的位置
初始时有m=(low+high)/2
若表长为偶数，根据小数与int型数的转换可知，m应该向下取整。
每次比较之后，根据比较的结果调整low或high的值来调整需要继续进行二分搜索操作的表的范围。
二叉搜索树
每个结点的关键字都大于其左子树上所有结点的关键字，小于右子树上所有结点的关键字(中序遍历该树，所得序列的关键字的值递增)。
搜索过程中，若元素值小于根结点的关键字值，则进入左子树，反之进入右子树。
1)二叉搜索树的删除：
a.若被删结点没有孩子：用空子树NULL代替即可。
b.若被删结点有一个孩子：用孩子代替即可。
c.若被删结点有两个孩子：找到其中序遍历下的直接后继，将其值复制，并删除该后继。
2)二叉搜索树的高度：
对于n个结点的二叉搜索树：
最大高度为n，此时，按此顺序插入的元素的关键字值递增或者递减。
最小高度为log2n，将结点按关键字从小到大排列，二分搜索的过程中，按比较次数由小到大的顺序，插入结点可得最小高度。
平衡二叉树
任何一个结点的左右子树的高度相差不过1。
1)平衡因子：结点的左子树的高度减去右子树的高度。
平衡过程：插入、平衡、重组
a.插入：将新结点q按照平衡二叉搜索树的排序性质作为树叶插入，令其平衡因子为0，记下离q最近且平衡因子不为0的祖先结点s，若所有祖先结点的平衡因子均为0，令s指向根结点。
b.平衡：修改从s到q的路径上的结点的平衡因子，不修改s和q，对于其中的结点p，若q插在p的左子树，则平衡因子+1，否则-1。
c.重组：当s的平衡因子为0时，s为根结点，此时将s的平衡因子+1或者-1即可。
若s的平衡因子为-1，q插在s的左子树，或+1，插在右子树，只需改平衡因子为0。
若s的平衡因子为+1，q插在左子树，此时左重组，反之右重组。
2)重组方式：
a.若插入前，从根结点到新结点的插入位置的路径上，所有结点的平衡因子值均为0，则插入即可。
b.若插在结点较矮的子树上，则插入即可。
c.if(r->bf==1)
{s->lchild=r->rchild;r->rchild=s;}//LL
d.u=r->rchild;
r->rchild=u->lchild;
u->lchild=r;
s->lchild=u->rchild;
u->rchild=s;
散列表：
散列搜索的搜索过程是按照关键字来计算元素可能的存储地址
确定一个函数，每个元素的关键字经由这一函数映射出一个函数值
这样的函数称作散列函数，得到的值为散列地址，函数的值域为散列地址空间
好的散列函数应该使得函数值尽可能均匀分布在散列地址空间
1)处理冲突：
a.开地址法(线性探测)
地址为i的单元发生冲突时，依次探测(i+1)%m，(i+2)%m…将元素插入第一个空单元。
即每次往后移动一个存储单元查找是否有空闲地址，允许循环，直到再次到达地址i或在此之前找到空闲地址。
缺点：n个被占用的单元连成一片时，后面的空单元被占用的可能性增加。
b.开地址法(双散列函数探测)
当i=h1(k)被占用时，
C=h2(k)然后依次探测(i+c)%m(i+2c)%m…
线性探测每次只移动一个存储单元，双散列函数探测法中，每次移动的大小由第二个散列函数决定。
缺点：由于寻找是跳跃性的，部分空单元可能总被跳过去，无法利用。
c.拉链法：将散列地址相同的元素链接起来，构成一个线性链表，将各链表的表头指针存入散列表。
2)装载密度=存入散列表的节点个数散列地址空间大小。
3)开地址法中，删除一个结点时，只能在删除的结点上做标记，不能真正删除，不然会影响其他的结点查找。
不同搜索方式的时间复杂度：
顺序搜索：查找和插入的时间复杂度：O(n)
二分查找：查找时间复杂度O(logn)插入时间复杂度O(n)
二叉搜索树：查找时间复杂度O(logn)插入时间复杂度O(logn)
散列表法：O(1)
写评论
