자료구조 - 트리

트리(Tree)

트리(Tree) 구조란 그래프의 일종으로 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

노드(Node)

트리 구조를 이루는 모든 개별 데이터이다.

• 루트 노드(Root Node)
  • 트리 구조의 시작점이 되는 노드
  • 트리는 하나의 루트노드를 가진다.
• 부모 노드(Parent Node)
  • 부속 트리를 가진 노드를 의미한다. 위 그림에서 Q는 A, B노드의 부모노드이다.
  • 부모 노드는 여러 개의 자식 노드를 가질 수 있다.
• 자식 노드(Child Node)
  • 부모에 속하는 노드를 의미한다. 위 그림에서 노드 E, F, G 는 L의 자식 노드이다.
  • 자식 노드는 1개의 부모 노드만 가질 수 있다.
• 형제 노드(Sibling Node)
  • 같은 부모를 가지는 노드를 의미힌다. 위 그림에서 A의 형제 노드는 E이다.
• 조상 노드(Ancestor Node)
  • 특정 노드의 모든 부모 노드들을 의미한다. 위 그림에서 A의 조상 노드는 Q, P이다
• 자손 노드(Descendant Node)
  • 특정 노드의 모든 자식 노드들을 의미한다. 위 그림에서 C의 자손 노드는 M, H, I이다.
• 리프(Leaf)
  • 트리 구조의 끝지점이고, 자식 노드가 없는 노드이다.

간선(Edge)

• 노드와 노드를 연결하는 선
• edge, branch 라고도 부른다.

깊이(depth)

• 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수 이다.
  • Q의 깊이 : 1
  • A의 깊이 : 2
• 트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수있다.
• 최상위 노드를 깊이 0으로 할때 하위 간선으로 연결된 노드의 깊이를 나타낸다.

레벨(Level)

• 갚은 깊이를 가지고 있는 노드들을 묶에서 표현할 수 있다.
  • Q, R의 레벨 : 1
  • A, B, C, D의 레벨 : 2

높이(Height)

• 리프 노드를 기준으로 루트까지의 높이를 표현한다.
• 높이를 표현할 때에는 리프 노드의 기준으로 표현한다.
  • E, F, G, H, I의 높이 : 0
  • P의 높이 : 4

노드의 크기(Size)

• 자신을 포함한 모든 자식 노드의 개수
  • L 노드의 크기 : 4

노드의 차수(Degree)

• 노드의 자식 노드의 개수
  • L 노드의 차수는 : 3

트리의 차수(Degree Of Tree)

• 트리에서 가장 큰 차수를 가진 노드를 의미힌다.
• 위 그림에서 L노드가 가장 많은 3의 차수를 가지고 있으므로 트리의 차수는 3이다.

서브 트리(Sub Tree)

• 서브 트리란 트리 구조에서 루트에서 뻗어나오는 큰 트리의 내부에 트리 구조를 갖춘 작은 트리를 말한다.

트리의 특징

• 트리 자료구조는 일반적으로 대상 정보의 각 항목들을 계층적으로 구조화할 때 사용하는 비선형 자료구조이다.
  • 비선형 자료구조(NonLinear)
    • 비선형 자료구조란 하나의 자료 뒤에 여러개의 자료가 존재할 수 있는 것이다.
    • 자료들 간의 앞뒤 관계가 1:n 또는 n:n의 관계
    • 트리와 그래프가 대표적이며 계층적 구조를 나타내기에 적절하다
  • 선형 자료구조(Linear)
    • 선형 자료구조란 하나의 자료 뒤에 하나의 자료가 존재하는 것이다.
    • 자료들 간의 앞뒤 관계가 1:1의 선형관계를 이룬다.
    • 배열과 리스트가 대표적이고 스택, 큐도 이에 해당된다
      
  • 정점(Node)과 간선(Edge)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 형태
    - 사이클 이란?
    • 그래프의 특정 정점에서 출발하여 돌아다니다가 다시 처음 출발했던 곳으로 되돌아 갈 수 있다면 사이클이 있다고 한다.
      
  • 트리의 구조는 데이터 저장의 의미보다는 저장된 데이터를 더 효과적으로 탐색하기 위해서 사용된다.
  • 트리는 두 개의 노드 사이에 반드시 1개의 경로만을 가진다

