       (recur (lookup* v k))
       v)))
 
-(defn tree []
-  (leaf-node))
-
-
-#_(-> (tree)
+(defn tree [b]
+  (leaf-node b))
+
+
+#_(-> (tree 3)
     (insert 5 55)
     (insert 9 99)
     (insert 3 33)

          nks       (concat ks1 [k] ks2)
          nvs       (concat vs1 [v] vs2)]
      #_(println "IINS" nks nvs)
      (internal-node nks nvs nsize))
    (let [nvs (-> vs butlast (concat [v]))]
      #_(println "IINS (INF)" ks nvs)
      (internal-node ks nvs size))))

(defn- inode-insert [{:keys [ks vs] :as n} k v]
  (let [[childk childv] (inode-lookup n k)
        [n1 nk n2]      (insert* childv k v)
        nn              (if (nil? n2)
                          (inode-ins n childk n1)
                          (-> (inode-ins n nk n1)
                              (inode-ins childk n2)))]
    (if (>= (-> nn :ks count) 3)
      (inode-split nn)
      [nn])))


(defn- leaf-node
  ([ks vs size]
   {:pre [(= (count vs)
             (count ks))]}
   {:type :leaf
    :m (->> (interleave ks vs)
            (apply sorted-map))
    :size size})

  ([]
   (leaf-node nil nil 0))

  ([m size]
   {:type :leaf
    :m m
    :size size}))

(defn- lnode-lookup [{:keys [m] :as n} k]
  [nil (get m k)])

(defn- lnode-split [{:keys [m size] :as n}]
  (let [partition-size (-> size (/ 2) Math/ceil int)
        [ks1 ks2] (partition-all partition-size (keys m))
        m1 (apply dissoc m ks2)
        m2 (apply dissoc m ks1)]
    #_(println "LSPLIT" m1 m2)
    [(leaf-node m1 partition-size)
     (last ks1)
     (leaf-node m2 (- partition-size (rem size 2)))]))

(defn- lnode-ins [{:keys [m size] :as n} k v]
  (let [nm (assoc m k v)]
    #_(println "LINS" nm)
    (leaf-node nm (inc size))))

(defn- lnode-insert [{:keys [m] :as n} k v]
  (let [nn (lnode-ins n k v)]
    (if (>= (-> nn :m count) 3)
      (lnode-split nn)
      [nn])))


      (<= (compare k k*) 0) [k* v*]
      true                  (recur ks* vs*))))

(defn- inode-split [{:keys [b ks vs size] :as n}]
  (let [partition-size  (-> size (/ 2) Math/ceil int)
        [ks1 ks2]       (partition-all partition-size ks)
        [ks1 nk]        [(butlast ks1) (last ks1)]
        [vs1 vs2a vs2b] (partition-all partition-size vs)
        vs2             (concat vs2a vs2b)]
    #_(println "ISPLIT")
    [(internal-node b ks1 vs1 (dec partition-size))
     nk
     (internal-node b ks2 vs2 (- partition-size (rem size 2)))]))

(defn- inode-ins [{:keys [b ks vs size] :as n} k v]
  (if-not (= k ::inf)
    (let [[ks1 ks2] (split-with #(< (compare % k) 0) ks)
          [vs1 vs2] (split-at (count ks1) vs)
