A variant of an order statistic tree would allow you to add and get by index in O(log n).
The basic idea is as follows:
- Have each node store the size of the subtree rooted at that node.
The index of a node will correspond to its position in the in-order traversal of the tree.
This means that the ordering of the nodes is determined based on where in the tree they appear - this is not the way a binary search tree typically works, where the nodes' elements have some ordering that's not dependent on where in the tree it appears (e.g. f is greater than a in a regular BST ordered lexicographically, but in our case f may be smaller or greater than a, since it's ordered based on the index of f and a).
To add or get, we start at the root and recursively go through the tree, determining whether our insert or lookup position is to the left or right based on the target index and the subtree sizes.
More specifically, we have the following recursive definitions:
(with some added complexity for null nodes and actually inserting the node)
node.add(index, element):
if index <= left.subtreeSize
left.add(index, element)
else
// anything to the right is after left subtree and current node, so those must be excluded
right.add(index - left.subtreeSize - 1, element)
node.get(index, element):
if index == left.subtreeSize
return node
if index < left.subtreeSize
return left.get(index)
else
return right.get(index - left.subtreeSize - 1)
To understand this better, the following example tree might be helpful:
Values: Indices (in-order pos): Subtree sizes:
a 5 8
/ \ / \ / \
b g 1 6 5 2
/ \ \ / \ \ / \ \
f c h 0 3 7 1 3 1
/ \ / \ / \
e d 2 4 1 1
If we want to insert a new node at position 5, for example, it will be inserted to the right of d.
Below is a small test program to demonstrate this (creating the tree shown above).
Note that balancing will still need to be done to achieve O(log n) running time per operation.
class Test
{
static class Node<T>
{
Node<T> left, right;
T data;
int subtreeCount;
Node(T data) { this.data = data; subtreeCount = 1; }
public String toString(int spaces, char leftRight)
{
return String.format("%" + spaces + "s%c: %s\n", "", leftRight, data.toString())
+ (left != null ? left.toString(spaces+3, 'L') : "")
+ (right != null ? right.toString(spaces+3, 'R') : "");
}
int subtreeSize(Node<T> node)
{
if (node == null)
return 0;
return node.subtreeCount;
}
// combined add and get into 1 function for simplicity
// if data is null, it is an get, otherwise it's an add
private T addGet(int index, T data)
{
if (data != null)
subtreeCount++;
if (index == subtreeSize(left) && data == null)
return this.data;
if (index <= subtreeSize(left))
{
if (left == null && data != null)
return (left = new Node<>(data)).data;
else
return left.addGet(index, data);
}
else if (right == null && data != null)
return (right = new Node<>(data)).data;
else
return right.addGet(index-subtreeSize(left)-1, data);
}
}
static class TreeArray<T>
{
private Node<T> root;
public int size() { return (root == null ? 0 : root.subtreeCount); }
void add(int index, T data)
{
if (index < 0 || index > size())
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
if (root == null)
root = new Node<>(data);
else
root.addGet(index, data);
}
T get(int index)
{
if (index < 0 || index >= size())
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
return root.addGet(index, null);
}
@Override
public String toString() { return root == null ? "Empty" : root.toString(1, 'X'); }
}
public static void main(String[] args)
{
TreeArray<String> tree = new TreeArray<>();
tree.add(0, "a");
tree.add(0, "b");
tree.add(1, "c");
tree.add(2, "d");
tree.add(1, "e");
tree.add(0, "f");
tree.add(6, "g");
tree.add(7, "h");
System.out.println("Tree view:");
System.out.print(tree);
System.out.println("Elements in order:");
for (int i = 0; i < tree.size(); i++)
System.out.println(i + ": " + tree.get(i));
}
}
This outputs:
Tree view:
X: a
L: b
L: f
R: c
L: e
R: d
R: g
R: h
Elements in order:
0: f
1: b
2: e
3: c
4: d
5: a
6: g
7: h
Live demo.
