트리 (Tree)

• [작성중]
• 사이클이 없는 연결된 무향 그래프
  • 연결되지 않으면 트리가 아니라 포레스트(forest).
• 루트가 주어진 경우는 rooted tree라고 부른다
• rooted tree에서는 부모노드/자식노드가 정의되고, depth/height 개념이 적용된다
  • 노드의 depth 는 루트에서부터 노드까지의 거리이다. 0-base, 1-base 둘다 가능하긴 한데, 우리는 항상 0-base로 통일하자. 그러면 루트노드의 depth는 0이 된다
  • 노드의 level은 depth와 똑같다.
  • 노드의 height는 가장 먼 리프에서부터의 거리이다. 여기도 0-base를 쓰자. 그러면 리프노드의 height는 0이다
• rooted tree에서, 모든 노드가 최대 2개의 자식노드를 가질수 있다면 이진트리가 된다.
  • preorder/postorder/inorder 순회는 이진트리에서 적용되는 개념

• rooted tree 인 경우에는, 각 노드의 parent노드를 저장하는 1차원 배열 하나만으로도 표현이 가능하긴 하다.
• 하지만, 일반적으로 문제에서 주어지는 입력 형식은, 노드수 n과 n-1개의 엣지를 (u,v) 형태로 주는 것이다.
• 입력형식으로부터 트리 생성을 간단하게 하기 위해서, 그리고 그래프 알고리즘을 바로 적용하기 쉽게 하기 위해서 (실제로 트리⊂그래프 이니), 그래프와 똑같이 adjacency list 형태, 즉 Sequence[Iterable[Node]] 의 타입으로 Tree를 정의하도록 하자.

• 문제에서 입력으로 트리를 주는 가장 흔한 형태는 다음 형태이다.

  • N
    u_1 v_1
    u_2 v_2
    ...
    u_(N-1) v_(N-1)
    
    (1 ≤ u_i, v_i ≤ N) 

• 이 형태를 입력받는 가장 전형적인 코드는 다음과 같다.

  • N = int(sys.stdin.readline())
    tree = [set() for _ in range(N)]
    for _ in range(N - 1):
        u, v = [int(x) for x in sys.stdin.readline().split()]
        tree[u - 1].add(v - 1)
        tree[v - 1].add(u - 1)

    • 0-base 인덱싱으로 변환하기 위해서 -1을 해준다. 드물지만 0-base로 입력이 주어지는 문제에서는 -1 없이 넣어주면 된다.
    • 트리가 입력으로 주어지는 경우, N이 1000 이하인 경우는 거의 드물다고 보면 된다. 다시 말하면 input()으로 입력을 받을 가능성은 거의 없고, 그냥 무조건 sys.stdin.readline()으로 입력을 받아야 한다고 생각하는게 편하다
• 이 코드 자체는 전혀 복잡하지 않고, 매 문제마다 이렇게 처리해도 별로 불편할것이 없지만, 워낙 많은 문제에서 반복해서 써야 하다보니 매번 쓰기 귀찮아져서 그냥 라이브러리 함수를 만들었다.
  • (사실 1500문제를 넘게 풀 동안 이것을 함수로 빼려는 생각을 하지 않았을 정도로 별 불편함 없이 살았었다..)
  • teflib.tree.create_tree_from_input
  • 사용법은 이런식이다

    • from teflib import tree as ttree
      ...
      N = int(sys.stdin.readline())
      tree = ttree.create_tree_from_input(N)

  • 위의 코드를 그대로 함수로 묶은 수준이긴 하지만 sys.stdin.readline에 해당하 alias를 만들어서 그것으로 호출하는 점과, u, v를 입력받을때부터 0-base로 바꿔서 입력받는 덕분에, 오히려 속도가 아주 약간 더 빠르다. N<100,000 이고 1-base로 주어진 트리를 입력받을때, 함수를 이용하는 쪽이 40ms정도 빨라졌다. (python 3.11)
    • 트리의 부모 찾기기준으로 그냥 입력받기 (344ms) vs create_tree_from_input으로 입력 받기 (340ms

• 그래프에서는 지정된 출발점에서 시작해서 BFS와 DFS 방식으로 순회하는 방법이 있었다.
• 트리에서 필요한 순회는 대부분 다음 3가지이다.
  • 루트에서부터 탑다운
    • 모든 노드에 대해서 값을 계산해줘야 하는 경우가 있다. 이 값을 계산하기 위해서 parent의 값이 필요하다면, top-down 순서로 순회하면서 채워줄수 있다.
    • 예를 들어, 각 노드의 depth를 구할때는, depth[u] = depth[parent[u]] + 1 로 계산되므로 탑다운 순회가 필요하다.
    • 루트에서 출발하는 dfs와 bfs 모두 탑다운이므로 아무거나 써도 된다. 일반 그래프에 대해서는 graph.dfs 보다는 graph.bfs가 더빨랐다. 트리에서는 방문처리를 좀더 간단하게 해줄수 있는데, 이때는 dfs와 bfs 둘다 속도가 비슷하다. dfs를 쓰자.
  • 루트에서부터 DFS
    • 단순히 값을 채워주는게 아니라, 방문 순서가 중요한 경우이다
    • DFS 순서대로 방문하는 것을 오일러 투어 테크닉이라고도 하는데, 노드들을 이렇게 방문된 순서대로 배열에 저장하면, 같은 서브트리 내의 노드들이 한개의 부분배열로 저장되게 된다. 그래서 서브트리에 대한 쿼리를 1차원 배열의 구간에 대한 쿼리로 변환할수 있어서 유용하다.
  • 리프 노드들에서부터 바텀업

• 탑다운 뒤에 바텀업

==== 이진 트리에서

• 자세한 것은 위키피디아 참고
• 관련 문제
  • 트리의 순회

• 트리에서 parent 배열을 찾기에 가장 간단한 방법은?
  • p

• 정의는 '트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이'
• 구하는 방법은 그래프 탐색을 이용하는 방법과, tree dp를 이용하는 방법이 있다. 그래프 탐색을 이용하는 방법이 더 심플하게 구현 가능.
• 그래프 탐색을 이용하는 방법은
  • 1) 임의의 노드 v0를 잡는다.
  • 2) v0에서 가장 먼 노드 v1을 찾는다.
  • 3) v1에서 가장 먼 노드 v2을 찾는다.
  • 4) v1에서 v2까지의 길이가 트리의 지름.
  • 이 알고리즘의 타당성 증명은 간단하다. 여기 참고
• Tree DP를 이용하는 방법은
  • dp[v]를 v의 자손인 리프 노드들중, 가장 먼 노드까지의 거리라고 정의하면, dp[v] = max(dp[child] + dist[v][child])로 계산 가능
  • 또한 dp2[v]를 v의 자손인 리프 노드들중, 두번째로 먼 노드까지의 거리라고 정의하면, 이것도 같이 구할 수 있다.
  • 트리의 지름은 max(dp[v] +dp2[v])이 된다.
• 트리의 지름에 해당하는 모든 경로는 트리의 중앙지점(centroid)를 지난다. 이것 역시 증명은 어렵지 않다.

• 트리의 지름