二重連鎖木
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/10/07 03:44 UTC 版)
Jump to navigation Jump to search
二重連鎖木(にじゅうれんさぎ、英: doubly chained tree)や左-子,右-兄弟表現(英: left-child, right-sibling representation)[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.
|
二重連鎖木
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/02 06:29 UTC 版)
「トライ (データ構造)」の記事における「二重連鎖木」の解説
「二重連鎖木」も参照 別の方法は、ノードに(文字, 子ノードへのポインタ, 兄弟ノードへのポインタ)の3つ組みを格納する方法である。つまり二重連鎖木である。子ノードへのポインタは1つ目の子供だけをさし、2つ目の子供は、その子供から兄弟ノードへのポインタを使い参照する。
※この「二重連鎖木」の解説は、「トライ (データ構造)」の解説の一部です。
「二重連鎖木」を含む「トライ (データ構造)」の記事については、「トライ (データ構造)」の概要を参照ください。
- 二重連鎖木のページへのリンク