CS 공부/자료구조22 이진 트리 최종 수정 : 25.1.2이진 트리트리의 구조는 정의하는 방법에 따라 연산이 단순하고 명확해진다.1. 이진 트리의 정의트리의 차수가 2 이하로 제한시켜 노드의 구즈를 링크를 두 개 갖는 연결 리스트로 정형화하여 구성할 수 있도록 한 트리가 이진 트리(binary tree)이다. 이진 트리는 모든 노드가 정확하게 두 서브 트리를 가질 수 있는 트리로 왼쪽 서브 트리와 오른쪽 서브 트리를 분명하게 구별할 수 있는 트리이다.2. 이진 트리의 성질이진 트리는 자노드의 개수가 2 이하인 일반 트리와 의미가 다르다. 이진 트리의 왼쪽 자노드는 일반트리의 부자 관계와 같고, 오른쪽 자노드는 일반 트리의 형제 관계이다. 이는 일반 트리를 이진 트리로 변환에서 본다.노드가 없는 트리(empty tree)도 이진 트리이다.. 2025. 1. 2. 트리 최종 수정 : 25.1.2트리 선형구조는 자료들이 1 : 1로 연결되어 있는 구조이다. 트리와 그래프는 대표적인 비선형 구조로 노드의 자료들이 1 : 다 또는 다 : 다의 구조를 가진다.1. 정의트리는 그래프 중에서 사이클 관계를 포함하지 않는 연결 그래프로서 임의의 노드에서 상위로 연결된 경로가 1개이고, 하위로 연결된 경로가 여러 개를 가지는 계층적 구조를 가진다. 트리는 계층적인 자료구조로 노드와 각 노드들을 연결하는 간선들로 구성된다. 노드 중 최상위 노드를 한 개 가지고 이를 루트라 한다. 루트에 다른 하위 노드들이 간선들로 연결된 비선형 구조의 계층 구조이다. 트리의 응용 분야는 계층적인 조직이나 디렉토리 구조 및 인공지능에서 인간의 의사결정 구조를 표현하는 결정 트리(decision tree.. 2025. 1. 2. 다중 스택 최종 수정 : 12.24.29다중 스택1. 다중 스택의 정의다중 스택이란 2개의 스택을 이요한 구조를 의미하며, 하나의 기억 장소에 2개의 스택을 표현한다. 양쪽 끝은 각 스택의 bottom을 의미하고, 사용 가능 공간을 스택 2개의 top pointer가 1씩 증가하면서 각 스택이 할당받아 사용하게 된다.2. 다중 스택의 삽입다중 스택에서의 삽입은 몇 번째 스택에 원소를 삽입할지 하는 스택의 번호와 삽입할 원소가 필요하다.참고독학사 교재 2024. 12. 29. 동적연결 스택과 큐 최종 수정 : 24.12.29동적연결 스택과 큐순차 표현방법은 스택이나 큐가 하나만 있을 때는 효율적이나 여러 개의 스택이나 큐가 동시에 있을 때, 이들을 순차 리스트로 표현하면 비효율적이다. 이것을 연결 리스트로 표현해야 효율적이다. 스택은 tp pointer로 첫 노드를 가리키게 하고, 큐의 경우에는 첫째와 마지막 노드를 각각 front와 rear pointer로 가리킴으로써 삽입&삭제가 가능하도록 할 수 있다. 스택과 큐를 연결 리스트로 만들면 메모리르 좀 더 효율적으로 쓸 수 있고, 1차원 배열로 표현했을 때 발생하는 메모리 한계를 극복할 수 있다.1. 연결 리스트로 구현된 스택의 노드 추가스택에서의 노드 추가는 가용 공간이 가득 찼는지 확인 후에 노드를 삽입한다. 순차 표현으로 표현된 스택에서의.. 2024. 12. 29. 덱(Deque) 최종 수정 : 24.12.29덱(Deque)덱(Deque : double-ended queue의 약어)은 큐의 특수한 형태로, 디큐, 데크, 덱이라는 이름으로 불린다. 덱은 리스트의 양쪽 끝에서 삽입과 삭제가 모두 이루어지는 자료구조 형태이다. 덱은 스택과 큐를 혼합한 구조로 하나의 배열을 선언한 후 2개의 포인터로 양쪽 끝을 가리킴으로써 양쪽에서 삽입 및 삭제 연산이 이루어지는 구조이다. 덱을 표현하는 방법에는 1차원 배열 형태인 스택을 이용하는 방법과 단순 연결 리스트나 이중 연결 리스트를 사용하여 표현하는 방법이 있다. 연결 구조를 위한 포인터 기억공간을 더 요구하게 되는 문제점을 갖는다. 덱은 리스트의 양쪽 끝에서 삽입과 삭제가 발생하여 항상 2개의 포인터가 필요하다. 덱은 양쪽 끝에서 원소들의 .. 2024. 12. 29. 이전 1 2 3 4 5 다음