使用Python编写B+树时遇到奇怪问题

Question

树节点结构：

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

错误出现的地方：

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

输入顺序是 3,1,4,5，输出是：

输出结果

奇怪的是，新节点已经被赋值了。

但是如果我这样写，程序就能正常运行：

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

为什么会这样呢？

我注意到在 Python 中有一个默认参数的机制：

对可变对象（比如列表）使用默认参数时，这些操作会被保留。

举个例子：

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

输出结果将会是：

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

但是在我的代码中：

def __init__(self,isleaf = True,val=[],parent=None,children=[]):

参数 "val" 并没有被操作过。

这个问题和这个机制有关吗？还是说是其他原因造成的？

Answer 1

是的，可变的默认参数是在函数或方法被定义的时候就初始化了，所以每一个使用这些可变默认参数的BPlusNode都会得到相同的列表。

为了避免使用可变的默认参数，应该使用以下方法：

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

这样做会在默认值是None的时候分配一个新的空列表，否则就使用默认值。

这里运行得很好：

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

因为默认值没有被使用，你是明确传入了新的列表对象。