DouKaku?

B+木(B+Tree、B-Plus-Treeなど)とは、B木を拡張した平衡木です。
元のB木は枝や葉に関係なくキーとデータの組が入りますが、
B+木では葉に全てのキーとデータが入り、ルートから葉までの
枝には索引と分岐しか入らず、B木より空間効率が良いアルゴリズムです。
DBなどでよく使われますが、Web上のサンプルとしてはあまり見かけません。

問題：
B+木の検索や追加は比較的簡単なので、本題では削除のみに注目します。
B+木のルート(根)とキーを与えると、キーに一致するB+木中の要素を、
要素の順序と木の平衡を保ちながら削除し、更新したB+木を返す関数を
作ってください。(入力するB+木のサンプルは後述します)

条件：
・B+木としては最小のオーダー3の構造を対象にします。
  「オーダー3」とは、葉の要素数が2～3、枝の分岐の数も
  2～3の範囲を取るものです。(枝の索引数は分岐の数-1)
  ただしルートのみは、B+木全体の要素の数が3以下の場合、
  葉の要素の数が2未満になりえます。(例を見てください)
・要素や索引のキーは数字とし、データは省略してかまいません。
・B+木そのものやDB以外のライブラリならば使用してかまいません。
・結果で得られるB+木は入力の複製でもかまいません。(関数型言語への配慮)
・ノードの索引の更新は必ずしも存在する要素のキーと同期させる必要はありません。
  ただし検索に支障のない範囲である事。
・関数に与えたキーがどの要素とも一致せず、削除に失敗する場合は、
  NULLなどの生存ノードと区別できる値を返してください。

例：
問題の理解を促すための例示としてB+木をS式のリストで表します。
※この例の結果と違っていても平衡が保てていればOKです。
リストのタグの意味 … L=葉, N=枝(ノード), B=分岐, K=索引, 数字=キー

例) 1から7までのB+木
(N (K 3 6)        ; 検索に使われる索引は、middleとright各々の最小キーがあれば良い
   (B (L 1 2)     ; left    
      (L 3 4 5)   ; middle (分岐と葉の数は最小2、最大3つです)
      (L 6 7)))   ; right  
1を削除
=>(N (K 4 6)      ; middleの最小キーが変化したので索引も更新します
     (B (L 2 3)   ; middleの最小キーをもらって平衡を保ちます
        (L 4 5)
        (L 6 7)))
さらに2を削除
=>(N (K 6)        ; middleの最小キーが変化したので索引も更新します
     (B (L 3 4 5) ; 不完全なleft(またはmiddle)を削除し統合します
        (L 6 7)))
さらに6を削除
=>(N (K 5)
     (B (L 3 4)
        (L 5 7)))
さらに4を削除
=>(L 3 5 7)       ; 葉の数を保てなくなるので葉のみになります
さらに3と5を削除
=>(L 5 7) 
=>(L 7)           ; ルートのみ葉の数が2未満になりえます

入力するB+木のサンプル：
1から81までのB+木を用意しました。
本題はこれらを全て削除して要素数をゼロにできればOKです。
※S式のリストで出してますが、実際のデータ構造は何でもいいです。
(N (K 28 55)
   (B (N (K 10 19)
         (B (N (K 4 7)
               (B (L  1  2  3)
                  (L  4  5  6)
                  (L  7  8  9)))
            (N (K 13 16)
               (B (L 10 11 12)
                  (L 13 14 15)
                  (L 16 17 18)))
            (N (K 22 25)
               (B (L 19 20 21)
                  (L 22 23 24)
                  (L 25 26 27)))))
      (N (K 37 46)
         (B (N (K 31 34)
               (B (L 28 29 30)
                  (L 31 32 33)
                  (L 34 35 36)))
            (N (K 40 43)
               (B (L 37 38 39)
                  (L 40 41 42)
                  (L 43 44 45)))
            (N (K 49 52)
               (B (L 46 47 48)
                  (L 49 50 51)
                  (L 52 53 54)))))
      (N (K 64 73)
         (B (N (K 58 61)
               (B (L 55 56 57)
                  (L 58 59 60)
                  (L 61 62 63)))
            (N (K 67 70)
               (B (L 64 65 66)
                  (L 67 68 69)
                  (L 70 71 72)))
            (N (K 76 79)
               (B (L 73 74 75)
                  (L 76 77 78)
                  (L 79 80 81)))))))