kdtree를위한 C++에서 키 집합을 구현하는 방법

Question

k -d 트리가되도록 조정 된 B + 트리를 구현해야합니다. 에 대한 설명으로, k -d 트리는 노드에 여러 값을 갖는 키인 여러 값을 갖는 점을 제외하면 이진 트리와 같습니다. 그리고 그것은 또한 B + tree가 될 것입니다. 내부 노드는 키의 값인 중 하나만 저장하려고하고 실제 데이터는 리프 노드에 저장됩니다. 여기의 짧은 그래픽 설명입니다 :

내 잎 노드가이 개 요소에 대한 공간이, 내가 세 번째를 추가하고 내가 분할을해야합니다까지 잘 작동 처음 2 모두를 추가 할 때. 그 때문에, 내가 키의 첫 번째 값을 순서를 정의하는 값으로 선택하기 때문에 나는 모든 세 요소의 중간 값을 으로 가져오고 결과는 모두 27이므로 모든 요소는 보다 작고 왼쪽으로 이동합니다. 오른쪽보다 크거나 같은 사람들.

톰과 린다가 이미 리프 노드를 완료 (27)보다 나이가 있기 때문에 내가 4 요소를 추가

는, 아들은 추가 돔, 다시 을 분할 노드를 만들지 만 이번에는 내가 키의 어떤 값을 전환해야 사회 보장 번호 (Social Security Number) 순서를 정의합니다. 다시 나는 중앙값을 취하고 그 결과는 530이므로, 은 SS 번호가 530 미만인 모든 사람들이 왼쪽으로가는 식입니다.

내부 노드 의 인덱스로서 특정 키 값과 최종 K -d 트리 생성하고, 리프 노드에서 완전한 키.

지금 내 질문은 컨텍스트를 설명 한 후 키를 구현할 수 있습니다. 리프 노드에 키를 저장해야하지만 내부 노드에서는 하나만 사용합니다. 키의 값 중 하나입니다.

값이 여러 개인 필드 이있는 데이터베이스와 유사 함을 확인할 수 있으며 동일한 필드에서 서로 시간, 다음보다 중요한 정보를 정렬 할 수 있습니다.

나는 모든 값을 포함하는 것이, 위의 예를 들어, 이름에 대한 연령 int 및 int SSNumber 및 string이 될 수 부가 요소와 더불어, class 이름 Key 또는 다른 이름을 생각했다. 하지만 내 문제는 내 고객이 그가 에 더 많은 값을 추가하려고한다고 결정하면 내 수업이 점점 더 커질 것입니다. 이건 좋은 OO 결정입니까? 이 방법을 다른 방식으로 구현해도 OO가 될 수 있습니까? 내 상상력이 좋지 않다는 것을 알고 있지만 클라이언트가 더 많은 값을 원한다고 생각할 수 있기 때문에 은 내 값을 보유하는 일종의 목록을 만들 수 있습니다. 그런 다음 데이터 유형을 지원할 수있는 목록을 만들기 위해 을 가질 수 있습니다. OO 처럼 들리지는 않습니다. 어떤 아이디어?

또한 트리의 알고리즘 중 일부 지점에서 나무의 색인으로 사용하기 위해 키의 1 속성을 사용해야합니다. 도 지원해야합니다.

나는 OO 접근 방법을 따라이 문제를 해결하는 방법에 대한 아이디어를 정말 고맙게 생각합니다.

Answer 1

은 KeyPart의 배열이 다음 키 값 (연령, SS 번호)의 각 유형은 KeyPart에서 서브 클래스 수 Key합니다. 그런 다음 트리의 각 내부 노드에는 하나의 KeyPart과 키 부분 색인 (어떤 부분이 분할인지 알기 위해)을 저장할 수 있습니다. 잎은 전체 Key을 저장할 수 있습니다.