pythondefault-parametersb-plus-tree

Encountered a strange problem when writing b+trees using Python


Tree node structure:

class BPlusNode:
    def __init__(self,isleaf = True,val=[],parent=None,children=[]):
        self.values = val
        self.children = children
        self.parent = parent
        self.isleaf = isleaf
        self.order=3

where the bug appears:

def split(self,node):
    if (len(node.children)==0 and len(node.values) <= self.order) or (len(node.children)!=0  and len(node.values) < self.order):
        return
    if node.parent==None:
        #if current node is the root , create a new node as root
        new_root=BPlusNode(isleaf=False)  #something wrong this line

        global CNT
        CNT+=1 
        if(CNT>5):
            sys.exit()
        print('<debug>',new_root.values)

        node.parent=new_root
        self.root=new_root
        parent=new_root

input 3,1,4,5 in order the output is: the output strangely the new node has already been assigned values

but the program runs correctly if I write like this:

new_root=BPlusNode(isleaf=False,val=[],parent=None,children=[])

Why does this happens?

I noticed a mechanism of default parameter in python: operations on mutable objects with default parameters will be preserved for example:

cnt=2
def f(data=[]):
    global cnt
    data.append(1)
    print(data)
    data[0]=cnt
    cnt+=1
    return data
f()
f()
f()

the output will be:

[1]
[2, 1]
[3, 1, 1]

but in my code: def __init__(self,isleaf = True,val=[],parent=None,children=[]): the parameter "val" has not been operated

Is this problem related to this mechanism? Or it is caused by other reasons?


Solution

  • Yes, mutable default arguments are initialized when the function/method is defined so every BPlusNode that uses the mutable defaults receives the same list.

    Instead use the following to avoid mutable defaults:

    class BPlusNode:
        def __init__(self,isleaf = True,val=None,parent=None,children=None):
            self.values = [] if val is None else val
            self.children = [] if children is None else children
            self.parent = parent
            self.isleaf = isleaf
            self.order3
    

    This will assign a new empty list if the default is None, otherwise use the default.

    It runs correctly here:

    new_root=BPlusNode(isleaf=False,val=[],parent=None,children=[])
    

    Because the default isn't used, and you explicitly pass in new list objects.