完全二叉树

2024-10-15

完全二叉树（精选7篇）

完全二叉树篇1

1 引言

对期权价格的研究是金融资产定价理论的一个重要课题。传统的定价理论往往设定了一些理想的条件。例如, Black和Scholes[1]模型 (下文简称BS模型) 假设股票价格服从几何布朗运动, 并且假设无风险利率和股票波动率为常数。Cox、Ross和Rubinstein[2]的二叉树模型 (下文简称CRR模型) 也假设了同样的理想条件, 得到了二叉树期权定价公式, 并且证明这个公式和BS公式是等价的。但是, 在实践中常常发现, 这些期权公式得到的理论价格与实际市场价格存在着明显的偏差。造成这种现象的主要原因是, 真实市场比模型假设的更加复杂。比如, 在BS模型和CRR模型中股票波动率为常数的假设往往不能满足。其根本原因在于, 市场上获取到的信息往往是不完全的。在一般情况下, 参数值不能准确得到;在某些情况下, 参数几乎无法直接观测。

为了解决前述模型假设与现实情况不符的问题, 学者们在BS和CRR模型基础之上, 发展了更为复杂的模型。在Merton (1976) [3]模型中, 股票价格不再服从几何正态分布。Hull和White[4] (1987) , Heston[5] (1993) 放宽股票波动率恒定的假设, 建立随机波动率模型。基于CRR模型, Milne, Madan和Shefrin[6] (1989) 发展了更一般的多叉树模型, 从而可以容纳更多类型的股票价格变化。韩立岩、郑承利[7] (2005) 基于非可加测度的模糊期权, 对市政债券发债规模控制进行了实证研究。韩立岩、周娟[8] (2007) 基于模糊测度的Choquet积分, 导出欧式无红利股票期权的定价公式;他们发现期权价格不是某个特定数值而是一个区间。李伟、韩立岩[9] (2009) 基于模糊二叉树模型, 也得到了类似结论。但是, Epstein和Schneider[10] (2008) 指出, 个体获得信息的质量对于资产定价有重要影响。这些模型虽然在不同的角度改进了BS模型和CRR模型的结论, 但是, 对在信息不完全下, 信息的获得以及信息的质量对期权价格的影响, 尚未做深入的研究。

本文基于CRR定价理论, 建立了不完全信息下的二叉树模型, 并使用一个含有限信息的信号 (下文简称有限信号) 来描述信息的不完全。在本文的模型中, 由于受市场上各种可能的冲击, 股票的波动率不能准确得到, 也不能直接观测;只能通过其他可以直接观测的信号对冲击进行估计。这个假设比较符合事实, 在实践中通常遵从如下方式确定波动率:先由历史数据得到波动率的估计值, 再对其进行适当地调整。本文模型通过一个反映冲击的有限信号作为调整项, 对信息在期权定价中的重要作用进行了分析。本文有如下贡献:第一, 在二叉树模型中加入不完全信息的有限信号, 从而研究了信息及其质量在期权定价中的重要作用, 也体现了定价中信息的获取与利用的重要性;第二, 在多期模型中, 本文不但研究了单信号, 也研究了多信号 (信号流) 对期权定价的影响;基于多信号的期权定价模型, 不但是单信号模型的推广, 也可以容纳广泛的波动率为随机变量的期权定价模型;第三, 本文发现在不完全信息下, 基于二叉树的期权价格不再唯一而是个区间;个体得到的有限信号的质量, 直接影响期权价格区间大小;即个体获得信息的准确性影响定价的准确程度。同时, 我们也发现, 本文的模型是经典CRR模型的推广。

本文第1节为引言, 主要介绍本文的研究背景和研究思路。第2节描述本文的模型设定。我们对不完全信息下的有限信号进行描述, 并在此基础上研究单期二叉树模型, 得到期权价格公式。在第3节, 基于单个信号, 把单期模型扩展到多期, 得到期权的价格区间, 并分析了影响价格区间的因素。第4节研究多信号的多期二叉树期权定价模型, 通过对多信号模型的转换最终求得期权的价格区间, 并对期权的上下界进行分析。第5节是结论。

2 单期二叉树模型

假设在t=0期, 股票的初始价格为S0.由CRR模型可知, 存在风险中性概率p, 使得在t=1期, 股价分别以p和1-p的概率变动至Su=S0u, Sd=S0d;并且有 $u = e^{v \sqrt{Δ t}} ‚ d = e^{- v \sqrt{Δ t}} ‚ p = \frac{r - d}{u - d}$ .其中, v为股票的波动率。为了表述简单, 设定Δt=1;由此可得u=ev, d=e-v.正如本文第1节所述, 因为市场上各种可能的冲击, 在实践中很难得到准确的股票波动率;对v通常的取值方式是以历史估计值为基础, 然后对其进行适当的调整。在本文中, 假设波动率v服从如下的表达式:

$v = \bar{v} + ε^{v} (1)$

其中, $\bar{v}$ 表示由历史数据估计出的波动率, εv～N (0, σ2v) 表示市场上各种冲击对波动率的综合效应, 也表示个体应当对 $\bar{v}$ 的调整量。由于市场的复杂性和信息不完全, 个体不能直接观察到εv, 只能观察到包含εv的信号:

$s = ε^{v} + ε^{s} (2)$

其中, εs～N (0, σ2s) 表示对信号本身的冲击。根据贝叶斯法则, 通过观察信号s可以推断 $E (ε^{v} | s) = \frac{σ_{v}^{2}}{σ_{v}^{2} + σ_{s}^{2}} s$ .因此, 得到调整后基于有限信号的波动率为:

$v = \bar{v} + \frac{σ_{v}^{2}}{σ_{v}^{2} + σ_{s}^{2}} s (3)$

假设在不完全信息下, 由于随机冲击εs, 个体也不能准确地观察到信号s, 而仅能以概率π1, π0, π-1分别观测到s的可能取值为1, 0, -1;其中π1+π0+π-1=1。换句话说, 个体仅能得到定性而非定量的信号。这是一个合理的假设。在复杂的市场条件下, 更容易得到是定性而非定量的信息, 个体实际能观察到是不完全信息的信号:s∈ (1, 0, -1) 。也因为信息的不完全, 个体不能得到准确的σ2s, 而只能得到一个区间 $σ_{s}^{2} \in [\underline{σ}_{s}^{2}, \bar{σ}_{s}^{2}]$ 。根据Epstein和Schneider[10] (2008) 可知, σ2s区间体现了信号的质量。 σ2s区间越大, 信号质量越差。

由以上分析易知, 假设在期初个体观察到有限信号s, 从而u, d, p与s和σ2s有关。为表述方便, 在不引起误解时省略记号σ2s, 把这种依赖关系简记为us, ds, ps.因此, 在t=1期, 有Su=S0us, Sd=S0ds.对于行权价格为K的欧式看涨期权, 可知Cu=max (S0ud-K, 0) 。为保持期权的吸引力并且简化模型, 假设S0us>K>S0ds, 可得Cu=S0ud-K.从而计算期初的期权价格为:

$\begin{array}{l} C_{0} (σ_{s}^{2}) \\ = \sum_{i = - 1, 0, 1} π_{i} \frac{1}{1 + r} C_{u} (σ_{s}^{2}, i) p_{i} (S_{0} u_{i} - Κ) \\ = \frac{1}{1 + r} \sum_{i = - 1, 0, 1} π_{i} p_{i} (S_{0} u_{i} - Κ) \end{array} (4)$

易知, 当 $σ_{s}^{2} \in [\underline{σ}_{s}^{2}, \bar{σ}_{s}^{2}]$ 变动时, 期初的期权价格也在一个区间中变动。因为个体观测到信号的信息不完全, 期权的价格不再唯一。

3 单信号多期二叉树模型

本节在前文不完全信息环境下, 有限信号设定的基础之上, 把模型推广到多期二叉树的情形。考察一种相对简单的单信号情形:信号只在期初出现一次。由CRR二叉树的定价模型可以知道, 在t=1期, S1, u=S0us, S1, d=S0ds; 在t=2期, S2, uu=S0usus, S2, ud=S0usds, S2, dd=S0dsds.一般地, 在第t期, St有t+1个可能的值:

$S_{t, i} = S_{0} u_{s}^{i} d_{s}^{t - i}, i = 0, 1, 2, \dots, t (5)$

取到St, i的概率为

$(\begin{array}{l} t \\ i \end{array}) p_{s}^{i} (1 - p_{s})^{t - i}$

.因此,

$\begin{array}{l} C_{t, i} (s) = \max (S_{0} u_{s}^{i} d_{s}^{t - i} - Κ, 0) ‚ \\ i = 0, 1, 2, \dots, t; t = 0, 1, 2, \dots, Τ (6) \end{array}$

其概率也为

$(\begin{array}{l} t \\ i \end{array}) p_{s}^{i} (1 - p_{s})^{t - i}$

.则对于续存期为T的期权, 可得期初的价格为:

