VBAによる木構造への要素の挿入方法

Question

ある木構造

図1.

id	parent_id	depth
1	1
2	1
3	1	2
4	2	2
5	3	3
6	3	3
7	4	3
8	5	4
9	5	4
10	6	4
11	6	4

に対して、

depthの変わり目に適当な要素を挿入できるものとします。

挿入する要素のidを通し番号、parent_idを1つ上のparent_idと同じにするというルールの下、

適当な要素を挿入すると、

図2.

id	parent_id	depth
1	1
2	1
3	1
4	1
5	1	2
6	2	2
7	2	2
8	2	2
9	5	3
10	5	3
11	6	3
12	9	4
13	9	4
14	10	4
15	10	4

のような木構造が得られます。(太字は挿入した要素)

以上のルールの下で、図1の配列から図2の配列を作成する方法がわからなくて困っています。

考え方のヒントで良いので教えていただきたいです。

よろしくお願いいたします。

Option Explicit

Sub main()
    Dim tree() As String        ' 図1.の木構造配列格納用変数
    Dim expand_tree() As String ' 図2.の木構造配列格納用変数
    
    ' 変数treeの初期化
    Call Initialize(tree)
    
    ' 処理を記述
    
    ' 図2.の配列をexpand_treeに取得
    
End Sub

Sub Initialize(ByRef tree() As String)
    Dim tmp() As String
    Dim i As Integer
    
    ReDim tree(1 To 11, 1 To 3)
    ReDim tmp(0 To 2)
    
    For i = 1 To 3
        tmp() = Split("1,,1", ",")
        tree(1, i) = tmp(i - 1)
    Next i
    
    For i = 1 To 3
        tmp() = Split("2,,1", ",")
        tree(2, i) = tmp(i - 1)
    Next i
    
    For i = 1 To 3
        tmp() = Split("3,1,2", ",")
        tree(3, i) = tmp(i - 1)
    Next i
    
    For i = 1 To 3
        tmp() = Split("4,2,2", ",")
        tree(4, i) = tmp(i - 1)
    Next i
    
    For i = 1 To 3
        tmp() = Split("5,3,3", ",")
        tree(5, i) = tmp(i - 1)
    Next i
    
    For i = 1 To 3
        tmp() = Split("6,3,3", ",")
        tree(6, i) = tmp(i - 1)
    Next i
    
    For i = 1 To 3
        tmp() = Split("7,4,3", ",")
        tree(7, i) = tmp(i - 1)
    Next i
    
    For i = 1 To 3
        tmp() = Split("8,5,4", ",")
        tree(8, i) = tmp(i - 1)
    Next i
    
    For i = 1 To 3
        tmp() = Split("9,5,4", ",")
        tree(9, i) = tmp(i - 1)
    Next i
    
    For i = 1 To 3
        tmp() = Split("10,6,4", ",")
        tree(10, i) = tmp(i - 1)
    Next i
    
    For i = 1 To 3
        tmp() = Split("11,6,4", ",")
        tree(11, i) = tmp(i - 1)
    Next i
    
End Sub

Comments

[can110]

挿入後の末尾４行のparent_idは10,10,11,11ではなく9,9,10,10ではないでしょうか？

[teratailist]

確認したところ、指摘されたとおりでした。修正しておきました。

Answer 1

挿入位置の特定と、既存要素のID、親IDをずらす処理が肝になるかと思います。
Pythonで書いてみました。参考まで。

# ツリーに要素を挿入
def add_tree( tree, depth, parent_id = 0, name = ''):

    # 挿入位置＝指定レベルの末尾 を末尾から探す
    TREE_LEN = len(tree)
    ins_pos = TREE_LEN
    for i in range(TREE_LEN):
        idx = TREE_LEN - i - 1
        node = tree[idx]
        if node[2] == depth:
            ins_pos = idx + 1

            # 親IDの指定がなければこの要素と同じ親にする
            if parent_id <= 0:
                parent_id = node[1]
            break

    ins_id = ins_pos+1

    # 挿入要素以降の自身IDと親IDを１つずらす
    for i in range( ins_pos, TREE_LEN):
        tree[i][0] += 1 # 自身ID

        # 追加ID以上の親IDも
        if tree[i][1] >= ins_id:
            tree[i][1] += 1

    # 要素を挿入
    tree.insert(ins_pos, [ ins_id, parent_id, depth, name])


# 指定IDの要素を返す
def get_node( tree, id):
    for node in tree:
        if node[0] == id:
            return node
    return None


# ツリー内容を表示
def print_tree( tree):
    print('自ID\t親ID\t深さ\t名前(親の名前)')
    for node in tree:
        parent_name = ''
        parent = get_node( tree, node[1])
        if parent:
            parent_name = parent[3]
        print( '{}\t{}\t{}\t{}({})'.format( node[0], node[1], node[2], node[3], parent_name))



tree = []

# 初期化
add_tree( tree, 1, 0, 'a')
add_tree( tree, 1, 0, 'b')
add_tree( tree, 2, 1, 'c')
add_tree( tree, 2, 2, 'd')
add_tree( tree, 3, 3, 'e')
add_tree( tree, 3, 3, 'f')
add_tree( tree, 3, 4, 'g')
add_tree( tree, 4, 5, 'h')
add_tree( tree, 4, 5, 'i')
add_tree( tree, 4, 6, 'j')
add_tree( tree, 4, 6, 'k')

print('挿入前')
print_tree( tree)

