I have an assignment where I am "Tasked to modify a Red-black tree to have access by indices and other behaviors from the lists interface and that you cannot just use indices as keys – i.e., wrapping your calls around a map implementation, as doing so would require the indices to be renumbered every time an item is added to or removed from a list (this would take O(n log n)). Instead, you will use subtree sizes in every node and base the insertions on those when given indices. In fact, the items in your list will be ordered only by their list indices."
This would mean the following methods
Would be coded using the following specifications.
I am not asking for someone to write an answer to this, rather I am asking how would I do it? I asked my professor and TAs but they are not providing any more information or hints onto how to answer or work with this so I wanted to ask for any sense of direction on how you guys would go about doing this, thank you.
You can easily do O(log n) access (if you need O(1) access as with arrays, I am not so sure).
Let's say you want to get index i in a tree rooted in node v, and that you know the sizes of all (sub-)trees. If v's left tree has size v.left.size == i - 1, then you have i-1 values to the left, so the value in v must be number i. Return that.
If left.size >= i the i'th value is in the left subtree, so search(v.left, i) to get it.
If left.size < i - 1 then v has an index less than i, and the i'th index must be in v.right. You should search there. But, you shouldn't search for index i there; you need to account for having already skipped v.left.size + 1 values when you go right. So you should search(v.right, i - (v.left.size + 1)).