时间戳

首页 > 解决方案 > 用于快速索引查找的列表数据结构

data-structures - 用于快速索引查找的列表数据结构

问题描述

我需要将大量元素存储在类似列表的数据结构中。额外的要求是在任何时候都应该快速确定每个元素的索引。元素未排序，无法排序。

如果使用简单数组，则每次查询元素的索引时都必须使用线性搜索。这可行，但它是一个非常低效的解决方案。这是伪代码中的数据结构：

class IndexList1 {
  Array elements

  getIndex(e) {
    for (i = 0; i < elements.length; i++) {
      if (elements[i] == e) {
        return i
      }
    }
    return -1;
  }

  insertAt(e, i) {
    elements.insertAt(e, i)
  }

  removeFrom(i) {
    elements.removeFrom(i)
  }

}

更好的方法是将元素映射到内部映射中的索引或作为元素中的字段。这种方式不需要搜索来确定元素的索引。这里的问题是，在列表中间插入或删除元素后，插入点之后的所有索引都必须更新。对于频繁的插入和删除以及大量元素，这不是很有效。

在伪代码中，改进后的数据结构如下所示：

class IndexList2 {
  Array elements
  Map elementIndexMap

  getIndex(e) {
    return elementIndexMap.get(e)
  }

  insertAt(e, i) {
    elements.insertAt(e, i)
    updateIndicesFrom(i)
  }

  removeFrom(i) {
    elementsIndexMap.delete(elements[i])
    elements.removeFrom(i)
    updateIndicesFrom(i)
  }

  updateIndicesFrom(i) {
    for (; i < elements.length; i++) {
      elementsIndexMap[elements[i]] = i
    }
  }

}

是否有用于大量元素的巧妙的类似列表的数据结构，以有效的方式跟踪每个元素的索引，即使有很多插入和删除？高效我的意思是 O(1) for getIndex()and 比 O(n) for insert()and更好remove()。

标签： data-structures

解决方案

解决这个问题的通常方法是把项目放在某种平衡树（红黑树、B+树、skip-list等）中，并带有父指针，并用大小标记树中的每个节点的子树。

然后，您可以通过走到根节点并将其左侧的任何子树的大小相加来找到任何项目的索引。

它就像一个订单统计树（https://en.wikipedia.org/wiki/Order_statistic_tree），没有对键进行排序。

推荐阅读