Здравствуйте, WolfHound, Вы писали:
WH>Вставку уже написал. Сейчас думаю как удаление сделать красиво и эффективно.
Когда-то развлекался:

module MyList { //вспомогательно
 public Replace['a] (L : list['a], x : 'a, y : list['a]) : list['a];
 public indexOf['a] (L : list['a], x : 'a) : int;
}
[Record]
public class Tree {
 [Record]
 public class Node {
  public sons : list[Node];
  public isLeaf () : bool { List.IsEmpty (sons) }
  public sonsCount () : int { List.Length (sons) }
  public getBrother (s : Node) : Node * bool {
   match (MyList.indexOf (sons, s)) {
     | 0 => (List.Nth (sons, 1), true)
     | i => (List.Nth (sons, i - 1), false)
   }
  }
 };
 root : Node;
 public Replace (path : list[Node], lst : list[Node]) : Tree
 requires List.Length (lst) <= 2
//requires lst.ForAll(x => x.height () == path.Head.height ()) //примерно так
 {
   | ([_], [l]) => Tree (l)
   | ([_], [l1, l2]) => Tree (Node ([l1, l2]))
   | (q :: w :: rst, _) =>
     def l = MyList.Replace (w.sons, q, lst);
     match(List.Length (l)) {
       | 2 | 3 => Replace (w :: rst, [Node (l)])
       | 1 when List.IsEmpty (rst) => Tree (l.Head)
       | 1 =>
         def e = rst.Head;
         def ls = MyList.Replace (e.sons, w, []);
         def (b, lft) = e.getBrother (w);
         if (lft)
           Replace (b.sons.Head :: b :: rst, [l.Head, b.sons.Head])
         else
           Replace (b.sons.Last :: b :: rst, [b.sons.Last, l.Head])
       | 4 =>
         def l1 = l.FirstN (2);
         def l2 = l.ChopFirstN (2);
         Replace (w :: rst, [Node (l1), Node (l2)])
     }
 }
 public height () : int; // в лоб
 public static merge (L : Tree, R : Tree) : Tree {
  def Lh = L.height ();
  def Rh = R.height ();
  if (Lh == Rh)
   Tree (Node ([L.root, R.root]))
  else {
   if (Lh < Rh) {
    def g(n, x) {
     | (_, 0) => [n]
     | _ => n :: g (n.sons.Head, x - 1)
    }
    def p = g(R.root, Rh - Lh);
    R.Replace (p, [L.root, p.Head])
   } else {
    def g(n, x) {
     | (_, 0) => [n]
     | _ => n :: g (n.sons.Last, x - 1)
    }
    def p = g(L.root, Lh - Rh);
    L.Replace (p, [p.Head, R.root])
   }
  }
 }
};

Replace позволяет делать вставку, удаление, замену произвольного узла. На его базе + Find легко построить Set.
Merge сливает два дерева, до Split не добрался