二叉树搜索效率如何与其它算法相比？

本文共计1503个文字，预计阅读时间需要7分钟。

二叉树搜索性能比较+我想测试一下不同类型二叉树搜索数据的能力是怎样的。众所周知，二叉树有多种类型：BST、AVL、红黑树。对于搜索数据，当树保持平衡时，它们的性能如下：BST。

二叉树搜索性能比较

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

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

• 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树以及红黑树的搜索性能，得到了一些规律。发现二叉树的平衡性对搜索数据的性能影响较大。