다음은 이진 검색 트리에 대한 간략한 개요입니다.
이진 검색 트리는 최대 두 개의 자식 노드를 가질 수 있습니다.
단, 자식 노드를 3개로 늘리면 이진 탐색 트리와 동일하게 데이터를 삽입, 편집, 삭제할 수 있다.
내가 그것에 대해 무엇을 할 수 있습니까 ???
왼쪽 BST의 왼쪽 하위 트리에 있는 모든 노드는 50보다 작고 오른쪽 하위 트리에 있는 모든 노드는 50보다 큽니다.
오른쪽에 3개의 자식 노드가 있더라도 동일한 규칙성을 갖도록 노력해 봅시다.
우선 자식 노드가 3개이므로 BST가 2인 경우와 달리 각 노드와 부모 노드의 크기 관계는 3이다.
즉, 왼쪽 자식 노드부터 시작하여 다음과 같이 정의한다. (참고로 이 경우 부모 노드가 2개여야 합니다.)
1) SubTree < k1 : 왼쪽 하위 트리의 모든 노드가 k1보다 작습니다.
2) k1 < SubTree < k2 : 중간 하위 트리는 k1보다 크고 k2보다 작습니다.
3) k2 < 하위 트리: 오른쪽 하위 트리의 모든 노드가 k2보다 큽니다.
( 상위 노드 수 = 하위 노드 수 -1 )
자식 노드를 3개 이상으로 늘려야 하는 경우 위와 같이 트리를 만들고 BST와 유사한 데이터를 삽입합니다.
검색 및 삭제할 수 있습니다. (이 점에서 B-Tree는 BST의 일반화 트리라고도 함)
이 형태로 작동하는 나무 B트리그것은 말한다.
B-Tree의 4가지 주요 매개변수(주로 각 노드의 키 수와 자식 수에 관한 것)
키 수와 B-트리 노드의 자식 수 사이의 관계(주로 각 노드의 키 수와 자식 노드 수에 관한 것입니다)
B-Tree 데이터 삽입
B-tree 데이터를 삽입할 때 다음 두 가지만 기억한다면 연산 방식을 이해하는 데 문제가 없다.
1. 항상 리프 노드에 키 값을 추가하십시오.
2. 삽입 시도 시 노드 수가 오버플로(최대 키 수 초과)되면 중간 키를 기준으로 왼쪽 및 오른쪽 키를 분할하고,
중간 키격려하다
B-Tree 데이터 삽입 예
먼저 최대 자식 수가 3인 3차 B-트리의 예를 제공합니다.
(Tertiary -> 최대 3개의 하위 노드 -> 노드당 최대 2개의 키 값 )
1) 1과 15를 삽입하자.
항상 리프 노드에 키 값 추가
오름차순으로 잘 정렬되어 있습니다.
2) 2를 더하자
키 값은 항상 잎에 추가
단, 키값의 최대 개수는 2개이지만 현재 키값은 3개이며, 노드가 오버플로되었습니다.
노드가 오버플로되면 가운데 버튼인 2를 기준으로 왼쪽과 오른쪽 버튼 즉 1(왼쪽)과 15(오른쪽)를 공유하고,
중간 키 2를 부모 노드로 승격합니다. 결과는 아래와 같습니다.
3) 5를 더하자
에 추가 항상 리프 노드키 값 5는 루트 노드에서 크기를 비교하고 5가 입력되어야 하는 리프 노드를 찾습니다.
5가 가는 리프 노드를 찾아 오름차순으로 정렬하고 붙여넣습니다.
3) 30을 더한다
50이 가는 리프 노드를 찾아 붙여넣습니다.
그러나 넘치는 노드가 있기 때문에 중간 키 15를 부모 노드로 승격시키고 5(왼쪽 키)와 30(오른쪽 키)을 공유한다.
4) 사실 이후에 90을 더했다고 가정하면 20을 더하자!
20이 추가되었습니다.
하지만 넘쳐나는 노드가 있기 때문에 분할과 승격을 해야 하고 그 결과는 아래 그림과 같습니다.
다시, 상위 노드가 오버플로되었습니다.
노드가 넘쳐나기 때문에 균등하게 분할하고 승격해야 합니다.
그런데 여기서 특이한 점이 있습니다.
즉, 4개의 하위 노드가 있습니다. 현재 우리는 3차 B-트리를 만들고 있으므로 4개의 자식 노드가 없어야 합니다.
이에 다음과 같이 분할 및 승격을 실시한다.
5) 7.9 추가!
6) 8, 10 더하기
7) 50.70 더하기
8) 60.40 추가
참고로 B-Tree의 기능 중 하나로
모든 리프 노드는 동일한 수준에 있습니다. 이것이 의미하는 바는 이것입니다.
-> 균형 트리: BST는 편향 트리인 경우 최악의 경우 시간 복잡도 0(N)이지만 B-트리는 균형
최악의 경우에도 시간 복잡도는 O(logN)입니다.