修改红黑树以具有列表行为并使用索引
Modify Red-black tree to have list behavior and work with indices
我有一个任务，我的任务是“修改红黑树以通过列表界面中的索引和其他行为进行访问，并且你不能只使用索引作为键 - 即，将你的调用包装在一个map 实现，因为这样做需要在每次将项目添加到列表或从列表中删除时重新编号索引（这将花费 O(n log n)）。相反，您将在每个节点中使用子树大小并基于在给定索引时插入那些。实际上，列表中的项目将仅按其列表索引排序。“
这意味着以下方法
- 布尔加法(E e)
- void add(int index, E element)
- E 删除（整数索引）
- E get(整数索引)
- 整数大小()
- 无效清除()
将使用以下规范进行编码。
我不是要别人写答案，而是问我该怎么做？我问了我的教授和助教，但他们没有提供更多关于如何回答或处理这个问题的信息或提示，所以我想问问你们如何做这件事的任何方向，谢谢。
您可以轻松地进行 O(log n) 访问（如果您需要像数组一样需要 O(1) 访问，我不太确定）。
假设您想在以节点 v 为根的树中获取索引 i，并且您知道所有（子）树的大小。如果 v 的左树大小为 v.left.size == i - 1，那么左边有 i-1 个值，因此 v 中的值必须是数字 i。 Return那个。
如果left.size >= i第i个值在左子树中，那么search(v.left, i)得到它。
如果 left.size < i - 1 则 v 的索引小于 i，并且第 i 个索引必须在 v.right 中。你应该在那里搜索。但是，您不应该在那里搜索索引 i；当你向右走时，你需要考虑已经跳过了 v.left.size + 1 个值。所以你应该 search(v.right, i - (v.left.size + 1)).
我有一个任务，我的任务是“修改红黑树以通过列表界面中的索引和其他行为进行访问，并且你不能只使用索引作为键 - 即，将你的调用包装在一个map 实现，因为这样做需要在每次将项目添加到列表或从列表中删除时重新编号索引（这将花费 O(n log n)）。相反，您将在每个节点中使用子树大小并基于在给定索引时插入那些。实际上，列表中的项目将仅按其列表索引排序。“
这意味着以下方法
- 布尔加法(E e)
- void add(int index, E element)
- E 删除（整数索引）
- E get(整数索引)
- 整数大小()
- 无效清除()
将使用以下规范进行编码。
我不是要别人写答案，而是问我该怎么做？我问了我的教授和助教，但他们没有提供更多关于如何回答或处理这个问题的信息或提示，所以我想问问你们如何做这件事的任何方向，谢谢。
您可以轻松地进行 O(log n) 访问（如果您需要像数组一样需要 O(1) 访问，我不太确定）。
假设您想在以节点 v 为根的树中获取索引 i，并且您知道所有（子）树的大小。如果 v 的左树大小为 v.left.size == i - 1，那么左边有 i-1 个值，因此 v 中的值必须是数字 i。 Return那个。
如果left.size >= i第i个值在左子树中，那么search(v.left, i)得到它。
如果 left.size < i - 1 则 v 的索引小于 i，并且第 i 个索引必须在 v.right 中。你应该在那里搜索。但是，您不应该在那里搜索索引 i；当你向右走时，你需要考虑已经跳过了 v.left.size + 1 个值。所以你应该 search(v.right, i - (v.left.size + 1)).