본문 바로가기

# Foundation/자료구조

트리 ADT

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

    https://github.com/AeroCodeX/

트리 ADT

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

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




트리는 ADT?  자료구조?

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)

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




일반적 형태의 구현

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

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

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



'# Foundation > 자료구조' 카테고리의 다른 글

힙 ADT  (0) 2019.02.08
이진트리 ADT  (0) 2019.02.06
트리 ADT  (0) 2019.02.06
그래프 ADT  (0) 2019.02.06
덱 (데크)  (0) 2019.02.04
환형 배열 (원형 배열)  (0) 2019.02.03