$C_{0} (σ_{s}^{2}, s) = (\frac{Τ}{1 + r})^{Τ} \sum_{i = 0}^{Τ} (\begin{array}{l} Τ \\ i \end{array}) p_{s}^{i} (1 - p_{s})^{t - i} C_{Τ, i} (s) (7)$

进而得到最终期初的期权价格为:

$\begin{array}{l} C_{0} (σ_{s}^{2}) \\ = \sum_{j = - 1, 0, 1} π_{j} C_{0} (σ_{s}^{2}, j) \\ = (\frac{Τ}{1 + r})^{Τ} \sum_{j = - 1, 0, 1} [π_{j} \sum_{i = 0}^{Τ} (\begin{array}{l} Τ \\ i \end{array}) p_{j}^{i} (1 - p_{j})^{t - i} C_{Τ, i} (j)] (8) \end{array}$

因为信号s信息不完全, e2s∈[e2s, e2s], 因此期权价格C0 (e2s) 不唯一, 而是一个区间[min C0 (e2s) , max C0 (e2s) ]。下e2s e2s面分别估计期权价格的上下界。考察期权价格的下界:

由期权定价公式知, 期权价格是关于波动率v的增函数。因为当s=1时, 期权价格是e2s的减函数;当s=-1时, 期权价格是的增函数;当s=0时, 期权价格和e2s无关。因此, 式 (8) 可以写成其中,

类似地, 可以确定期权的价格上界为 $\max_{σ_{s}^{2}} C_{0} (σ_{s}^{2}) \leq \bar{C}_{0}$ .其中,

从而得到最终确定的期权价格区间为 $[\underline{C}, \bar{C}]$ 。

根据Epstein和Schneider[10] (2008) , $[\underline{σ}_{s}^{2}, \bar{σ}_{s}^{2}]$ 区间的大与小, 意味着信号质量的差与好。当 $\bar{σ}$ 2s不变, $\underline{σ}_{s}^{2}$ 变大, 由式 (9) 、式 (10) 可知, $\underline{C}_{0}$ 变大、 $\bar{C}$ 0变小;因此期权的价格区间变窄。类似地, 当 $\underline{σ}_{s}^{2}$ 不变, $\bar{σ}$ 2s变小, 由式 (9) 、式 (10) 可知, $\underline{C}_{0}$ 变大、 $\bar{C}$ 0变小;同样地, 期权的价格区间也变窄。从而可以得到这样一个结论:当 $[\underline{σ}_{s}^{2}, \bar{σ}_{s}^{2}]$ 区间变窄, 期权的价格区间也随之变窄。这表明, 信号的质量越高, 期权的定价就越准确。可见, 获得更充分的信息能对期权定价有着正面的效应。也易知, CRR模型是式 (8) 的一个特例。如果以概率1取得某个信号值, 式 (8) 即退化成标准的CRR期权定价公式。

4 多信号多期二叉树模型

本节建立基于多信号的多期二叉树模型。与基于单信号多期二叉树模型不同的是, 在多信号模型中, 个体不仅能在期初获得信号, 而且在多叉树的每一期也能观测到信号s.因此, 在多信号的多期二叉树模型中, 个体实际获得的是一条信号流。由二叉树模型可知, 在任意的第t-1期, 可以得到如图1所示, 以t-1期某节点St-1为起点的部分二叉树片段。

在任意的第t-1期, 个体都以概率π1、π0、π-1观测到可能值为1、0、-1的有限信号s.如图1所示, 对于每个可能的信号值s, 第t期股票价格为St, u=St-1us, St, d=St-1ds.考虑s的不同可能值, 对于给定St-1, 其后续的可能节点共有6种 (图1中仅仅具体描绘了s=0时的情况) 。根据单期的二叉树模型, 可以得到在t-1期, 在此节点St-1上对应的期权价格为:

其中, qi=1-pi, i=-1, 0, 1; Ctui=max (St-1us-K, 0) , Ctdi=max (St-1ds-K, 0) 分别表示在给定信号值s下, 二叉树第t期的上枝和下枝的期权值。整理式 (12) , 得:

容易知道, $\sum_{i = - 1, 0, 1} (π_{i} p_{i} + π_{i} q_{i}) = 1$ 。考察式 (13) 可知, 这实际上等价于一个六叉树期权定价模型。重新标记πipi, πiqi, ui, di;即标记 $\hat{p}_{1} = π_{1} p_{1} ‚ \hat{p}_{2} = π_{1} q_{1} ‚ \hat{p}_{3} = π_{0} p_{0} ‚ \hat{p}_{4} = π_{0} q_{0} ‚ \hat{p}_{5} = π_{- 1} p_{- 1} ‚ \hat{p}_{6} = π_{- 1} q_{- 1} ‚ \hat{u}_{1} = u_{1} ‚ \hat{u}_{2} = d_{1} ‚ \hat{u}_{3} = u_{0} ‚ \hat{u}_{4} = d_{0} ‚ \hat{u}_{5} = u_{- 1} ‚ \hat{u}_{6} = d_{- 1}$ ;多信号的多期二叉树模型可以转化成如图2所示的六叉树期权定价模型。

根据Madan, Milne和Shefrin[6] (1989) 多叉树的期权定价公式 (其论文的定理1) , 得到基于多个有限信号s, 初始价格为S0, 行权价格为K, 期权续存期为T的多期二叉树看涨期权的价格公式为:

其中, A={n|n= (n1, n2, …, n6) , ni≥0, 整数, 且 $\sum_{i = 1}^{6} n_{i} = Τ, S_{0} \prod_{j = 1}^{6} \hat{u}_{j}^{n_{j}} > Κ}$ 。

和单期二叉模型以及单信号的多期二叉树模型一样, 信号s信息不完全, 式 (14) 也得到一个区间 $[\min_{σ_{s}^{2}} C_{0} (σ_{s}^{2}), \max_{σ_{s}^{2}} C_{0} (σ_{s}^{2})]$ 。下面具体考察这种情况下期权价格的上下界。

与单信号模型不同, 在多信号的情况下, 不能直接根据σ2s的取值来具体确定期权价格的上下界。从单信号模型上下界确定的过程中可以发现, 如果直接根据σ2s确定价格上下界, 需要知道信号s的所有可能取值。在多信号T期二叉树模型中, 不只存在一个s, 而是存在由T个s所构成的有限信号流。这样多的可能组合使得直接根据σ2s来具体确定期权价格上下界变得困难。但是可以根据σ2s来间接确定期权价格上下界。由期权定价理论可知, 对于任何的σ2s, 都可以确定一个隐含波动率 $\hat{v}$ (σ2s) ;事实上, σ2s对期权价格的效应可以看成是先通过影响隐含波动率, 进而影响期权价格。因此, 可以把C0 (σ2s) 写成参数为隐含波动率的形式C0 ( $\hat{v}$ (σ2s) ) , 并且期权价格是关于隐含波动率 $\hat{v}$ 的增函数。根据Madan, Milne和Shefrin[6] (1989) 引理A2可知, 当多叉树模型趋向无穷期时, 期权定价公式的隐含波动率即为期初的股票波动率。根据本文有限信号s的设定以及等式 (3) , 可得到期初波动率的估计值为:

因为C0 ( $\hat{v}$ (σ2s) ) 是关于 $\hat{v}$ 的增函数, 根据式 (15) 从以下三种情形讨论多信号多期二叉树期权价格上下界限的性质。①当π1-π-1=0时, 期权的价格与σ2s无关。②当π1-π-1>0时, $\min_{σ_{s}^{2}} C_{0} (σ_{s}^{2}) = C_{0}^{\hat{v}} (\hat{v} (\bar{σ}_{s}^{2})), \max_{σ_{s}^{2}} C_{0} (σ_{s}^{2}) = C_{0}^{\hat{v}} (\hat{v} (\underline{σ}_{s}^{2}))$ ;当 $\bar{σ}$ s不变, $\underline{σ}_{s}$ 变大时, $\max_{σ_{s}^{2}} C_{0} (σ_{s}^{2})$ 变小, 期权价格区间变窄;当 $\underline{σ}_{s}$ 不变, $\bar{σ}$ s变小时, $\min_{σ_{s}^{2}} C_{0} (σ_{s}^{2})$ 变大, 同样地, 期权价格区间变小。③当π1-π-1<0时, $\min_{σ_{s}^{2}} C_{0} (σ_{s}^{2}) = C_{0}^{\hat{v}} (\hat{v} (\underline{σ}_{s}^{2})), \max_{σ_{s}^{2}} C_{0} (σ_{s}^{2}) = C_{0}^{\hat{v}} (\hat{v} (\bar{σ}_{s}^{2}))$ ;当 $\bar{σ}$ s不变, $\underline{σ}_{s}$ 变大时, $\min_{σ_{s}^{2}} C_{0} (σ_{s}^{2})$ 变大, 期权价格变窄;当 $\underline{σ}_{s}$ 不变, $\bar{σ}$ s变小时, $\max_{σ_{s}^{2}} C_{0} (σ_{s}^{2})$ 变小, 期权价格也变窄。综合①、②和③可得如下结论:当 $[\underline{σ}_{s}^{2}, \bar{σ}_{s}^{2}]$ 变窄时, 即有限信号s质量提高时, 期权的价格区间不会变得更宽;除去π1-π-1=0这种特殊情况, 更高质量的信号意味着更狭窄的期权价格区间, 也意味着可以对期权进行更准确的定价。

