I am writing a implementation about 2-3-4 tree. node structure is as below
type Node struct {
items []int
childs []*Node
parent *Node
}
I am confusing about the code below. In my opinon, the two part is doing the same thing. However, one of these is wrong.
cur = cur.parent
cur._insertNode(upTo, rn)
upTo, rn = cur._splitNode()
cur.parent._insertNode(upTo, rn)
upTo, rn = cur.parent._splitNode()
cur = cur.parent
Can anyone tells me what is the difference?
What I expect is explaintion about the question. Is it a Go pointer method pitfall? Or compiler bug?
Let C be the node that cur
originally points to, let A be the node that is originally the parent of C, and suppose that the call to _insertNode
inserts a new node B between A and C; so, we go from this:
A
|
C
(plus other nodes, not relevant to my point) to this:
A
|
B
|
C
(plus other nodes, still not relevant to my point).
The important thing to note is that before the call to _insertNode
, the parent of C is A; and after the call to _insertNode
, the parent of C is B.
With that in mind, here's your "right code", plus comments explaining what it's doing:
// initially, cur = C
// set cur = A:
cur = cur.parent
// insert B between A and C:
cur._insertNode(upTo, rn)
// cur is still A
// split A:
upTo, rn = cur._splitNode()
And here's your "wrong code", plus comments explaining what it's doing:
// initially, cur = C
// insert B between A and C:
cur.parent._insertNode(upTo, rn)
// cur.parent is now B
// split B:
upTo, rn = cur.parent._splitNode()
// set cur = B:
cur = cur.parent
Do you see?