트리 ADT

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.

    https://github.com/AeroCodeX/

트리 ADT

다음 성질을 만족하는 그래프 ADT를  트리라고 한다.

• 순환회로가 없고,
• 각 노드를 참조하는 노드의 개수가 1개 또는 0개인 그래프.

트리는 ADT?  자료구조?

A tree is a widely used abstract data type (ADT)

— or data structure implementing this ADT.

트리는 넓은 의미에서 ADT로 사용되나,

구현화된 트리는 자료구조로 사용한다.

출처 :  위키백과(en)

트리에서 사용되는 용어

노드의 종류

• 루트 노드 (Root Node)       :  부모가 없는 최상위 노드
• 단말 노드 (Leaf Node)        :  자식이 없는 노드
• 내부 노드 (Internal Node) : 단말 노드가 아닌 노드.
• 외부 노드 (External Node) : = 단말 노드
• 부모 노드 (Parent Node)   :  바로 한 레벨 위의 노드.
• 자식 노드 (Child Node)     :  바로 한 레벨 아래의 노드.
• 형제 노드 (Sibling Node)  :  부모가 같은 노드.
• 자손 노드 (Descendant -) :  자기보다 레벨이 낮은 모든 노드.

노드의 특성

• 노드의 크기(Size)        :  자신을 포함한 자손 노드의 개수

• 노드의 레벨(Level)     :  루트 노드로부터 거쳐야 하는 간선의 수    // 루트 노드의 레벨은 0.

• 노드의 차수(degree)  :  자식 노드의 개수
  

트리의 특성

• 트리의 차수(degree)  :  트리내 노드 차수의 최댓값.
• 트리의 높이(height)   :  트리내 노드 레벨의 최댓값.

제한된 형태의 트리

• K-진 트리  (K-ary Tree)

모든 노드의 차수가 K 이하인 트리. 

• 이진 트리  (Binary Tree)

모든 노드의 차수가 2 이하인 트리.  

특수한 형태의 트리

• 사향 트리  (Skewed Tree)

한 쪽으로 치우쳐진 트리.

• 비균형 트리  (Unbalanced Tree)
  

루트 노드를 기준으로,  양쪽 서브트리의 높이가 다른 트리.

• 균형 트리  (Balanced Tree)

루트 노드를 기준으로,  양쪽 서브트리의 높이가 같은 트리.

일반적 형태의 구현

제한되지 않은 트리를 구현하려면,

통일되지 않은 자식의 수를 유동적으로 결정할 수 있어야 한다.

• 동적 배열
• 고수준 배열
• 연결 리스트