二叉树搜索性能比较

二叉树搜索性能比较

我想测试一下不同类型的二叉树搜索数据的性能是什么样的。

众所周知，二叉树有以下几种类型：

• BST
• AVL
• 红黑树

对于搜索数据，具体来讲，当树保持平衡时，其搜索时间复杂度是O（log₂n）,当树退化成链表时，其搜索时间复杂度变成O(n)，其他情况下树的平均搜索时间复杂度就介于这两者之间。

事实上红黑树的插入、删除、查找、旋转等操作都被控制在O（log₂n）之中，对数级别的时间复杂度，使得红黑树尤其适用于数据无序程序高、数据量庞大且需要快速定位节点的场合。

测试环境

测试主机频率是4GHz，运行在ubuntu20.04系统上。

程序设计

设计一个程序，实现以下功能：

1. 分别创建一棵BST树、一棵AVL树、一棵红黑树

2. 使用for循环递增整数i生成数据，i取值范围是[0,9999999]

3. 给三棵二叉树插入相同的数据

4. 搜索所有插入的数据并统计用时

5. 打印出所有二叉树的搜索用时

代码示例

核心代码如下：

#define TREE_NODE_NUM 1000000	//搜索的数据量

#define BST_SEARCH 	0	//BST搜索开关
#define AVL_SEARCH 	0	//AVL搜索开关
#define RB_SEARCH 	1	//红黑树搜索开关

extern void rb_insert(linktree *proot, linktree new);
//extern linktree rb_find(linktree root, tn_datatype data);
extern linktree bst_find(linktree root, tn_datatype data);
extern linktree bst_insert(linktree root, linktree new);

int main(void)
{
	linktree avl_root = NULL;	//avl树的根节点指针
	linktree bst_root = NULL;	//bst树的根节点指针
	linktree rb_root = NULL;	//红黑树的根节点指针
	linktree tmp;	//待查找的节点指针
	
	int find_counts;	//找到的节点数
	int node_to_find;	//待查找的数据
	
	int num[TREE_NODE_NUM];
	
 	volatile int i = 0;
	int n;	//保存待插入的数据
	
    //生成数据
	for (i=0; i<TREE_NODE_NUM; i++)
	{
		num[i] = i;
	}
	
	i = 0;	
	while(i < TREE_NODE_NUM)
	{
		n = num[i];
		
#if AVL_SEARCH
		//插入avl树节点
		linktree avl_new = new_node(n);
		avl_root = avl_insert(avl_root, avl_new);
#elif BST_SEARCH	
		//插入bst树节点
		linktree bst_new = new_node(n);
		bst_root = bst_insert(bst_root, bst_new);
#elif RB_SEARCH
		//插入红黑树节点
		linktree rb_new = new_node(n);
		if(NULL == rb_new)
		{
			printf("rb new fail\n");
		}
		rb_insert(&rb_root, rb_new);
#endif		
		i++;
	}

	struct timeval tv_start;
	struct timeval tv_end;
	float cost_time;	//毫秒
	
#if BST_SEARCH
	//从bst树查找指定数据，并统计用时
	gettimeofday(&tv_start, NULL);	
	i = 0;
	find_counts = 0;
	while(i<(TREE_NODE_NUM/2))
	{
		node_to_find = num[i];	//随机获取一个要查找的数据
		tmp = bst_find(bst_root, node_to_find);	//搜索该数据
		if(tmp != NULL)
		{
			find_counts++;
		}
		i++;
	}
	gettimeofday(&tv_end, NULL);	
	
	if(tv_start.tv_sec == tv_end.tv_sec)
	{
		cost_time =  (tv_end.tv_usec-tv_start.tv_usec)/1000.0;
		printf("bst树搜索到%d个节点，用时为%.2f ms\n", find_counts, cost_time);
	}
	else
	{
		cost_time =  (tv_end.tv_sec*1000+tv_end.tv_usec/1000.0) - (tv_start.tv_sec*1000+tv_start.tv_usec/1000.0);
		printf("bst树搜索到%d个节点，用时为%.2f ms\n", find_counts, cost_time);
	}
	
#endif

#if AVL_SEARCH
	find_counts = 0;
	//从avl树查找指定数据，并统计用时
	gettimeofday(&tv_start, NULL);	
	i=0;
	while(i<(TREE_NODE_NUM/2))
	{
		node_to_find = num[i];	//随机获取一个要查找的数据
		tmp = bst_find(avl_root, node_to_find);	//搜索该数据
		if(tmp != NULL)
		{
			find_counts++;
		}
		i++;
	}
	gettimeofday(&tv_end, NULL);	
	
	if(tv_start.tv_sec == tv_end.tv_sec)
	{
		cost_time =  (tv_end.tv_usec-tv_start.tv_usec)/1000.0;
		printf("avl树搜索到%d个节点，用时为%.2f ms\n", find_counts, cost_time);
	}
	else
	{
		cost_time =  (tv_end.tv_sec*1000+tv_end.tv_usec/1000.0) - (tv_start.tv_sec*1000+tv_start.tv_usec/1000.0);
		printf("avl树搜索到%d个节点，用时为%.2f ms\n", find_counts, cost_time);
	}
#endif

#if RB_SEARCH 
	//从rb树查找指定数据，并统计用时
	gettimeofday(&tv_start, NULL);	
	find_counts = 0;
	i = 0;
	while(i<(TREE_NODE_NUM/2))
	{
		node_to_find = num[i];	//随机获取一个要查找的数据
		tmp = bst_find(rb_root, node_to_find);	//搜索该数据
		if(tmp != NULL)
		{
			find_counts++;
		}
		
		i++;
	}
	gettimeofday(&tv_end, NULL);	
	
	if(tv_start.tv_sec == tv_end.tv_sec)
	{
		cost_time =  (tv_end.tv_usec-tv_start.tv_usec)/1000.0;
		printf("rb树搜索到%d 个节点，用时为%.2f ms\n", find_counts, cost_time);
	}
	else
	{
		cost_time =  (tv_end.tv_sec*1000+tv_end.tv_usec/1000.0) - (tv_start.tv_sec*1000+tv_start.tv_usec/1000.0);
		printf("rb树搜索到%d 个节点，用时为%.2f ms\n", find_counts, cost_time);
	}
#endif
    
	//draw(bst_root);
	//system("firefox  *.html &");
	//draw(avl_root);
	//system("firefox -new-tab *.html &");
	//draw(rb_root);
	//system("firefox -new-tab *.html &");

	//system("rm *.html");
	
	
	return 0;
}

运行结果

BST、AVL、红黑树的搜索用时统计结果如下表格：

二叉树类型 搜索数据量（单位：十万） 搜索总用时（单位：毫秒） 搜索一个节点平均用时（单位：毫秒） BST 5 297772.88 0.15 AVL 5 30.48 0.00006 RD 5 38.96 0.00008

由上表可以看出，搜索性能是AVL树最优，然后是红黑树，最后是BST树；而且平衡的二叉树比不平衡的二叉树的搜索时间短很多，可见树的平衡对搜索性能影响很大。

另外：
1、本实验BST树和红黑树的插入算法都是非递归实现。详见附录
2、所有树的查找算法都是非递归实现。详见附录

附录

1、二叉搜索树插入算法非递归实现如下：

//使用非递归实现bst树插入节点
linktree bst_insert(linktree root, linktree new)
{
	linktree tmp = NULL;

	if(new == NULL)
		return root;

	if(root == NULL)
		return new;

	tmp = root;
	while(1)
	{
		if(new->data > root->data)
		{
			if(root->rchild == NULL)
			{
				root->rchild = new;
				break;
			}
			else
			{
				root = root->rchild; 
			}
		}	
		else if(new->data < root->data)
		{
			if(root->lchild == NULL)
			{
				root->lchild = new;
				break;
			}
			else
			{
				root = root->lchild; 
			}
		}
		else
		{
			//printf("%d is already exist.\n", new->data);
			break;
		}
	}

	return tmp;
}

2、二叉搜索树查找算法非递归实现如下：

//非递归算法实现bst树查找节点
linktree bst_find(linktree root, tn_datatype data)
{
	if(root == NULL)
		return NULL;

	while(1)
	{
		if(root == NULL)
			break;

		if(data < root->data)
			root = root->lchild;
		else if(data > root->data)
			root = root->rchild;
		else
			break;
	}
		
	return root;
}

总结

本文通过实验测试对比了BST树、AVL树以及红黑树的搜索性能，得到了一些规律。发现二叉树的平衡性对搜索数据的性能影响较大。