比较单信号的多期二叉树模型和多信号的多期二叉树模型, 可以发现前者是后者的特例。当多信号流各期都取的相同信号值时, 多信号的多期二叉树模型退化成单信号的多期二叉树模型。因为单信号的多期二叉树模型是CRR模型的推广, 从而多信号的多期二叉树模型也是CRR模型的进一步拓展。考虑不同组合的多期有限信号流, 多信号模型可以包含各种形态变化的波动率模型。进一步地, 因为每一期信号的取值都是随机的, 意味着在各期波动率可以发生随机变化;从而多信号模型可以描述波动率为随机变量的模型。因此, 多信号多期二叉树模型可以容纳众多波动率不确定的期权模型。

5 结论

金融市场上存在着诸多不确定性因素, 也存在着来自金融市场内外的各种冲击。这些因素都导致了经典CRR二叉树模型的理想条件不再满足。在信息不完全下, 由于受到各种难以直接观测冲击的干扰, 股票波动率的获取变得困难, 从而经常导致期权理论价格和实际价格存在明显偏差。

本文基于二叉树模型, 通过引入在一定程度上反应各种冲击的不完全信息信号 (本文称之为有限信号) , 建立了不完全信息下的二叉树模型。本文发现在不完全信息下, 基于二叉树的期权价格不再唯一而是一个区间。本文展示了信息的获取、信息的质量对期权价格区间的影响, 体现了信息在资产定价中的重要性。本文发现, 更高质量的信号, 使期权价格区间变窄, 从而提高了期权定价的准确性。

本文分析的单信号多期二叉树模型与多信号多期二叉树模型, 都是经典CRR二叉树模型的推广。基于多信号的期权定价模型, 不但是单信号模型的推广, 也可以容纳更广泛的波动率为随机变量的期权定价模型。因此, 本文分析的多信号多期二叉树模型, 可以作为各类变动波动率、波动率未知期权的一般定价方式。

摘要：由于信息不完全和市场冲击, 经典期权定价理论的股票波动率不能准确得到, 从而导致期权的理论价格和实际价格出现偏差。本文假设可以通过相关的有限信息信号对波动率进行推断, 基于二叉树框架对欧式看涨期权进行定价, 得到了不完全信息下期权价格的定价区间, 并研究了影响期权价格上下界的因素。通过对单期模型和多期模型、单信号和多信号模型的分析表明, 信息质量的提高使得定价区间变小, 从而提高定价的准确性。本文的模型也能包容波动率为随机变量的期权模型, 是经典二叉树模型的推广。

关键词：期权定价,二叉树模型,有限信号,多叉树模型,不完全信息,风险中性

参考文献

[1]Black F, Scholes M.The valuation of option andcorporate liabilities[J].Journal of PoliticalEconomy, 1973, 81:637~654.

[2]Cox J C, Ross S A, Rubinstein M.Option pricing:A simplified approach[J].Journal of FinancialEconomics, 1979, 7 (3) :229~263.

[3]Merton R C.Option pricing when underlying stockreturns are discontinuous[J].Journal of FinancialEconomics, 1976, 3:125~144.

[4]Hull J, White A.The pricing of options on assetswith stochastic volatilities[J].Journal of Finance, 1987, 42:281~300.

[5]Heston S L.A close-form solution for option withstochastic volatility with applications to bond andcurrency options[J].The Review of FinancialStudies, 1993, 6:327~343.

[6]Milne F, Madan D, Shefrin H.The multinomialoption pricing model and its Brownian and Poissonlimits[J].The Review of Financial Studies, 1989, 2:251~265.

[7]Han L Y, Zheng C L.Fuzzy options withapplication to default risk analysis for municipalbonds in China[J].Nonlinear Analysis, Theoryand Methods, 2005, 63:2353~2365.

[8]韩立岩, 周娟.Knight不确定环境下基于模糊测度的期权定价模型[J].系统工程理论与实践, 2007, 12:123~132.

[9]李伟, 韩立岩.Knight不确定条件下的模糊二叉树期权定价模型[J].中国管理科学, 2009, 12:9~16.

[10]Epstein L G, Schneider M.Ambiguity, information quality, and asset pricing[J].TheJournal of Finance, 2008, (February) :197~228.

完全二叉树篇2

三维场景中物体的真实感模拟是计算机图形学的主要任务之一。其中,柔性物体,如:布料、毛发、肌肉等,在外力的作用下会产生形变。随着计算机软硬件能力的提升,对计算能力要求更高的物理模型得以广泛应用,从而达到更真实的模拟效果。

在物理模拟仿真过程中,系统的一个重要任务就是在第一时间检测到正在发生的碰撞——碰撞检测,并相应做出正确的处理——碰撞响应。相对于刚体模型,柔性物体的碰撞检测与响应的计算代价更为高昂。柔性物体一般使用大规模的三角面片进行表达,而这些三角形在外力作用下形变,存在大量相互碰撞的可能,因此,柔性物体的碰撞检测处理除了继承了刚体碰撞检测的任务,还增加了更为复杂的自碰撞检测任务,对计算的要求更高。在超过10K的三角面片的复杂场景中,碰撞检测是主要的计算瓶颈。

基于层次包围盒BVH(bounding volume hierarchy)的查询数据结构是一种有效的用于碰撞检测的加速结构。BVH将场景中的物体对象模型在多个层次上划分成不同粗细粒度的包围盒,并且自上而下,由粗向细地构建成一棵树形结构。BVH利用了模型的空间相关性有效降低了碰撞检测查询的复杂度,使得物理模拟的规模得以进一步提高。然而基于BVH的碰撞检测查询的计算量仍然很大,是物理仿真过程中最为耗时的一个阶段。

另一方面,由于计算机硬件领域取得了迅猛发展,CPU的计算能力不断增强,且同时向多核发展。与此同时,面向通用并行计算的众核GPU技术逐渐成熟,越来越多的计算任务被分配到GPU上并行计算,并取得了理想的加速比。利用GPU的并行计算能力是物理模拟仿真系统的一个理想方案:GPU是数据的处理者,同时也是直接消费者,从而避免了多个数据传输的环节,进一步体现了GPU的计算优势。

本文的目标是设计并实现更高效且内存友好的BVH构建、遍历以及在此之上的碰撞检测算法,并将相应算法并行化在GPU上实现。本文将利用这些算法,实现复杂场景中布料类柔性物体的碰撞检测与物理模拟。

1 相关工作

1.1 柔性物体动力学建模

柔性物体的动力学建模包括物体在场景中的组织方式和在仿真环境中受内外作用力后的动力学特征的建立两个方面。文献[1] 的综述性文章总结了在织物建模方面的主要方法与成果。其中,文献[2]提出的基于物理弹性变形模型开创了织物建模的新领域,之前大部分方法都建立在几何模型上,而几何模型因难以表达复杂的、特别是产生碰撞的场景,而逐渐弃用。

文献[3]提出的隐式迭代方法正是基于物理的弹性变形模型。模型认为柔性物体的变换遵循牛顿力学以及弹性力学原理,将对物体质点的运动模拟转化为求解涉及时间、受力、速度的微分方程,进行矩阵方程求解。而当前仿真应用中使用最广泛的模型是文献[4,5]提出的弹簧-质点模型以及在此之上的显式迭代方法。

1.2 包围盒及其层次结构

包围盒以及由包围盒构成的层次结构被证明是用于碰撞检测的最有效的数据结构。从刚体的碰撞检测开始,BVH就被作为基本而重要的工具来运用。

BVH结构仅是一个算法框架,其中涉及多个子问题,包括:① 包围盒类型的选取;② BVH的构造;③ BVH的遍历;④ BVH的更新;⑤ 碰撞与自碰撞的策略等。文献[6,7]的综述中详细讨论了包括BVH在内的大部分问题。

1.3 碰撞与自碰撞检测

在快速碰撞与自碰撞检测算法设计上,研究者们已经做了大量的工作。文献[8]指出制约织物碰撞检测速度的几个主要方面:① 基本图元,即三角形对的碰撞检测的计算量大,若采用连续碰撞检测的策略,每次检测都将转化为对15组一元三次方程的求解;② 碰撞剔除效率低,即假阳性问题,因此在BVH上加入有效的剔除算法是提高检测效率的关键之一。文献[9]提出了一种基于表面规则性的自碰撞剔除策略,该方法在BVH结构的基础上增加了法向锥和轮廓线信息,以此为判定条件,取得了显著的效率提升;③ 自碰撞检测数量巨大,以织物模拟为例,自碰撞检测任务占全部碰撞检测工作的70%-90%,是亟待优化的重点。

1.4 并行化碰撞检测

