基于自定义二叉树实现二项式期权定价的问题及适用数据结构咨询
二项式期权定价模型实现的适配数据结构问题
提问内容
模型基本规则
当前正在开展二项式期权定价模型的实现,对股票价格的建模规则如下:
- 初始时刻股价为给定值
S_0 - 第1个时间步n=1,股价仅存在上行、下行两种状态:上行状态股价为
u*S_0,下行状态股价为d*S_0 - 第2个时间步n=2,n=1时刻的两个价格各自拆分出上行、下行状态:
- 对应n=1时刻的上行价格,n=2上行价格为
u^2*S_0、下行价格为u*d*S_0 - 对应n=1时刻的下行价格,n=2上行价格为
d*u*S_0、下行价格为d^2*S_0
- 对应n=1时刻的上行价格,n=2上行价格为
- 由于乘法交换律
u*d*S_0 = d*u*S_0,n=2时刻实际共有3个可能价格:u^2*S_0、u*d*S_0(通常假设u*d = 1,该值等于初始价S_0)、d^2*S_0 - 该结构为分层连通的特殊形态,带有跨路径的共享节点,区别于常规独立分叉的二叉树。
现有实现与矛盾
- 目前查阅到的主流实现方案,大多是先生成分层价格序列,再以numpy数组形式存储为上三角矩阵
- 项目初期设计直觉是采用树类数据结构,通过递归方法实现各类期权定价公式。但实际落地时发现,上述模型对应的结构并不符合普通二叉树的定义:不同路径交汇的共享节点,会导致子树存在多根问题。
自定义二叉树的测试
自行编写的二叉树类代码如下:
class BinaryTree: class Node: def __init__(self, val, left=None, right=None): self.val = val self.left = left self.right = right def __init__(self): self.size = 0 self.root = None def pprint(self, width=64): height = self.height() nodes = [(self.root, 0)] prev_level = 0 repr_str = '' while nodes: n,level = nodes.pop(0) if prev_level != level: prev_level = level repr_str += '\n' if not n: if level < height-1: nodes.extend([(None, level+1), (None, level+1)]) repr_str += '{val:^{width}}'.format(val='-', width=width//2**level) elif n: if n.left or level < height-1: nodes.append((n.left, level+1)) if n.right or level < height-1: nodes.append((n.right, level+1)) repr_str += '{val:^{width}}'.format(val=n.val, width=width//2**level) print(repr_str) def __len__(self): return self.size def height(self): def height_rec(t): if not t: return 0 else: return 1 + max(height_rec(t.left), height_rec(t.right)) return height_rec(self.root) def add(self, val): assert(val not in self) def add_rec_notin(node): if not node: return BinaryTree.Node(val) elif val < node.val: # 向左子树添加 return BinaryTree.Node(node.val, left=add_rec_notin(node.left), right=node.right) else: # val > node.val,向右子树添加 return BinaryTree.Node(node.val, left=node.left, right=add_rec_notin(node.right)) self.root = add_rec_notin(self.root) self.size += 1 def __iter__(self): def iter_rec(node): if node: for x in iter_rec(node.left): yield x for x in iter_rec(node.right): yield x for x in iter_rec(self.root): yield x
构建价格树的测试逻辑:
T = 2 # 时间周期数 S0 = 2 # 初始股价 d = 0.9 # 下行因子 u = 1.1 # 上行因子 stock_tree = BinaryTree() stock_prices = [] for t in range(T+1): lst = [] for r in range(t+1): lst.append(S0 * (u ** r) * (d **(t-r))) stock_prices.append(lst) for p in stock_prices: for i in range(len(p)): stock_tree.add(round(p[i],3)) stock_tree.pprint()
运行后的输出结构为:
2.0 1.8 2.2 1.62 1.98 - 2.42
核心不适配问题:普通二叉树结构完全无法匹配该场景需求。即便尝试将重复值1.98添加到树中,该值也不会填充到输出预留的空位位置,反而会被挂载到左子树已有1.98节点的右孩子位置。
参考解答
首先需要明确一个核心认知:二项式期权定价模型对应的结构根本不属于树结构。数据结构领域对树的定义是“任意节点最多有1个父节点,不存在环的连通图”,而二项式模型中t≥2的节点都有2个来自上一层的父节点,自然无法用二叉树实现。
适配该场景的标准数据结构是分层有向无环图(Layered DAG),常见实现方式有三种:
- 显式节点类实现
自定义节点结构,按时间层记录节点位置,直接指向对应相邻层的共享节点,代码示例:
构建时按层遍历生成每个位置的唯一节点,再依次连接相邻层的节点引用即可——t=2层k=1位置的节点(对应class BinomialNode: def __init__(self, t: int, k: int, val: float): self.t = t # 所在时间步索引 self.k = k # 该时间步内的位置(对应k次上行) self.val = val self.up_child = None # 指向t+1层k+1位置的节点 self.down_child = None # 指向t+1层k位置的节点u*d*S0)会同时被t=1层k=0位置的up_child和t=1层k=1位置的down_child指向,完全实现共享节点的逻辑。 - 分层嵌套列表实现
二项式模型的连接关系是固定的:对于任意t层k位置的节点,对应的孩子节点永远在t+1层的k和k+1位置。不需要额外维护节点间的显式引用,直接用嵌套列表存储每层的节点值即可:
这种实现和numpy上三角矩阵的存储逻辑完全一致,但可以通过递归函数封装节点访问逻辑,满足递归定价的需求。# 构建价格分层列表 price_grid = [] for t in range(T+1): layer = [S0 * (u**k) * (d**(t-k)) for k in range(t+1)] price_grid.append(layer) - 纯递归无存储实现
如果项目规模不大,甚至不需要预生成所有节点,直接在递归函数内根据节点位置(t, k)动态计算当前股价、期权价值即可。这种方式的计算逻辑和结构存储完全独立,没有冗余节点的存储开销。
上述所有实现方式都可以完美支持递归期权定价:从最后一层的节点开始,按风险中性概率向上折现计算期权价值,每个节点的价值由两个孩子节点的加权收益得到,和最初的树状递归设计直觉完全匹配。
内容的提问来源于stack exchange,提问作者Alex
相关产品推荐
相关产品推荐

