세상의 모든 Software 지식을 정리

B-Tree는 self-balancing 탐색 트리로. 거의 모든 데이터가 메모리상에 존재한다고 보면된다. 그러나 데이터량이 커지면 이 모든 것을 메인 메모리에 보관할 수 없다. 만약 key의 숫자가 커질 수록, 데이터들은 디스크에서 정보를 가져올 수 밖에 없다. 디스크 액세스 타임의 비용은 메인메모리 액세스 타임보다 훨씬 비용이 크다. B-Tree의 핵심은 디스크 액세스타임을 감소 시키는 것이 목적이다. B-Tree의 높이 h는 디스크 접근의 횟수와 비례한다 즉, 이것에 따라 성능이 결정된다. B-Tree의 PseudoCode는 다음과 같다. 1. B트리의 검색 (B-Tree-Search) 2. 빈 트리 생성 (B-Tree-Create) 3. B트리에 삽입 (B-Tree-Insert) 4. B트리 분할 (B-Tree-Split) 1. B트리의 검색 (B-Tree-Search) B-Tree-Search (x, k)  // x is node, k is value what we find. i = 1 while i<= x.n && k > x.key(i)  i= i + 1 if i <= x.n && k == x.key(i)  return (x, i) // x is node , i is index number else if x. leaf  return nil else DISK-READ(x)  return B-Tree-Search(x, k) 2. 빈 트리 생성 (B-Tree-Create) B-Tree-Create (T) x = new Node() x.leaf = true x.n = 0 (X노드에 있는 값의 갯수 0) Disk-Write(x) T.Root = x 3. B트리에 삽입 (B-Tree-Insert) O(h)번의 디스크 접근과 , O(tlogN)의 CPU시...

특징: -사전 순 배열 시간복잡도: 가정: 균형트리일 경우 삽입: O(logN) 삭제: O(logN) 탐색: O(logN) 단점: 한곳으로 쏠릴 수 있다. 삭제의 경우: 1. 자식이 두 개인 경우 - 왼쪽자식에서 가장 큰 값을 가지고 오는경우와 - 오른쪽자식에서 가장 작은 값을 가지고 오는 경우 두가지가 가능하다 그렇다면 무엇을 선택하는게 좋을까? 내 생각은 두 서브트리중 더 작은 갯수의 서브트리를 선택하는 것이 낫다고 생각한다. 아마도 탐색 횟수가 줄어들기 때문에, 근데 장기적 관점에서 보면 한쪽으로 쏠린 서브트리의 자식갯수를 줄이는게 더 좋을 수 있지 않을까? ---> 이 경우 두 서브트리의 균형을 맞추기 위해 , 두 서브트리가 대칭을 이루기 위한 StdRandom.beronuii 로 접근한다. L/(L+R)로 접근. 응용: 이진트리의 경우에서 자식노드의 갯수를 3,4... 늘리는 경우를 B트리라 한다.

*트리 정점: V개 간선: V-1개 그렇다면 위 두 조건을 만족하는 것은 트리다???NO O-O   O-O O 이 처럼 왼쪽 세개는 다 연결되어 사이클을 이루고 나머지 두개는 따로 인경우가 있을 수 있다. 결국 3가지조건을 만족해야 한다. 1. 정점이 V개 2. 간선 V-1개 3. 모두 연결되어 있다. <조상, 자손 개념> 자기자신도 조상,자손이 된다. 예를들어 5가 단말노드고 5->2->1(루트노드)일때, 5의 조상노드느 5,2,1 3개 모두 해당된다. <이진트리 종류> 1. 포화 이진트리(Full Binary Tree) 잎 노드를 제외한 모든 노드가 자식을 둘씩 가지고, 또한 모든 잎 노드들이 높이가 같다. 가장 안정적인 구조이다. 2. 완전 이진 트리(Complete Binary Tree) 잎 노드들이 왼쪽부터 차근차근 채워지는 것이 특징. 트리를 이용한 검색에서는 완전한 모습에 가까울 수록 높은 성능을 보인다. 그러니 데이터를 배치할 때는 최대한 완전이진트리에 가깝게 배치한다. 3. 높이 균형 트리(Height Balanced Tree) 루트노드를 기준으로 왼쪽 하위트리와 오른쪽 하위트리의 높이가 1이상 차이나지 않는 트리 4. 완전 높이 균형트리 왼쪽 하위트리의 높이와 오른쪽 하위 트리의 높이가 같은 것

*트리 정점: V개 간선: V-1개 그렇다면 위 두 조건을 만족하는 것은 트리다???NO O-O   O-O O 이 처럼 왼쪽 세개는 다 연결되어 사이클을 이루고 나머지 두개는 따로 인경우가 있을 수 있다. 결국 3가지조건을 만족해야 한다. 1. 정점이 V개 2. 간선 V-1개 3. 모두 연결되어 있다.

스택은 Last in Fisrt Out, 또는 First int Last Out <스택을 구현하는 3가지방법> 1. 간단한 배열을 기반으로 2. 동적 배열을 기반으로 3. 연결리스트로 1번: 공간복잡도 O(n)이고 나머진 O(1)이다. 2번: 공간복잡도 O(n)이고 나머지O(1)이다. 배열의 크기를 증가시키는 것은 비용이 매우 많이든다. 예를들어, n=1에서 한개의 요소를 추가하기 위해서는 2인 배열을 만들고 이전 배열에 있던 요소들을 새로운 배열로 복사해야 한다. n번의 push연산의 수행시간은 T(n)(복사연산의 수)=1+2+3+....n 은 O(n^2)와 비슷해진다. **만약 배가제곱 반복을 하여 스택의 크기를 늘린다면? n=1에서 n=32까지 늘려간다고 가정해보자. 배열의 크기가 1,2,4,8,16일 떄 배열의 크기를 두배 늘린다. n=1일 떄, 복사를 한 번 수행하고 n=2일때 두번 ,n=4에서는 4번 수행. 즉 1+2+4+8+16=31이다. 즉 , 배가 연산은log(n)번 수행한다. n번의 push연산 일 때는 log(n)번 수행한다. n개 요소에 대한 push연산의 전체 시간은T(n)이 된다.(다음과 같다. 1+2+4+8+16+...n/4+n/2+n)=n*(1+2+4+8+16+....1/n)=n*(2)=O(n) T(n)은 O(n)이 되며 분할 상환시간은O(1)이 된다. 다음의 주소에서 분할 상환시간이 무엇인지 설명해놓았다. http://yumere.tistory.com/42 3번: 이 경우는 공간복잡도O(n)그리고 DeleteStack()의 복잡도는 O(n)이다. 순차탐색을 시행해야 하므로... **********배열 스택과 연결리스트를 이용한 것의 비교*************8 배열: 연산은 고정시간, 비용을 많이 소요하는배가연산이 종종 수행 된다., (빈스택에서 시작 했을 때) 모든 n에 대한 관련된 연산-n에 비례한 분할 상환 시간을 포함한다. 연결리스트-자연스럽게...