[자료구조] 트리 (Tree)

Tree란?

  1. 노드의 연결관계로 이루어진 자료구조
  2. 트리는 하나의 루트 노드를 갖는다.
  3. 자식 노드도 0개 이상의 자식 노드를 가지고 있다.
  4. 비선형 자료구조로 계층적 관계를 표현 할 수 있다. 
  5. 그래프의 하위 개념으로 볼 수 있다.

 

Tree 구조 & 용어

루트 노드(root node)	최상위 노드
말단 노드(leaf node)	자식이 없는 노드
내부 노드(internal node)	단말 노드가 아닌 노드
간선(edge)	노드와 노드를 연결하는 선
형제(sibling)	같은 부모를 가지는 노드
노드의 깊이(depth)	루트 -> 찾는 노드 까지의 edge의 수
노드의 레벨(level)	트리의 특정 깊이를 가지는 노드의 집합
노드의 차수(degree)	각 노드가 지닌 가지의 수
트리의 차수(degree of tree)	트리의 최대 차수
트리의 높이(height)	트리에서 가장 깊숙히 있는 노드의 level

 

Degree와 Degree of tree의 이해를 도울 표

 

Tree의 종류

1. 트리 (Tree)
2. 이진 트리 (Binary Tree)
  2.1 완전 이진 트리 (Complete Binary Tree)
  2.2 꽉찬 이진 트리 (Full Binary Tree)
  2.3 포화 이진 트리 (Perfect Binary Tree)
  2.4 편향 이진 트리 (Skewed Binary Tree)

3.이진 탐색 트리 (Binary Search Tree)
 3.1 균형 이진 탐색 트리 (Balanced Binary Search Tree)
      - Red Black Tree , AVL Tree, B Tree, B+ Tree, B* Tree (개별적으로 포스팅 예정)
 3.2 비균형 이진 탐색 트리 (Unbalanced Binary Search Tree)

 

  - 자식 노드가 2개 까지인 트리
  - 자식 노드의 수에 따라 삼진, 사진 트리로도 변할 수 있다.

 

 

  - 이진트리의 종류 중 하나
  - 마지막 레벨을 제외한 모든 노드들은 빈자리가 없어야하며, 
    마지막 노드도 좌측부터 순서대로 채워 진 트리를 의미한다.

 

 

 - 자식노드는 꼭 하나도 가지고 있지 않거나, 
   가질꺼면 2개를 채워서 가진 트리를 의미한다.

 

 - 빈 노드 없이, 2개의 자식노드를 가진 트리입니다.

 

 - 왼쪽이나 오른쪽으로만 서브 트리를 가진 트리입니다.

 

 

 

 - 이진 트리에서 검색을 용이하게 정렬된 트리입니다.
 - 좌측 노드는 부모 노드보다 작은 숫자를 지니게 됩니다.
 - 우측 노드는 부모 노드보다 큰 숫자를 지니게 됩니다.

 

- 추가 하는 숫자가 부모 노드보다 큰 숫자면 우측 노드에만 생성되는 편향 이진 트리가 될 가능성이 높다.
  이를 방지하기 위해 균형 이진 탐색트리가 있습니다.

 

이진 트리 탐색 방식
 1. 전위 순회 (Preorder Traversal)
    본인 -> 왼쪽 노드 -> 오른쪽 노드
 2. 중위 순회 (Inorder Traversal)  
    왼쪽 노드 -> 본인 -> 오른쪽 노드
 3. 후위 순회 (Postorder Traveral)
    왼쪽 노드 -> 오른쪽노드 ->본인

 

문제 1 : 트리는 방향성일까요? 무방향성일까요?
          (루트의 여부가 중요)