When adding nodes to an already spanned tree, do I need to re-calculate the entire tree from scratch, or can I just locally re-structure it?

To illustrate


I want to add both the green and black nodes. The green one seems straightforward because it doesn't affect the local structure much. But the black node's insertion would disrupt it quite a lot.

Now I have a theory...

I draw a new Node (P) on the graph. Its 6 closest neighbouring nodes are the only ones potentially affected by the new node P.

Is that theory viable? I'm not sure how to go about proving/disproving it and I wondered if anyone had done it already.

(I came by the number 6 because 6 is the maximum number of connections a single node can have. On a 2D plane it is impossible for a node to be connected to 7 or more other nodes. 6 is possible but only by chance and the order in which the nodes are processed. 5 is rare, 3 and 4 are common)