본문 바로가기

CS/자료구조24

자료구조 문제 풀이 문제 : 다음 설명 중 틀린 것은 무엇인가? 1. 스택은 자료의 삽입과 삭제가 같은 변수를 통해 제어된다. 2. 스택은 객체와 객체가 저장되는 순서를 기억하는 방법에 관한 추상자료형이다. 3. 스택의 크기는 가변적이다. 4. 후위 표기식은 연산자를 피연산자의 뒤에 표기하는 방법이다. 정답 : 3번 정답 설명: 3번 "스택의 크기는 가변적이다." "스택은 자료의 삽입과 삭제가 같은 변수를 통해 제어된다." - 맞는 설명. 스택에서는 데이터의 삽입과 삭제가 'top'이라는 동일한 위치(변수)에서 이루어진다. 이 'top'은 스택의 가장 위에 있는 요소를 가리킨다. 새로운 요소는 top에 추가되고(top을 증가시키고), 요소를 제거할 때는 top에서 제거된다(top을 감소시키고)... 2023. 11. 26.
멀티웨이 탐색 트리 2 : 2-3 트리, 2-3-4 트리, 레드 블랙 트리 개관 트리 구성도 1. 2-3 트리 차수가 2 또는 3인 내부 노드를 갖는 트리를 2-3 트리라고 한다. 이때 차수가 2인 노드를 2-노드, 3인 노드를 3-노드 라고 부른다. 즉, 2-3 트리는 2-노드와 3-노드만으로 구성된 특수한 형태의 B트리이다. 다음 조건을 만족할 때 2-3트리라고 한다. 1) 각각의 내부 노드는 2-노드 이거나 3-노드이다. 2-노드는 한 개의 키값을, 3-노드는 두 개의 키값을 갖는다. 2) lchild, mchild를 각각 2-노드의 좌측 및 중간 자식이라 하고, lkey가 이 노드의 키값이라 하면, 루트가 lchild인 모든 2-3 서브트리 키값은 lkey보다 작고, 루트가 mchild인 모든 2-3 서브트리 키값은 lkey보다 크다. 3) lchild, mchild 및.. 2023. 11. 26.
멀티웨이 탐색 트리 1 - m원 탐색 트리, B 트리, B*트리, B+ 트리 멀티웨이 탐색 트리 개관 이진 탐색 트리를 발전시킨 멀티웨이 탐색 트리에 대해 알아본다. 이것은 기존 이진 탐색 트리의 장점을 활용하면서, 보다 다양한 형태의 자식 노드를 가질 수 있도록 확장한 개념이다. m원 탐색 트리: m개 이하의 가지를 가질 수 있는 확장된 형태의 탐색 트리. 이진 탐색 트리는 사실상 2-way 탐색 트리의 한 형태. 파일 인덱스 구현에 효율적으로 사용 가능하며, 빠른 레코드 참조가 장점. B, B*, B+ 트리: 이들 트리는 서로 다른 조건과 특징을 가지며, 각각의 삽입 및 삭제 방법을 이해하는 것이 중요. B 트리: 루트와 단말 노드를 제외한 모든 노드가 최소 (M/2)개의 서브트리를 가져야 함. 루트는 최소 2개의 서브트리를 보유. 모든 단말 노드는 같은 레벨에 위치. B* .. 2023. 11. 26.
이진 탐색 트리Bs) - Splay, Avl, BB 트리 Bs, Splay Avl, BB 개요 삽입, 삭제 연산을 보다 효과적으로 작업하기 위해 만든 이진 탐색 트리에 대한 정의와 순회 방법에 대해 학습한다. 이진 탐색 트리에서는 각 노드를 식별하기 위해서 별도의 일므을 붙인 '키'라는 용어를 사용한다. 노드의 데이터라고 생각해도 된다. 정해진 노드(vi)를 기준으로 왼쪽 서브트리에 있는 모든 노드는 vi의 키값보다 값이 작아야 하고, 오른쪽 서브트리의 노드들은 vi의 키값보다 값이 커야 한다는 조건을 만족하는 이진 트리를 이진 탐색 트리, 즉 BS 트리라고 한다. 균형 잡힌 트리로 Splay, AVL, BB 트리가 있다. Splay 연산을 적용한 Splay 트리는 최근에 사용한 노드 x를 다음에도 사용할 수 있다는 가정 하에 노드 x를 루트에 .. 2023. 11. 25.
선택 트리, 숲, 이진 트리 개수 선택 트리 1) 개념 선택 트리는 정렬된 여러 데이터 리스트를 효과적으로 병합하는 데 사용되는 트리 구조이다. 이는 합병 정렬 과정에서 중요한 역할을 한다. 예를 들어, 8개의 정렬된 리스트가 있을 때, 이들 중 가장 작은 값을 빠르게 찾아내어 새로운 리스트를 생성하는 과정을 단순화한다. 선택 트리는 이러한 비교 과정의 횟수를 줄이는 데 크게 기여한다. 이 트리는 주로 승자 트리와 패자 트리의 두 가지 형태로 구성된다. 승자 트리는 더 작은 값을 가진 노드가 승자가 되어 상위 노드로 올라가는 완전 이진 트리 구조이다. 이는 각 노드가 두 자식 노드 중 작은 값을 선택하여 상위 노드로 올라가는 토너먼트와 유사한 방식으로 작동한다. 반면, 패자 트리는 루트 노드 위에 최상위 0번 노드를 두어 최종 승자를 저.. 2023. 11. 25.

티스토리툴바