python - 葉だけに動的な深さとデータを持つツリー構造

Question

私は次の階層を持っています：

- A
    - X : [1, 2, 3]
    - Y : [4, 5]
    - Z : [10, 11]
- B
    - X : [6, 7]
    - Y : [8]

そして、私が欲しいのは、次のクエリで次の結果が得られるようにすることです。

get(A) ==> [1,2,3,4,5,10,11]
get(A,Y) ==> [4,5]
get(B) ==> [6,7,8]
get(B,X) ==> [6,7]

これまでのところ、それは簡単なようです。Pythonでdefaultdict（lambda：defaultdict（list））になり得るDictionary>を使用することで、これを実現できます。ただし、より一般的にして別のレベル、または別の2つのレベルを設定する必要がある場合はどうなりますか？何かのようなもの：

- A
    - X
        - i  : [1]
        - ii : [2,3]
    - Y
        - i  : [4, 5]
    - Z
        - ii : [10, 11]
- B
    - X
        - ii  : [6]
        - iii : [7]
    - Y
        - i   : [8]

この例では、最初の階層は、最後のレベルが親にマージされる2番目の階層の「投影」です。したがって、最初の階層に対するすべてのクエリで同じ結果が得られるはずです。

新しいレベルのいくつかのサンプルクエリ：

get(B, X, ii) ==> [6]
get(B,X) ==> [6,7]          (same query and result as before)

データはリーフノードにのみ存在することに注意してください。したがって、挿入するには、パス全体を指定する必要があります。

insert(A, X, i, 20)

これは、データ構造のコンストラクターでツリーの深さを指定できることも意味します。

編集：私は深さの検証が必要であることに気づきました：

挿入操作：パス全体を指定する必要があり、len（path）はdepthと等しくなければなりません
Get操作：構造の深さよりも「深い」パスは許可されていません

score 2 · Accepted Answer

from collections import defaultdict
def tree(): return defaultdict(tree)

def get_(t):
    L = []
    if isinstance(t, list):
            L.extend(x for x in t)
    else:
        for k in t:
            L.extend(get_(t[k]))
    return sorted(L)

t = tree()
t['A']['X']['i'] = [1]
t['A']['X']['ii'] = [2,3]
t['A']['Y']['i'] = [4,5]
t['A']['Z']['ii'] = [10,11]

t['B']['X']['ii'] = [6]
t['B']['X']['iii'] = [7]
t['B']['Y']['i'] = [8]

print get_(t)
print get_(t['A'])
print get_(t['A']['X'])
print get_(t['A']['X']['i'])
print get_(t['B']['Y']['i'])

>>> 
[1, 2, 3, 4, 5, 6, 7, 8, 10, 11]
[1, 2, 3, 4, 5, 10, 11]
[1, 2, 3]
[1]
[8]
>>>

score 0 · Accepted Answer

これを見てください：

>>> A = Tree()
>>> B = Tree()
>>> A.insert_subtree("x", Leaf([1, 2, 3]))
>>> A.insert_subtree("y", Leaf([10, 20, 30]))
>>> B.insert_subtree("y", Leaf([100, 101, 102]))
>>> root = Tree({'A': A, 'B': B})
>>> root.get("A")
[1, 2, 3, 10, 20, 30]
>>> root.get("A", "x")
[1, 2, 3]
>>> root.insert("A", "x", 4)
>>> root.get("A", "x")
[1, 2, 3, 4]
>>> root.get("A")
[1, 2, 3, 4, 10, 20, 30]
>>> root.get("B")
[100, 101, 102]

これを機能させるコードは次のとおりです。

class Leaf(object):
    def __init__(self, data=None):
        self.data = data[:] if data else []

    def __iter__(self):
        for item in self.data:
            yield item

    def insert(self, value):
        self.data.append(value)


class Tree(object):
    def __init__(self, trees=None):
        self.trees = dict(trees) if trees else {}

    def insert_subtree(self, name, tree):
        if name in self.trees:
            raise TreeAlreadyExists()

        self.trees[name] = tree

    def get(self, *args):
        child_name, rest = args[0], args[1:]
        child = self._get_child(child_name)

        if len(rest):
            return child.get(*rest)
        else:
            return [item for item in child]

    def _get_child(self, name):
        if name not in self.trees:
            raise KeyError("Child %s does not exist" % name)
        return self.trees[name]

    def insert(self, *args):
        child_name, rest = args[0], args[1:]
        child = self._get_child(child_name)
        child.insert(*rest)

    def __iter__(self):
        for key in sorted(self.trees.keys()):
            for item in self.trees[key]:
                yield item

class TreeAlreadyExists(Exception):
    pass

score 0 · Accepted Answer

@black_dragonのアイデアに基づいて、深さの検証をサポートするこのクラスを作成しました。使用方法は次のとおりです（テストケースからコピー）：

def test_index_with_sample_case_for_depth_2(self):
    idx = HierarchicalIndex(2)

    # A
    idx.insert(1, 'A', 'X')
    idx.insert(2, 'A', 'X')
    idx.insert(3, 'A', 'X')

    idx.insert(4, 'A', 'Y')
    idx.insert(5, 'A', 'Y')

    idx.insert(10, 'A', 'Z')
    idx.insert(11, 'A', 'Z')

    #B
    idx.insert(6, 'B', 'X')
    idx.insert(7, 'B', 'X')

    idx.insert(8, 'B', 'Y')

    assert_that(idx.get('A'), equal_to([1, 2, 3, 4, 5, 10, 11]))
    assert_that(idx.get('A', 'Y'), equal_to([4, 5]))
    assert_that(idx.get('B'), equal_to([6, 7, 8]))
    assert_that(idx.get('B', 'X'), equal_to([6, 7]))


def test_index_with_sample_case_for_depth_3(self):
    idx = HierarchicalIndex(3)

    # A
    idx.insert(1, 'A', 'X', 'i')
    idx.insert(2, 'A', 'X', 'ii')
    idx.insert(3, 'A', 'X', 'ii')

    idx.insert(4, 'A', 'Y', 'i')
    idx.insert(5, 'A', 'Y', 'ii')

    idx.insert(10, 'A', 'Z', 'ii')
    idx.insert(11, 'A', 'Z', 'iii')

    #B
    idx.insert(6, 'B', 'X', 'ii')
    idx.insert(7, 'B', 'X', 'iii')

    idx.insert(8, 'B', 'Y', 'i')

    #same queries with case for depth 2
    assert_that(idx.get('A'), equal_to([1, 2, 3, 4, 5, 10, 11]))
    assert_that(idx.get('A', 'Y'), equal_to([4, 5]))
    assert_that(idx.get('B'), equal_to([6, 7, 8]))
    assert_that(idx.get('B', 'X'), equal_to([6, 7]))

    #new queries
    assert_that(idx.get('B', 'X', 'ii'), equal_to([6]))
    assert_that(idx.get('A', 'X', 'ii'), equal_to([2, 3]))

そして深さの検証:

def test_index_should_validate_depth_in_operations(self):
    # ....
    # depth=3
    idx = HierarchicalIndex(3)

    assert_that(idx.get('A'), has_length(0))
    assert_that(idx.get('A', 'X'), has_length(0))
    assert_that(idx.get('A', 'X', 'i'), has_length(0))
    self.assertRaises(AssertionError, lambda: idx.get('A', 'X', 'i', '1'))

    self.assertRaises(AssertionError, lambda: idx.insert(1))
    self.assertRaises(AssertionError, lambda: idx.insert(1, 'A'))
    self.assertRaises(AssertionError, lambda: idx.insert(1, 'A', 'X'))
    idx.insert(1, 'A', 'X', 'i')        # should not raise anything
    self.assertRaises(AssertionError, lambda: idx.insert(1, 'A', 'X', 'i', 'a'))

    assert_that(idx.get('A', 'X', 'i'), equal_to([1]))

python - 葉だけに動的な深さとデータを持つツリー構造

3 に答える 3

Related

Reference