近年来随着并行化硬件的成熟,在模拟系统特别是碰撞检测问题上,研究者们从不同的并行粒度到不同的并行化硬件设备,给出了一些有效的解决方案。文献[10,11]提出了一种图像空间碰撞检测算法,利用众核GPU的深度缓存测试加速计算。文献[12,13]提出了多核CPU上基于SIMD指令的指令级并行k-DOP包围盒重叠测试以及基于BVTT前线技术的任务级并行碰撞检测算法。文献[14]则使用了CPU与GPU的混合算法对碰撞检测进行加速。

2 模拟系统概述

物理模拟仿真系统在框架设计与实现细节上涉及多方面的取舍考虑,下面以本文工作为例阐述一个仿真系统的整体结构与重点内容。

图1描述了物理模拟仿真系统的工作流程,包含预处理、模型仿真、后处理三个阶段。

1) 预处理阶段

预处理阶段需要完成所有的初始化任务,包括计算资源与存储资源的分配、数据结构的建立、模型中各个参数的设置等。

系统会对场景中每个物体的三角格网构造对应的BVH,这是预处理阶段较为重要且计算量较大的任务,也是本文关注的重点之一。

2) 模型仿真阶段

图2详细描述了仿真阶段的主要任务,分为动力学模拟与碰撞检测两个部分。

动力学模拟即运用牛顿运动力学与弹性力学的基本性质,依次更新受力、速度、位置数据,再进行弹簧调整约束,以时间步长Δtd进行n次迭代。显式迭代计算量较小,在系统过程中占用时间短。同时,由于显式迭代的数据独立性,很适合使用众核GPU进行并行运算。由于精度与数值稳定性的问题,显式迭代的时间步长一般设置得较小,在一次场景模拟中多次迭代。文献[15]提出的经验结论指出,为了保证仿真的精确性,在每个时间步长内,弹簧的形变程度不应超过10%。较小的时间步长可以减少弹簧形变超过10%的情况,此外本文运用了文献[4]提出的方法,对整个网格中的弹簧进行检查和必要的调整,保证了仿真的精确性。

碰撞检测阶段的任务包括BVH更新操作,碰撞检测与处理操作。该阶段需对BVH索引树进行遍历,对模型顶点数据进行空间位置和运动状态的判断以及对检测出的碰撞对进行空间位置修正,避免碰撞发生。碰撞检测是系统中复杂度最高、工作量最大的任务。

3) 后处理阶段

后处理阶段的任务是释放系统申请的空间,以及对计算资源的回收。特别是在运用到GPU设备的情况下,预处理与后处理的任务更多一些。

3 完全二叉树BVH

基于BVH在碰撞检测中的有效和广泛使用,本文工作也围绕着BVH展开。本节将给出一种使用连续空间表达的、结构上为完全二叉树的BVH,并从构建、遍历更新、碰撞检测几个方面针对这种BVH的特点进行描述。

3.1 连续空间的二叉树存储

文献[15]指出,在运用BVH进行碰撞检测查询操作时,若采用“同时下降”规则,树的度数为2时有最优效率。同时,考虑到二叉树的表达方便,构造时的分裂、合并操作简单,本文工作也采用了二叉树BVH。

相对于一般二叉树而言,我们选择了完全二叉树作为BVH的底层结构。对任意一棵完全二叉树,可以采取逐层遍历的顺序,使用连续空间存储整个树结构。这种组织方式的好处包括:

1) 节省存储空间

使用连续空间表达的完全二叉树隐含着结点链接关系。通过下标值(偏移量)索引的一个结点,其父结点、兄弟结点、左右孩子结点都可通过简单计算获得。与链式表达的树相比,不需要显式存储指针数据;与用连续空间表达的一般二叉树相比,不存在无效结点空间。

2) 内存更友好

完全二叉树的连续存储具有“关联数据存储位置接近”的特点,并具有平衡树的性质,是一种更为友好的存储方式,在多种遍历方式下都有更好的性能。此外,这种简单的表达适合GPU的存储方式,易于实现并行算法。

3.2 BVH构造

BVH树的叶子结点对应于三角网格的单个面片,内部结点对应于子树构成的面片区域。因此对于一个基于完全二叉树的BVH,若对应模型有n个三角面片,那么这棵树的叶子结点有n个,内部结点n-1个,共2n-1个结点,BVH结构即为长度为2n-1个结点数据的连续空间T[0:2n-1]。

因此,BVH构造问题转换为将这n个面片一一对应到连续空间中的后n个结点空间,即空间T[n-1:2n-1]的问题。这里我们采用自顶向下、逐层递归地分为左右两组的方式调整面片顺序,使得最后的面片能够从左向右地对应完全树的叶子结点。

该问题的难点在于:当前BVH的建立方法,不管是自底向上还是自顶向下的分离轴中点、中位数等方式,都无法保证得到的是完全二叉树,例如图3给出的11个叶子结点二叉树的例子。本文使用一个结点划分规则(LeafDivide)指导结点自顶向下划分,同时利用一种高效取第k位数并调整的算法(RandomizedSelect)[16],保证在0(NlogN)的时间复杂度下建立完全二叉树的BVH(算法LeafArrange)。

算法RandomizedSelect在选定的分离轴上选择并调整代表三角面片的顶点序列pt,使得区间[begin,mid)与[mid,end)内的三角面片在空间上分离。该算法类似快速排序中的分割操作,使用随机枢轴元素的方式移动分割元素,不同的是该算法最多递归调用自身一次。该算法的渐进时间复杂度为O(N)。

算法1 子树结点划分

算法LeafArrange完成了面片与BVH树叶子结点的关系映射,即BVH的构造过程。

算法2 完全二叉树BVH构建:面片-叶子结点映射

3.3 BVH更新

BVH的更新主要有两种方式:包围盒修整(Refit)和BVH重建(Rebuild)[17]。本文使用包围盒修整的方式更新BVH。连续空间完全二叉树BVH的包围盒修整更新操作,因为自身的结构特征,有简洁高效的解决方案。

包围盒修整的BVH更新方式采用自底向上,由叶子结点到根节点的顺序逐步更新。基本规则是:叶子结点首先更新,中间结点等两个孩子结点都更新后,再进行更新。由于连续空间的完全二叉树BVH,对于任意一个中间结点,其左右孩子结点的偏移量都大于自身的偏移量。那么,仅需要对整个包围盒顺序结构进行从后向前依次遍历,即可修整包围盒。

这种BVH更新策略实现简单,无需一般树结构(后序)遍历时的辅助栈空间。并且这种更新可以逐层同时进行,是一种适合并行的算法。

算法3给出了本文提出的完全二叉树BVH结构中结点包围盒数据的更新算法伪代码。该伪代码是基于OpenCL C在GPU上的并行实现。除了结点包围盒数据的更新,BVH更新操作往往还包含其他辅助数据结构的更新。这些数据依附于BVH结点存在,例如法向锥数据、面片拓扑信息。因此处理的方法与算法3在结构上类似,这里不再赘述。

算法3 完全二叉树BVH更新:伪代码基于OpenCL C在GPU上的实现

3.4 碰撞检测

本文的碰撞检测算法采用了26-DOP作为基本包围盒。k-DOP包围盒具有更紧密的拟合,并且构建、更新以及相交判断也相对简单快速。

对于两棵不同BVH树(子树)的碰撞检测,采用包围盒层次“同时下降”规则(Klosowski[15]),保证测试的包围盒大小接近,并且对于二叉树有更好的性能;对于单个内部结点的自碰撞检测,采用了文献[9]提出的基于表面规则性的剔除算法,采用法向锥附加到BVH结点数据中,进行表面规则性判断。

在具体的系统实现中,我们采用了文献[13]提出的GPU上的碰撞检测并行算法,该算法采用了“前线”技术,使得任务能够有效分解,从而利用了众核GPU的计算能力。

4 实验与评价

本文实验主要针对提出的BVH构造、更新算法,在实现的仿真系统(如图4所示)上进行效果对比实验。实验采用了两组数据,如图5所示,分别是Cloth on sphere模型和Dragon模型。实验环境分别为Windows XP,2.5GHz CPU和Windows 7,3.2GHz CPU,对于GPU并行算法实验,采用显卡ATI HD 6870。

图5比较了采用本文提出的BVH构建算法(绿色)与使用均值划分(红色)和中值划分(蓝色)的链式BVH构建算法的时间效率。前者因为存储空间的完整一次性开辟,相比后两者的频繁动态空间申请,有较高的效率。此外,我们观察到,动态空间开辟的效率在不同系统上表现不一。如均值划分策略在Win7, 3.2G环境下时间效率更高,尽管使用了链式二叉树。

图6比较了三种BVH更新算法的时间效率。由于本文提出的BVH遍历实质是线性空间的遍历,优于链式二叉树的遍历过程。实验还给出了本文提出的BVH更新算法在GPU上实现的结果,达到了近三倍的加速比。

图7是应用本文的仿真系统模拟Cloth on sphere场景的动画截图。在该场景中,一块布料织物自由落体在一个球体上方,并与之相互作用,本文的实现取得了理想的仿真效果。Cloth on sphere场景多被用于对柔性物体的物理模拟与碰撞检测系统进行算法效率与模拟质量的测试。

