728x90 개발새발8 [자료구조] 트리(Tree) ■ 트리 (Tree) 트리는 일반적으로 대상 정보의 각 항목들을 계층적으로 연관되도록 구조화시키고자 할 때 사용하는 비선형 자료구조이다. 데이터 요소들의 단순한 나열이 아닌 부모-자식 관계의 계층적 구조로 표현이 된다. 트리는 그래프의 한 종류이며 사이클이 없다. [Tree 구조] Node: 트리를 구성하고 있는 각 요소 Edge(간선): 트리를 구성하기 위해 노드와 노드를 연결하는 선 Root Node: 최상위 계층에 존재하는 노드 Level: 트리의 특정 깊이를 가지는 노드의 집합 Degree(차수): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수 Terminal Node ( = leaf Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드 Interna.. 2021. 4. 20. [자료구조] 배열(Array) / 리스트(List) ■ 배열 (Array) 배열의 크기는 한 번 정하면 변경할 수 없다. 배열 초기화 시에 메모리에 할당되어 ArrayList보다 속도가 빠르다. 논리적 저장 순서와 물리적 저장 순서가 일치한다. 인덱스를 사용해 특정 원소에 접근이 가능하다. 즉, Random Access(비순차적 접급)가 가능하다. 인덱스를 알고 있다면 특정 원소에 접근하는 시간 복잡도는 O(1)이다. 생성할 때 데이터를 저장하는데 필요한 메모리를 한 번에 확보해서 사용한다. (연속된 메모리 사용) 배열의 크기를 바꿀 수 없다. 즉, 배열의 크기는 제한적이다. 배열의 원소를 삭제할 경우 삭제한 원소보다 큰 인덱스를 값을 갖는 원소들을 1씩 옮겨줘야 하기 때문에 시간 복잡도는 O(n)이다. 배열의 원소를 삽입할 경우 배열의 크기가 충분할 때.. 2021. 4. 20. 이전 1 2 다음 728x90 반응형
