具有 2 个键的二叉搜索树
Binary Search Tree with 2 keys
我有一个包含用户名和 ID 的用户数据库。这些是程序将处理的操作：
insert、delete（by username）、search（by username）、print（打印所有用户信息，按 id)
排序
前 3 个操作的时间复杂度不应超过 O(log n)，对于打印，它应该是 O(n)。解决方案应该使用平衡的 BST 来实现。
我的解决方案是必须有 2 个 BST，一个是 id，另一个是 username。因此我们可以在 O(log n) 时间内通过名称或 ID 访问元素。但这会使内存 space 和操作时间加倍。
有没有比我解释的更好的方式在 O(log n) 时间内通过 username 和 id 访问元素的方法？
My idea to solve the problem is to have to 2 BST, key of one is id and
for another is username. So we can access an element by their username or
id both in O(log n) time. But this doubles memory space and time of
operations.
您提出的建议确实会使您的数据结构的内存和时间要求加倍。 （只有插入和删除会花费两倍的时间。其他操作不会花费额外的时间）。但是，回想一下 O(2 log n) 通常与 O(log n) 相同，并且比 O(n) 少得多。作为说明，我绘制了 2 log n 和 n。请注意，当 n 为 2 或 4 时它们相等。与 n 相比，log n 本质上是一条扁平线。
我建议您使用平衡的 BST（或者就此而言）不能做得比这更好。由于需要在 O(log n) 时间内根据 username 进行搜索，因此 username 必须是树的键。但是，您还需要在 O(n) 时间内检索按 id 排序的用户。这基本上禁止您在检索它们后对它们进行排序，因为您无法比 O(n log n) 更快地对它们进行排序。因此，它们必须已经按 id 排序。因此，id 必须是树的键。因此，你需要两棵树。
虽然 2 棵树很好，但您也可以使用散列 table 进行查找和删除，并使用排序索引进行打印。红黑树可以作为排序索引。
但是，如果ID是连续的非负整数，维护一个简单的数组会更有效率，其中position i 包含 ID 为 i 的对象。现在你可以通过遍历数组来打印。散列 table 值可以是 ID，对于这些 "point" 到数组中的相应对象。
我有一个包含用户名和 ID 的用户数据库。这些是程序将处理的操作：
insert、delete（by username）、search（by username）、print（打印所有用户信息，按 id)
前 3 个操作的时间复杂度不应超过 O(log n)，对于打印，它应该是 O(n)。解决方案应该使用平衡的 BST 来实现。
我的解决方案是必须有 2 个 BST，一个是 id，另一个是 username。因此我们可以在 O(log n) 时间内通过名称或 ID 访问元素。但这会使内存 space 和操作时间加倍。
有没有比我解释的更好的方式在 O(log n) 时间内通过 username 和 id 访问元素的方法？
My idea to solve the problem is to have to 2 BST, key of one is
idand for another isusername. So we can access an element by theirusernameoridboth inO(log n)time. But this doubles memory space and time of operations.
您提出的建议确实会使您的数据结构的内存和时间要求加倍。 （只有插入和删除会花费两倍的时间。其他操作不会花费额外的时间）。但是，回想一下 O(2 log n) 通常与 O(log n) 相同，并且比 O(n) 少得多。作为说明，我绘制了 2 log n 和 n。请注意，当 n 为 2 或 4 时它们相等。与 n 相比，log n 本质上是一条扁平线。
我建议您使用平衡的 BST（或者就此而言）不能做得比这更好。由于需要在 O(log n) 时间内根据 username 进行搜索，因此 username 必须是树的键。但是，您还需要在 O(n) 时间内检索按 id 排序的用户。这基本上禁止您在检索它们后对它们进行排序，因为您无法比 O(n log n) 更快地对它们进行排序。因此，它们必须已经按 id 排序。因此，id 必须是树的键。因此，你需要两棵树。
虽然 2 棵树很好，但您也可以使用散列 table 进行查找和删除，并使用排序索引进行打印。红黑树可以作为排序索引。
但是，如果ID是连续的非负整数，维护一个简单的数组会更有效率，其中position i 包含 ID 为 i 的对象。现在你可以通过遍历数组来打印。散列 table 值可以是 ID，对于这些 "point" 到数组中的相应对象。