트리의 기본속성들

트리

• 계층 구조(hierarchical structure) 로 데이터들이 저장되있는 상태

• 두 "노드" 사이에 parent-child 관계가 성립해야함

• 트리안에 있는 어떤 노드(데이터)든간에 parent 또는 child 를 물어보면 찾아갈 수 있어야함. (어떤 노드가 parent 또는 child 인지)

• linked structure 이라고 부름

트리 용어(terminology)

• root(루트 노드) : 맨위 노드. 외부에서 트리에 access 할수있는 포인트.

• internal node(내부 노드) : child 노드를 최소한 하나이상 가지는 노드

• external node(외부 노드) : leaf 노드라고 부름. 맨 아래층 노드이다. (child 노드가 없다)

• ancestors of a node(조상 노드) : parent 노드, grandparent 노드, great-grandparent 노드, ...기타 등등 순으로 올라감

• Descendant of a node(후손 노드) : 조상과 반대개념. child 노드, grandchild 노드. great-grandchild 노드, ...기타 등등

  • K의 조상은 A(parent 노드), B(grandparent), F(great-granparent 노드)

• Depth of a node ("노드"의 깊이) = 조상의 수 = 루트노드까지 가는데 만나는 조상의 수

  • F의 깊이는 2이고, K의 깊이는 3이다.
  • 깊이가 얼마인지 알기위해 조상의 수를 카운팅할때, 자기 자신은 제외하고 노드 개수를 카운팅하기!!

• Height of a tree("트리"의 높이) : 트리에 속한 노드들의 깊이중에서 최댓값

  • 예시의 트리의 높이는 3이다.

• subtree(부분트리) : 특정 노드가 루트이고 그 밑에 있는 모든 노드들의 집합

  • C가 root인 subtree 는 C,G,H로 이루어진 트리이다.
    ("모든 노드의 집합" 임을 유의!! C,G,H 모든 노드의 집합이지, C,G / G,H 이렇게 일부 노드들의 집합이 아니다.)