Pal*_*din 86 tree b-tree avl-tree red-black-tree data-structures
作为程序员,我应该何时考虑使用RB树,B树或AVL树？在决定选择之前需要考虑哪些关键点？
有人可以解释一下每个树形结构的场景,为什么选择其他树木结构参考关键点？
blw*_*y10 110
拿一小撮盐:
当您管理超过数千个项目并且从磁盘或某些慢速存储介质中分页时,B树.
当您在树上进行相当频繁的插入,删除和检索时,RB树.
当您的插入和删除相对于您的检索很少时,AVL树.
Ste*_*314 19
我认为B +树是一个很好的通用有序容器数据结构,即使在主内存中也是如此.即使虚拟内存不是问题,缓存友好性通常也是如此,并且B +树特别适合顺序访问 - 与链表相同的渐近性能,但缓存友好性接近于简单数组.所有这些和O(log n)搜索,插入和删除.
但是B +树确实存在问题 - 例如当你进行插入/删除时项目在节点内移动,使指向这些项目的指针无效.我有一个容器库,它执行"游标维护" - 游标将自己附加到它们当前在链表中引用的叶节点,因此它们可以自动修复或失效.由于很少有一个或两个游标,它运行良好 - 但它是一个额外的工作所有相同.
另一件事是B +树基本上就是这样.我想你可以根据你是否需要它们来剥离或重新创建非叶子节点,但是使用二叉树节点你会获得更多的灵活性.二进制树可以转换为链接列表并返回而无需复制节点 - 您只需更改指针,然后记住您现在将其视为不同的数据结构.除此之外,这意味着你可以很容易地合并树(将树转换为列表,合并它们,然后转换回树).
另一件事是内存分配和释放.在二叉树中,这可以从算法中分离出来 - 用户可以创建一个节点然后调用插入算法,删除可以提取节点(从树中分离它们,但不要释放内存).在B树或B +树中,显然不起作用 - 数据将存在于多项目节点中.编写插入方法来"规划"操作而不修改节点,直到他们知道需要多少个新节点并且可以分配它们是一个挑战.
红黑与AVL？我不确定它会有什么大不同.我自己的库有一个基于策略的"工具"类来操作节点,使用双链表,简单二叉树,splay树,红黑树和treaps的方法,包括各种转换.其中一些方法只是因为我曾经无聊而被实施.我不确定我是否测试过treap方法.我选择红黑树而不是AVL的原因是因为我个人更好地理解算法 - 这并不意味着它们更简单,只是我对它们更熟悉的历史侥幸.
最后一件事 - 我最初只开发了我的B +树容器作为实验.这是那些从未真正结束的实验之一,但这并不是我鼓励别人重复的事情.如果您只需要一个有序容器,那么最好的答案就是使用现有库提供的容器 - 例如,在C++中使用std :: map等.我的库经过多年的发展,需要很长时间才能保持稳定,而我最近才发现它在技术上是不可移植的(取决于一些未定义的行为WRT offsetof).
| 归档时间： |
|
| 查看次数： |
27637 次 |
| 最近记录： |