[2]

 재귀와 관계 중심의 사고 방식 : 대상에서 관계로 이동

 관계 중심의 문제 파악에서 가장 중요한 것은 재귀다. 재귀란 어떤 문제 A가 문제 A 자신을 포함하는 것을 뜻한다. 

 

-평균 선형 시간 선택 알고리즘, 최악의 경우에도 선형 시간을 보장하는 선택 알고리즘, 

 

n개의 원소로 된 집합에서 최소 원소를 찾기 위해서는 적어도 n-1번의 비교가 필요하다. 이 대, n에 비례하는 시간, 즉 선형 시간이 소요된다. 최대 원소를 찾기 위해서도 마찬가지. 

  일반적으로 n개의 원소 중 i번째 작은 원소를 찾기 위해서는 시간이 얼마나 필요할까 - 예를 들어, 중앙값을 찾는다고 가정. 최소부터 시작해서 n/2번째 원소까지를 저장하면서 계속 갱신할 것인가. 비효율적인 정렬에 드는 시간과 거의 비슷한 시간이 소요. 

n개의 원소 각각을 한 번씩 보지 않고는 알아낼 방법이 없으니 적어도 선형시간임은 명백함. 

 -> 선형 시간이 가능하도록 보장할 수 있음. 기발한 아이디어가 포함되어 있는 재미있는 자기호출 알고리즘 중 하나. 

 

평균 선형 시간 선택 알고리즘 - 퀵 정렬처럼 분할한 후 자기호출 방법을 쓰면 평균적으로 선형 시간에 i번째 작은 원소를 찾을 수 있다. 

 

 최악의 경우에도 선형 시간을 보장하는 선택 알고리즘 -  어느 쪽에 속하는지 판단하는 오버헤드를 수행하고 나면 자신보다 크기는 작지만 성격이 똑같은 문제 하나를 만난다. 

 

 

--검색트리 : 레코드, 키의 정의 및 검색 트리. 이진 검색 트리. 레드 블랙 트리. B 트리. 다차원 검색 트리. 

이진 검색 트리는 자료를 찾는 색인 역할을 하는 자료구조 중 하나다. 이렇게 다른 레코드와 중복되지 않으면서 레코드를 대표할 수 있는 필드를 검색키 또는 키라고 한다. 키는 필드 하나로 구성할 수도 있고, 복수 개의 필드로 구성할 수도 있다. / 이진 검색 트리는 최대 두 개의 자식 노드를 가질 수 있고, 다진 검색 트리는 세 개 이상의 자식 노드로 분기할 수 있다. 일반적으로 k진 검색트리라 하면 자식을 최대 k개까지 가질 수 있는 검색 트리를 말한다. 

 레드 블랙 트리: 이진 검색 트리는 저장과 검색에 평균 logn 시간이 소요되지만 운이 나쁘면 트리의 모양이 균형을 잘 이루지 못한다. 균형이 많이 깨지면 n에 근접한 시간이 소요될 수도 있다. 그래서 고안해 낸 것이 균형잡힌 이진 검색 트리다. 최악의 경우에도 이진 트리의 균형이 잘 맞도록 유지한다. 균형잡힌 이진 검색 트리의 예) 레드블랙 트리와 AVL 트리. 

 

> 레드 블랙 트리에서 삽입: 레드 블랙 트리에서 노드를 삽입할 때는 먼저 이진 검색 트리의 삽입 알고리즘에 따라 삽입을 한 다음 새 노드의 색상을 레드로 칠한다. 내부 룰에 의해 블랙 노드의 최대 갯수가 정해지게 된다. 

 

 디스크에 데이터를 읽고 쓰기 위해서는 블록 단위로 접근을 한다. 단 한 바이트만 읽거나 쓰고 싶어도 한 블록을 통짹로 읽어오거나 써야 한다. 

 

B-트리에서 검색 : 이진 검색 트리에는 각 노드에 키가 하나밖에 없지만 B-트리에서는 최대 k개까지 키를 가질 수 있다. 자식으로 분기를 하고 나면 깊이만 하나 내려간 똑같은 검색 문제가 된다. 이것은 이진 검색 트리에서처럼 재귀호출로 처리할 수 있다. 

 

리프 노드?

 

분할은 한 노드를 두 개로 만드는 것이므로 부모 노드에 키가 하나 더 필요하다. 따라서 분할할 때 노드에 있는 키 중 하나를 부모 노드로 넘긴 다음 나머지로 분할한다. 이 분할의 결과로 키가 하나 늘어난 부모 노드에서 오버플로가 발생할 수 있다. 앞에서 발생한 오버플로와 성격은 같지만 발생 장소만 다르다. 재귀적으로 처리할 수 있다. / 언더플로가 발생할 때는 우선 키를 가져올 수 있는 형제 노드가 있는지 본다. 

 

다차원 검색 트리 - 지금까지 배운 트리는 모두 레코드를 색인하는 키가 하나의 필드로 구성됨. 이런 검색 트리를 일차원 검색 트리라 한다. 하나의 키가 여러 개의 필드를 사용해야 하는 경우도 있다. 

 

 그 중, KD-트리는 이진 검색 트리를 확장한 것으로 k개의 필드로 이루어지는 키를 사용한다. KD-트리는 검색 트리의 각 레벨이 하나씩의 차원만을 다룬다. 

 

 

 해시 테이블 - 검색 효율의 극단. 해시 함수. 충돌 해결. 해시 테이블에서 검색 시간 분석.