   (-replace [this entry left right]
     (make-red-node entry left right)))
 
-(deftype SortedRedNodeVal ^{:private true}
-  [-map-entry]
-
-  SortedNode
-  (-color [this] :red)
-  (-entry [this] -map-entry)
-  (-left [this] nil)
-  (-right [this] nil)
-  (-add-left [this node]
-    (make-red-node -map-entry node nil))
-  (-add-right [this node]
-    (make-red-node -map-entry nil node))
-  (-remove-left [this node]
-    (make-red-node -map-entry node nil))
-  (-remove-right [this node]
-    (make-red-node -map-entry nil node))
-  (-balance-left [this node]
-    (make-black-node (-entry node) this (-right node)))
-  (-balance-right [this node]
-    (make-black-node (-entry node) (-left node) this))
-  (-blacken [this]
-    (make-sorted-black-node-val -map-entry))
-  (-redden [this]
-    (throw (new-unsupported-error "Invariant Violation")))
-  (-replace [this entry left right]
-    (make-red-node entry left right)))
-
 (deftype SortedRedBranch ^{:private true}
-  [-map-entry -left-node -right-node]
-
-  SortedNode
-  (-color [this] :red)
-  (-entry [this] -map-entry)
-  (-left [this] -left-node)
-  (-right [this] -right-node)
-  (-add-left [this node]
-    (make-red-node -map-entry node -right-node))
-  (-add-right [this node]
-    (make-red-node -map-entry -left-node node))
-  (-remove-left [this node]
-    (make-red-node -map-entry node -right-node))
-  (-remove-right [this node]
-    (make-red-node -map-entry -left-node node))
-  (-balance-left [this node]
-    (cond
-      (red-node? -left-node)
-        (let [blackened-node (make-black-node (-entry node) -right-node (-right node))]
-          (make-red-node -map-entry (-blacken -left-node) blackened-node))
-      (red-node? -right-node)
-        (let [blackened (make-black-node -map-entry -left-node (-left -right-node))
-              blackened-right (make-black-node (-entry node) (-right -right-node) (-right node))]
-          (make-red-node (-entry -right-node) -map-entry blackened blackened-right))
-      :else
-        (make-black-node (-entry node) this (-right node))))
-  (-balance-right [this node]
-    (cond
-      (red-node? -right-node)
-        (let [blackened (make-black-node (-entry node) (-left node) -left-node)]
-          (make-red-node -map-entry blackened (-blacken -right-node)))
-      (red-node? -left-node)
-        (let [blackened-left (make-black-node (-entry node) (-left node) (-left -left-node))
-              blackened-right (make-black-node -map-entry (-right -left-node) -right-node)]
-          (make-red-node (-entry -left-node) blackened-left blackened-right))
-      :else
-        (make-black-node (-entry node) (-left node) this)))
-  (-blacken [this]
-    (make-sorted-black-branch -map-entry -left-node -right-node))
-  (-redden [this]
-    (throw (new-unsupported-error "Invariant Violation")))
-  (-replace [this entry left right]
-    (make-red-node entry left right)))
-
-(deftype SortedRedBranchVal ^{:private true}
   [-map-entry -left-node -right-node]
 
   SortedNode


(defn- sorted-map-add [root compare-fn k v]
  (if (nil? root)
    (if (nil? v)
      [(make-sorted-red-node (make-map-entry k v)) false]
      [(make-sorted-red-node-val (make-map-entry k v)) false])
    (let [comparison (compare-fn k (key (-entry root)))]
      (if (zero? comparison)
        [root true]

      :else
        (make-black-node (-entry node) (-left node) this)))
  (-blacken [this]
    (make-sorted-black-branch -map-entry -left-node -right-node))
  (-redden [this]
    (throw (new-unsupported-error "Invariant Violation")))
  (-replace [this entry left right]
