dev-waterparsley

01. m원 탐색 트리

🔸이진 탐색 트리(BS 트리; binary search tree)

• 트리에서 특정 데이터를 검색하고, 노드의 삽입/삭제 연산이 자주 발생하는 응용 문제에 가장 효과적인 이진 트리
• 왼쪽과 오른쪽이라는 방향성을 가지며 다루기가 매우 편리함
• 부모 노드를 중심으로[부모 보다 큰 데이터 노드]와 [부모 보다 작은 데이터 노드]로 구분됨
  • =왼쪽 서브 트리와 오른쪽 서브 트리의 중간 값은 이들의 부모 노
• 일반적으로 노드의 개수가 많아지면 트리의 높이가 커지게 됨
• BS 트리가 2원(2-way) 탐색 트리임

✅ m원 탐색 트리

• 트리의 노드가 m개 이하의 가지를 가질 수 있는 탐색 트리 => 같은 수의 노드를 갖는 이진트리보다 낮은 높이의 m원 트리
  • m원: 탐색 트리가 가질 수 있는 자식 노드들의 개수
• 이진 탐색 트리의 확장된 형태
• 탐색 트리의 제한을 따르되 2개 이상(m개 이하)자식을 가질 수 있음

✅ m원 탐색 트리의 제한 조건

▪️ m원 탐색 트리 - 3원 탐색 트리

• 3원 탐색 트리는 최대 3개의 자식 노드를 가질 수 있음 == (정렬된) 키 값은 최대 2개
• 키 값들과 서브트리들의 값의 관계 확인 (어떤 것은 작고, 어떤 것은 크고, 어떤 것은 사잇값인지를 확인)
  • 만약 키값이 60, 62이면 첫번째 자식 노드의 값은 60보다 작아야 하고, 두번째 자식 노드는 60과 62 사이의 값이어야 하고, 세번째 자식 노드는 62보다 큰 값이어야 함

🔸m원 탐색 트리 노드의 구조

🔸m원 탐색 트리의 탐색 연산

🔸m원 탐색 트리의 탐색

• 일반적으로 노드의 가지 개수가 많을수록(서브트리가 많을 수록), 최대 탐색 길이는 짧아짐(트리의 깊이가 얕으므로 더 빨리 찾을 수 있음)
• 예를 들어, 키가 255개인 경우 4원 트리로 구성하면 최대 경로 길이가 4가 됨

02. B 트리

✅ B 트리

• m원 탐색 트리는 서브트리의 균형에 대해서는 특별히 제한하지 않았음
• 각 노드가 자식을 많이 갖게 하여 트리의 높이를 줄이고 전체적으로 균형을 유지한다면 탐색 성능을 더욱 향상할 수 있음
• m원 탐색트리를 개선한 B트리는 인덱스 구조를 구현하는데 가장 일반적으로 사용함
• 차수  m인 B 트리의 탐색 경로 길이는 같은 개수의 키를 가지는 이상적인 m원 탐색 트리보다 길 수 있지만 키값을 삽입/삭제할 때 B트리를 유지하는 것이 더 쉬움

✅ B 트리의 조건

• 루트와 잎노드를 제외한 트리의 각 노드는 최소 [ m/2 ]개의 서브트리를 갖는다
  • 루트와 잎노드를 제외한 트리의 각 노드는 언제나 하나의 키값 혹은 두 개의 자식 노드를 가져야 함
• 트리의 루트는 최소한 2개의 서브트리를 갖는다
• 트리의 모든 잎노드는 같은 레벨에 있다

* [ ] 가우스 함수: 소수점을 포함하는 수를 그것보다 1큰 정수로 바꿈
예) [3/2] = [1.5] = 2

🔸B 트리에 키를 삽입하는 알고리즘

🔸B 트리의 노드 삽입

🔸B 트리에서 키를 삭제하는 알고리즘 - 잎노드에서 삭제

삭제할 키값을 포함한 노드를 찾는다

