재민

이진트리의 표현으로는, 배열과 연결리스트를 들 수 있다. 1) 배열 우선 1차원 배열에 노드를 저장한다. 자신의 번호를 가진 인덱스 위치에 저장해둔다. 이 때 인덱스 0번은 사용하지 않고 비워두고, 인덱스 1번부터 루트 노드를 저장한다. n개의 노드를 가진 트리는 부모와 자식 노드의 인덱스 관계임을 볼 수 있다. 따라서 parent(i) : [i/2] if i != 1이 되고, leftChild(i) : 2i if 2i

AVL tree란 Adelson-Velskii와 Landis에 의해 1962년에 제안된 트리로, 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차가 1이하인 이진탐색트리를 의미한다. AVL tree의 연산과정은 다음과 같다. 탐색 연산 : 이진 탐색 트리와 동일하다. 값들을 비교하며 내려가는 구조이다. 삽입,삭제 연산: 삽입-삭제 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 받는다. LL type 혹은 RR type을 맞추기 위해 rotation을 진행한다.

BST(Binary Search Tree)란 탐색을 효율적으로 하기 위한 자료구조이다. 이진탐색트리는 다음과 같은 특징을 가진다. 1) 이진트리이며 모든 원소는 서로 다른 유일한 키를 가짐 2) 왼쪽 서브트리의 key값< 루트의 key값< 오른쪽 서브트리의 key값 3) 왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리 -이진탐색 트리의 연산 1) 탐색(searchBST()) 연산 루트에서 시작, 탐색할 키값 X를 루트노드의 키값과 비교한다. 키값이 루트노드의 키값과 같으면 탐색 성공, 크거나 작으면 각각 오른쪽, 왼쪽으로 위치시켜 다시 탐색연산 수행 -탐색 방법: 반복적 방법, 순환적 방법(재귀적으로 수행) 2) 삽입(insertBST())연산 탐색연산이 모두 완료된 이후에 진행된다. 탐색이 실패한 위..

[자료구조의 분류] - 단순구조: 문자,정수,실수, 문자열 - 파일구조: 순차파일, 색인파일, 직접파일 - 선형구조: 스택, 큐, 링크드리스트, 배열 - 비선형구조: 트리, 그래프

프로그램 구동 시에 프로그램은 메인메모리를 통해 데이터 i/o를 진행한다. 그리고 Secondary storage(디스크)에서 필요할 때마다 필요한 파일만 메인메모리에 적재시켜서 쓰는 구조이다. 데이터 구조의 접근시간은 메인메모리 영역에서 진행되고 단 한번의 접근에 의해 이루어지므로 independent 하다고 볼 수 있고, 그에 반해 File system은 데이터 위치에 의존적이라고 볼 수 있다