我再次尝试问同样的问题question https://stackoverflow.com/questions/3808708/delete-parts-of-a-dynamic-array-and-grow-other，但我最终提出了一个不同的问题，没有提供有关我的问题的基本信息。
我实现了一个数据结构，它是一棵树。该树的每个节点都有一个数组/向量/（随机访问结构）及其所有子节点，可以是任意多个。元素的插入/删除很容易，因为我们总是将该数组中的元素数量加倍/除以二。
这就是O(k)在此上下文中，插入/移除是指。我们有k元素并添加k更多或删除k/2。到目前为止，重建整个数据结构都很好。 Adynamic array (or a vector) works.
提出问题的操作如下。有时我们必须"split"一个节点有n子节点，这意味着我们将子节点“划分”到不同的节点中。我们潜水的方式是连续分组。我猜想，这种分割的最有效方法是，为每个新节点在其子节点所在的位置以及有多少个节点提供一个指针（假设每个节点采用k孩子们）。但是，这些子级的数量可能会发生变化，并且这不应该影响其兄弟级（或者更糟糕的是，整个树），即插入的执行时间应该是O(k)并不是O(n)。我们该怎么做呢？
一个简单但低效的解决方法是，每次分割一个节点时，我们都会替换“大”数组children有许多（与分割部分一样多）“小”动态数组。
下面的每个“盒子”都是一个随机访问结构。
怎么样一个hashmap http://en.wikipedia.org/wiki/Hash_table?
已经摊销了O(1)访问、插入和移除平均情况；O(n)最坏的情况下。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
