0
here 비슷한 질문이있는 것 같지만 대답의 명확성이나 실용성에 만족하지 않았습니다. 나는 최근 인터뷰에서 어떤 데이터 구조를 사용하여 큰 숫자의 부동 소수점 숫자를 저장하여 내가 그 자체 또는 가장 가까운 이웃을위한 새로운 도착을 찾도록 요청 받았다. 바이너리 검색 트리를 사용하여 O (log n)를 달성하기 위해 균형을 이루도록했습니다.효율적인 검색을 위해 좌표를 저장하는 데 가장 적합한 데이터 구조입니까?
다음 질문은 두 가지 차원으로 확장되었습니다. 빠른 검색을 위해 지리적 좌표와 같은 (x, y) 쌍의 큰 세트를 저장하는 데 사용할 데이터 구조는 무엇입니까? 나는 만족스러운 대답을 생각할 수 없었고, K- 차원까지 확장했을 때 완전히 포기했다. 좌표 값을 사용하여 직접 공간을 "분할"하는 k 차원 트리를 사용하면 원점 근처에있는 두 개의 가까운 점이 있지만 다른 사분면의 내부에는 멀리 떨어져있는 나뭇잎으로 끝날 수 있으므로 작동하지 않는 것 같습니다.
인터뷰 후, 나는 K 차원 공간을 멋지게 분할하기 위해 보로 노이 다이어그램을 기억했다. 어떤 데이터 구조를 사용하여 이것을 구현하는 가장 좋은 방법은 무엇입니까? 룩업은 어떻게 수행 될까요? 나는이 질문이 마치 컴퓨터 과학에서 흔히있는 것처럼 느껴진다. 지금은 심지어 전용 데이터 구조조차 가지고있다.
부동 소수점의 경우 이진 검색 트리부터 시작합니다. 그 병목 있다면 정수 부분을 (또는 그 개념을 따라 무언가를 해시로 전환). 지리적 좌표의 경우 좌표 벡터 벡터 또는 유사한 좌표 벡터 벡터 해시 벡터를 가질 수 있습니다. –