开发工具:
文件大小: 309kb
下载次数: 0
上传时间: 2020-03-17
详细说明：AVL和红黑树性能对比，有详细的测试数据。AVL和红黑树都是平衡树。
Binary search tree (BST) based data structures, such
as AVL trees, red-black trees, and splay trees, are often
used in system software, such as operating system
kernels. Choosing the right kind of tree can impact
performance significantly, but the literature offers few
empirical studies for guidance. We compare 20 BST
variants using three experiments in real-world scenarios
with real and artificial workloads. The results indicate
that when input is expected to be randomly ordered
with occasional runs of sorted order, red-black
trees are preferred; when insertions often occur in
sorted order, AVL trees excel for later random access,
whereas splay trees perform best for later sequential
or clustered access. For node representations, use of
parent pointers is shown to be the fastest choice, with
threaded nodes a close second choice that saves memory;
nodes without parent pointers or threads suffer
when traversal and modification are combined; maintaining
a in-order doubly linked list is advantageous
when traversal is very common; and right-threaded
nodes perform poorly.
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