트리의 종류

• 이진 트리(Binary Tree)
  • 노드가 하나 이상의 자식을 가지게 되면 트리라고 부르는데 자식 노드가 최대 2개까지만 하용되는 트리를 이진트리라고 부른다.
• 이진 탐색 트리(Binary Search Tree)
  • 이진 탐색 트리는 왼쪽 서브 트리가 현재 노드보다 작아야 하고 오른쪽 서브 트리가 현재 노드보다 크다는 조건을 만족해야 한다. 모든 값들이 노드들을 기준으로 두가지 방향으로만 찾으면 되기 때문에 값을 찾는데 편리한 조건을 지니고 있다.
  • 이진 탐색 트리는 중복된 노드가 없어야 한다.
  • 왼쪽 서브트리, 오른쪽 서브 트리 또한 이진 탐색 트리이다.

• 완전 이진 트리(Complete Binary Tree)

  • 마지막 레벨을 제외 하고 모든 레벨이 완전이 채워져 있다.
  • 마지막 레벨은 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
    

• 꽉 찬 이진 트리(Full Binary Tree)

  • 하나의 자식 노드를 가진 트리가 하나도 존재하지 않을 경우에 Full Binary Tree라고 한다. 노드들의 자식이 하나도 없거나 두개의 자식으로만 구성될 경우이다.

• 포화 이진 트리(Perfect Binary Tree)

  • 양 쪽으로 빈 공간 없이 모든 노드가 두 개의 자식을 가지며 레벨도 같은 경우를 말한다. 레벨의 개수를 n이라고 할때 2^n - 1의 노드 개수를 가지게 된다
    
  • 위 그림에서 레벨은 3이기 때문에 노드의 개수는 2^3 - 1 즉 7개가 된다.

트리의 순회(Tree Travesal)

트리의 모든 노드들을 방문하는 과정을 트리 순회(Tree Travesal)라고 한다.

선형 자료 구조(연결 리스트, 스택, 큐 등)는 순차적으로 요소에 접근하지만 트리 자료구조는 다른 방식을 사용해야 한다.

일반적으로 트리 순회에는 다음과 같은 방법들이 있다.

전위 순회(Preorder Traversal)

• 전위 순회는 깊이 우선 순회(DFT, Depth-First Traversal)이라고도 한다.
• 트리를 복사하거나, 전위 표기법을 구하는데 주로 사용된다.
  • 트리를 복사할때 전위 순회를 사용하는 이유는 트리를 생성할 때 자식 노드보다 부모 노드가 먼저 생성되어야 하기 때문이다.
• 전위 순회 방문 순서
  • 루트 노드 → 왼쪽 노드 → 오른쪽 노드
  • 전위 순회를 재귀적으로 탐색하면 위 그림처럼 탐색할 수 있다.

중위 순회(Inorder Traversal)

• 중위 순회는 왼쪽 오른쪽 대칭 순서로 순회를 하기때문에 대칭 순회(Symmetric Traversal)라고도 한다.
• 중위 순회는 이진 탐색트리에서 오름차순 또는 내림차순으로 값을 가져올 때 사용 된다.
• 중위 순회 방문 순서
  • 왼쪽 노드 → 루트 노드 → 오른쪽 노드
    
  • 중위 순회를 재귀적으로 탐색하면 위 그림처럼 탐색할 수 있다.

후위 순회(Postorder Traversal)

• 후위 순회는 트리를 삭제하는데 주로 사용된다. 부모노드를 삭제하기 전에 자식 노드를 삭제하는 순으로 노드를 삭제해야 하기 때문이다.
• 후위 순회 방문 순서
  • 왼쪽 노드 → 오른쪽 노드 → 루트 노드
  • 후위 순회를 재귀적으로 탐색하며 위 그림처럼 탐색할 수 있다.