2
배송에 데이터를 저장하는 바이너리 검색 트리를 작성한 경우 검색 키는 음향 서명입니다.int 배열을 키로 사용하는 이진 트리 (유클리드 거리)?
트리를 검색 할 때 올바른 서명이있는 선박이나 검색된 서명과 가장 일치하는 선박을 반환하고 싶습니다. (가장 가까운 유클리드 거리를 가진 선박을 보는 것).
내가 겪고있는 문제는 실제 수치가 아닌 다른 서명을 비교하는 방법입니다. 그렇다면 수행 된 모든 검색은 순차적이며 2 진수가 아님을 의미합니까?
아이디어가 있으십니까?
트리를 형성 할 때 순서 체계를 선택하고 A 노드의 키로 서명 A를, B 노드의 서명 B로 끝난다 고 가정합니다. 그러한 서명 쌍에 대해서, 나무가 형성된 후에, A로부터의 유클리드 거리가 B보다 더 큰 인공적인 서명을 만들 수 있습니다. (B의 서명과 매우 가까운 서명을 선택하십시오. 서명). 따라서 B가 A의 왼쪽 하위 트리에 있어야합니다. – ely
그게 문제가되는 경우에만 데이터에 이진 검색을 사용할 수있는 방법을 볼 수 없습니다. 나무가 아니라면/나무/순차 검색 (모든 유클리드 거리를 계산하는 곳)에 있습니다. – lex
문제는 이진 검색 트리는 트리가 생성 될 때 노드의 순서가 고정되어 있다고 가정하고 나중에 트리에서 인덱싱/검색을 위해 변경되지 않습니다. 변화하는 순서로 요소를 검색 할 수 있기를 원한다면 올바른 데이터 구조가 아니며 변수 쿼리 서명과의 유클리드 거리는 순서 변경으로 간주됩니다. 쿼리가 변경되면 저장된 데이터의 순서가 변경됩니다. 당신은 주문을 바꾸는 데 드는 벌금을 최소화하는 구조가 필요합니다. 아래 답변은 합리적인 Kd- 나무를 제안했습니다. – ely