go2-3-4-tree

Pointer invoke method pitfall?


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?


Solution

  • 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?