반응형 컴퓨터과학7 4-2. 이진 탐색 트리 (Binary Search Tree) 이진 탐색 트리란? 이진 트리에 삽입, 삭제 규칙을 가미하여 탐색에 용이하도록 구성된 트리이다. 이진 탐색 트리의 규칙 이진 트리는 다음과 같은 규칙을 가지고 있다. 1. 모든 노드의 값은 유일하다. 2. 오른쪽 자식 노드의 값이 왼쪽 자식 노드보다 항상 크다. 이진 탐색 트리의 연산 각 예시 코드에 쓰이는 트리 노드의 구조체는 이전 공부 기록을 참조. 2024.07.07 - [전산/자료구조] - 4-1. 이진 트리 (Binary Tree) 삽입// 새로운 노드를 삽입하는 함수struct Node* insert(struct Node* node, int key) { // 트리가 비어있으면 새 노드를 반환 if (node == NULL) { return newNode(key); .. 2024. 7. 9. 4-1. 이진 트리 (Binary Tree) 이진 트리란? 트리의 차수가 2인 트리. 트리를 구성하는 노드들의 자식은 최대 2개이다. 하나의 부모 노드에는 왼쪽, 오른쪽 자식이 존재하는 형태이다. 이진 트리의 형태 1. 정 이진 트리 (Full Binary Tree) 모든 노드의 차수가 2 혹은 0인 경우이다. 만약 자식이 하나만 존재하는 노드가 있다면, 정 이진 트리라고 할 수 없다. 위 같은 경우 차수가 1인 노드가 존재하지 않고, 리프 노드를 제외한 노드들의 자식은 모두 2개 이므로 정 이진 트리이다. 2. 포화 이진 트리 (Perfect Binary Tree) 정 이진 트리의 조건에 더하여 모든 리프 노드의 레벨이 같아야 한다. 우리가 생각하는 예쁘게 꽉 찬 트리의 모습이 포화 이진 트리이다. 3. 완전 이진 트리 (Complete B.. 2024. 7. 7. 4. 트리 (Tree) 트리란? 노드 간에 부모 - 자식 관계를 가지는 방향성이 있는 그래프. 한 부모 노드가 여러 개의 자식 노드를 가질 수 있기 때문에 비 선형 자료 구조이다. 항상 부모가 없는 가장 상위의 루트(root)노드로 부터 시작해 뻗어나가는 모양이 나무와 닮아 tree라는 이름이 붙었다. 트리의 용어 트리에는 사용의 편리함을 위해 사용하는 개념과 용어들이 있다. 아래 트리의 예시를 기준으로 설명하겠다. 1. 루트 노드 (root) : 부모가 없는 가장 최상위 노드. 위 트리에서는 가장 상단의 1번 노드이다. 2. 부모 노드 (parent) : 한 노드와 연결된 상위 노드. 예를 들어 2번 노드의 부모는 1번 노드이고, 6번 노드의 부모는 3번 노드이다. 3. 자식 노드 (child) : 한 노드와 연결된 .. 2024. 7. 6. 3. 큐 (Queue) 큐란? 선입선출(First In First Out / FIFO) 특성을 가지는 선형 자료 구조이다. 앞서 살펴본 스택과는 대비되는 특성으로, 스택과는 반대로 먼저 들어온 데이터가 먼저 나오는 순서를 유지하는 구조를 가지고 있다.큐의 연산 큐에는 선형큐, 환형큐, 우선순위 큐 등의 바리에이션이 있지만 여기서는 선형큐를 기준으로 설명한다.기능명칭시간복잡도삽입enqueueO(1)삭제dequeueO(1)큐의 장점 1. 작업의 순서를 유지하여야 하는 알고리즘에 적합하다. 2. 효율적인 삽입과 삭제로 연산 시간이 매우 적다. 3. 운영체제의 스케줄링, 네트워크 패킷 처리, 예약, 대기열 등 많은 분야에서 활용도가 높다. 큐의 단점 1. 순서를 유지해야하는 특성상 스택과 배열에 비해서는 약간 복잡한 구조. 2. 스택.. 2024. 7. 2. 2. 스택 (Stack) 스택이란? 후입선출(Last In First Out / LIFO) 특성을 가지는 선형 자료 구조이다. 구조가 간단하고 후입선출이라는 특성을 이용해 각종 알고리즘과 로직, 메모리에 사용된다. 예를 들어보자면, ctrl + z를 누르면 실행되는 '되돌리기'가 스택의 예이다. 가장 나중에 들어온 작업이 가장 먼저 나오는 방식이다. 스택의 연산기능명칭시간복잡도삽입pushO(1)삭제 및 반환popO(1)상단 값 조회topO(1) 스택의 모든 연산은 상수시간의 시간복잡도를 가지고 있다. 하지만 이는 장단점을 가지기 마련이다. 스택의 장점 1. 매우 간단하다. 배열과 더불어 간단한 구조, 배열보다 훨씬 간단한 연산과 규칙으로 구현과 사용이 매우 쉽다. 배열과 별도의 변수를 이용해 구현할 수 있고, 연결리스트로도 손.. 2024. 6. 28. 1. 배열 (Array) 배열이란? 배열은 선형 자료 구조의 대표적인 형태이다. 프로그래밍을 접해본 사람이면 누구나 배열의 존재를 알고있을 것이다. 동일한 타입의 데이터를 연속적인 메모리 공간에 저장하는 자료 구조이다. 배열의 장점 간단한 구조로 이루어져 빠른 접근이 가능하고, 연속적인 메모리 할당으로 캐시 적중률이 높아져 메모리 기대 성능이 좋다. 인덱스로 바로 직접 접근이 가능하기 때문에 접근하는 시간은 O(1) 상수시간으로, 인덱스를 알고 있다면 중간과정 없이 즉시 값을 꺼낼 수 있다. 또한, 우리가 생각하는 배열의 모양과 같이 실제 메모리 상에서도 연속적인 주소로 이루어져 있어 캐시 적중률이 높아 타 자료 구조에 비해 빠른 속도를 자랑한다. 배열의 단점 장점을 모두 잊게 만드는 치명적인 단점은, 생성 시 크기가 고정된다는.. 2024. 6. 27. 이전 1 2 다음 반응형
