[Tree] 트리, Tree

https://github.com/cuttingworms/Data-Structures-with-Python

GitHub - cuttingworms/Data-Structures-with-Python

- 순차 구조 vs 계층 구조(Sequential structure vs Hierarchical structure)

• 순차 구조 (Sequential structure)
  • 파이썬 리스트나 연결 리스트는 데이터를 개념적으로 일렬로 저장하므로 "순서"가 정의되고, 연산은 순차적으로 진행됨
  • 탐색이 모든 데이터를 순서대로 검사하므로 O(n) 소요
  • 순차 구조가 정렬된 상태로 유지된다면 이진 탐색이 가능하여 O(log n) 소요
  • 그러나 정렬 상태를 유지하기 위하여 삽입과 삭제에 O(n) 소요
• 계층 구조 (Hierarchical structure)
  • 데이터 사이에 순서가 아닌 "부모 - 자식" 관계
  • 조직의 계층 구조

 

- 트리 (Tree)

• 데이터의 계층 구조를 표현하기 위한 자료구조
• 일반 트리(General tree)의 정의
  • 트리는 노드의 구조체이다.
  • 트리는 비어있을 수 있다.
  • 트리가 비어있지 않으면, 루트 노드 R과 트리의 집합으로 구성된다.
    • 각 트리의 집합은 공집합일 수 있다.
    • 각 트리의 루트 노드는 R의 자식 노드이다.
• 일반 트리의 특징
  • 모든 노드는 없는 것을 포함하여 여러 개의 자식 노드를 갖는다.
  • 모든 노드는 단 하나의 부모 노드를 갖는다.
    • 단, 루트 노드는 부모 노드를 갖지 않는다.

 

- 용어

• 노드의 분류에 따른 용어
  • 루트(Root) : 트리의 최상위 노드, 부모가 없는 노드
  • 부모(Parent) : 노드의 상위에 연결된 노드
  • 자식(Child) : 노드의 하위에 연결된 노드
  • 내부(Internal) : 자식 노드를 가지는 노드
  • 단말(External) : 자식 노드가 없는 노드 (Leaf라는 표현도 혼용)
  • 조상(Ancestor) : 부모 노드로부터 루트 노드에 이르는 경로 상의 모든 노드의 집합
  • 자손(Descendant) : 자식 노드를 포함한 모든 하위에 매달린 노드의 집합
  • 형제(Sibling) : 같은 부모를 가지는 노드들의 집합
• 노드 및 트리의 특징을 표현하는 용어
  • 깊이(Depth) : 조상 노드의 개수 + 1 (Level이라는 표현도 혼용)
  • 차수(Degree) : 자식 노드의 개수
  • 높이(Height) : 모든 노드의 깊이 중 가장 큰 값 (트리의 속성임)
  • 서브트리(Subtree) : 노드와 자손으로 구성된 트리의 부분 트리

 

- 왼쪽 자식-오른쪽 형제(Left Child-Right Sibling) 표현

• 일반적인 트리를 메모리에 저장하려면 각 노드에 키와 자식 수만큼의 레퍼런스 저장 필요
• K가 클수록 메모리의 낭비가 심해지는 것은 물론 트리를 탐색하는 과정에서 None 레퍼런스를 확인해야 하므로 시간적으로도 매우 비효율적
• 이것을 해결하기 위한 방법으로 왼쪽 자식-오른쪽 형제 표현을 사용
• 노드의 왼쪽 자식과 왼쪽 자식의 오른쪽 형제를 가리키는 두 개의 레퍼런스만을 사용

Key
왼쪽 자식	오른쪽 형제

 

- 순회 (Traversal)

• 노드를 방문하는 순서에 따라 생각하면 됨
  • 중위 순회 (Inorder traversal) : 왼쪽 서브트리를 방문 후에 루트 노드를 방문 후 오른쪽 서브트리 방문 
  • 전위 순회 (Preorder traversal) : 루트 노드를 방문 후 왼쪽-오른쪽 서브트리를 순서대로 방문
  • 후위 순회 (Postorder traversal) : 왼쪽-오른쪽 서브트리를 순서대로 방문 후 루트 노드 방문
  • 층별 순회 (Leverorder traversal) : 맨 위 노드부터 시작하여 왼쪽-오른쪽 순서대로 차례로 내려가며 방문
• Time Complexity : n개의 노드를 모두 한 번씩 방문하므로 O(n) 소요