나의 IT일지

하나의 노드에 여러개의 노드를 연결한 자료구조를 트리구조라고 하며, 트리구조중에서 주로 이진트리를 사용한다. 이진트리란 차수가 2개 이하로 구성되어 있는 트리구조로, 마지막 레벨을 제외하고 전부 채워저있는 완전이진트리와 완전이진트리에서 마지막 레벨을 모두 채운 포화이진트리가 이진트리에 속한다. 힙 완전 이진 트리에서도 부모 노드의 키 값이 자식의 노드의 키 값보다 항상 크거나 작은 형식을 가진 완전 이진 트리가 있는데, 이를 힙이라고 한다. 힙이란 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 완전 이진 트리로, 다음과 같은 조건을 가지고 있다. 완전 이진 트리여야 한다. 루트노드는 제일 크거나 작은 값을 가지고 있어야 한다. 형제간의 대소관계는 상관..

자료구조는 1:1 구조인 선형구조와 1:n구조인 비선형구조로 구분되어 있다. 그런데 비선형 구조에서 여러 노드가 같은 노드를 가리키는 자료구조가 있는데, 이를 그래프라고 한다. 그래프란 n:n구조인 비선형구조로, 선형자료구조나 트리구조로 표현할 수 없다. 그래프에서 데이터를 저장하는 노드를 정점(Vertex)이라고 하며, 정점과 정점을 연결한 선을 간선(Edge)라도 하며, 해당 그래프는 G=(V,E)로 표현한다. 그래프의 종류 무방향 그래프와 방향 그래프 무방향 그래프 무방향 그래프 예시 인접 행렬 정점과 정점을 연결한 간선의 방향이 없는 그래프로, 해당 간선을 통해 쌍방으로 이동이 가능하다. 이때, 해당 그래프의 정점들은 "V(G)"에 표현하며, 정점을 연결한 간선들은 연결된 정점들을 "(정점, 정점..

하나의 노드에 여러개의 노드를 연결하는 자료구조를 트리 구조라고 하며, 그 중 차수가 2개 이하로 구성되어 있는 트리구조를 이진 트리라고 한다. 이진 트리에는 왼쪽 자식노드의 주소와 오른쪽 자식노드의 주소를 저장하는 포인터가 노드에 생성되어 있으며, 검색하는 방식에 따라 전위 순회, 중위 순회, 후위 순회로 나뉜다. typedef struct TreeNodeType { element data; //데이터 필드 struct TreeNodeType* right; //오른쪽 서브트리 struct TreeNodeType* left; //왼쪽 서브트리 }treeNode; 이진 탐색 트리 이진 트리중에서 아래의 조건을 만족하는 이진트리가 있다. 그리고 이러한 이진트리를 이진 탐색 트리라고 한다. 모든 노드의 데이터..

트리란 1:n구조로 하나의 노드에 여러개의 노드를 연결한 자료구조로, 노드와 노드를 연결한 선을 간선, 간선의 위쪽 노드를 부모노드, 간선의 아래쪽 노드를 자식노드라고 한다. 그리고 부모노드가 갖는 자식노드의 숫자에 따라 차수가 결정이 되는데, 데이터를 검색하기 위해서는 이진 트리를 사용한다. 이때, 이진 트리는 차수가 2이하인 트리구조로, 왼쪽 자식과 오른쪽 자식을 구분한다. 그래서 이진 트리의 노드에는 데이터를 저장하는 필드와 오른쪽 노드와 왼쪽노드를 저장할 수 있는 필드가 필요하다. typedef struct TreeNodeType { element data; //데이터 필드 struct TreeNodeType* right; //오른쪽 서브트리 struct TreeNodeType* left; //왼..

자료구조에는 데이터를 저장하는 방식에 따라 선형형식, 비선형형식으로 나뉜다. 선형 구조 : 데이터를 1:1 관계로 하나씩 나열시킨 구조로, list, stack, queue가 해당 구조에 해당한다. 비선형 구조 : 데이터를 1:n 관계로 나열 시킨 구조로 Tree가 해당 구조에 해당한다. 그리고 비선형 구조 중에서 가장 기초적인 자료구조는 Tree이다. Tree란 1개의 노드에 다수의 노드를 연결하는 자료구조로, 데이터 사이의 계층 관계로 만들어진 계층형 자료 구조이다. 트리 관련 용어 트리는 하나의 노드에 여러개의 노드를 연결해서 형성하는 1:n 관계인 자료구조로, 트리에서 사용하는 용어가 따로 존재한다. 용어 설명 간선 노드와 노드를 연결하는 연결 선 레벨 루트로 부터 떨어져 있는지에 대한 값으로, ..

Queue는 데이터를 입력한 순서대로 데이터를 삭제하는 선출선입 자료구조로, 주로 순서대로 처리해야 하는 경우에 사용한다. 반대로 Stack은 최근에 입력한 데이터를 먼저 삭제하는 후출선입 자료구조로, 주로 순서를 반대로 처리해야 하는 경우에 사용된다. 삽입 / 삭제 삽입 위치 / 삭제 위치 Queue enQueue / deQueue rear / front Stack push / pop top / top 이러한 Queue와 Stack 자료구조를 합쳐서 만든 자료구조가 있는데, 이 자료구조를 Deque라고 한다. Deque Deque란 양쪽 끝에서 삽입과 삭제가 가능한 자료구조로, Queue와 Stack처럼 삽입되는 순서대로 데이터를 저장하며, 삭제한다. 단지 Queue처럼 양쪽으로 데이터를 삽입 / 삭제..