BST-递归类比结构元素插入
BST-analogous structure element insertion recursively
我想知道为什么作者不直接写下面的代码而不是原来的代码。我测试了很多,不错过一个案例。所以,它按预期工作。与时间复杂度有关吗?我错过了什么要点或细微差别?
将元素视为 [key,value,left-node,right-node]
// my simplification
def insert_binary_tree(x, T):
if T == []:
T.extend([x[0], x[1], [], []])
else:
if x[0] < T[0]:
insert_binary_tree(x, T[2])
else:
insert_binary_tree(x, T[3])
原代码
def insert_binary_tree(x, T):
if T == []:
T.extend([x[0], x[1], [], []])
else:
if x[0] < T[0]:
if T[2] == []:
T[2] = [x[0], x[1], [], []]
else:
insert_binary_tree(x, T[2])
else:
if T[3] == []:
T[3] = [x[0], x[1], [], []]
else:
insert_binary_tree(x, T[3])
示例 运行、
t = ['Emma', '2002/08/23',
['Anna', '1999/12/03', [], []],
['Paul', '2000/01/13',
['Lara', '1987/08/23',
['John', '2006/05/08', [], []],
['Luke', '1976/07/31', [], []]],
['Sara', '1995/03/14', [], []]]]
def insert_binary_tree(x, T):
if T == []:
T.extend([x[0], x[1], [], []])
else:
if x[0] < T[0]:
insert_binary_tree(x, T[2])
else:
insert_binary_tree(x, T[3])
print(t)
insert_binary_tree(['Abba', '1111/11/11', [], []], t)
print(t)
唯一的原因可能是对象之间的独立性更高。通过稍微改变输入来比较两个代码:
empty = []
t = ['Emma', '2002/08/23',
['Anna', '1999/12/03', empty, empty],
['Paul', '2000/01/13',
['Lara', '1987/08/23',
['John', '2006/05/08', empty, empty],
['Luke', '1976/07/31', empty, empty]],
['Sara', '1995/03/14', empty, empty]]]
现在,原来的代码仍然有效,但你的不行。您仍然可以简化它,同时保持对空列表的独立引用:
def insert_binary_tree(x, T):
if T == []:
T.extend([x[0], x[1], [], []])
else:
child = 2 + (x[0] >= T[0])
if T[child]:
insert_binary_tree(x, T[child])
else:
T[child] = x[:2] + [[], []]
# again trying to avoid mutable list references
我想知道为什么作者不直接写下面的代码而不是原来的代码。我测试了很多,不错过一个案例。所以,它按预期工作。与时间复杂度有关吗?我错过了什么要点或细微差别?
将元素视为 [key,value,left-node,right-node]
// my simplification
def insert_binary_tree(x, T):
if T == []:
T.extend([x[0], x[1], [], []])
else:
if x[0] < T[0]:
insert_binary_tree(x, T[2])
else:
insert_binary_tree(x, T[3])
原代码
def insert_binary_tree(x, T):
if T == []:
T.extend([x[0], x[1], [], []])
else:
if x[0] < T[0]:
if T[2] == []:
T[2] = [x[0], x[1], [], []]
else:
insert_binary_tree(x, T[2])
else:
if T[3] == []:
T[3] = [x[0], x[1], [], []]
else:
insert_binary_tree(x, T[3])
示例 运行、
t = ['Emma', '2002/08/23',
['Anna', '1999/12/03', [], []],
['Paul', '2000/01/13',
['Lara', '1987/08/23',
['John', '2006/05/08', [], []],
['Luke', '1976/07/31', [], []]],
['Sara', '1995/03/14', [], []]]]
def insert_binary_tree(x, T):
if T == []:
T.extend([x[0], x[1], [], []])
else:
if x[0] < T[0]:
insert_binary_tree(x, T[2])
else:
insert_binary_tree(x, T[3])
print(t)
insert_binary_tree(['Abba', '1111/11/11', [], []], t)
print(t)
唯一的原因可能是对象之间的独立性更高。通过稍微改变输入来比较两个代码:
empty = []
t = ['Emma', '2002/08/23',
['Anna', '1999/12/03', empty, empty],
['Paul', '2000/01/13',
['Lara', '1987/08/23',
['John', '2006/05/08', empty, empty],
['Luke', '1976/07/31', empty, empty]],
['Sara', '1995/03/14', empty, empty]]]
现在,原来的代码仍然有效,但你的不行。您仍然可以简化它,同时保持对空列表的独立引用:
def insert_binary_tree(x, T):
if T == []:
T.extend([x[0], x[1], [], []])
else:
child = 2 + (x[0] >= T[0])
if T[child]:
insert_binary_tree(x, T[child])
else:
T[child] = x[:2] + [[], []]
# again trying to avoid mutable list references