2

出于我的一种算法的目的，我想创建一个支持以下O(lg n)时间复杂度操作的数据结构：

  • 添加一个新项目；
  • 寻找新项目；
  • 删除所有键小于给定值的项目。

我猜一棵树将是支持这些操作的最合适的数据结构。但是，我实际上不知道如何在对数时间内实现最后一个。我该如何设计它？

4

1 回答 1

1

您可以使用平衡二叉搜索树（AVL，红黑，您选择）。低于给定元素的元素将在沿着连接它到根的路径的左子元素中找到。剩下的很简单...

于 2013-09-07T10:19:44.223 回答