===Псевдокод===
Node insert(Node node, '''int''' insertIndex, '''string''' s):
Node t1, t2 (t1tree1, t2tree3) = split(node, insertIndex) Node t3 tree2 = Node(s) t1 = merge(t1, t3) '''return''' merge(t1merge(tree1, tree2), t2tree3)
===Время работы===
