在Python中动态更改BST的比较函数

Question

在下面的library的帮助下，我创建了一个二叉搜索树。我做了一个比较函数来确定节点应该去哪里。比较函数确定每个段的当前y值

请看以下示例：

from sortedcontainers import SortedList

def findCurrentY(segment):
   #uses current_x to calculate value of y...

def compare(segment):
   position = findCurrentY(segment)
   return position

global current_x
myList = SortedList(key = compare)

segments = [segment1,segment2]

current_x = 1
for segment in segments:
   myList.add(segment)

print(MyList)

current_x = 2
print(MyList)

current_x = 3
print(MyList)

这就是我的输出的样子

For current_x = 1:
MyList = [segment2,segment1] #y value of segment1 is higher than segment2
For current_x = 2:
MyList = [segment2,segment1]
For current_x = 3:
MyList = [segment2,segment1] 

它显示了相同的三倍，因为它只计算了比较函数。当我的当前_x更改时，如何动态更改比较函数，而不删除每个元素并将其再次添加到列表中

所以它必须看起来像这样

For current_x = 1:
MyList = [segment2,segment1] #segment 1 has higher y value
For current_x = 2:
MyList = [segment2,segment1] #segment 1 has higher y value
For current_x = 3:
MyList = [segment1,segment2] #segment 1 has **lower** y value

Answer 1

更改current_x的值不会按预期更改列表。这是因为，如果我们更改compare函数（即，根据生成的新y值重新排序），整个列表需要再次更新，这个过程对于这个数据结构是必要的

请参见下面的示例，以查看此处使用全局变量带来的意外结果

global current_x
current_x = 1


def key_func(val):
    return globals()['current_x'] * val


list = SortedList(key=compare)

>>> list.add(2)
>>> list.add(3)
>>> list.add(5)
>>> print(list)
SortedKeyList([2, 3, 5], key=<function compare at xxx>)
>>> current_x = -1
>>> list.add(5)
>>> list.add(4)
>>> print(list)
SortedKeyList([5, 4, 2, 3, 5], key=<function compare at xxx>)

显然，[5, 4, 2, 3, 5]不是我们期望的结果。因此，一种更安全的方法是将原始列表复制到一个新的SortedList中，而不是就地更改键函数

# Return a function that gives the y value according to x
# Segments are expected to be functions representing expressions like y=x or y=-x+4
def get_key_func(x_value: int):
    return lambda segment: segment(x_value)


# Return a new sorted list based on the same list but with different x
def new_sorted(sl: SortedList, new_x_value):
    return SortedList(sl, key=get_key_func(new_x_value))

所以，根据你给出的图，我们可以定义分段1和分段2

# define y = -x + 4
def expr_one(x):
    return -x + 4


# define y = x
def expr_two(x):
    return x


# The x of the current list is 0
myList = SortedList(key=get_key_func(0))
myList.add(expr_one)         
myList.add(expr_two)         

然后，我们可以尝试创建按结果y和x排序的新列表

for i in range(1, 4):
   print(f'For current_x = {i}:\nMyList = {new_sorted(myList, i)}')

上述代码输出：

For current_x = 1:
MyList = SortedKeyList([<function expr_two at xxx>, <function expr_one at xxx>], key=<...>)
For current_x = 2:
MyList = SortedKeyList([<function expr_two at xxx>, <function expr_one at xxx>], key=<...>)
For current_x = 3:
MyList = SortedKeyList([<function expr_one at xxx>, <function expr_two at xxx>], key=<...>)

但是，如果您坚持要对列表进行动态排序，则可以实现一个包装器类，其中self.list始终引用按预期排序的列表

class DynamicSorted:
    def __init__(self, key_func):
        self.list = SortedList(key=key_func)

    def update_key_func(self, new_key_func):
        self.list = SortedList(self.list, key=new_key_func)