[Swift 자료구조 ch12] Tree 의 기본정의

Tree는 한 Set의 Node로 구성되어있다. 각 Node는 키값, 하위 Node의 집합 및 상위 Node에 대한 링크가 포함된 데이터 구조를 갖는다.

• 부모가 없는 노드 : Root of Tree
• Tree 구조는 계층적 형태로 데이터를 나타낸다.

제약 조건

• 노드는 두번이상 참조될 수 없다
• Root를 가리키는 Node는 없다
• Tree에는 Cycle이 포함되지 않는다.

용어

1. Root : Tree의 맨 위에 있는 Node, 유일하게 부모가 없는 Node이다.
2. Node : Value Key를 갖고 하위 및 상위 Node에 대한 참조를 포함할 수 있는 자료 구조이다.
3. Edge : 상위 Node와 하위 Node 간의 연결을 나타낸다.
4. Parent : 다른 Node에 연결되어 있고, 해당 Node 바로 위에 있는 Node를 parent라고 한다.
5. Child : 다른 Node에 연결되어 있고, 해당 Node 바로 아래에 있는 Node를 child라고 한다.
6. Sibling : 같은 부모를 가지고 있는 Node들을 일컫는다.
7. Leaf : 더이상 child Node가 없는 하위 Node를 의미한다.
8. Subtree : 주어진 Node의 무든 하위 목록
9. Height of the Node : Node와 가장 멀리 연결된 leaf사이의 Edge의 개수이다.
10. Depth : Node에서 Root까지의 Edge 개수이다.