add_tree( tree, 1, 0, 'add_a')
add_tree( tree, 1, 0, 'add_b')
add_tree( tree, 2, 0, 'add_c')
add_tree( tree, 2, 0, 'add_d')

print('挿入後')
print_tree( tree)

結果

挿入前
自ID    親ID    深さ    名前(親の名前)
1       0       1       a()
2       0       1       b()
3       1       2       c(a)
4       2       2       d(b)
5       3       3       e(c)
6       3       3       f(c)
7       4       3       g(d)
8       5       4       h(e)
9       5       4       i(e)
10      6       4       j(f)
11      6       4       k(f)
挿入後
自ID    親ID    深さ    名前(親の名前)
1       0       1       a()
2       0       1       b()
3       0       1       add_a()
4       0       1       add_b()
5       1       2       c(a)
6       2       2       d(b)
7       2       2       add_c(b)
8       2       2       add_d(b)
9       5       3       e(c)
10      5       3       f(c)
11      6       3       g(d)
12      9       4       h(e)
13      9       4       i(e)
14      10      4       j(f)
15      10      4       k(f)

Python Tutorによる動作の様子(1000ステップまで)

Comments

[teratailist]

ありがとうございます。
まさに、欲しい結果です。
コードを解読してVBAに変換してみましたが、まだエラーだらけです。
エラーなくなり次第、ご提示します。

[teratailist]

お世話になっております。

pythonコードをVBAに変換する作業で苦戦しているのですが、
add_tree関数内、tree.insertの直前で
tree[i][0]、tree[i][1]
にはそれぞれどのような値が格納されているのでしょうか。
教えていただきたいです。
よろしくお願いいたします。

[can110]

0から、自ID、親ID、深さ、名前です。
動作の様子が見れるリンクを回答に追加しましたので
詳細動作についてはリンク先を確認、参照ください。

[teratailist]

詳細動作についてもご提示いただきありがとうございます。

お陰様で、tree.insertの直前までは欲しい結果を得られるようになりました。
tree.insertの処理を現在書いておりますが、
VBAで用意されているプロシージャでは、これに相当するプロシージャはありませんよね？

Answer 2

1件追加するサブ関数を書いてみました。
木構造だとかは全く意識してません。
ルールに従って配列にデータを挿入しているだけです。
質問にあるように、数件追加してから、expand_treeを得たいというのとは動作が異なります。
（数件追加する場合の処理手順がわからなかったので省きました）
参考程度にしてください。

Sub main()
    Dim tree() As String        ' 図1.の木構造配列格納用変数
    Dim expand_tree() As String ' 図2.の木構造配列格納用変数

    ' 変数treeの初期化
    Call Initialize(tree)

    ' 1件追加
    Call Add(tree, expand_tree, "2")

End Sub

Sub Add(ByRef tree() As String, ByRef extree() As String, depth As String)
    ReDim extree(1 To UBound(tree, 1) + 1, 1 To UBound(tree, 2))
    Dim ti As Integer
    Dim eti As Integer
    eti = 1
    For ti = 1 To UBound(tree, 1)
        If depth < tree(ti, 3) And ti = eti Then
            extree(eti, 1) = CStr(eti)
            extree(eti, 2) = tree(ti - 1, 2)
            extree(eti, 3) = depth
            eti = eti + 1
        End If
        extree(eti, 1) = CStr(eti)
        extree(eti, 2) = tree(ti, 2)
        extree(eti, 3) = tree(ti, 3)
        eti = eti + 1
    Next
End Sub

最終行の処理が足りていませんでしたので修正してみました。
処理済みかどうかの判定をフラグに変更しました。
なんか無駄が多いですが、基本的な作りとしてはこんな感じかと思います。
配列に代入する３行を関数化したりすれば多少は見やすくなりますかね。
そこらへんはご自分で調整願います。

Sub Add(ByRef tree() As String, ByRef extree() As String, depth As String)
    ReDim extree(1 To UBound(tree, 1) + 1, 1 To UBound(tree, 2))
    Dim ti As Integer
    Dim eti As Integer
    Dim f As Boolean
    eti = 1
    f = False
    For ti = 1 To UBound(tree, 1)
        If depth < tree(ti, 3) And f = False Then
            extree(eti, 1) = CStr(eti)
            extree(eti, 2) = tree(ti - 1, 2)
            extree(eti, 3) = depth
            eti = eti + 1
            f = True
        End If
        extree(eti, 1) = CStr(eti)
        extree(eti, 2) = tree(ti, 2)
        extree(eti, 3) = tree(ti, 3)
        eti = eti + 1
    Next
    If f = False Then
        extree(eti, 1) = CStr(eti)
        extree(eti, 2) = tree(ti - 1, 2)
        extree(eti, 3) = depth
    End If
End Sub

Comments

[teratailist]

ご回答いただきありがとうございます。
ご提示いただいたプログラムを参考に自分のコードに組み込んでおりました。
そこで、問題が生じました。

こちらから示した例が不足していたのですが、
depthが最終番号のとき、要素がうまく追加されず考え中です。
今回の例だと、
main関数で
Call Add(tree, expand_tree, "4")
を使用したとき、
expand_tree(12)の要素が全て""になってしまいます。

私の方でも考え中ではありますが、
原因が分かり次第、ご助言いただければ助かります。

[ttyp03]

最終行の処理が足りてませんでした。考慮不足です。
修正版を追記してみましたのでご確認ください。