C语言-二叉搜索树的常用操作和复杂度分析_二叉树的插入和查找复杂度

一、二叉搜索树的定义

      一个二叉树，对于每一个节点X均满足X的左子树所有节点的值比X小，右子树所有节点的值比X大，且左、右子树均为二叉搜索树，那么这种树称为二叉搜索树

二叉搜索树的存储结构和操作

typedef struct treenode {
	int data;
	struct treenode* left;
	struct treenode* right;
}treenode;
 
treenode* empty(treenode* root);//初始化
treenode* find(treenode* root, int x);//查找
treenode* findmax(treenode* root);//查找最大值
treenode* findmin(treenode* root);//查找最小值
void insert(treenode** root, int x);//插入节点
void delete(treenode** root, int x);//删除节点

二、二叉搜索树的相关操作

1.初始化操作：利用递归清空树

代码：

//利用递归完成树的初始化（清空树）
treenode* empty(treenode* root) {
	if (root != NULL) {
		empty(root->left);
		empty(root->right);
		free(root);
	}
	return NULL;
}

2.查找值

思路：先考察root节点，若值相等则返回；如果x>root->data，向右侧寻找，反之向左侧找

代码：

//查找树中元素。如果有，返回指向该节点的指针，如果没有返回NULL
treenode* find(treenode* root, int x) {
	if (root == NULL) return NULL;
	if (x > root->data) {
		return find(root->right, x);
	}
	else if (x < root->data) {
		return find(root->left, x);
	}
	else return root;
}

3.查找最大、最小值

思路和上一个比较像。这里查找最大值用递归实现，查找最小值用非递归方式

代码：

//查找树中最大/最小元素，返回指向该节点的指针
//利用递归找到最大
treenode* findmax(treenode* root) {
	if (root != NULL){
		if (root->right != NULL) {
			return findmax(root->right);
		}
		else {
			return root;
		}
	}
	return NULL;
}
 
//利用非递归找到最小
treenode* findmin(treenode* root) {
	if(root!=NULL){
		while (root->left != NULL) {
			root = root->left;
		}
		return root;
	}
	return NULL;
}

4.插入节点

插入节点时，可以像find那样沿着树上寻找合适的位置。如果找到和x值一样的节点，则什么都不用作（或者做一些“更新”）。否则，将这个值插到遍历的路径的最后一点上。下图是一个简单演示，假如我们要插入一个新的节点，它的值为5：

具体代码：

//插入节点操作
void insert(treenode** root, int x) {
	if ((*root) == NULL) {
		(*root) = (treenode*)malloc(sizeof(treenode));
		(*root)->data = x;
		(*root)->left = NULL;
		(*root)->right = NULL;
	}
	else {
		if (x > (*root)->data) insert(&(*root)->right, x);
		else if (x < (*root)->data) insert(&(*root)->left, x);
		//如果x==root->data说明树中已经有该节点，不再插入
	}
}

 （注意此次函数值传递，应当是root的地址，即类型为treenode**）

5.删除节点

和以上操作相比，删除节点显得较为复杂。

节点情况可以分为以下几类：

（1）没有子节点： 它可以被立即清除

（2）有一个子节点：可以在其父节点调整指针绕过该节点后删除。具体而言，可以把当前节点的非空子节点赋成该节点，在释放这个节点。可以由以下几行实现：  

temp = *root;
if((*root)->left) (*root) = (*root)->left;
else  (*root)=(*root)->right;
free(temp);

有一个子节点的示意图，删除左图节点4

（3）有两个子节点：一般的删除策略是用其右子树的最小的数据代替该节点的值，并继续递归调用delete函数将那个右子树最小数据节点删除。注意这里替代品为右子树的最小数据，如果使用的是全树最小数据可能会使节点的左右子节点的值都大于该节点的值。示意图如下：

有两个子节点的示意图，删除左图节点2

整个删除节点操作的代码：

void delete(treenode** root, int x) {
	treenode* temp = (treenode*)malloc(sizeof(treenode));
	if ((*root) != NULL) {
		if ((*root)->data > x) {
			delete(&(*root)->left, x);
		}
		else if ((*root)->data < x) {
			delete(&(*root)->right, x);
		}
		else {
			if ((*root)->left && (*root)->right) {//左右子节点都存在
				temp = findmin((*root)->right);
				(*root)->data = temp->data;
				delete(&(*root)->right, temp->data);
			}
			else {//只有一个或没有子节点
				temp = *root;
				if ((*root)->left) {
					(*root) = (*root)->left;
				}
				else {
					(*root) = (*root)->right;
				}
				free(temp);
			}
		}
	}
}

（第二部分的完整代码及测试使用的main函数放在文末）

三、二叉搜索树的理论分析

1.时间复杂度

(1).最好情况分析：假设有N个节点排成完全二叉树，则树的高度为是[log2(N)]+1，时间复杂度为O(logN)级别；

(2).最坏情况分析：N个节点是按序输入的，导致排成一串。此时时间复杂度为O(N)级别。

(3).平均情况分析：

不难发现，这些操作的时间复杂度都是O(d)的，其中d为被访问节点的深度。在具体计算之前，我们先做出一个假设，即所有的树出现的机会相等。在这个前提下，二叉搜索树的时间复杂度就是树所有节点的平均深度。

