通过参数化递归调用，使用 Python 假设生成有效的二叉搜索树

Question

如何在 Python 假设库中参数化递归策略？

我想测试is_valid_bst函数是否通过使用递归策略生成有效的 BST 来工作。

import hypothesis as hp
from hypothesis import strategies as hps

class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def __repr__(self):
if not self.left and not self.right:
return f'TreeNode({self.val})'
return f'TreeNode({self.val}, left={self.left}, right={self.right}'

def is_valid_bst(node):
if not node:
return True
is_valid = True
if node.left:
is_valid = is_valid and node.val > node.left.val
if node.right:
is_valid = is_valid and node.val < node.right.val
if not is_valid:
return False
return is_valid_bst(node.left) and is_valid_bst(node.right)

@hps.composite
def valid_bst_trees(draw, strategy=None, min_value=None, max_value=None):
val = draw(hps.integers(min_value=min_value, max_value=max_value))
node = TreeNode(val)
node.left = draw(strategy)
node.right = draw(strategy)
return node

def gen_bst(tree_strategy, min_value=None, max_value=None):
return hps.integers(min_value=min_value, max_value=max_value).flatmap(
lambda val: valid_bst_trees(
strategy=tree_strategy, min_value=min_value, max_value=max_value))

@hp.given(hps.recursive(hps.just(None), gen_bst))
def test_is_valid_bst_works(node):
assert is_valid_bst(node)

Answer 1

我想通了。 我的主要误解是：

• 假设递归策略创建的tree_strategy可以安全地从多次中提取，并将生成适当的递归。

其他一些陷阱：

• 基本情况需要None和单例树。 只有None，您将只会生成 None。
• 对于单一实例树，每次都必须生成一个新树。 否则，您最终会在树中出现循环，因为每个节点都是同一棵树。 实现此目的的最简单方法是hps.just(-111).map(TreeNode).
• 如果是单例树，则需要覆盖基本情况以遵守min_value和max_value。

完整的工作解决方案：

import hypothesis as hp
from hypothesis import strategies as hps

class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def __repr__(self):
if not self.left and not self.right:
return f'TreeNode({self.val})'
return f'TreeNode({self.val}, left={self.left}, right={self.right}'

def is_valid_bst(node):
if not node:
return True
is_valid = True
if node.left:
is_valid = is_valid and node.val > node.left.val
if node.right:
is_valid = is_valid and node.val < node.right.val
if not is_valid:
return False
return is_valid_bst(node.left) and is_valid_bst(node.right)

@hps.composite
def valid_bst_trees(
draw, tree_strategy, min_value=None, max_value=None):
"""Returns a valid BST.
Idea is to pick an integer VAL in [min_value, max_value) for this tree and
and use it as a constraint for the children by parameterizing
`tree_strategy` so that:
1. The left child value is in [min_value, VAL).
2. The right child value is in (VAL, min_value].
"""
# We're drawing either a None or a singleton tree.
node = draw(tree_strategy)
if not node:
return None
# Can't use implicit boolean because the values might be falsey, e.g. 0.
if min_value is not None and max_value is not None and min_value >= max_value:
return None
# Overwrite singleton tree.val with one that respects min and max value.
val = draw(hps.integers(min_value=min_value, max_value=max_value))
node.val = val
node.left = draw(valid_bst_trees(
tree_strategy=tree_strategy,
min_value=min_value,
max_value=node.val - 1))
node.right = draw(valid_bst_trees(
tree_strategy=tree_strategy,
min_value=node.val + 1,
max_value=max_value))
return node

def gen_bst(tree_strategy, min_value=None, max_value=None):
return valid_bst_trees(
tree_strategy=tree_strategy,
min_value=min_value,
max_value=max_value)

# Return a new, distinct tree node every time to avoid self referential trees.
singleton_tree = hps.just(-111).map(TreeNode)

@hp.given(hps.recursive(hps.just(None) | singleton_tree, gen_bst))
def test_is_valid_bst_works(node):
assert is_valid_bst(node)

# Simple tests to demonstrate how the TreeNode works
def test_is_valid_bst():
assert is_valid_bst(None)
assert is_valid_bst(TreeNode(1))
node1 = TreeNode(1)
node1.left = TreeNode(0)
assert is_valid_bst(node1)
node2 = TreeNode(1)
node2.left = TreeNode(1)
assert not is_valid_bst(node2)
node3 = TreeNode(1)
node3.left = TreeNode(0)
node3.right = TreeNode(1)
assert not is_valid_bst(node3)