[Trees]20. Tree

목차

1. Tree(트리)

2. Tree Terminology

3. Tree ADT

 

1. Tree(트리)

 Tree(트리)는 hierachical structure(계층 구조)를 지닌 추상 모델입니다. Tree는 각각 element를 지닌 node들을 parent-child relation(부모-자식 관계)로 묶어서 분류한다는 점을 특징으로 삼을 수 있습니다.

 

2. Tree Terminology

 Tree를 구성하는 요소들은 다음과 같습니다.

1) Root:

- parent를 가지지 않는 node이다.

- (A)

 

2) Internal node:

- 최소한 하나의 children를 지닌 node이다.

- (A, B, C, F)

 

3) External node(leaf):

- children를 지니고 있지 않는 node이다.

- (E, I, J, K, G, H, D)

 

4) Ancestors of a node:

- 이름 그대로 본인보다 부모인 node들을 의미한다(parend, grandparent, great-grandparent, ...)

 

5) Depth of a node:

- node의 깊이를 뜻하며, ancestor의 수로 표현할 수 있다.

 

6) Height of a tree:

- tree의 높이를 뜻하며, depth of a node의 최대치로 표현할 수 있다.

 

7) Descendant of a node:

- 이름 그대로 본인의 후손인 node들을 의미한다(child, grandchild, great-grandchild, ...)

 

8) Subtree:

- 특정 tree 안의 소규모 tree를 일컫는다.

 

3. Tree ADT

1) 특징

- tree의 특징들에 대해서는 위에서 언급하였음

 

2) 기능

- int size(), boolean empty

- root(): root의 위치를 반환하는 함수

- list<position> positions(): tree 구성물을 반환하는 함수

- position parent(): 부모의 위치를 반환하는 함수

- list<position> children(): 해당 node의 자식들의 위치를 반환하는 함수

- boolean isRoot(), boolean isExternal()