コンテンツにスキップ

二重連鎖木

出典: フリー百科事典『ウィキペディア(Wikipedia)』
六分木を二重連鎖木で表現した物
トライ木を二重連鎖木で実装した物。縦の矢印は子ポインタを表現し、横の点線の矢印は兄弟ポインタを表現する。

二重連鎖木(にじゅうれんさぎ、: 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.