자료구조(트리, 정렬, 그래프)

소개

"자료구조(트리, 정렬, 그래프)"에 대한 내용입니다.

목차

1. 트리
2. 정렬
3. 그래프

본문내용

empty도 트리이다.

루트 : 트리의 최상위에 있는 노드
자식노드 : 노드 하위에 연결된 노드
차수 : 자식노드의 수
부모노드 : 노드의 상위에 연결된 노드
이파리 : 자식이 없는 노드
형제노드 : 동일한 부모를 가지는 노드
조상노드 : 루트까지의 경로 상에 있는 모든 노드들의 집합
후손노드 : 노드 아래로 매달린 모든 노드들의 집합
서브트리 : 노드 자신과 후손노드로 구성된 트리
레벨 : 루트가 레벨 1에 있고 아래층으로 내려가며 레벨이 1씩 증가한다. 레벨을 깊이와 같다
높이 : 트리의 최대 레벨
키 : 탐색에 사용되는 노드에 저장된 정보

이진트리 : 각 노드의 자식 수가 2 이하인 트리
- 이진트리가 데이터의 구조적인 관계를 잘 반영하고
- 효율적인 삽입과 탐색을 가능하게 하며
- 이진트리의 서브트리를 다른 이진트리의 서브트리와 교환하는 것이 쉽기 때문에 널리 활용됨

포화이진트리 : 모든 이파리의 깊이가 같고 각 내부노드가 2개의 자식노드를 가지는 트리이다.
완전이진트리 : 마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리이다.

한 층에 존재 할 수 있는 최대 노드 수는 이전 층에 있는 최대 노드 수의 2배인데, 이는 이전 층에 있는 각 노드가 최대 2개의 자식노드를 가질 수 있기 때문이다.

완전이진트리를 저장하기 위해 리스트를 사용하는 경우, 자식노드들을 참조할 레퍼런스를 저장할 메모리 공간이 필요 없기 때문에 효율적이다.
하지만, 편향이진트리를 리스트에 저장하는 경우 트리의 높이가 커질수록 메모리 낭비가 매우 심각해진다.

모든 순회 방식은 루트로부터 순회를 시작하여 트리의 모든 노드들을 반드시 1번씩 방문하여 순회를 종료한다.

- 전위순회 : 전위순회는 노드 n에 도착했을 때 n을 먼저 방문한다. 그 다음에 n의 왼쪽 자식노드로 순회를 계속한다. n의 왼쪽 서브트리의 모든 노드들을 방문한 후에는 n의 오른쪽 서브트리의 모든 후손 노드들을 방문한다.

참고자료

· 없음