数据结构之常见查找

     二叉排序树:

     二叉排序树或者是一棵空树,或者是一棵具有以下性质的二叉树:

     (1)若它有左子树,则左子树上的所有结点都小于根结点数据.

     (2)若它有右子树,则右子树上的所有结点都大于根结点数据.

     (3)左右子树各是一棵二叉排序树.

 

 二叉排序树删除节点(有左右子树)

删除无右子树节点

 删除无左右子树

     索引查找:

     对大量数据进行查找时块,索引要多占用空间,更新时不仅要更新主表,也要更新索引表.

     1.在索引表中进行查找.

     查找过程如下:

     (1)首先根据给定的关键字key,按定义的函数计算出索引值index1,在索引表上查找出索引值等于index1的索引项,以确定对应子表在主表中的开始位置和长度.

     (2)接着根据从索引表中获取的开始序号start,在主表指定的位置(即子表的开始处)顺序查找关键字key.

     2.向主表中插入数据.

     在线性表的索引存储结构上进行插入删除运算的算法,与查找算法类似.其具体过程如下:

     (1)根据待插入的元素的值查找索引表,确定出对应的子表.

     (2)接着,根据待插入元素的关键字,在该子表中做插入元素的操作.

     (2)插入完成后,修改索引表中相应子表的长度.

     哈希表:

     哈希表的基本思想是:以线性表中每个元素的关键字key为自变量,通过一定的函数关系h(key)计算出函数的值,把这个值作为数组的下标,将元素存入对应的数组元素中. 

     函数h(key)称为哈希函数,函数的值称为哈希地址.

     缺点1:可能浪费空间

     缺点2:可能发生冲突

     常用的构造哈希函数的方法:

    >直接定址法(关键字本身或者关键字加上某一个常数直接作为地址,一般要求关键字连续不重复)

    >除法取余法(一般除数选择奇数或者素数)

    >数字分析法(对关键字的某些部分进行分析)

    >平方取中法(平方取中)

    >折叠法(用关键字拆分成长度相等的几段再相加)

    可以根据数据特点自己构造适合的哈希函数

     处理冲突的方法:

    >开放地址法.

    >链接法.