与语言无关 – 使用哈希映射优化二进制树插入O(1)以写入重树
发布时间：2020-12-15 04:51:38 所属栏目：Java 来源：网络整理
导读：首先,我假设在考虑这个问题时我已经错过了一些重要的东西,但我仍然想发布它,看看我是否真的没有错过任何东西,用它… 我有一个非常重写的二叉树(写入和读取之间约为50/50),在回家的路上,我正在考虑如何优化这一点,特别是使写入更快 – 这就是我提出的. 考虑到
|
首先,我假设在考虑这个问题时我已经错过了一些重要的东西,但我仍然想发布它,看看我是否真的没有错过任何东西,用它…
我有一个非常重写的二叉树(写入和读取之间约为50/50),在回家的路上,我正在考虑如何优化这一点,特别是使写入更快 – 这就是我提出的. 考虑到向树T添加x的操作add(T,x)首先由find(T,x)组成,以查看x是否已经存在,并且在这种情况下它不返回父,所以我们可以添加它而不是其中一个父母空叶. 如果我们将一个哈希表作为中间缓存添加到add操作,那么当我们调用add(T,x)时,真正发生的是x被散列并插入到哈希映射M中.就是这样.优化发生在我们其他地方要求查找(T,现在当我们搜索树时,我们将来到叶节点,因为x尚未插入树(它只存在于哈希映射M中),我们哈希x并将其与M中的键进行比较,以查看它是否应该在树中.如果它在M中找到,那么我们将它添加到树中并从M中删除它. 这将消除add(T,x)上的find(T,x)运算并将其减少为添加(M,x),即O(1).然后(ab) – 使用我们在第一次插入节点时执行的find(T,x)操作. 解决方法
为什么不为所有内容使用哈希表并完全省略二叉树？
这一切都取决于你首先使用二叉树的原因.如果您选择二叉树来增强共享,则会丢失哈希表缓存,因为哈希表不会被共享. 缓存不会比较容易地比较两个地图. 编辑： 如果利用树的特殊性的操作很少(你提到利用RB树的排序事实),另一方面,如果你经常查找最近添加的键,或者更换最近添加的密钥的值,使用其他结构实现的小型缓存可能有意义.您还可以考虑使用哈希表表示,偶尔转换为树. 此缓存层的额外复杂性可能意味着您在实践中没有获得任何时间,或者不足以偿还具有此类临时数据结构的技术债务. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |