자료구조 (2) 썸네일형 리스트형 [자료구조] 트리와 그래프 1. 트리(Tree) 트리는 정점(Node)와 선분(Branch)을 이용하여 사이클이 이루어지지 않게 구성된 자료구조이다. 트리의 특징 트리는 계층 모델이다. 트리는 비순환 그래프이다. 노드가 N개인 트리는 항상 N-1개의 간선을 가진다. 순회는 Pre-order, In-order, Post-order로 이루어진다. 트리는 이진트리, 이진 탐색 트리, 균형 트리, 이진 힙 등이 있다. 트리의 용어 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드 만을 가진다. 단말 노드(leaf node) : 자식이 없는 노드 내부(internal) 노드 : 단말 노드가 아닌 노드 간선(edge) : 노드를 연결하는 선 형제(sibling) : 같은 부모를 가지는 노드 조상 노드(ancest.. [자료구조] 배열, 연결리스트, 스택, 큐 1. 배열(Array) 배열은 특정 자료형들이 메모리 공간상에 연속적으로 이루어져 있는 자료구조이다. 배열의 특징 메모리상에 연속적으로 저장되는 특성 때문에, 데이터 접근 속도가 빠르다. 인덱스를 통해 접근하기 때문에 어떤 열에 접근하더라도 접근하는 속도가 같다. 배열의 최대크기를 변경 할 수 없다. 삽입/삭제 시 자료의 이동이 생기기 때문에 오버헤드가 발생한다. 2. 연결리스트(LinkedList) 연결리스트는 여러개의 노드들이 연결된 형태의 자료구조이다. 메모리상에 노드들이 흩어져 있으며, 각각의 노드는 다음 노드에 대한 위치 정보를 저장하고 있다. 연결리스트의 특징 노드는 자료와 링크로 구성된다. 배열 보다 삽입, 삭제 연산이 빠르다. head와 tail이 존재한다. head는 가장 첫번째 노드를 .. 이전 1 다음