二叉树搜索性能比较
二叉树搜索性能比较
我想测试一下不同类型的二叉树搜索数据的性能是什么样的。
众所周知，二叉树有以下几种类型：
- BST
- AVL
- 红黑树
对于搜索数据，具体来讲，当树保持平衡时，其搜索时间复杂度是O（log2n）,当树退化成链表时，其搜索时间复杂度变成O(n)，其他情况下树的平均搜索时间复杂度就介于这两者之间。
事实上红黑树的插入、删除、查找、旋转等操作都被控制在O（log2n）之中，对数级别的时间复杂度，使得红黑树尤其适用于数据无序程序高、数据量庞大且需要快速定位节点的场合。
测试环境
测试主机频率是4GHz，运行在ubuntu20.04系统上。
程序设计
设计一个程序，实现以下功能：
-
分别创建一棵BST树、一棵AVL树、一棵红黑树
-
使用for循环递增整数i生成数据，i取值范围是[0,9999999]
-
给三棵二叉树插入相同的数据
-
搜索所有插入的数据并统计用时
-
打印出所有二叉树的搜索用时
代码示例
核心代码如下：
#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运行结果
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树以及红黑树的搜索性能，得到了一些规律。发现二叉树的平衡性对搜索数据的性能影响较大。