// 安插新值；節點鍵值不允許重複，若重複則安插無效。

// 注意，傳回值是個pair，第一元素是個 RB-tree 迭代器，指向新增節點，

// 第二元素表示安插成功與否。

template <class Key, class Value, class KeyOfValue, class Compare, class Alloc>

pair<typename rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::iterator, bool>

rb_tree<Key, Value, KeyOfValue, Compare, Alloc>::insert_unique(const Value& v)

{

  link_type y = header;

  link_type x = root(); // 從根節點開始

  bool comp = true;

  while (x != ) {      // 從根節點開始，往下尋找適當的安插點

    y = x;

    comp = key_compare(KeyOfValue()(v), key(x)); // v 鍵值小於目前節點之鍵值？

    x = comp ? left(x) : right(x);  // 遇「大」則往左，遇「小於或等於」則往右

  }

  // 離開 while 迴圈之後，y 所指即安插點之父節點（此時的它必為葉節點）

  iterator j = iterator(y);   // 令迭代器j指向安插點之父節點 y

  if (comp) // 如果離開 while 迴圈時 comp 為真（表示遇「大」，將安插於左側）

    if (j == begin())   // 如果安插點之父節點為最左節點

      return pair<iterator,bool>(__insert(x, y, v), true);

      // 以上，x 為安插點，y 為安插點之父節點，v 為新值。

    else    // 否則（安插點之父節點不為最左節點）

      --j;  // 調整 j，回頭準備測試...

  if (key_compare(key(j.node), KeyOfValue()(v)))

    // 小於新值（表示遇「小」，將安插於右側）

    return pair<iterator,bool>(__insert(x, y, v), true);

  // 進行至此，表示新值一定與樹中鍵值重複，那麼就不該插入新值。

  return pair<iterator,bool>(j, false);

}