[자료구조] 전공 필기 시험 정리

✔️ 이진트리 

각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료구조

1. 이진 트리의 종류

 

1) 정이진트리(포화이진트리,Full binary tree) 

- leaf node가 끝까지 정말 꽉 찬 트리

 

2) 완전이진트리(Complete binary tree) 

- 마지막 레벨을 제외한 모든 레벨에서 순서대로 node가 꽉 채워진 트리

- 높이가 k라면 k-1레벨까지는 노드가 꽉 채워져있고, 마지막 레벨에서는 노드가 꽉 차있지 않아도 되지만 왼쪽부터 순서대로 차있어야 한다
-노드 i의 부모 노드 인덱스는 floor(i/2), 왼쪽 자식 노드 인덱스는 2*i ,오른쪽 자식 노드 인덱스는 2*i+1

3) 균형이진트리(Balanced binary tree) 

- leaf node들의 레벨차이가 최대 1레벨까지만 나는 트리 (균형이 깨지면 별도의 로직을 통해 다시 균형을 유지)

- 검색할 때 최악의 경우에도 O(logN)의 안정성을 유지

- AVL 트리, 레드블랙 트리, B-Tree, B+Tree, B*Tree 등

 

---

✔️  B트리

1. B-Tree

- 균형 이진 트리 중 하나 (O(logN)의 검색 성능)
- 이진 트리와는 다르게 하나의 노드에 많은 정보를 가질 수 있음(이진 트리보다 훨씬 많은 데이터를 더 효율적으로 저장소에 담을 수 있게 됨)

- 하나의 노드에 담은 자료의 수가 M개라면 M차 B-Tree라고 한다.(자식 노드가 최대 M개)

 

1) B-Tree 특징

• 노드의 자료수가 N이라면 자식의 수는 N+1이어야 한다. 
• 각 노드의 자료는 정렬된 상태여야 한다.
• 노드의 자료Dk의 왼쪽 서브트리는 Dk보다 작은 값들이고 오른쪽 서브트리는 Dk보다 큰 값들이어야 한다.
• Root 노드는 적어도 2개이상의 자식을 가져야 한다.
• Root 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야 한다.
• 외부 노드로 가는 경로의 길이는 모두 같다. 
• 외부노드는 모두 같은 레벨에 있다
• 입력자료는 중복될 수 없다.
• 단점 :  구조를 유지하기 위해서 추가적인 연산이 수행되거나 새로운 노드가 생성됨

2. B*Tree 

B-Tree의 단점인 노드의 추가적인 생성과 추가적인 연산의 최소화를 위해서 B-Tree에서 몇 가지 규칙이 추가된 트리
B-Tree와 B*Tree의 가장 대표적인 차이점 : 최소 M/2개의 키값을 가져야 했던 기존 노드의 자식 노드 수 최소 제약조건이 2M/3개로 늘어났고, 노드가 가득 차면 분열 대신 이웃한 형제 노드로 재배치를 하게 됩니다. (더이상 재배치를 할 수 없는 시점이 되어서야 분열.)

 

1)  B*Tree 특징

각 노드의 자료는 정렬되어 있음
자료는 중복되지 않음
모든 leaf node는 같은 레벨에 있음
root node는 자신이 leaf node가 되지 않는 이상 적어도 2개 이상의 자식 노드를 가짐
root node가 아닌 노드들은 적어도 2[(M-2)/3]+1개의 자식 노드를 가짐 (최대 M개)

 

2) 조건

 Root 노드를 제외한 모든 노드는 2/3 이상 채워져야 된다. (B-Tree는 1/2 이상)

B* Tree는 노드의 분열을 줄여서 보조 연산을 줄이려고 한다. 따라서 노드가 가득차면 분열하는 대신 이웃한 형제 노드로 재배치를 한다. 재배치 작업은 부모노드+해당노드+형제노드의 key들을 나열한 뒤, 중간 key 값을 부모 노드로 보내고 남은 key들을 반복하여 해당노드와 형제노드에 배치한다.

한 노드가 가득차고 인접 노드까지 모두 가득찰 때까지 분열을 지연한다.

3) 삽입

1) B-Tree에서와 같은 방법으로 삽입을 한다.

2) 노드가 가득차면 이웃한 형제 노드를 살펴 빈 자리가 있으면 정렬하여 재배치한다.
3) 인접 노드에도 key 넘침 현상(overflow)이 일어나서 더 이상 빈 자리가 없을 경우, 가득찬 두 노드를 분열하여 2/3 정도 채워진 3개의 노드로 만든다. 이 과정에서 재배치 동작은 2번 발생한다. (가득찬 두 노드를 분열하여 3개의 노드로 만들 때 첫번째 노드와 두번째 노드간의 재배치 그리고 두번째 노드와 세번째 노드간의 재배치)

4) 삭제

B-Tree와 똑같이 삭제 후 key 값의 개수가 모자라면 이웃한 형제 노드로부터 재배치하고 재배치도 할 수 없는 경우 합병한다. 합병할 때는 세 개의 노드를 두 개의 노드로 합병한다.

 

3. B+Tree

 B-tree와 각 노드에 데이터가 저장이 되지만 B+tree의 경우엔 인덱스노드와 리프노드가 분리되어서 존재한다. 

리프노드는 서로 연결되어 있어서 임의접근과 순차접근모드 성능이 우수하다. 

 

1) B+ Tree 구조

- 인덱스 노드의 Value값에는 다음 노드를 가리킬 수 있는 포인터 주소가 존재
- 데이터 노드의 Value값에 데이터가 존재

- 따라서 키값은 중복될 수 있고 데이터 검색을 위해서는 반드시 leaf node까지 내려가야 한다.

- leaf node가 아닌 node의 키값의 수는 그 노드의 서브트리수보다 하나가 적다.
- 모든 leaf node는 연결리스트로 연결되어 있다.

- 차수가 N인 B+ Tree의 리프노드는 최대 N-1개 이다.

 

2) B-Tree와 B+Tree 비교 

공통점

1. 모든 leaf의 depth가 같다

2. 각 node에는 k/2 ~ k 개의 item이 들어있어야 한다.

3. search가 비슷하다.

4. add시 overflow가 발생하면 split 한다

5. delete 시 underflow가 발생하면 redistribution하거나 merge 한다.

 

차이점

1. B-tree의 각 노드에서는 key 뿐만 아니라 data도 들어갈 수 있다. 여기서 data는 disk block으로의 포인터가 될 수 있다.
  B+tree는 각 node에서는 key만 들어가야 한다. 그러므로 B+tree에서는 data는 오직 leaf에만 존재한다.

2. B+tree는 B-tree와는 달리 add, delete가 leaf에서만 이루어진다.

3. B+ tree는 leaf node 끼리 linked list로 연결되어 있다.

 

B+tree의 장점

- 블럭사이즈(노드사이즈) 를 더 많이 이용할수잇다 ( 키값에 대한 harddisk 엑세스 주소가 없기 때문에 )

- leaf node 끼리 linked list로 연결되어있어서 시퀀셜한 레인지 탐색에 매우 유리하다 

 

B + Tree 의 단점

- B Tree의 경우 best case에는 루트에서 끝날수 있지만, B+ Tree의 경우 무조껀 leaf노드까지 가야한다.

 

https://ssocoit.tistory.com/217
출처: https://wangin9.tistory.com/entry/B-tree-B-tree [잉구블로그]