Tree 개념 정리

정의

• "계층형 트리 구조를 시뮬레이션하는 추상 자료형(ADT)으로, 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다."(박상길, 파이썬 알고리즘 인터뷰, 원 출처 영문 위키피디아)
• 무방향이면서 사이클이 없는 연결 그래프(Undirected Acyclic Connected Graph)
• "V개의 정점을 가지고 V-1개의 간선을 가지는 연결 그래프"
• "임의의 두 점을 연결하는 simple path가 유일한 그래프"(이하 바킹독)

등이 있다.

 

용어

• 노드(node): 트리를 구성하는 기본 요소
  • 루트 노드(root node): 부모가 없는 노드, 트리의 시작점
  • 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
  • 자식 노드(child node): 루트 노드 반대 방향으로 직접 연결된 노드
  • 형제 노드(siblings node): 같은 부모 노드를 갖는 노드
  • 리프 노드(leaf node/leaf): 자식이 없는 노드
• 간선(edge): 노드간의 연결
• 차수(degree): 자식 노드의 개수
• 트리의 차수(degree of tree): 모든 노드의 차수의 최대값
• 레벨(level): 루드 노드부터 해당 노드까지 연결된 간선 수의 합
• 깊이(depth): 루트 경로의 길이
• 높이(height): 가장 긴 루트 경로의 길이
• 너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기

 

트리의 종류

※ 찾아보는 자료마다 사용하는 용어가 달라, 인터넷에서 글을 볼 때에는 맥락상 이해할 필요가 있다. 본 정리는 수업 자료를 참고하였다.

• (Rooted) Tree
  • root가 1개로 유일하며, root를 제외한 모든 node가 1개의 parent node를 갖는 tree
  • 우리가 일반적으로 정의하는 'tree'이다. 조금 더 세밀한 구분이라고 생각하면 될 듯하다.
• (Rooted) Binary Tree
  • rooted tree이며 트리의 차수가 2인 tree
• Binary Search Tree(이진 탐색 트리, BST)
  • Rooted Binary Tree이면서 모든 노드 x에 대해 다음 2가지가 성립한다:
    1. x의 왼쪽 서브트리에 있는 모든 노드 y의 값은 노드 x의 값보다 작다
    2. x의 오른쪽 서브트리에 있는 모든 노드 z의 값은 노드 x의 값보다 크다
  • 정의에 따라 모든 노드의 값이 유일하다는 것도 자연스럽게 알 수 있다.
  • 이상적으로 노드가 분배되어 있는 상황에서, 원소의 삽입/검색/삭제가 O(logN)으로 작동함.
  • 반대로, 자료가 한쪽으로 몰려있는(=skewed) 경우, 원소의 삽입/검색/삭제가 O(N)이 걸림

 

Tree에서의 탐색

• 전위 순회(preorder traversal): root를 먼저 방문(VLR)
• 중위 순회(inorder traversal): 왼쪽 subtree 방문 후 root를 방문(LVR)
• 후위 순회(postorder traversal): 하위 subtree 모두 방문 후 root를 방문(LRV)
• 층별 순회(level order traversal): tree에서의 bfs를 수행한 결과

 

Tree의 구현

트리는 그래프의 일종이기에, 양방향 그래프의 형태로 저장하고, 이후 root에서부터 bfs/dfs를 실행하면서 int 배열 p에 현 노드의 부모를 저장한다. 

이진 트리의 경우, left와 right를 구분하기 위해 이전의 p와 '현재 노드의 왼쪽 자식을 저장'하는 int 배열 l, '현재 노드의 오른쪽 자식을 저장'하는 int 배열 r을 통해 구현한다.