Abstract Data Types에서는, 어떤 데이터를 저장하고 있고, 데이터의 동작 방식, 그리고 동작 방식에 대해서 에러 핸들링을 어떻게 하는지가 있으면 그것은 Abstract Data Types이라고 부른다. 그 중 Tree도 존재한다.
Tree는 tree 구조 방식으로 데이터가 쌓이고, 운영 방식은 linked list와 같다. 그래서 insert, delete, search 지원이 가능하다. tree만이 가지고 있는 기능은 Traverse이다.
tree와 linked list와 차이점은, 하나의 노드에 하나의 next 지점을 가지고 있는게 아니라, 여러 개가 있을 수 있다는 것이다. 하나에서 시작해서 노드의 next 개수만큼 지수적으로 가질 수 있다. 그에 따른 문제도 존재한다. 해당 next 노드의 개수만큼 어떤 방식으로 접근할 수 있는지에 따른 방법도 여러 가지가 있을 수 있다.
Tree의 용어
- Root
트리에서 맨 위에 있는 노드를 root라고 부른다.
- Edge
하나의 Node에서 다른 자식 노드를 가리키는 부분을 Edge로써 두 개의 노드가 연결되어 있다고 한다.
- Node
하나의 요소를 의미한다.
- Parent and Child
위의 요소에서 Edge로써 아래의 요소를 가리킬 때, 그것을 Parent와 Child의 관계라고 한다.
- Siblings
같은 라인의 요소들을 Siblings라고 한다.(형제라는 뜻의)
- Leaves, Terminal Nodes
자식 요소로써 제일 아래에 있는, 자식이 더 이상 존재하지 않는 노드를 의미한다.
- Internal Node
반대로 자식이 있는 노드는 Internal Node라고 부른다.
- Descendants of Node
특정 노드에 속하는 자식 노드들을 의마한다.
- Ancestors of Node
특정 노드가 속하고 있는 조상 노드를 가리킨다.
- Path to Node
root라는 위치에서, 특정 노드한테 최단거리로 가는 거리를 의미한다.
- Depth and level of Node
특정 노드의 Depth는 path의 길이를 가리킨다.
- Height of tree
가장 킨 path의 길이를 가리킨다. 즉, 가장 아래에 있는 Node에서 root로 가는 path의 길이를 의미한다.
- Degree of Node
특정 노드의 Degree는, 특정 노드가 가질 수 있는 자식의 개수를 의미한다.
- Size of tree
tree의 사이즈는, 노드의 총 개수를 의미한다.
- Full Tree vs Complete Tree
