CODEWITHSUNDEEP
data-structures
Seldon
Seldon

Reputation: 387

Efficient data structure that returns smallest element greater or equal than given key and allows decrease key

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.

Upvotes: 1

Views: 433

Answers (2)

santosbogo
santosbogo

Reputation: 23

As it is answered you could implement a binary search tree. This code may help.

  1. 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;
 }

  2. 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;
    }

Upvotes: 0

Pramod
Pramod

Reputation: 5208

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.

Upvotes: 1

Related Questions