在 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]

它显示了三个相同的东西，因为它只计算了比较函数。当我的 current_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))

所以，根据你给的图，我们可以定义segment1和segment2。

# 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=<...>)

但是，如果您坚持让列表动态排序，您可以实现一个包装器 class，其中 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)

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

Change comparison function for BST dynamically in Python

python

binary-search-tree