「二重連鎖木」の版間の差分
削除された内容 追加された内容
en:Left-child right-sibling binary tree 05:33, 29 August 2015 を翻訳 |
(相違点なし)
|
2015年10月31日 (土) 13:54時点における版
二重連鎖木（にじゅうれんさぎ、英: doubly chained tree, left-child right-sibling binary tree[1], child-sibling representation[2], filial-heir chain[3]）とは、多分木を、直接子ノードのポインタの集合で管理するのではなく、子ノード1つと兄弟ノード1つのポインタで管理する方法。つまり多分木を二分木に変換する。1963年に Edward H. Sussenguth が発表した[4]。
ノード n の k 番目の子供を取得するには、以下のように行う。ノードは child と next-sibling を保持している。
procedure kth-child(n, k):
child ← n.child
while k ≠ 0 and child ≠ nil:
child ← child.next-sibling
k ← k − 1
return child // nil を返す場合もある
参照
- ^ T. コルメン; R. リベスト; C. シュタイン; C. ライザーソン (2013). アルゴリズムイントロダクション. ISBN 978-4764904088
- ^ Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. (1986). “The pairing heap: a new form of self-adjusting heap”. Algorithmica 1 (1): 111–129. doi:10.1007/BF01840439.
- ^ binary tree representation of trees
- ^ Sussenguth, Edward H. (1963). “Use of tree structures for processing files”. Communications of the ACM 6 (5): 272–279. doi:10.1145/366552.366600.
 | この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |