Изменения

$B-TREETree-INSERT Insert(T, k)$

$r = T.root$ $if (r.n == 2t - 1)$

$s = ALLOCATEAllocate-NODENode()$ $T.root = s$ $s.leaf = FALSE$ $s.n = 0$ $s.c_1 $C_1$ = r$ $B-TREETree-SPLITSplit-CHILDChild(s, 1)$ $B-TREETree-INSERTInsert-NONFULLNonfull(s, k)$

$else$ $B-TREETree-INSERTInsert-NONFULLNonfull(r, k)$

Функция $B-TREETree-INSERTInsert-NONFULLNonfull$ вставляет ключ $k$ в узел $x$, который должен быть незаполненным при вызове. Использование функции $B-TREETree-SPLITSplit-CHILDChild$ гарантирует, что рекурсия не встретится с заполненным узлом.