New World

m원 탐색 트리 노드의 가지 개수가 많을 수록 최대 탐색 길이는 짧아짐 B트리 B*트리, B+트리 B* 트리 - 노드의 약 2/3 이상이 채워지는 B트리 - B+트리 - 탐색 트리로 구성하면 매우 빠르게 탐색할 수 있지만 전체 데이터를 차례로 처리하기는 불편함 - 잎노드를 연결하는 포인터를 가짐 - 모든 키값이 잎노드에 있고 그 그 키값에 대응하는 실제 데이터 (파일 내용)에 대한 주소를 잎노드만이 가지고 있음 2-3트리 차수가 2 또는 3인 내부 노드를 갖는 탐색 트리 2-노드와 3-노드만으로 구성되는 특수한 형태의 B 트리 2-3-4트리 2-3 트리를 확장하여 4개의 자식을 가진 4-노드를 허용하는 탐색 트리 2-3 트리보다 삽입과 삭제가 용이 삽입 및 삭제 연산을 수행하는데 더 효율적 레드 블랙 트..

이진 탐색 트리 트리에서 특정 데이터의 효과적인 검색을 위해 제한점을 가지는 이진트리 특정 데이터를 검색하고 노드를 삽입/삭제하는 응용 문제에 가장 효과적인 이진 트리 탐색에 최적화된 이진 트리 키:이진 트리의 노드의 데이터 같은 순서 데이터에 대해 BS 트리를 다양하게 만들 수 있음 BS 트리 연산 SPLAY 트리 : 편향된 이진트리 BB 트리, AVL 트리 : 루트를 중심으로 균형된 이진트리 (탐색을 위한) SPLAY 트리 휴리스틱 알고리즘을 사용 (경험적 알고리즘) 자주 탐색하는 키를 가진 노드를 트리의 루트에 가깝게 위치하도록 구성 Splay 연산 : Zig, Zag, Zig-Zag Zig: 찾는 것이 트리의 루트 노드이면 간선 연결을 회전 Zig-Zag : 루트가 아니고 왼쪽/오른쪽 자식들이면 ..

우선순위 큐 큐 : 먼저 들어간 데이터가 먼저 삭제되는 자료구조 우선순위 큐 - 대기 리스트에서 항상 우선순위가 높은 순대로 먼저 서비스를 받는 구조 - 순서와 상관없이 대기리스트에서 우선순위가 높은 순으로 힢 부모-자식 노드 사이에 정렬된 완전 이진트리로 부모노드는 자식노드보다 우선순위가 높음 최소 힢 : 루트가 전체 노드 중에서 최소값인 힙 최대 힢 : 루트가 최대값을 가짐 트리의 모든 노드가 자식 노드보다 작은 값을 가짐 트리의 레벨에 따라 데이터가 순서를 갖지는 않음 탐색 트리처럼 왼쪽 노드와 오른쪽 노드 사이에 크기 제한도 없음 루트가 가장 작은 값을 갖고 부모는 자식보다 작은 값을 가짐 트리의 모든 노드가 자식 노드보다 큰 값을 가짐 트리의 레벨에 따라 데이터가 순서를 갖지는 않음 탐색 트리처..

Top-Down 구문분석 Bottom-Up 구문분석 좌단유도 과정 우단유도과정 Shift-Reduce 구문분석 파싱표를 만드는 것 First Follow

정규언어 : 어휘 Context-Free 언어 : 문장 유도트리 1. 좌단 유도 2. 우단유도 모호성 불필요한 생성규칙 제거 입실론 생성규칙의 제거 Backtracking 과 Left - factoring Left – recursion 제거

트리 분류 - 검색의 편리함 - 논리적 계층 - 계급적 특성 용어와 논리적 표현 방법 노드 : 트리의 항목/트리에 저장되는 데이터묶음 부모노드 - 자식노드 : 상하 계층 구조가 있고 직접적으로 연결된 노드로 상위계층의 부모 노드와 하위 계층의 자식 노드 루트노드 : 트리의 최상위 노드 (부모가 없는 노드) 서브트리 : 부모 노드를 삭제하면 생기는 트리들 리프 노드 : 트리의 맨 끝에 있으면서 자신의 서브트리를 갖지 않는 노드 진입/진출 차수 루트 노드 : 진입차수 = 0 루트를 제외한 모든 노드의 진입 차수 : 1 리프 노드 : 진출 차수 = 0 노드의 레벨 : 루트로부터 그 노드까지 이어진 선의 길이 트리의 높이 : 루트로부터 가장 멀리있는 노드까지 이어진 선의 길이에 1을 더한 값 이진 트리 모든 노..

리스트의 개념 리스트 : 일정한 순서(논리적/의미적)의 나열 개발자가 보는 것은 추상화된 데이터 메인 메모리에서는 순서가 다르되 리스트로 구현하면 리스트의 순서는 동일하게 노출 배열은 인덱스로 표현되는 순서는 물리적인 위치와 동일 리스트의 순서 개념은 논리적인 순서 구현 방법 포인터 배열 배열을 이용한 리스트 구현 배열은 메인메모리와 동일한 순서여야 하여 원소 삽입 시, 원소가 이동하여 이동 시간이 걸림 배열의 확장 - 초기 배열 선언에서 충분히 크게 하면 배열의 추가 확장을 피할 수 있다 - 배열의 추가 확장을 위해 하나씩 뒤로 밀어야 하는 상황이 발생 배열을 이용한 원소 삽입.삭제 - 원소 순서가 연속적인 물리적 주소에 저장 - 모든 원소를 뒤로 물리거나 앞으로 당겨야만함 - 원소 삽입은 프로그램의 ..

큐의 개념 및 추상 자료형 큐의 의미 : 먼저 들어와서 먼저 빠지는 것 작업 큐에 들어간 작업이 가장 처음에 처리되는 작업 스케줄 (First-in-First-out) 한쪽에서는 삽입 연산만 발생 가능하고 다른 한쪽에서는 삭제 연산만 발생 가능한 양쪽이 모두 터진 관 rear과 front 는 내용 이해를 위한 것 Element : item에서 나온 것 큐의 응용 CPU의 관리 방법 : FCFS 스케줄링은 작업이 준비 큐에 도착한 순서대로 CPU를 할당받도록 해주는 기법 RR 스케줄링 기법은 대화형 시스템에 사용되는 스케줄링 방식 배열을 이용한 큐의 구현 큐의 생성 : 변수 rear 초기값은 큐의 공백 상태를 나타내는 -1로 시작함 원형 큐 큐를 연결시켜 회전문처럼 사용하겠다 원형 큐 초기 상태 : 원형 ..