查找算法【二叉查找树】 - 二叉查找树的查找

查找算法【二叉查找树】 - 二叉查找树的查找

因为二叉查找树的中序遍历有序性，所以查找与二分查找类似，每次都缩小查找范围，查找效率较高。

【算法步骤】

① 若二叉查找树为空，查找失败，则返回空指针。

② 若二叉查找树非空，则将待查找关键字x 与根节点的关键字T->data进行比较。

• 若x ==T ->data，查找成功，则返回T 。
• 若x data，则递归查找左子树。
• 若x >T ->data，则递归查找右子树。

【举个栗子】

例如，一棵二叉查找树如下图所示，查找关键字32。

① 将32与二叉查找树的树根25进行比较，32>25，在右子树中查找，如下图所示。

② 将32与右子树的树根69进行比较，32<69，在左子树中查找，如下图所示。

③ 将32与左子树的树根32进行比较，相等，查找成功，返回该节点指针，如下图所示。

【算法实现】

BSTree SearchBST(BSTree T, ElemType key){ //二叉查找树的递归查找
	
	//若查找成功，则返回指向该数据元素节点的指针，否则返回空指针
	if((!T) || key == T->data){
		return T;
	}
	else if(key < T->data){
		return SearchBST(T->lchild , key); //在左子树中查找
	}else{
		return SearchBST(T->rchild , key); //在右子树中查找
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

【算法分析】

① 二叉查找树的查找时间复杂度和树的形态有关，可分为最好情况、最坏情况和平均情况进行分析。

• 在最好情况下，二叉查找树的形态和二分查找的判定树相似，如下图所示。

每次查找都可以缩小一半的搜索范围，查找路径最多从根到叶子，比较次数最多为树的高度logn ，在最好情况下查找的时间复杂度为O (logn )。

• 在最坏情况下，二叉查找树的形态为单支树，即只有左子树或只有右子树，如下图所示。

每次查找的搜索范围都缩小为n -1，退化为顺序查找，在最坏情况下查找的时间复杂度为O (n )。

• n 个节点的二叉查找树有n ！棵（有的形态相同），可以证明，二叉查找树在平均情况下查找的时间复杂度也为O (logn )。

② 空间复杂度为O (1)。