• 잎노드에서 삭제하는 경우
  1. 노드에서 키값을 삭제한다.
  2. 필요하면 재배열한다.

🔸B 트리에서 키를 삭제하는 알고리즘 - 내부노드에서 삭제

내부노드의 키값은 하위 노드에 대한 기준값(중간값)이기 때문에 삭제 시, 대체할 수 있는 적절한 값을 찾아야 한다.
보통 왼쪽 서브트리의 가장 큰 키값 또는 오른쪽 서브트리의 가장 작은 키값으로 대체할 수 있다. 이들은 모두 잎노드에 위치한다.

• 새로운 기준값(삭제된 자리에 올 키값)을 선택하여 해당 (잎)노드에서 삭제하고 그 값을 현재 키값을 삭제한 자리로 옮긴다. 즉 대체한 것이다.
• 기준값으로 대체하기 위해 키를 삭제한 잎노드가 정해진 개수의 키값을 갖지 않으면 트리를 재배열 한다.

▪️ 40 삭제(내부노드에서 삭제)

• 40을 삭제하면 중간값을 오른쪽 서브트리의 가장 앞에 있는 값을 올려줌
  • 키값이 부족한 노드의 오른쪽 형제가 존재하고 키 개수가 여유있다면 오른쪽 키값의 가장 앞에 있는 것을 부모 노드로 한다는 규정

03. B*, B+ 트리

✅ B* 트리의 정의

• 노드의 약 2/3 이상이 채워지는 B 트리 → 높이가 더 줄어듬(B트리는 1/2)
• 노드가 꽉 차면 분리하지 않고, 키와 포인터를 재배치하여 다른 형제 노드로 옮김
• 삽입/삭제 시 발생하는 노드 분리를 줄이려고 고안됨

✅ B* 트리의 조건

차수가 m인 B* 트리는 다음 조건을 만족하는 B트리이다

① 공집합이거나 높이가 1 이상인 m원 탐색 트리이다
② 루트 노드는 2개 이상 2 ⌊ (2m-2)/3 ⌋ + 1개 이하의 자식노드를 갖는다
③ 내부노드는 최소한 ⌈ (2m-1)/3 ⌉개의 자식노드를 갖는다
④ 모든 잎노드는 동일한 레벨에 놓인다
⑤ 포인터가 k개인 잎이 아닌 노드는 k-1개의 키를 갖는다(루트노드 포함)

✅ B+ 트리의 정의

• 탐색 트리로 구성하면 매우 빠르게 탐색할 수 있지만, 전체 데이터를 차례로 처리하기는 불편함
  • => 데이터 전체를 이진 탐색 트리로 구성해놓으면 검색은 빠르지만! 전체 데이터를 다 찾아서 제일 큰 값부터 차례로 출력할 때는 굉장히 복잡
  • 매번 왼쪽인지 오른쪽인지 비교해가면서 다음 노드를 찾아가면서 처리해야 함
  • 스택을 써서 프로그래밍 하기 때문에 pop(), push() 연산이 추가되면 속도가 굉장히 느려짐
• B+ 트리는 인덱스된 순차 파일을 구성하는데 사용됨
• B 트리와 같이 각 노드의 키가 적어도 1/2이 채워져야 하는 점은 같음
• 잎노드를 순차적으로 연결하는 포인터 집합이 있다는 점에서 다름
  • 잎노드의 마지막 포인터를 다음 키값을 갖는 노드를 가리킴
  • 순차 처리를 할 때는 이 포인터를 이용해서(키값을 비교하지 않고) 차례로 다음 데이터에 접근해서 처리
• 모든 키값이 잎 노드에 있고 그 키값에 대응하는 실제 데이터(파일 내용)에 대한 주소를 잎노드만이 가지고 있음
  • 직접 탐색은 잎노드에 도달해야 종료
  • 중간노드는 잎노드를 찾아가기 위한 징검다리 역할