5 结语

本文提出了基于完全二叉树的层次包围盒结构。该结构相对简单,支持高效的BVH构建、更新以及碰撞检测操作。通过分析以及实验证明,该结构在本文实现的柔性物体模拟仿真系统中取得了良好效果。

未来工作主要包含两个方面:① 完善仿真系统,实现完整的GPU并行方案;② 设计实现更优的自碰撞剔除算法。

二叉树的遍历算法篇3

关键词：二叉树,遍历,满二叉树,完全二叉树

1二叉树

二叉树是由n (n≥0) 个结点组成的有限集合, n=0时称为空二叉树; n>0的二叉树由一个根结点和两棵互不相交的、分别称为左子树和右子树的子二叉树构成。可见二叉树是递归定义的。二叉树的结点最多只有两棵子树。因此二叉树的度最多为2。二叉树的子树有左右之分, 即使只有一棵子树也要区分左子树还是右子树。

一棵高度为h的满二叉树是具有2h-1 (h≥0) 个结点的二叉树。满二叉树中每一层的结点数目都达到最大值。对满二叉树的结点按照从根结点开始、自上层而下层、每层自左而右进行编号, 约定根结点编号为0, 则可以得到一个有序序列。对于一棵高度为h的二叉树, 如果它的每个结点都与高度为h的满二叉树序号为0~n-1的结点一一对应, 则称这棵二叉树为完全二叉树。满二叉树是完全二叉树, 而完全二叉树不一定是满二叉树。完全二叉树的第1~h-1层是满二叉树, 并且该层所有结点都必须集中在该层左边的若干位置上。如图1所示。

二叉树的遍历是按照一定规则和次序访问二叉树中的所有结点, 并且每个结点仅被访问一次。虽然二叉树是非线性结构, 但遍历二叉树访问结点的次序是线性的, 而且访问的规则和次序不止一种。二叉树的遍历规则有孩子优先和兄弟优先。

1.1孩子优先的遍历规则

假设有一棵由A、B、C 3个元素构成的二叉树: A为根结点、B为左孩子、C为右孩子, 对其遍历可得到所有的序列有: ABC、BAC、BCA、CBA、CAB、ACB。可以发现, 后3个序列分别与前3个序列的次序相反, 并且前3个序列的共同特点是, B在C之前, 即先遍历左子树还是右子树在算法设计上没有本质区别, 因此约定遍历子树的次序是先左后右, 则二叉树孩子优先的遍历有3种次序, 分别称为先根次序、中根次序和后根次序。规则如下:

(1)先根次序: 访问根结点, 遍历左子树, 遍历右子树;

(2)中根次序: 访问左子树, 遍历根结点, 遍历右子树;

(3)后根次序: 访问左子树, 遍历右子树, 遍历根结点。

二叉树的遍历过程是递归的。如图2所示的一棵二叉树的3种遍历序列为 : 先根次序ABDGCEFH、中根次序DGBAECHF、后根次序GDBEHFCA。由此可知 , 先根次序遍历最先访问根结点; 后根次序遍历最后根结点; 中根次序遍历左子树上的结点在根结点之前访问, 右子树上的结点在根结点之后访问。

将一个中缀表达式 (a+b) ×c-d/e表示为一棵表达式二叉树, 两个操作数分别为运算符结点的左、右孩子结点, 运算符都是分支结点, 操作数都是叶子结点, 则按照后根次序遍历可得到后缀表达式ab+c×de/-。

1.2兄弟优先的遍历原则

二叉树的层次遍历是按照层次次序进行的。遍历过程是从根结点开始, 逐层深入, 从左至右依次访问完当前层的所有结点, 再访问下一层。如图2 (a) 所示的二叉树的层次遍历序列为: ABCDEFGH。这种遍历的特点是兄弟优先。

2二叉树的存储结构

如果将一棵完全二叉树的所有结点按照序号进行顺序存储, 根据二叉树的性质, 由结点序号i可知其父母结点、左孩子结点和右孩子结点的序号。将完全二叉树的结点按照次序进行编号, 实际上是对完全二叉树的一次层次遍历。与非完全二叉树的层次遍历不同, 完全二叉树在按层次遍历到最后一个结点之前不会遇到空子树。如果对非完全二叉树进行顺序存储, 有以下两种办法: 其一, 仅仅存储结点, 则结点顺序存储的线性关系不能反映二叉树中的结点间的层次关系; 其二, 通过补充空子树的方式将一棵非完全二叉树变成完全二叉树的方式, 则不仅浪费存储空间, 而且线性映射关系也不明确, 也不可行。

因此, 二叉树的顺序存储结构仅适用于完全二叉树和满二叉树。二叉树主要采用链式存储结构。每个结点至少要有两条链分别连接左、右孩子结点, 才能表达二叉树的层次关系。

采用二叉链表结构的每个结点有3个域: data数据域、left左孩子结点、right右孩子结点。一棵有n个结点的二叉树及其二叉链表存储结构如图3所示, 其中root指向二叉树的根结点。采用二叉链表存储二叉树, 设p指向其中一个结点, 则p.left、p.right分别指向其左、右孩子结点 , 每个结点到达其孩子结点所花费的时间是O (1), 这种方式只存储了结点到孩子结点的单向关系, 没有存储结点到父母结点的关系。因此, 要获得父母结点将花费较多时间, 需要从根结点开始在二叉树中进行查找。

为了解决二叉链表存储的二叉树操作效率问题, 可在二叉链表的基础上采用三叉链表结构, 即增加一条链parent连接父母结点。这样三叉链表存储了父母结点与孩子结点的双向关系。如图4所示。

后面的二叉树操作都基于二叉链表及Java语言。二叉树的操作主要有创建二叉树、获得父母或孩子结点、遍历、插入和删除等。描述二叉树抽象数据类型BinaryTTree接口定义如下。其中, 泛型T为结点的元素类型。

二叉树主要由二叉树结点类BinaryNode和二叉树类BinaryTree共同完成。BinaryNode的定义如下。

为了方便地更改结点间的链接关系, BinaryNode类声明中成员变量的访问权限定义为public, 允许其他类访问。否则, 要提供公有方法set、getData、getLeft、getRight等, 提供给其他类调用。

二叉树类BinaryTree及其部分成员方法声明如下, 其中成员变量root指向二叉树的根结点。

3二叉树的遍历

3.1递归遍历算法

作为遍历问题的基本点, 需要在BinaryTree类中增加先根次序、中根次序、后根次序遍历二叉树的成员方法。这3种遍历算法都是递归算法, 差别只是在于结点的访问时间不同。具体实现如下。

递归方法必须有参数, 通过不同的实际参数区别递归调用执行中的多个方法。一棵二叉树由多棵子树组成, 一个结点也是一棵子树的根。因此, 二叉树中实现遍历规则的递归方法以结点p为参数, 比如preOrder (p) 表示以先根次序遍历以p结点为根的子树, 当p指向不同结点时, 遍历不同的子树; 当p为空子树时, 递归结束。每个遍历算法都有两个重载。

3.2二叉树基本操作

基于二叉树遍历的基本操作有: 构建二叉树、求结点个数、求高度、查找、求父母结点、替换、插入、删除等。根据不同的应用需求, 可采用不同的次序进行遍历。

3.2.1 构造二叉树

由于二叉树是数据元素之间具有层次关系的非线性结构, 而且二叉树中每个结点的两棵子树有左右之分, 因此建立一棵二叉树必须明确两点: 结点与父母结点及孩子结点之间的层次关系; 兄弟结点之间的左右子树的次序关系。

二叉树的一种遍历序列将二叉树的非线性关系映射成一种线性关系。因此, 已知一棵二叉树可得到唯一的一组先根、中根和后根或层次遍历序列; 但是, 已知二叉树的一种遍历序列却不能唯一确定一棵二叉树。以下讨论两种能够唯一确定一棵二叉树的表示法。

3.2.1.1 先根和中根序列表示

由于先根次序或后根次序反映父母与孩子结点的层次关系, 中根次序反映兄弟结点间的左右次序。因此, 已知先根和中根两种遍历, 或中根和后根两种遍历序列, 能够唯一确定一棵二叉树。证明过程如下:

已知: 二叉树的先根和中根两种次序遍历序列, 可唯一确定一棵二叉树。

证明: 假设数组prelist和inlist分别表示一棵二叉树的先根和后根次序遍历序列。序列长度均为n。

(1)由先根次序遍历算法可知 , 该二叉树的根为prelist[0];该根结点必定在中根序列中 , 假设它在中根序列inlist中的位置为i, 则有inlist [i] =prelist [0]。

(2) 由中根次序遍历算法可知, inlist [i] 之前的结点在根的左子树上, inlist [i] 之后的结点在根的右子树上。因此, 根的左子树由i个结点组成, 子序列为:

左子树的先根序列: prelist [1] ,…,prelist [i]; 右子树的中根序列: inlist [0] ,…,inlist [i-1]。

根的右子树由n-i-1个结点组成, 子序列为:

