[CS] 트리

트리

트리는 노드로 이루어진 자료구조로 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 

트리는 계층적 관계를 표현하는 자료구조이다. 

 

 

트리 특징

1. 트리는 하나의 루트 노드를 갖는다.
2. 루트 노드는 0개 이상의 자식 노드를 갖는다.
3. 자식 노드 또한 0개 이상의 자식 노드를 갖는다.
4. 노드(Node)들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다.
5. 트리에는 사이클(cycle)이 존재할 수 없다.
   • 사이클: 시작 노드에서 출발해 다른 노드를 거쳐 다시 시작 노드로 돌아올 수 있다면 사이클이 존재한다고 한다. 
   • 트리는 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)라고 할 수 있다.
   • 트리의 노드는 self-loop가 존재 해서는 안된다.
6. N개의 노드를 갖는 트리는 항상 N-1 개의 간선(edge)을 갖는다.
7. 모든 자식 노드는 한 개의 부모 노드만을 갖는다.

 

 

 

 완전 이진트리, 전 이진트리, 포화 이진트리

 

• 완전 이진트리(Complete Binary Tree)
  • 완전 이진트리는 마지막 레벨을 제외 하고 모든 레벨이 완전히 채워져 있다.
  • 마지막 레벨은 꽉 차 있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.
  • 마지막 레벨 h에서 1~2h-1 개의 노드를 가질 수 있다.
  • 완전 이진 트리는 배열을 사용해 효율적으로 표현 가능하다.

 

 

 

• 정 이진트리(Full Binary Tree)
  • 정 이진트리는 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리이다.

 

 

 

• 포화 이진트리(Perfect Binary Tree)
  • 포화 이진트리는 모든 레벨이 노드로 꽉 차 있는 트리를 뜻한다. 
  • 전 이진트리의 성질도 만족해야 한다. 즉 모든 노드가 0개 혹은 2개의 자식 노드를 갖는다.
  • 모든 말단 노드가 동일한 깊이 또는 레벨을 갖는다.
  • 트리의 노드 개수가 정확히 2^k-1 개여야 한다. 여기서 k는 트리의 높이다. 

 

 

 

 

 

 

이진 탐색 트리(Binary Search Tree)

: 이진트리이면서 아래의 속성을 갖는 트리

• 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.
• 부모의 키가 왼쪽 자식 노드의 키보다 크다.
• 부모의 키가 오른쪽 자식 노드의 키보다 작다.
• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

 

출처: https://code-lab1.tistory.com/8 [코드 연구소:티스토리]