定义：内部路径长：一棵树所有节点的深度和。

我们知道了一棵有N个节点的树的内部路径长，除以N即为这棵树所有节点的平均深度。

令D(N)是具有N个节点的某棵树T的内部路径长，D(1)=0。这个树是由含有i个节点的左子树和含有N-i-1个节点的右子树组成的。它们的内部路径长分别为D(i)和D(N-i-1)。对于全树，这些由于根节点和左右节点也有连接，所以左右子树所有节点的深度都要加1。由此得到递归关系：

如果所有子树的大小都等可能的出现，那么D(i)和D(N-i-1)的平均值都是，得到公式

进行一些简单的变形：

上下相减，得到：

 同时除以（N+1)(N+2)并裂项求和：

可以看到，当N足够大时，等式右侧是调和级数，我们有公式：

其中γ是欧拉常数，值约为0.5772156649

由于我们只关心D(N)的数量级，所有可以得到D(N)=O(NlnN),因此我们得到二叉搜索树相关操作的时间复杂度为O(logN)级别。

值得注意的是，以上分析仅为在一定假设下完成的分析。对于频繁使用删除操作的二叉搜索树，上述假设并不成立，因为我们对有两个子节点的节点删除策略是使用右子树的最小节点代替，可能导致假设中的等可能性出现问题。解决这一问题的方法是把这棵树加上平衡条件。不过，在多数情况下我们还是可以认为二叉搜索树相关操作的时间复杂度为O(logN)级别的。

2.空间复杂度：O(N)

（附：第二部分的完整代码，在vs2022中经过测试运行）

#include<stdio.h>
#include<stdlib.h>
 
typedef struct treenode {
	int data;
	struct treenode* left;
	struct treenode* right;
}treenode;
 
treenode* empty(treenode* root);
treenode* find(treenode* root, int x);
treenode* findmax(treenode* root);
treenode* findmin(treenode* root);
void insert(treenode** root, int x);
void delete(treenode** root, int x);
 
int main() {
	treenode* root=NULL,*temp=(treenode*)malloc(sizeof(treenode));
	insert(&root, 1);
	insert(&root, 5);
	insert(&root, 3);
	insert(&root, 4);
	insert(&root, 2);
	insert(&root, 2);
	insert(&root, 11);
	temp = find(root, 4);
	if(temp) printf("%d ", temp->data);
	temp = find(root, 12);
	if(!temp) printf("not found!");
	temp = findmax(root);
	printf("%d ", temp->data);
	temp = findmin(root);
	printf("%d ", temp->data);
	delete(&root, 5);
	delete(&root, 3);
	delete(&root, 1);
	delete(&root, 11);
	temp = findmax(root);
	printf("%d ", temp->data);
	temp = findmin(root);
	printf("%d ", temp->data);
	return 0;
}
 
//利用递归完成树的初始化（清空树）
treenode* empty(treenode* root) {
	if (root != NULL) {
		empty(root->left);
		empty(root->right);
		free(root);
	}
	return NULL;
}
 
//查找树中元素。如果有，返回指向该节点的指针，如果没有返回NULL
treenode* find(treenode* root, int x) {
	if (root == NULL) return NULL;
	if (x > root->data) {
		return find(root->right, x);
	}
	else if (x < root->data) {
		return find(root->left, x);
	}
	else return root;
}
 
//查找树中最大/最小元素，返回指向该节点的指针
//利用递归找到最大
treenode* findmax(treenode* root) {
	if (root != NULL){
		if (root->right != NULL) {
			return findmax(root->right);
		}
		else {
			return root;
		}
	}
	return NULL;
}
 
//利用非递归找到最小
treenode* findmin(treenode* root) {
	if(root!=NULL){
		while (root->left != NULL) {
			root = root->left;
		}
		return root;
	}
	return NULL;
}
 
//插入节点操作
void insert(treenode** root, int x) {
	if ((*root) == NULL) {
		(*root) = (treenode*)malloc(sizeof(treenode));
		(*root)->data = x;
		(*root)->left = NULL;
		(*root)->right = NULL;
	}
	else {
		if (x > (*root)->data) insert(&(*root)->right, x);
		else if (x < (*root)->data) insert(&(*root)->left, x);
		//如果x==root->data说明树中已经有该节点，不再插入
	}
}
 
//删除节点操作
void delete(treenode** root, int x) {
	treenode* temp = (treenode*)malloc(sizeof(treenode));
	if ((*root) != NULL) {
		if ((*root)->data > x) {
			delete(&(*root)->left, x);
		}
		else if ((*root)->data < x) {
			delete(&(*root)->right, x);
		}
		else {
			if ((*root)->left && (*root)->right) {//左右子节点都存在
				temp = findmin((*root)->right);
				(*root)->data = temp->data;
				delete(&(*root)->right, temp->data);
			}
			else {//只有一个或没有子节点
				temp = *root;
				if ((*root)->left) {
					(*root) = (*root)->left;
				}
				else {
					(*root) = (*root)->right;
				}
				free(temp);
			}
		}
	}
}

参考资料：《数据结构与算法分析：C语言描述》