由静态查找表观察，可得一下结论

• 从查找性能看，最好情况能达O(logn)，此时要求表有序
• 从插入和删除的性能来看，最好情况能达O(1)，此时要求存储结构为链表

本篇文章是对各种查找树的一个简单概括，具体分析会慢慢更新

二叉查找树

关于二叉查找树的具体介绍

http://www.saberismywife.com/2016/11/10/二叉查找树/

1.定义

二叉查找树或者是一颗空树；或者是具有如下特性的二叉树

• 若他的左子树不空，则左子树上所有结点的值均小于根结点的值
• 若他的右子树不空，则右子树上所有结点的值均大于根节点的值
• 他的左右子树也分别为二叉查找树

通常，取二叉链表作为二叉查找树的存储结构

1
2
3
4
5

typedef struct BiTNode {
	//结点结构
	tElemType data;
	struct BiTNode *lChild, *rchild;
}BiTNode, *BiTree;

2.二叉查找树的查找算法

若二叉排序树为空，则查找不成功；否则

• 若待查找值与根结点的关键字相等，则查找成功
• 若待查找值小于根结点的关键字，则继续在左子树上进行查找
• 若待查找值大于根结点的关键字，则继续在右子树上进行查找

在查找过程中，生成了一条查找路径：从根结点出发，沿着左分支或者右分支逐层向下纸质关键字等于给定结点的值的结点。（查找成功）

或者，从根结点出发，沿着左分支或者右分支逐层向下直至指针指向空树为止。（查找失败）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Status searchBST(BiTree T, keyType kval, BiTree f, BITree &p) {
	/*
	在根指针T所指二叉搜索树中递归的查找其关键字等于kval的数据元素
	若查找成功，则返回指针p所指向的该数据元素的结点，并返回函数值TURE
	若查找不成功，返回指针p指向查找路径上访问的最后一个结点，并返回函数值为FALSE
	在不成功的同时指针f指向当前访问的结点的双亲，其初始调用值为NULL
	BiTree f 的作用为，当查找失败时将数据元素插入到当前二叉搜索树中
	*/
	if (!T) {
		//查找失败
		return FLASE;
	}
	else if (kval == T->data.key) {
		//查找成功
		p = T;
		return TURE;
	} 
	else if (kval < T->data.key)
		//在左子树中继续查找
		return searchBTS(T -> lChild, kval, T, p);
	else
		//在右子树中继续查找
		return searchBTS(T -> rChild, kval, T, p);
}		

3.二叉查找树的插入算法

• 根据动态查找表的定义，插入操作在查找不成功时才进行
• 若二叉查找树为空树时，则插入新的结点为新的根结点；否则，新插入的结点毕为一个新的叶子结点，其插入位置由查找过程得到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Status insertBTS(BiTree T, elemType e) {
	/*
	当二叉查找树中不存在关键字等于e.key的数据元素时
	插入元素值为e的结点，并返回TRUE
	否则，不进行插入并返回FALSE
	*/
	if (!searchBTS(T, e.key, NULL, p)) {
		//为新结点分配空间
		s = new BiTNode;
		s -> data = e;
		s -> lChild = s -> rChild = NULL;
		if (!p)
			//插入s为新的根结点
			T = s;
		else if (e.key < p -> data.key) 
			//插入*s为*p的左孩子
			p -> lChild = s;
		else
			//插入*s为*p的右孩子
			p -> rChild = s;
	} else
		return FLASE;
	return TURE;
}

4.二叉查找树的删除算法

和插入相反，删除在查找成功后进行，并且要求在删除二叉查找树上某个结点后，仍然保持二叉查找树的特性

具体情况看我的另外一篇文章，那里写的很清楚了，这里不再进行重复的描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Status deleteBTS(BiTree T, ketType kval) {
	//若二叉查找树T中存在其关键字等于kval的数据元素，则删除该元素结点，并返回TRUE，否则FLASE
	if (!t)
		return FALSE;
	else {
		if (kval == T->data.key) {
			//找到关键字等于key的数据元素
			delete(T);
			return TRUE;
		}
		else if (kval < T->data.key) 
			//继续在左子树中进行查找
			return deleteBTS(T -> lChild, kval);
		else
			//继续在右子树中进行查找
			return deleteBTS(T -> rChild, kval);
	}
}

//删除操作
void delete(BiTree &p) {
	//从二叉查找树中删除结点p，并重接它的左子树或者右子树
	if (!p -> rChild) {
		
	} else if (!p -> lChild) {
	
	} else
	
}

平衡二叉树

平衡二叉树是二叉搜索树的另一种形式，其特点为：

树中每个结点的左右子树深度之差的绝对值不大于1

构造平衡二叉树的方法是：在插入过程中，采用平衡旋转技术(LL,RR,LR,RL)

平衡二叉树的代表就是红黑树了

关于红黑树我会在之后几天内整理出来

B-树

• B-树的定义

B-树是一种平衡的多路查找树

在m阶的B-树上，每个非终端结点可能含有：

1.n个关键字Ki(1 <= i <= n, n < m)

2.n个指向记录的指针Di(1 <= i <= n)

3.n+1个指向子树的指针Ai(0 <= i <= n)

• 搜索树的特性

非叶子结点中的多个关键字均自小到大有序排列，即K1<K2<K3<…<Kn

且A(i-1)所指子树上所有关键字均小于Ki；Ai所指子树上所有关键字均大于Ki

• 平衡树的特性

树中所有叶子结点均不带信息，且在树中的同一层次上

根结点或为叶子结点，或至少含有两棵子树

其余所有非叶子结点，均至少含有m/2(并向上取整)棵子树，至多含有m棵子树

• B-树的查找过程

1.从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找，两个过程交叉进行

2.若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置

3.若查找不成功，则返回插入位置

• 性能分析

这里会在几天后的关于B树的文章中进行具体分析

B+树

B+树是B-树的一个变形

• B+树的结构特点

每个叶子结点中含有n个关键字和n个指向记录的指针

并且，所有叶子结点相互连接构成一个有序链表，其头指针指向含最小关键字的结点

每个非叶子结点中的关键字Ki即为其相应指针Ai所指子树中关键字的最大值

所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于m/2(向上取整)和m之间

严格的来讲，B+树已经不是一种树结构了，因为它把叶子结点都链接上了

• B+树的查找过程

在B+树上，既可以进行缩小范围的查找，也可以进行顺序查找

在进行缩小范围查找时，不管成功与否，都必须查到叶子结点才能结束

若在结点内查找时，待查找值<=Ki，则应继续在Ai所指子树中进行查找

eg:
下面关于B-树与B+树的叙述中，错误的是（ ）
A. B-树与B+树都是平衡的多分树
B. B-树与B+树都可以用于文件的索引结构
C. B-树与B+树都能有效的支持随机检索
D. B-树与B+树都能有效的支持顺序检索

分析：因为B+树所有的叶子结点中包含了全部关键字信息，以及指向含有这些关键字记录的指针，且叶子结点本身依关键字结点的大小自小而大顺序链接，所以支持从根结点的随机检索和直接从叶子结点开始的顺序检索，但是B-树不具有这种结构特性，所以只支持从根结点的随机检索，而不支持从叶子结点开始的顺序检索。
所以选择D