Cтраница 2
Или же, как описывалось в разделе 13.3 применительно к 2 - 3 - 4-деревьям, разделение можно выполнять снизу вверх: вставка реализуется через поиск и помещение нового ключа в нижний узел, если только последний не является 8-узлом - в этом случае он делится на два 4-узла со вставкой среднего ключа и двух связей в его родительский узел. Восходящее разделение выполняется до тех пор, пока не встретится узел-потомок, отличный от 8-узла. [16]