트리

비선형 자료 구조

비선형 자료 구조 비선형 자료 구조는 데이터 요소들이 선형적으로 나열되어 있지 않고 계층적인 구조를 의미한다. 그래프 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조를 의미한다. 그래프 저장 방법 1. 인접 행렬 : 정점과 간선의 관계를 2차원 행렬로 표현, 공간 복잡도 : O(V^2) 2. 인접 리스트 : 정점과 간선이 주어졌을 때 2차원 ArrayList로 표현, 공간 복잡도 : O(E) 트리 정점들이 계층적인 구조를 가지고 있는 비선형 자료 구조이다. 하나의 루트 노드 에서 시작하여, 부모-자식 관계를 가지는 노드들로 구성되어 있다. 반드시 노드가 N인 트리는 항상 N-1개의 간선을 가진다. 노드의 종류 루트 노드 : 최상단에 있는 노드 내부 노드 : 루트 노드와 리프 노드 사이에 있는..