@Override
  public V put(final K key, final V value) {
    OMVRBTreeEntry<K, V> parentNode = null;

    try {
      if (root == null) {
        root = createEntry(key, value);
        root.setColor(BLACK);

        setSize(1);
        modCount++;
        return null;
      }

      // TRY TO GET LATEST SEARCH
      parentNode = getLastSearchNodeForSameKey(key);
      if (parentNode != null) {
        if (lastSearchFound) {
          // EXACT MATCH: UPDATE THE VALUE
          pageIndex = lastSearchIndex;
          modCount++;
          return parentNode.setValue(value);
        }
      }

      // SEARCH THE ITEM
      parentNode = getEntry(key, true, PartialSearchMode.NONE);

      if (pageItemFound) {
        modCount++;
        // EXACT MATCH: UPDATE THE VALUE
        return parentNode.setValue(value);
      }

      setLastSearchNode(null, null);

      if (parentNode == null) {
        parentNode = root;
        pageIndex = 0;
      }

      if (parentNode.getFreeSpace() > 0) {
        // INSERT INTO THE PAGE
        parentNode.insert(pageIndex, key, value);
      } else {
        // CREATE NEW NODE AND COPY HALF OF VALUES FROM THE ORIGIN TO THE NEW ONE IN ORDER TO GET VALUES BALANCED
        final OMVRBTreeEntry<K, V> newNode = createEntry(parentNode);

        if (pageIndex < parentNode.getPageSplitItems())
          // INSERT IN THE ORIGINAL NODE
          parentNode.insert(pageIndex, key, value);
        else
          // INSERT IN THE NEW NODE
          newNode.insert(pageIndex - parentNode.getPageSplitItems(), key, value);

        OMVRBTreeEntry<K, V> node = parentNode.getRight();
        OMVRBTreeEntry<K, V> prevNode = parentNode;
        int cmp = 0;
        if (comparator != null)
          while (node != null) {
            cmp = comparator.compare(newNode.getFirstKey(), node.getFirstKey());
            if (cmp < 0) {
              prevNode = node;
              node = node.getLeft();
            } else if (cmp > 0) {
              prevNode = node;
              node = node.getRight();
            } else {
              throw new IllegalStateException("Duplicated keys were found in OMVRBTree.");
            }
          }
        else
          while (node != null) {
            cmp = compare(newNode.getFirstKey(), node.getFirstKey());
            if (cmp < 0) {
              prevNode = node;
              node = node.getLeft();
            } else if (cmp > 0) {
              prevNode = node;
              node = node.getRight();
            } else {
              throw new IllegalStateException("Duplicated keys were found in OMVRBTree.");
            }
          }

        if (prevNode == parentNode)
          parentNode.setRight(newNode);
        else if (cmp < 0)
          prevNode.setLeft(newNode);
        else if (cmp > 0)
          prevNode.setRight(newNode);
        else
          throw new IllegalStateException("Duplicated keys were found in OMVRBTree.");

        fixAfterInsertion(newNode);
      }

      modCount++;
      setSizeDelta(+1);

    } finally {
      checkTreeStructure(parentNode);
    }

    return null;
  }
@ Override public V put ( final K key , final V value ) { OMVRBTreeEntry < K , V > parentNode = null ; try { if ( root == null ) { root = createEntry ( key , value ) ; root . setColor ( BLACK ) ; setSize ( 1 ) ; modCount ++ ; return null ; } parentNode = getLastSearchNodeForSameKey ( key ) ; if ( parentNode != null ) { if ( lastSearchFound ) { pageIndex = lastSearchIndex ; modCount ++ ; return parentNode . setValue ( value ) ; } } parentNode = getEntry ( key , true , PartialSearchMode . NONE ) ; if ( pageItemFound ) { modCount ++ ; return parentNode . setValue ( value ) ; } setLastSearchNode ( null , null ) ; if ( parentNode == null ) { parentNode = root ; pageIndex = 0 ; } if ( parentNode . getFreeSpace ( ) > 0 ) { parentNode . insert ( pageIndex , key , value ) ; } else { final OMVRBTreeEntry < K , V > newNode = createEntry ( parentNode ) ; if ( pageIndex < parentNode . getPageSplitItems ( ) ) parentNode . insert ( pageIndex , key , value ) ; else newNode . insert ( pageIndex - parentNode . getPageSplitItems ( ) , key , value ) ; OMVRBTreeEntry < K , V > node = parentNode . getRight ( ) ; OMVRBTreeEntry < K , V > prevNode = parentNode ; int cmp = 0 ; if ( comparator != null ) while ( node != null ) { cmp = comparator . compare ( newNode . getFirstKey ( ) , node . getFirstKey ( ) ) ; if ( cmp < 0 ) { prevNode = node ; node = node . getLeft ( ) ; } else if ( cmp > 0 ) { prevNode = node ; node = node . getRight ( ) ; } else { throw new IllegalStateException ( "Duplicated keys were found in OMVRBTree." ) ; } } else while ( node != null ) { cmp = compare ( newNode . getFirstKey ( ) , node . getFirstKey ( ) ) ; if ( cmp < 0 ) { prevNode = node ; node = node . getLeft ( ) ; } else if ( cmp > 0 ) { prevNode = node ; node = node . getRight ( ) ; } else { throw new IllegalStateException ( "Duplicated keys were found in OMVRBTree." ) ; } } if ( prevNode == parentNode ) parentNode . setRight ( newNode ) ; else if ( cmp < 0 ) prevNode . setLeft ( newNode ) ; else if ( cmp > 0 ) prevNode . setRight ( newNode ) ; else throw new IllegalStateException ( "Duplicated keys were found in OMVRBTree." ) ; fixAfterInsertion ( newNode ) ; } modCount ++ ; setSizeDelta ( + 1 ) ; } finally { checkTreeStructure ( parentNode ) ; } return null ; }
Associates the specified value with the specified key in this map. If the map previously contained a mapping for the key, the
old value is replaced.

@param key
key with which the specified value is to be associated
@param value
value to be associated with the specified key

@return the previous value associated with <tt>key</tt>, or <tt>null</tt> if there was no mapping for <tt>key</tt>. (A
<tt>null</tt> return can also indicate that the map previously associated <tt>null</tt> with <tt>key</tt>.)
@throws ClassCastException
if the specified key cannot be compared with the keys currently in the map
@throws NullPointerException
if the specified key is null and this map uses natural ordering, or its comparator does not permit null keys