右子树的先根序列: prelist [i+1] ,…,prelist [n-1]; 右子树的中根序列: inlist [i+1] ,…,inlist [n-1]。

(3)如此递归, 可唯一地确定一棵二叉树。

同理可证明: 中根与后根次序遍历可唯一地确定一棵二叉树; 先根和后根次序遍历序列不能唯一确定一棵二叉树; 同一个层次遍历序列不能唯一确定一棵二叉树。

上面的证明过程实际上描述了由先根和中根序列如何构造一棵二叉树的过程。在BinaryTree类中增加以下构造方法, 以先根和中根次序遍历序列构造二叉树。

3.2.1.2 标明空子树的先根序列表示

已知一棵二叉树的先根遍历序列为AB, 则能够确定A是根结点, 并且B是A的孩子结点, 但不能确定是哪个孩子, 可能是左孩子, 也可能是右孩子。这是因为先根序列只能反映父母与孩子结点之间的层次关系, 不能反映兄弟结点之间的左右次序。

如果在先根遍历次序中标明空子树, 通过空子树位置反映兄弟结点之间的左右次序, 则可唯一确定一棵二叉树。比如, 以 ^ 表示空子树, 则二叉树及其先根次序遍历序列如图2所示。

这种标明空子树的先根便利序列, 明确了二叉树中结点与父母、孩子以及兄弟结点之间的关系, 因此能够唯一地确定一棵二叉树。设prelist表示一棵已标明空子树的二叉树的先根次序遍历序列, 则构造二叉树的递归算法如下:

(1)prelist [0]一定是二叉树的根 , 创建根结点。并且prelist [1] 一定是根的左孩子。

(2)如果prelist [i] 不是空子树 , 则创建一个结点 , 该结点的左孩子结点元素时prelist [i+1], 但父母与孩子之间的链接还未建立; 否则, 当前子树为空, 返回上一层结点。

(3)返回到当前结点时, 下一个元素prelist [i+1] 是当前结点的右孩子结点; 当一个结点的左、右孩子的链接都已建立, 则以当前结点为根的一棵子树已经构建好, 返回上一层结点。

(4)重复执行步骤 (2)、 (3), 直到返回根结点, 则二叉树构建完毕, root指向根结点。

在BinaryTree类中增加以下构造方法, 以标明空子树的先根序列构造一棵二叉树。

其中, prelist数组保存标明空子树的先根序列, create(prelist)方法创建一棵子树 , 子树的根值是prelist [i] 。由于create(prelist)是递归方法, 参数按照层次关系变化, 而i是数组下标, 从0递增到preorder.length-1, 因此i不能作为方法的参数, 也不能作为方法的局部变量, 只能将它作为BinaryTree类的私有成员变量, 相对于create方法是全局变量。

3.2.2 求二叉树结点个数

在BinaryTree类中增加count方法, 返回一棵二叉树或子树的结点个数。

3.2.3 求二叉树高度

一棵二叉树的高度是其较高的一棵子树的高度加1。因此求二叉树的高度必须采用后根次序遍历算法, 首先分别计算出左、右子树的高度, 再计算以当前结点为根的子树高度。在BinaryTree类中增加height方法, 返回一棵二叉树或子树的高度。

3.2.4 查找

在BinaryTree类中增加search方法, 在一棵二叉树或子树中查找关键字为key的元素, 返回首次出现的关键字为key的元素结点。若未找到, 则返回null。该方法采用先根次序遍历算法在二叉树中查找。

3.2.5 获得父母结点

在BinaryTree类中增加getParent方法 , 返回指定结点node的父母结点。

3.2.6 插入结点

在二叉链表的二叉树中, 链的方向是单向的, 都是由结点指向其孩子结点, 没有指向其父母结点的链。与单链表的插入操作类似, 在二叉链表的二叉树中插入一个结点p, 需要修改p的父母结点的left或right域。因此 , 在二叉树中插入一个结点, 需要指定插入结点作为哪个结点的左孩子还是右孩子。在BinaryTree类中增加以下方法 : insertRoot (x) 方法插入元素x作为根结点 , 原根结点作为其左孩子 ; insertChild ( p,x, leftChild) 方法插入元素x作为p结点的孩子, p结点的原左/右孩子成为新结点的左/右孩子, leftChild指定左/右孩子, 取值为true (左孩子)、false (右孩子), 返回插入结点。

3.2.7 删除一棵子树

在二叉链表的二叉树中删除一个结点p或一棵子树, 需要修改p的父母结点的left或right域。如果只删除一个结点p而不是删除一棵子树, 则需要约定如何调整子树结构的规则。换言之, 若删除一个结点p, 原先以p结点为根的子树则变成由原左子树和右子树组成的森林, 约定一种规则使这个森林组成一棵子树。这里简化, 只讨论删除一棵子树问题。

在BinaryTree类中增加以下删除一棵二叉树或子树的方法:

3.2.8 叶子结点

在BinaryTree类中增加以下方法, 判断某个结点是否为叶子结点; 计算叶子结点的数量。

3.3二叉树的层次遍历

二叉树层次遍历的特点是兄弟优先。两个兄弟结点的访问次序是先左后右, 连续访问; 它们后代结点的访问次序是: 左兄弟的所有孩子一定在右兄弟的所有孩子之前访问, 左兄弟的后代结点一定在右兄弟的同层后代结点之前访问。

在BinaryTree类中增加以下二叉树的层次遍历算法, 其中使用链式队列存储二叉树结点BinaryNode。

3.4二叉树的非递归算法

二叉树电子家谱设计篇4

1 电子家谱系统简介

1.1 系统复杂性

李士勇认为复杂性是指系统在演化过程中和环境交互作用, 呈现出的复杂的动态行为特性和突出的整体特性。除此之外, 人们一般认为复杂系统是由众多存在复杂相互作用的组分 (或子系统) 组成的。家谱系统涉及众多子系统, 形成了规模庞大的多层次结构, 因此家谱系统具有多方面的复杂性。

1.2 系统结构

家谱是家族成员间相互联系组成一种体系结构。同家谱数据中由后代节点和父代节点分别组成家谱树的特点对应, 家谱系统通常采用树形结构。

2 二叉树家谱系统设计

2.1 家谱的体系结构

二叉树能够很好的反映家谱中成员之间的关系。本文系统中使用父子——兄弟结构, 即左子树第一个节点为父节点的儿子 (或兄弟) , 同理右子树第一节点表示父节点的兄弟 (或儿子) 。并且采用三叉链表的方式存储二叉树, 不仅便于对字节点进行查找, 还可以回溯查询关联节点确定成员间关系。

2.2 家谱成员及功能设计

2.2.1 数据单元设计

选定家族成员作为数据基本单元, 并在程序中定义为结构体Bi TNode。因为在一个家族中, 家谱中每个家族成员是最基本的组成部分。Bi TNode结构如下:

typedef struct Bi TNode{

标记、姓名、生日、住址、婚否、建在否、性别、妻子 (如已婚) 、死亡日期 (如已死亡) ;

struct Bi TNode*lc, *rc, *father;

}Bi TNode, *Bi Tree;

2.2.2 功能设计

系统设计了多种实用功能, 主要功能有:

3 设计实现的注意要点

建立树时, 由于新申请结点的孩子指针、兄弟指针等均未赋空值;但在函数中对树进行递归操作时均以这些指针值中的一个或几个是否为空作为递归结束条件。从而导致调用函数时出现系统保护异常 (使用了不安全的指针) 。因此在系统初始化时, 需要对以上几种属性赋予无影响初始值。

删除结点时, 只考虑到删除本身结点, 而其孩子结点的情况未考虑, 故在删除某些结点时会出现“断链”现象。故在删除某一结点时, 首先要判断此结点是否有孩子及兄弟, 然后进行相应操作。

4 结语

电子家谱系统是一种重要工具, 它使家谱得以充分保护和使用。笔者的二叉树电子家谱系统设计提高了家谱使用的实用性和易用性, 为家谱系统的电子信息化打下了一定基础。家谱电子信息化是一个庞大的系统工程, 今后我们将研究家谱便易搜索算法以及家谱成员流动模式。

参考文献

[1]王鹤鸣.中国家谱通论[M].上海:上海古籍出版社, 2010:4.

[2]司马贺.人工科学:复杂性面面观[M].上海:上海科技教育出版社, 2004:78-79.

[3]李士勇.非线性科学与复杂性科学[M].哈尔滨:哈尔滨工业大学出版社, 2006:23.

二叉树操作的递归算法分析篇5

二叉树是数据结构课程内容中的重点和难点,学好数据结构就必须要掌握二叉树的存储结构和基本操作的算法。二叉树最常用的存储结构是二叉链表,根据二叉链表的示意图,我们很容易理解二叉树的这种存储形式。因此,掌握二叉树的关键就是要理解二叉树基本操作的算法。本文将分析二叉树操作的递归求解方法,以求和数据结构爱好者共同学习和研究。

2 递归

递归是一种非常有用的算法设计工具。一个函数、过程如果在其定义或说明内部直接地或间接地出现有其本身的引用,这种用自己定义自己的方法称之为递归[1]。

递归方法实际上是将一个原问题转化为和原问题相同的子问题,只不过子问题的规模比原问题的规模要小。这种转换多次进行,直到满足某个约束条件为止。用递归方法求解问题关键就是要确定两方面内容:(1)子问题(2)递归结束条件。

例如:求n!

因此,可将原问题“求n!”转换为子问题“求(n-1)!”,原问题和子问题为同样的问题,都是求某数的阶乘,但子问题数字小。随着不断转换,子问题数字越来越小,当求1!时,可直接给出值1。所以,递归结束条件就是n=1。

3 二叉树操作的递归求解方法

二叉树的特点是每个结点至多只有两棵子树(左子树和右子树),且左右子树也是二叉树。因此,二叉树或者为空,或者可分为三部分:根结点、左子树、右子树。由于二叉树中的左子树和右子树也是二叉树,因此,二叉树的组成具有递归的特点,那么,二叉树的许多操作可考虑用递归方法来描述。下面将讨论几个常见二叉树操作的递归算法。

3.1 遍历二叉树

遍历二叉树是指按某条搜索路径巡访二叉树中的每个结点,使得每个结点均被访问一次,而且仅被访问一次[2]。常见的二叉树遍历方法有三种:先序遍历、中序遍历、后序遍历,下面以先序遍历为例,分析其递归算法。

先序遍历二叉树的思想是:若二叉树为空,则没有任何结点可访问,因此空操作;当二叉树不为空时,先序遍历二叉树就是要:访问根结点、先序遍历左子树、先序遍历右子树。采用递归方法分析:1)原问题为先序遍历二叉树。2)原问题可分为三步:访问根结点、先序遍历左子树和先序遍历右子树。访问根结点直接对应访问语句,例如输出语句。先序遍历左子树和先序遍历右子树这两个问题都属于先序遍历二叉树的问题,与原问题一样,只不过左子树和右子树比原二叉树规模要小。因此,子问题为先序遍历左子树和先序遍历右子树。3)递归结束条件就是二叉树为空。

确定递归算法的子问题和递归结束条件后,就可写出先序遍历的递归算法:

3.2 建立二叉树的二叉链表

建立二叉树的二叉链表存储结构是二叉树的必备操作,因为在程序中,只有创建了二叉树的二叉链表存储结构,才可以进行二叉树的其他操作。显然,二叉树中的每个结点对应二叉链表中的一个结点,因此,创建二叉链表,就是要为二叉树中的每个结点建立一个结点存储结构。可以按照某种遍历顺序依次为各个结点建立存储结构。若按照中序遍历顺序或后序遍历顺序建立,则在建立二叉链表过程中,已建立的结点是分散的、不能连接成一个链表,这就不易掌控所有已建立的结点。如果按先序遍历顺序建立,则已建立的结点都可链接在根指针所指的二叉链表中。因此,可按先序遍历的顺序为各个结点建立存储结构。

建立二叉树的二叉链表的算法思想是:若二叉树为空树,则根指针应设置为空;若二叉树非空,则为根结点建立存储结构,再建立左子树的二叉链表和右子树的二叉链表。采用递归方法分析:1)原问题为建立二叉树的二叉链表。2)子问题为建立左子树的二叉链表和建立右子树的二叉链表。3)递归结束条件是二叉树为空树。

根据用户输入的序列,建立二叉树的二叉链表的递归算法如下:

使用此算法建立二叉树的二叉链表,用户在输入结点序列时要注意:空子树也要输入,用空格代表空子树。例如图1所示二叉树,应首先标出空子树,见图2,然后对其先序遍历得到输入序列:AB__CD__E__。

3.3 求二叉树的深度

二叉树深度可按如下规则求取:当二叉树为空树,则深度为0;当二叉树只有一个结点,则深度为1;否则,二叉树的深度为左子树深度和右子树深度中的较大值,再加上1。采用递归方法分析:1)原问题为求二叉树的深度。2)子问题为:求左子树深度和求右子树深度。3)递归结束条件是二叉树为空或者二叉树只含有一个结点。根据上面分析,可得到如下递归算法:

3.4 返回结点e的左兄弟

采用递归方法分析:1)原问题为在一棵二叉树中找结点e的左兄弟。2)子问题可设定为在左子树中找结点e的左兄弟,和在右子树中找结点e的左兄弟。3)递归结束条件可有两种情况:a)若二叉树为空树,则结点e的左兄弟不存在;b)若根结点的右孩子为结点e,则结点e的左兄弟为根结点的左孩子。递归算法如下:

4 总结

二叉树是数据结构课程中的重要内容,掌握二叉树关键是掌握二叉树各种操作的算法。本文采用递归方法分析了二叉树的先序遍历、创建二叉链表、求深度、求结点e的左兄弟这四个操作的求解方法。对于二叉树的许多其他操作,也可以与此类似,采用递归方法求解。

摘要：二叉树是数据结构课程中的重点内容。由于二叉树本身具有递归的特点,因此二叉树的许多操作可采用递归方法求解。该文首先介绍了递归方法,然后采用递归方法分析二叉树的几个常见操作,并给出详细算法。

关键词：递归,二叉树,遍历,算法

参考文献

[1]李伟.浅析C语言递归算法[J].电脑知识与技术,2012(10).

二叉树结构的文本模式显示篇6

检查二叉树结果可以通过输出二叉树的遍历结果来进行,尤其是层序遍历[2];也可以在集成开发环境中通过监视(Watch)追踪左右子树,这不直观也非常繁琐。图形显示二叉树是比较直观和形象的[3],因此在教学中可以采用图形显示[4,5],比如图1;但是它的缺点也很明显,要求学生掌握一定的图形编程,而不少学生在学习数据结构的时候图形编程基础比较弱,因此教与学往往是在命令行的方式下进行输出,即通过printf或cout进行输出(C/C++语言),所以采用图形输出进行数据结构教学有一定的局限性。

叶品菊等开发了在文本方式下显示二叉树的方法[2],该方法用层序进行输出,每一层输出在一行中,但该方法父结点与子结点之间没有任何东西相连(如图2),因而输出的图形不像一颗树,而是结点的有规律的排列,显示的直观性略差。任燕在其编著的教材《数据结构C++语言描述》[6]中,二叉树的示例图是屏幕截图的,从图中可以看出它利用’_’、’/’和’’三种特殊字符把子结点和父结点连接起来,显示效果非常直观与形象,与图形模式下的显示方式基本相同,只是链式存储二叉树需要转换成顺序存储二叉树,“以便使链式存储二叉树能以树状形式显示”[6]。该文给出了一种文本模式的二叉树结构显示方法,该方法利用’_’、’/’和’’三种特殊字符把子结点和父结点连接起来,使用队列对链式存储二叉树进行层序输出,该方法进行较小的改动可以应用于顺序存储二叉树的显示,加入特殊字符’|’经适当修改也可顺利地显示3阶B_树。由于该方法直观形象且是文本模式,因而可以作为数据结构教与学的有效手段之一。

1 显示方法

文本模式下的二叉树显示主要的是计算结点的输出位置,输出位置是由空格的多少来决定的,父结点与子结点之间的连接由三种特殊字符’_’、’/’和’’构成。倒数第一层和倒数第二层之间只需’/’和’’就可连接,左子树由’/’连接,右子树由’’连接。其它层数之间的结点连接由两行构成,第一行连接线由一个或多个’_’与’/’或’’构成,左子树的连接线形如“_____/”,右子树的连接线形如“_____”;第二行的连接只需’/’和’’,左子树是’/’,右子树是’’。其它非连接线位置由空格填充。为了让斜线(/或)指向结点位置,结点不在斜线(/或)的正下方(文献[6]是在正下方),而是偏一格,这样底层结点相邻3个空格,这样的显示效果比文献[6]中的显示效果更为自然和美观。输出的具体编排见图4。

为了计算空格的个数,需要知道二叉树的显示宽度。由于底层结点相隔3个空格,因此二叉树的显示宽度为满二叉树的底层结点数乘4,高度为5的二叉树显示宽度是64个字符长度,高度为6的二叉树显示宽度是128个字符长度。而在文本模式下,由于文本模式每行80个字符(缺省属性)的限制,该文的显示方法只能显示高度不超过5的二叉树。如果要显示高度为6的二叉树,有两种方法,一是修改文本模式每行显示宽度的属性,只要每行可显示超过128个字符即可;二是显示时采用紧凑格式,结点在斜线的正下方[6],这样底层相邻结点之间只有一个空格,高度为6的二叉树显示宽度为64,显示效果见图5,与图3相比美观性略差。文献[2]采用分页的方式来显示高度超过6的二叉树。考虑到该文的方法主要用于教与学,高度为5的满二叉树有31个结点,对于教学来说高度与结点数都足够,因此该文方法不需其它的改动完全满足正常的教学要求。

空格的具体个数依赖于结点所处的层数,计算时分数据域行、第一行连接符和第二行连接符,倒数第一层和倒数第二层之间只有第一行连接符。具体计算公式如下:

