어휘집 k-ary 깊이가 L 인 트리 데이터 구조를 사용하여 계층 적 k-means 클러스터링을 반복적으로 실행 한 결과입니다. 클러스터에 할당 된 데이터 포인트 수가 클러스터 수보다 작은 경우 클러스터링 프로세스가 중지 될 수 있으므로 불균형 구조입니다.행렬에 불균형 트리를 저장하는 방법
제 문제는이 트리를 매트릭스 형식으로 저장해야한다는 것입니다.
간단히 말해서 노드를 실제 순서대로 저장하는 것에 대해 생각했지만 실제 노드 수와 노드의 이론적 인 개수가 증가하면 메모리 낭비가 너무 클 수 있습니다. 이다
n << (1-k^L)/(1-k)
효율적으로 메모리를 낭비하거나 덜 가능한 낭비없이 매트릭스 형태 불평형 트리를 저장하는 방법이 있는가?
공간을 낭비하지 않는 것이 좋습니다. 그러나 리프에 대한 공간이 항상 할당되는 경우 (일부 경우에 유용함), N이 N의 개수 인 경우 상당히 단순한 접근법이 아래에 요약되어 있으며 O (N log_k N) 공간 또는 O (k N log_k N) 만 필요합니다. 트리에서 요소입니다. 비용은 요소에 액세스하는 데 O (log_k N)가 필요하다는 것입니다.
정확한 구현은 다양한 요인에 따라 다소 다양합니다. 아이디어는 간단히 균형 잡힌 이진 트리의 표현을 배열로 일반화하여 불균형 n- 트리를 행렬로 사용하는 것입니다. 이것은 행렬 셀을 노드로 사용함으로써 수행됩니다. 노드에 포함 된 정보는 데이터 구조가있는 단일 셀에 있거나 다음 몇 개의 셀에 분산되어있을 수 있습니다. 주요한 점은 각 노드가 특정 노드에 대한 정보와 노드의 정보를 포함해야한다는 것입니다. 증 분식 포인터는 그 다음에 아이들을위한 다음 무료 스팟이 위치한 곳을 추적하는 데 사용됩니다.
전체적으로 r * c 요소보다 작거나 같은 배열이며 r 행과 c 열의 행렬로 나뉩니다. 행 L이 깊이 L에 노드를 포함하기 때문에 목록의 목록이 더 유용 할 수 있습니다. 그렇지 않으면 많은 유용성이 없습니다.