概念

平均查找长度： \(ASL = \sum_{i=1}^n p_ic_i\) n是查找表中的长度，P~i~是查找第i个元素的概率 c~i~是找到表中其关键字与给定值相等的记录时，和给定值已进行过比较的关键字的个数（就是找到它之前比较过多少次了）

静态查找表

顺序表的查找

有序表的查找

索引顺序表的查找

动态查找表

二叉排序树和平衡二叉树

二叉排序树

• 左子树不空，左子树上所有结点的值均小雨它的根结点的值
• 右子树不空，右子树上所有结点的值均大于它根结点的值
• 其左、右子树也分别为二叉排序树

查找：

BiTree SearchBST(BiTree T, keyType key){
	if(T==NULL) return NULL;
	else if(T->data.key==key) return T;
		else if(key<T->data.key)
			return SearchBST(T->lchild, key);
		else
			return SearchBST(T->rchild);
}

插入：

Status InsertBST(BiTree &T, ElemType e){
	p = T; father = NULL;
	while(p&&p->data.key!=e.key){
		father = p;
		if(e.key > p->data.key)
			p = p->rchild;
		else
			p = p->lchild;
	}
	if(p)
		return false;
	s = new BiTree;
	s->data = e;
	s->lchild = s->rchild = NULL;
	if(father==NULL)  T = s;
	else if(e.key>father->data.key)
			father->rchild = s;
		else
			father->lchild = s;
	
}

删除：

待删除的结点为以下三种情况：

• 待删除的结点*p是个叶子结点

  如果是左孩子，让父结点的左指针域置空 如果是右孩子，让父结点的右指针域置空

• 待删除的结点*p仅有一个非空子树

  让这个结点的子树取代自己的位置

• 待删除的结点*p有两个非空子树

  法一： 找该结点的直接前趋或直接后继 直接前趋是它左子树的最右边结点，这个结点要么是叶子结点，要么只有左孩子 直接后继是它右子树的最左边，这结点要么是叶子结点，要么只有右孩子 这样就把两个非空子树的问题转化为了一个叶子结点或只有一棵非空子树的问题。

法二： 让该结点的左子树取代自己的位置，该结点的右子树接到直接前驱的右孩子上。

法三： 让该结点的右子树取代自己的位置，该结点的左子树接到直接后继的左孩子上。

平衡二叉树

要么是一颗空树，要么是一颗具有下列性质的二叉树：

• 左子树和右子树都是平衡二叉树
• 左右子树的深度之差绝对值不超过1

平衡因子bf：

• 结点左子树的高度减去右子树的高度
• 平衡二叉树中结点的平衡因子为0、1或-1

RR型左旋平衡处理 在a的右子树的根结点b的右子树上插入结点，导致a的平衡因子变为-2。把b的左子树接给a的右孩子，a接到b的左孩子上，b取代a的位置。 LL型右旋平衡处理 在a的左子树的根结点b的左子树上插入结点，导致a的平衡因子变为2，把b的右子树接给a的左孩子，a接到b的右孩子上，b取代a的位置 LR型先左后右旋转平衡处理 在a的左子树的根结点b的右子树上插入结点，导致a的平衡因子变为2。先对b做左旋平衡处理，再对a做右旋平衡处理。 RL型先右后左旋转平衡处理 在a的右子树的根结点b的左子树上插入根结点，导致a的平衡因子变为-2.先对b做右旋平衡处理，再对a做左旋平衡处理。

为什么要先左旋再右旋或者先右旋再左旋呢？ 管他那么多！记住就行了！

B-树和B+树

Note：B-树就是B树

B-树（m阶）：每个结点最多有m个孩子

• 树中每个结点至多有m棵子树
• 若根结点不是叶子结点，则至少有两颗子树
• 除根之外的所有非终端结点至少有$\lceil\frac{m}{2}\rceil$棵子树
• 结构类似平衡二叉树
• 叶子结点出现在同一层次

口语描述：

哈希表

散列函数的构造方法

• 直接定址法
• 数字分析法
• 平方取中法
• 折叠法
• 随机数法
• 除留取余法

解决冲突的方法

• 开放定址法

  从发生冲突的那个单元开始，按照一定次序，从哈希表中找出一个空闲的存储单元，把发生冲突的待插入关键字存储到该单元中。 \(H_i = (H(key)+d_i) \% m\)

  1. 线性探测再散列 $d_i = 1, 2, 3…$
  2. 二次探测再散列$d_i = 1, -1, 2^2, -2^2…$
  3. 伪随机探测再散列，$d_i$是伪随机数

• 链地址法（拉链法）

  通过哈希函数得到的值如果发生冲突，用一根链表链在一起。

• 再哈希法

  再用几次哈希函数，直到找到空地址

• 公共溢出区法

性能分析

装填因子 散列表中存入的元素个数n与哈希表的大小m的比值 \(装填因子\alpha = \frac{n}{m}\)

在题目没有告诉是求成功还是失败的ASL时用公式来算：

线性探查法的的查找性能分析 \(ASL \approx \frac{1}{2}(1+\frac{1}{1-\alpha})\)

链地址法的查找性能分析 \(ASL \approx 1 + \frac{\alpha}{2}\)

二叉排序树的查找性能分析

最坏情况下，其平均查找长度不会超过树的高度