void insertNonFull(BTreeNode* node, int key) { int i = node->n - 1; if (node->leaf) { while (i >= 0 && key < node->keys[i]) { node->keys[i + 1] = node->keys[i]; i--; } node->keys[i + 1] = key; node->n++; } else { while (i >= 0 && key < node->keys[i]) i--; if (node->children[i + 1]->n == MAX) { splitChild(node, i + 1, node->children[i + 1]); if (key > node->keys[i + 1]) i++; } insertNonFull(node->children[i + 1], key); } }