python3: trees [still ip]

数週間前に出くわした言葉。木の形をしたダイアグラム。図に書いてみるとこんな感じ。他のエンジニアリングでも同じらしいが、コンピューターサイエンスの世界でもTreesは基本的に逆さ構造になっている。leavesが下、the root of the treeが一番上に位置している。treesはlistでもlinked listでも表現することが可能。

Components of Trees

• parent (node): childrenを持っているnode (e.x. 21より下のleaves(12, 16, 27, 41)以外)
• child (node): parent nodeを持っているnode。parent nodeは一つしか持てない。(e.x. 21より下)
• Root: 一番上のnode (e.x.21)
• Leaf: child (nodes)を持っていないnode。別の言い方をすれば一番下の層のnode。(e.x. 12, 27, 41)
• Subtree: 木のしたの層に備わっている別の木は全てsubtreesにあたる。これは上の21をrootにした木ともとれるし14,23...と各nodeをrootにして見立ててもちゃんとした木になることを表している。ちなみにこの考え方こそがRecursive Data Structuresに関係してくる。
• Depth: nodeからrootまでの距離(e.x. the depth of 33 == 2)
• Height: 木全体の階層。(e.x. the height of T == 4, IOW the depth of the lowest leaves)

Constructor and Selectors

Treesを作るのに必要な道具は以下:

# constructor
def tree(label, children=[]):
    return [label] + list(children)

# selectors
def label(tree):
    return tree[0]

def children(tree):
    return tree[1:]

def is_leaf(tree):
    return not children(tree)
    # also be implemented: len(children(tree)) == 0 or len(tree) == 1

なぜこれがrecursive structureなのかというとtreeの形は基本的に:

• a label and
• a zero or more children, each a tree

の集合体みたいなものなのでこれを上手くrecursive algorithmに入れればtreeも簡単にいじれる。

More with trees

def count_leaves(tree):
"""returns the number of leaves in tree"""
    if is_leaf(tree):
        return 1
    return sum(count_leaves(child) for child in children(tree))

def leaf_labels(tree):
"""a list of the labels of all leaves in Tree"""
    [label(tree)] + reduce(add, map(leaf_labels, children(tree)), [])
    
    # Alternative
    result = [label(tree)]
    for child in children(tree):
        result += leaf(leaf_labels(child)
    result

More to come soon, stay tuned!

基本中の基本だけ触れようと思ったので、細かい概要や応用はまた追って投稿予定。