数据域:(2n-2个□)a(2n+1个□)(n为树高,□代表空格,a为数据)

第一行连接符:(2n-1个□)(2n-1-3个_)/□(2n-1-3个_)(2n-1+3个□)

第二行连接符:(2n-1-1个□)/(2n-3个□)(2n-1+2个□)

计算第一行连接符时,n=2将导致2n-1-3=-1,因此前面的空格需要减少一个,即2n-1个空格变为2n-1-1个空格。第二行连接符计算时,不会出现这种问题,因为n=2时没有第二行连接符。

2 程序实施

根据以上方法采用C++进行编程,二叉树的类定义如下:

二叉树的输出是从根结点开始,一层一层地输出。每一层分3行输出,第一行输出结点数据,简单起见结点数据类型为字符型;第二行和第三行为连接符,第一行连接符包括三种字符’_’、’/’和’’,第二行只包括’/’和’’两种字符。如果不用字符’_’而用字符’~’也可以,此时第一行连接符包括’/’和’’,第二行包括’~’、’/’和’’三种字符。倒数第一层没有连接符,倒数第二层没有第二行连接符。每一行输出时一个结点一个结点地输出,空结点也需输出,只是结点数据和连接符全部用空格替代。

由于整体输出顺序是层序,因此用结点指针型的队列来处理层序输出;每一层的结点需重复3次进行输出处理,每个结点处理完后需要放回到队列以便重复提取。每一层的3行输出结束后队列需要更新,即下一行的结点进入队列。由于空结点也需处理,队列一直不空,为了充分利用队列,用一个临时结点来表示一层结点的处理结束,否则需要计数处理。加了注释的代码如下:

由于空结点也需要处理,因此代码中有大量的分支语句;为了压缩代码长度,程序编制时大量使用了三目运算符?:。即使这样程序仍有70余行,如果希望进一步压缩代码,三行输出的循环控制压缩到一个循环,此时第一行和第二行的连接符需要存储在两串字符串中,循环结束再输出。这样处理后代码压缩到50余行,压缩量不大且可读性略有下降,不建议这样处理。

3 实例应用

二叉树是数据结构中的基础数据类型,因此应用的地方较多,该文举几个简单的例子。二排序叉树是有利于搜索的数据类型,采用该文方法把搜索的结果用特定字符’*’标识出来如图6。哈夫曼树是一种最优二叉树,带权的初始结点都在叶子上,构造过程中新建的结点都是分支结点;哈夫曼树可以采用顺序存储[6],该文方法略作修改即可应用于顺序存储,用特殊字符’@’标识分支结点显示的哈夫曼树如图7。平衡二叉树是一种优化后的二叉排序树,它的左右子树的高度不超过1,每个结点有一个平衡因子表示左右子树的平衡情况,可以用更为直观的符号表示平衡因子,即’>’代表1、’=’代表0和’<’代表-1,显示时把数据域后面的空格减少一个,用于输出平衡因子的代表符号,显示结果如图8。B_树是一种多路平衡查找树,可用于外部文件的动态查找,B_树的插入与删除算法比较复杂,非常适合学生的编程技能训练,在调试过程中如何快速有效地检查结果比较麻烦,采用该文的方法经适当地修改可以方便地显示3阶B_树。为了显示3阶B_树,增加一个符号’|’指向中间的子树,最重要的修改是显示起始位置的计算,另外用字符’~’替代了字符’_’,此时第一行连接符包括’/’、’|’和’’,第二行包括’~’、’/’、’|’和’’四种字符,这样显示的效果也非常好,如图9。

4 结论

二叉树结构的文本模式显示方法使用了’_’、’/’和’’三种字符来显示二叉树的结构,由于不涉及图形操作,该方法有很强的可移植性,不论TC环境或者VS环境,该文提供的代码都可直接使用。该文的方法也可方便地改为独立的函数,也方便其它的语言实现。该方法方便了树型数据结构程序的调试,不仅可以应用于各种二叉树,也可应用于三叉树,比如3阶B_树。由于直观地显示了二叉树的结构,因而可以提高教与学的效率。同时,算法也使用了队列,对学生巩固已学过的数据结构知识非常有帮助。

参考文献

[1]中国计算机科学与技术学科教程2002研究组.中国计算机科学与技术学科教程2002[M].北京:清华大学出版社,2002.

[2]叶品菊,吴斌,胡远望,等.直观显示二叉树结构的算法[J].江南大学学报:自然科学版,2008,7(1):60-63.

[3]刘福君,李华,王玉森,等.基于二叉树的故障树画树算法研究[J].计算机技术与发展,2006,16(7):117-118.

[4]刘惠敏,董毅.动态模拟二叉树的建立[J].黄冈职业技术学院学报,2004,6(1):75-76.

[5]白雪峰,李沛.二叉排序树的建立及对其中序遍历的动态模拟[J].电脑知识与技术,2005,12(8):84-86.

完全二叉树篇7

关键词：电路结构优化,二叉树优化法,CVSL电路,互补CMOS逻辑

0 引言

CVSL电路适合于整个系统或模块的高速设计中。在单端式逻辑(Single- ended logic)和差动式逻辑间需要提供互补信号的反相器[1]。对于复杂逻辑,由于两个NMOS Tree有共同项,电路可进一步化简,减少MOS管数量。传统的方法是用卡诺图法,但卡诺图并不能显示出电路的连接关系,若改用二叉树算法,则可以很明了的反映出电路的连接关系。

1 CVSL电路的特点

互补静态CMOS特点电路的特点是P管阵列的逻辑结构正好是N管阵列的对偶,若一阵列是串联,则另一阵列必定是并联。NMOS阵列是原量控制,PMOS阵列是非量控制, 因而,N型阵列和P型阵列可以接同一个输入信号[2]。电路中PMOS管的数目与NMOS管的数目相同。如果输入变量共有k个,则总共需要2k个晶体管,形成一种全互补电路。但管子数量多,版图可能比较复杂。只有设计得当, 版图才会有规则。

虽然CMOS电路有许多优点,但一般认为其与伪NMOS相比有两大缺点:

(1) CMOS电路的速度比伪NMOS低。任何一级CMOS倒相器至少有两只管子,一只P管和一只N管,它们的栅极是连接在一起的,输入电容加倍,前级的充放电就比较慢。

(2) CMOS电路所需的器件数多。一个逻辑电路需要设计两套逻辑函数,分别传送原函数和其补函数。因而,CMOS电路的逻辑冗余度较高。不仅浪费硅片面积,而且增加互联任务,使性能降低[3]。伪NMOS电路只采用一个P管作为上拉负载,以代替全互补标准CMOS电路中的P阵列逻辑。但增加了静态功耗,提高了输出低电平,降低了噪声容限。为克服功耗提出电路的改进方案即CVSL电路[4],如图1所示。

由于电路同时接收差动式的输入(Differential Input)且提供差动式的输出(Differential Outputs),所以又称为DCVSL(Differential Cascade Voltage Switch Logic)电路。并且原量反量同时输出。虽然比CMOS所用MOS管数量多,但提供互补输出且由于电子迁移率高于空穴,相同面积下速度比CMOS高(是一种高速设计)。由于存在正反馈,完全消除了Pseudo-NMOS中的静态电流,使输出达到rail to rail(低功耗高噪声容限),进一步提高了翻转速度。

该电路适合于整个系统或模块都用DCVSL的设计,在单端式逻辑(Single- ended Logic)和差动式逻辑间需要提供互补信号的反相器。对于复杂逻辑,由于两个NMOS Tree有共同项,所以电路可进一步化简,减少了MOS管数量。

2 用二叉树优化CVSL电路

任何一个逻辑表达式F可表示为一些简单函数的和,也即它的展开对应着一个递归的二叉树,以一位二进制全加器为例,其和S的真值表和逻辑表达式如下所表1所示。

本位和S=A′B′C1+A′BC1"+AB′C1′+ABC1,构造其所对应的二叉树如图2所示。

实际上,二叉树中的一些节点是重复的,在该图2中,最后一层的0和1节点它们可以合并,对二叉树有缩减规则,其一是当两个节点传输到下一个节点的传输路径完全相同时,两个节点可以缩减为一个;当一个节点的所有传输路径都归结到同一个下一级节点时,这个节点可以省略。如图3所示。

合并0项和1项,通过缩减规则最终可得一位二进制全加器的二叉树如图4所示。将所有节点转化为NMOS的连接点,将路径有相应的NMOS管来代替,即可得到最终的CVSL电路,如图5所示,这样用二叉树转化为MOS电路的过程就完成了。

3 结语

本文对比了CMOS电路与CVSL电路的特点,针对CVSL电路速度快功耗低的优点,在高速电路和VLSI设计中通常采用该电路,但由于CVSL电路共享的NMOS管较多,为提高利于率,对比互补的特点,提出了优化电路的二叉树算法。它比传统的真值表优化法,其直观性更强,很好地解决了CVSL电路的设计问题。

【完全二叉树】推荐阅读：

判定其是否为完全二叉树06-04

完全服务06-14

完全探究09-17