有效的数据结构返回比给定密钥大或相等的最小元素并允许降低密钥

Question

是否有一个有效的（log n）数据结构，允许以下操作：

• 返回最小或等于给定键的最小元素
• 用较小的元素交换此元素，然后重新排列结构

元素的数量是已知的，并且不会在一生中变化。

Answer 1

您可以像红黑树一样实现平衡的二进制树

一棵红黑树具有o（log（n））时间复杂性，用于搜索，插入和删除。

您将必须进行一些修改才能返回最小或等于给定键的最小元素。但是我猜该数据结构提供了基本行为。

Answer 2

，您可以实现二进制搜索树。此代码可能会有所帮助。

1. 首先，您必须在树中找到节点

    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. 现在我们有了节点，我们应该找到最小的键，但要比节点键更大或相等，这意味着如果节点具有正确的节点，这将是一个较大的键，但是如果正确的节点为null，我们必须返回节点键。

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

当您删除必须给孩子的节点时，您要问的第二个项目，因此它归其较小的孩子的孩子并将其插入他的位置。

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