Filling a pointer array with NULL in O(1)

Well, this is my first time posting in the text board, so...

I asked in /g/ already and I have some questions. My problem is as follows.

I'm building a tree structure in C. Each level has an array of pointers that point to the following node. The amount of pointers depends on the level too, so a lower level node will have less pointers than the father. An insertion in this structure has a O(lg lg n) complexity. However, building the node is using O(u) for u child nodes. And at times I need to build the node in the middle of the insertion function. This is slowing significantly the run time and adding a complexity time the function shouldn't have.

I was thinking of using a char variable initially set to zero, and if the amount of pointers to be allocated exceeds 8 I can resize the char variable with realloc. A zero in the i-th bit means the i-th node is not pointing to a node. I don't know how much time will this take and I don't know if it'll be too costly to search for a specific byte.

Then there's this function, memset. It seems awesome and all but I don't know how much time it takes.

I need this node building function to take O(1) or a really reasonable time so it doesn't make the whole function slower than it should be.

Wat do?

This question just doesn't make sense from a hardware pov, if you want to have values in memory you'd have to write to it.

If you use some pointer wizardry to work your way around it that's fine but don't call it something that it isn't.