2 개의 b-tree가 동일한 값을 가질 수 있지만 다른 모양을 가질 수 있다는 것을 알고 있으면 값을 검토하고 두 개의 트리가 모두 동일한 지 비교하는 알고리즘이 있습니다. 같은 열쇠?2 개의 b-tree를 비교하여 동일한 값이 포함되어 있는지 확인하십시오.
다른 키가 포함되어 있으면 가능한 한 빨리 해결할 수 있어야합니다.
추측과 동시에 두 b- 트리에서 조회를 수행하지 않으면 재귀 알고리즘이 작동하지 않을 수 있습니다.
알고리즘이 b 트리를 가로 지르는 것을 보았습니다. 그러나 두 가지를 모두 통과 한 다음 키를 비교하고 싶지는 않습니다. 차이가있을 경우 가능한 한 빨리 빠져 나갈 수있는 더 똑똑한 것을 원합니다.
기본적으로이 함수는 true/false를 반환합니다.
근본적인 기술은 어쨌든의 순차적 탐색에서 현재 지점을 나타내는 개체를 갖는 것입니다. 트리의 각 인스턴스에 하나씩 두 개가 있으면 다음 키에 대해 펌핑을 계속하고 두 사람이 처음으로 다른 다음 키를 반환하면 완료됩니다.
C#에서는 한 번에 하나의 키를 생성하고 트리에있는 위치를 추적하는 탐색을 수행하기 위해 yield return을 사용합니다. 그 중 두 개를 SequenceEquals에 전달하면 첫 번째 차이점을 발견하자마자 빠져 나옵니다. 자바에서는 그 메커니즘을 직접 만들어야하지만 그렇게하기는 어렵지 않습니다.
b-tree을 의미한다고 가정하면 한 번에 두 번 반복하면됩니다. 두 iterator 사이의 편차는 내용이 다르다는 것을 증명합니다. 나무를 만들 때 더 많은 세부 정보를 수집하지 않으면 그보다 나은 알고리즘을 찾을 수있을 것 같지 않습니다.
당신이로 설명하는 b-tree에 대해 이야기하지 않는 경우 :
... A B-트리 데이터가 정렬 유지하고 검색, 순차 액세스, 삽입 할 수있는 트리 데이터 구조이며, 및 로그 시간의 삭제.
그런 다음 먼저 정렬 한 다음 트래버스해야합니다.
문제는 ** 반복 방법 **입니다. 예를 들어, DFS에서 둘 다 반복하면 올바른 결과를 얻지 못할 수 있습니다. 이진 트리에서는 순차적 인 순회가 필요하고 순서대로 두 개의 이진 트리를 반복합니다. B-Tree에서는, 내가 생각한 몇 가지 수정 사항이 있어야합니다. – amit
따라서 컴퓨터 과학에서 B- 트리는 데이터를 정렬 된 상태로 유지하고 검색, 순차 액세스, 삽입 및 삭제를 대수 시간으로 허용하는 트리 데이터 구조입니다. 따라서 그것은 본질적으로 정렬되어 있으므로 순차 반복은 사소합니다. – OldCurmudgeon
나는 그것을 할 수 있다고 동의하지만 사소한 것은 아니다. 트래버스이 "정렬 된"순서를 따르게하려면 이진 트리의 순차 트래버스 ('traverse (left), op (root), traverse (right)')를 수정해야합니다. 나는 그것이 복잡하지 않다는 데 동의하지만,이 기술에 익숙하지 않은 사람에게는 사소하지 않습니다. – amit
문제는 ** 반복 방법 **입니다. 예를 들어, DFS에서 둘 다 반복하면 올바른 결과를 얻지 못할 수 있습니다. 이진 트리에서는 순차적 인 순회가 필요하고 순서대로 두 개의 이진 트리를 반복합니다. B-Tree에서는, 내가 생각한 몇 가지 수정 사항이 있어야합니다. – amit
@ amit : 죄송합니다. 귀하의 의견에 혼란 스럽습니다. DFS는 * 탐색 * 기술이지 트래버스 * 기술이 아닙니다. 당연히 당신은 in-order traversal이 필요합니다; post-order 또는 pre-order traversal은 올바른 일을하지 않을 것입니다. 나는 나무가 특정 항목을 검색하는 것과 관련이 있는지 보지 못합니다. –
참고 순차적 탐색은 B- 트리에서 다를 수 있습니다. 하나 이상의 자식 ("순차적으로"라는 것은 이진 트리에서 오른쪽 아들을 가로 지르기 전과 왼쪽 아들을 가로 지른 이후이므로)이라는 점을 상기하십시오. B-tree로 수정하는 것이 큰 이슈는 아니지만이 기술에 익숙하지 않은 사람들에게는 사소한 일은 아닐 수도 있습니다. 나는 DFS가 아니라 선매를 분명히 의미했다. 혼란에 빠져서 미안하다. – amit