Is there an efficient (log n) data structure that allows the following operations:
The number of elements is known and will not change during lifetime.
You could implement a balanced binary tree like a Red-Black Tree
A Red-Black tree has O(log(n)) time complexity for search, insertion and deletion.
You will have to make some modification to return the smallest element that is greater or equal to a given key. But the basic behavior is provided by this data structure I guess.
As it is answered you could implement a binary search tree. This code may help.
First you have to find the node in the tree
private Node<Key, Value> find (Node<Key, Value> node, Key key){ if (node == null) return null; int comp = comparator.compare(key, node.key); if (comp < 0) return find(node.left, key); else if(comp > 0) return find(node.right, key); else return node; } Now that we have the node, we should find the smallest key but bigger or equal than the node's key, this mean that if the node has a right node this will be a bigger key, but if the right node is null, we must return the node key.
private Node<Key, Value> min(Node<Key, Value> node){ if (node.left == null) return node; else return min(node.left); } public Key ceiling(Key key){ Node<Key, Value> node = find(root, key); if (node.right == null) return node.key; return min(node.right).key; } The second item you ask occur when you remove a node which has to children, so it goes to its smaller child of his right child and insert it in his position.
private Node<Key, Value> remove(Node<Key, Value> node, Key key){ if (node == null){ throw new NoSuchElementException(); } int comp = comparator.compare(key, node.key); if (comp > 0) node.right = remove(node.right, key); else if (comp < 0) node.left = remove(node.left, key); else{ //Found the node to remove if (node.right == null) return node.left; //Does not have right child. (if even does not have left child return null) else if (node.left == null) return node.right; //Does not have left child. else{ //Has right and left children Node<Key, Value> lower = min(node.right); //The lower node of its right child node node.key = lower.key; node.value = lower.value; remove(node.right, lower.key); //Remove the lower node that remains in the tree } } return node; } 