C语言博客作业05--查找

| 这个作业属于哪个班级 | 数据结构--网络2011,2012（集美大学） |
| ---- | ---- | ---- | ---- |
| 这个作业的地址 | C语言博客作业05--查找
| 这个作业的目标 | 学习查找的相关结构 |
| 姓名 | 张官德 |

• 顺序查找
  查找方式为从头扫到尾，找到待查找元素即查找成功，若到尾部没有找到，说明查找失败。

二叉搜索树做插入操作
若二叉排序树为空，则创建一个key域为k的节点。将它作为根结点；否则将k和
根结点的关键字比较，若俩者相同，则说明树中已有该关键字，无需插入；若k<key,
则将它插入根结点的左子树中，否则插入右子树中。

• 创建

• 插入

• 删除

平衡二叉搜索树又被称为AVL树，且具有以下性质：
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。
也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）
失衡做法：

有一组数据{16,3,7,11,9,26,18,14,15}一个个插入后失衡调节方法如下：

• AVL树的高度和树的总节点数n的关系？
  设N(h)为高度为h的AVL树的最小节点数目，则N(h)=N(h-1) + N(h-2) +1; N(0)=0, N(1)=1; 类似斐波那契数列； 插入、查找和删除的性能均为log(n)
• 介绍基于AVL树结构实现的STL容器map的特点、用法
  STL总共实现了两种不同结构的管理式容器：树形结构和哈希结构。
  Map是STL的一个关联容器，翻译为映射，数组也是一种映射。
  map通常被实现为二叉搜索树(更准确的说：平衡二叉搜索树(红黑树))。
  红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是红或黑（非红即黑）。
  通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍，因此，红黑树是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少，所以对于搜索，插入，删除操作较多的情况下，通常使用红黑树。
  特点：map提供关键字到值的映射 ，其中第一个可以称为关键字，每个关键字只能在map中出现一次，第二个称为该关键字的值。

• 1）B-树和AVL树区别，其要解决什么问题？
  B-树是一棵多叉平衡搜索树，旨在比AVL树能够拥有更低的树高，提高查找的效率，但是同AVL树一样，面对插入和删除数据的操作后需要维持平衡，这可能带来一些得不偿失的情况。
  其次B-树可以被采用在外存的数据查询上，因为树高比较低，这样就可以减少磁盘的I/O次数
• 2）B-树定义。结合数据介绍B-树的插入、删除的操作，尤其是节点的合并、分裂的情况。

B树也称B-树,它是一颗多路平衡查找树。我们描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。

一颗m阶的B树定义如下：

1）每个结点最多有m-1个关键字。

2）根结点最少可以只有1个关键字。

3）非根结点至少有Math.ceil(m/2)-1个关键字。

4）每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它。

5）所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。

• B树的插入
  对高度为h的m阶B树，新结点一般是插在第h层。通过检索可以确定关键码应插入的位置。然后分两种情况讨论：

（1）若该结点中关键码个数小于m-1，则直接插入。

（2）如该结点中关键码个数等于m-1，则将引起结点的分裂。以中间关键码为界将结点一分为二，产生一个新结点， 并把中间关键码插入到父结点（h-1层）中。

（3）向父亲结点插入中间关键字的时候，重复以上两个步骤最坏情况一直分裂到根结点，建立一个新的根结点，整个B树增加一层

• B树的删除
  删除操作是指，根据key删除记录，如果B树中的记录中不存对应key的记录，则删除失败。

1）如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key，

然后在后继key所在的子支中删除该后继key。此时后继key一定位于叶子结点上，这个过程和二叉搜索树删除结点的方式类似。删除这个记录后执行第2步

2）该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作，否则执行第3步。

3）如果兄弟结点key个数大于Math.ceil(m/2)-1，则父结点中的key下移到该结点，兄弟结点中的一个key上移，删除操作结束。

否则，将父结点中的key下移与当前结点及它的兄弟结点中的key合并，形成一个新的结点。原父结点中的key的两个孩子指针就变成了一个孩子指针，

指向这个新结点。然后当前结点的指针指向父结点，重复上第2步。

例如：

• B+树的定义
  每个节点最多可以有 m 个元素；

除了根节点外，每个节点最少有 (m/2) 个元素；

如果根节点不是叶节点，那么它最少有 2 个孩子节点；

所有的叶子节点都在同一层；

一个有 k 个孩子节点的非叶子节点有 (k-1) 个元素，按升序排列；

某个元素的左子树中的元素都比它小，右子树的元素都大于或等于它；

非叶子节点只存放关键字和指向下一个孩子节点的索引，记录只存放在叶子节点中；

相邻的叶子节点之间用指针相连。

• B+树的用途：
  B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。
  B+树的磁盘读写代价更低,盘块能容纳的结点中关键字数量更多，一次性读入内存中可以查找的关键字也就越多

• 1)哈希表的设计主要涉及哪几个内容？
  哈希表(hash table)又称散列表,其基本思路是，设要存储的元素个数为n.设置一一个长度为m(m≥n)的连续内存单元，以每个元素的关键字k;(0≤i≤<n-1)为自变量,通过一个称为
  称为哈希函数(hash function)的函数h(ki)把k;映射为内存单元的地址(或下标)h(ki),并把该元素存储在这个内存单元中,h(k.)也称为哈希地址(hash adress)。把如此构造的线
  性表存储结构称为哈希表。

• 2）哈希表的构造及ASL成功、不成功的计算

• 3）哈希链的构造及ASL成功、不成功的计算

伪代码：

伪代码：