병합,하지만 내가 생각할 수있는 최선의 복잡성은 다른 트라이의 값의내가 두 개의 트라이 구조를 병합 할 두 개의 이진 트라이를
가져 오기 목록입니다 O (N), n은 트라이의 노드 수입니다. 목록에서 모든 값을 삽입합니다. 대상 트라이 : n * O (m), m은 키의 길이입니다. 최악의 경우 키의 크기는 n이며 병합 O (n^2)의 복잡성은 아닙니다.)?
더 좋은 방법이 있습니까?
복잡성은 O (N + M)가 될 것입니다. 두 개의 이터레이터 (트리 노드 포인터)가 각각 트리의 루트 노드에서 시작해야합니다.
아이가 반복기 중 하나에있을 경우 아이를 봅니다. 그러면 아이를 결과로 직접 복사합니다 (아이를 직접 이동할 수있는 경우 (포인터를 더 잘 할당 할 수있는 경우). 자식이 양쪽에 있으면 해당 자식에서 함수를 재귀 적으로 호출합니다.
이렇게하면 모호한 노드를 병합하는 데만 시간을 소비하고 한 번에 전체 하위 트리를 복사/이동할 수 있습니다.
원래 아이디어를 실행하면 복잡성은 O (N * M)가되며 여기서 N은 항목 수이고 m은 항목의 평균 길이입니다. O (N^2)를 얻지는 않습니다. 왜냐하면 모든 노드가 단일 엔트리 (최악의 경우)를 위해서라면 그 엔트리를 한 번만 복사해야하기 때문입니다.
(추천 수정) 트리의 하위 집합 인 trie (https://en.wikipedia.org/wiki/Trie)를 병합하는 절차가 있으면 실제로 관심이 있습니다. 그러나 좀 더 구체적으로하려고했습니다. – Davar
예. 더 좋은 방법이 있습니다. 트라이가 나무라는 사실을 이용하십시오. 즉, 나무와 뿌리가 있습니다. 어떻게 이런 것들을 병합 하시겠습니까? –
@ n.m. 어쩌면 두 나무를 동시에 가로 지르며 그 값이 있는지 확인할 수 있습니다. – Davar