二重連鎖木とは? わかりやすく解説

二重連鎖木

出典: フリー百科事典『ウィキペディア(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 を返す場合もある

参照

  1. ^ T. コルメン; R. リベスト; C. シュタイン; C. ライザーソン (2013). アルゴリズムイントロダクション. ISBN 978-4764904088. 
  2. ^ 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. http://www.cs.cmu.edu/~sleator/papers/pairing-heaps.pdf. 
  3. ^ binary tree representation of trees
  4. ^ 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つ目の子供は、その子供から兄弟ノードへのポインタ使い参照する

※この「二重連鎖木」の解説は、「トライ (データ構造)」の解説の一部です。
「二重連鎖木」を含む「トライ (データ構造)」の記事については、「トライ (データ構造)」の概要を参照ください。

ウィキペディア小見出し辞書の「二重連鎖木」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「二重連鎖木」の関連用語

二重連鎖木のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



二重連鎖木のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの二重連鎖木 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのトライ (データ構造) (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS