[TIL]アルゴリズム&データ構造:ツリーとバイナリインデックスツリー

3.ツリー構造

意図したように階層を表すデータ構造.

ツリー関連用語

ルートノード:親ノードのない最上位ノード

端末ノード:サブノードなし

サイズ:ツリー内の全ノード数

深さ:ルートノードからの距離

高さ:奥行きの中での最値

序数:ノード毎の子方向幹線数

📌 ツリーサイズがNの場合、総幹線数はN-1

3-1. バイナリ検索ツリー

有効探索が可能な資料構造

特徴

左側サブノード<親ノード<右側サブノード

左サブノードが親ノードより小さい

右サブノードが親ノードより大きい

データ照会プロセス

ルートノードからアクセスし探索を行う

現在のノードと検索する要素の値を比較

検索する要素がもっと大きい場合は右側ノードにアクセス

現在のノードが検索する要素より大きい場合は左側のノードにアクセス

要素が見つかるまで繰り返す

3-2. 木の回り

ツリーリソース構造に含まれるノードに特定の方法でアクセスする方法.ツリー内の情報を直感的に見ることができるため、よく使われます.

木回り方法
・뉭묭・電位めぐり:根장左側장右側장장・장8・
・𐥍7・中尉巡り:左式❵根❵右式・𐥎8・
・뉭묭・後列巡り:左側장장右側장장장장・장8・

📌 実装例

class Node:
    def __init__(self, data, left_node, right_node):
        self.data = data
        self.left_node = left_node
        self.right_node = right_node

# 전위 순회
def pre_order(node):
    print(node.data, end=' ')
    if node.left_node != None:
        in_order(tree[node.left_node])
    print(node.data, end=' ')
    if node.right_node != None:
        in_order(tree[node.right_node])
        
# 중위 순회
def in_dorder(node):
    if node.left_node != None:
        in_order(tree[node.left_node])
    print(node.data, end=' ')
    if node.right_node != Nonde:
        in_order(tree[node.right_node])

# 후위 순회
def post_order(node):
    if node.left_node != None:
        post_order(tree[node.left_node])
    if node.right_node != None:
        post_order(tree[node.right_node])
    print(node.data, end=' ')
    
n = int(input())
tree = []

for i in range(n):
    data, left_node, right_node = input().split()
    if left_node == "None":
        left_node = None
    if right_node == "None":
        right_node = None
    tree[data] = Node(data, left_node, right_node)

pre_order(tree['A'])
print()
in_order(tree['A'])
print()
post_order(tree['A'])

4.バイナリインデックスツリー

a.k.a.BIT、フィンウィックの木.バイナリインデックス構造を用いて区間連結問題を効果的に解決するデータ構造
👉 区間連結アルゴリズム問題:https://www.acmicpc.net/problem/2042

整数のバイナリタグの例
整数バイナリ数表記700000000000000000000000011-711111111111111001

0以外の最後のビットを検索します.

計算非特定数Kの最下位:K&K

n = 8
for i in range(n+1):
    print(i, "의 마지막 비트:", (i & -i))

バイナリインデックスツリー実装動作原理

≪作成｜Create｜ldap≫:0以外の最後の値=保存した値の数

更新

特定の値を変更した場合:区間の値を0ではなく最下位に変更します.
例)3回値の変更:1～4回値の変更、1～8回値の変更、1～16回値の変更

累計和を求める

1からNまでの累計和:0ではなく最後のビットを減算し、区間値の和を計算します.
例)累計11回和:11回値+9~10回値+1~8回値を求める

📌 実装例

import sys
input = sys.stdin.readline

# 데이터의 개수(n), 변경 횟수(m), 구간 합 계산 횟수(k)
n, m, k = map(int, input().split())

# 전체 데이터의 개수는 최대 1,000,000개
arr = [0] * (n + 1)
tree = [0] * (n + 1)

# i번째 수까지의 누적 합을 계산하는 함수
def prefix_sum(i):
    result = 0
    while i > 0:
        result += tree[i]
        # 0이 아닌 마지막 비트만큼 빼가면서 이동
        i -= (i & -i)
    return result

# i번째 수를 dif만큼 더하는 함수
def update(i, dif):
    while i <= n:
        tree[i] += dif
        i += (i & -i)

# start부터 end까지의 구간 합을 계산하는 함수
def interval_sum(start, end):
    return prefix_sum(end) - prefix_sum(start - 1)

for i in range(1, n + 1):
    x = int(input())
    arr[i] = x
    update(i, x)

for i in range(m + k):
    a, b, c = map(int, input().split())
    # 업데이트 연산인 경우
    if a == 1:
        update(b, c - arr[b])	# 바뀐 크기(dif)만큼 적용
    else:
        print(interval_sum(b, c))