9.1.3分块香找又称索引顺序香找一介于顺序查和折半查找之间。适合于关键字分块有序typedef struct {KeyType key,intstadr,} indexItem;typedef struct:indexltem *elem;intlength;findexTable,- 算法Search Idx(SSTable ST,indexTable ID, KeyT kval)一设索引长度b，顺序表长度为n，则：ASLidx=ASL(b)+ASL(n/b)=log2(b+1)-1+(n/b+1)/26中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 6 中国科学技术大学 • 又称索引顺序查找 – 介于顺序查和折半查找之间。适合于关键字分块有序 typedefstruct { KeyType key; int stadr; }indexItem; typedefstruct{ indexItem *elem; int length; }indexTable; – 算法Search_Idx(SSTable ST,indexTable ID, KeyT kval) – 设索引长度b，顺序表长度为n，则： ASLidx=ASL(b)+ASL(n/b)≈log2 (b+1)-1+(n/b+1)/2 9.1.3分块查找
索引表2617487696块内最大关键字5811518块的起始序号SST.elem-732484229527668171016821262347304086968223456789101112131415161718011920中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 7 中国科学技术大学 索引表 17 26 48 76 96 1 5 8 15 18 块内最大关键字 块的起始序号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 17 10 16 8 21 26 23 47 30 40 32 48 42 29 76 52 68 86 96 82 SST.elem
9.2动态查找表ADT DynamicSearchTable:数据对象：D是具有相同特性的元素集合数据关系：同属集合关系。基本操作：-InitDSTable（&DT）- DestroyDSTable （&DT)- SearchDSTable （DT , kval )*- InsertDSTable （&DT,e)￥- DeleteDSTable (&DT,kval )-TraverseDSTable （DT,VisitO)ADT DynamicSearchTable:8中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 8 中国科学技术大学 9.2动态查找表 ADT DynamicSearchTable{ 数据对象：D是具有相同特性的元素集合。 数据关系：同属集合关系。 基本操作： – InitDSTable（&DT） – DestroyDSTable（&DT） – SearchDSTable（DT，kval） – InsertDSTable（&DT,e） * – DeleteDSTable（&DT,kval） * – TraverseDSTable（DT,Visit()） }ADT DynamicSearchTable;
9.2.1二叉香找树·查找树、二叉查找树一通过和根结点的关键字进行比较可以将继续查找的范围缩小到某一颗子树中，具有该特性的树称查找树。二叉查找树又称二叉排序树。·例：二叉查找树的查询过程。Status Search BST(BiTreeT,KeyTypekval,BiTreef,BiTree &p)·例：二叉查找树的插入算法电Status Insert BST(BiTree &T, ElemType e)9中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 9 中国科学技术大学 9.2.1二叉查找树 • 查找树、二叉查找树 – 通过和根结点的关键字进行比较可以将继续查找的范 围缩小到某一颗子树中，具有该特性的树称查找树。 二叉查找树又称二叉排序树。 • 例:二叉查找树的查询过程。 Status Search_BST(BiTree T,KeyType kval,BiTree f, BiTree &p) • 例:二叉查找树的插入算法 Status Insert_BST(BiTree &T, ElemType e)
册删除结点的处理方法1)若是叶子结点，直接删除2)只有一个孩子，则将其孩子直接挂到其双亲上3)有两个孩子，找左孩子中最大的一个元素，代替被删除结点，最大元素肯定只有一个孩子，按2）处理删除最大元素- Status Delete BST(BiTree &T, KeyType kval)·二叉查找树的平均查找长度p（n)=2（n+ 1) /n *logn+C·二叉平衡（查找）树一树中每个结点的左、右子树深度之差的绝对值不大于1，这种平衡状态的二叉查找树。实现方法：平衡旋转技术10中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 10 中国科学技术大学 • 删除结点的处理方法 1)若是叶子结点，直接删除 2)只有一个孩子，则将其孩子直接挂到其双亲上。 3)有两个孩子，找左孩子中最大的一个元素，代替被 删除结点，最大元素肯定只有一个孩子，按2）处 理删除最大元素 – Status Delete_BST(BiTree &T, KeyType kval) • 二叉查找树的平均查找长度 p（n）＝2（n＋1）/n *logn+C • 二叉平衡（查找）树 – 树中每个结点的左、右子树深度之差的绝对值不大 于1，这种平衡状态的二叉查找树。实现方法：平 衡旋转技术