動的木

OR事典

動的木

読み方：どうてきぎ
【英】：dynamic tree

最も多くの機能をもつ二分木形状のデータ構造. 大きさ の木構造のグラフを二分木により保持し, 頂点の追加・削除, 木の分割・合併, ある頂点を根にする, ある値をもつ頂点があるか確認, 与えられたパス上の頂点の重みの最大値・総和を計算, ある頂点の子孫の重みの最大値・総和を計算, といった操作をすべて O 時間で行う. 動的木は非常に複雑であるので, 構造が単純で, 回の操作の合計計算時間が O となるスプレー木が多く使われる.

「OR事典」の他の用語

組合せ最適化：

分枝切除法  分枝限定法  劣勾配法  動的木  動的計画  多面体理論  多項式時間アルゴリズム