2
노드가 0에서부터 많은 자식을 가질 수있는 트리 구조가있는 경우 각 노드가 부울 스위치와 함께 일부 데이터 값을 보유하고 있는데 어떻게 특정 스위치 값을 가진 노드에 대해이 트리의 상태를 최소한으로 나타낼 수 있습니까?어떻게 체크 트리의 체크 상태를 최소한으로 표현합니까?
다음A[0] -> B[1] -> C[1]
|-----> D[1]
|-----> E[1]
우리가 4 개 노드가 확인 된 상태를, 간결한 방식으로이 상태를 표현하는 방법이있다 : 예를 들어
, 내 나무 같이 보입니다이라고? 순진한 접근법은 네 개의 노드를 검사하는 것으로 나열하는 것이지만 노드 B가 네 개가 아닌 100 개의 자식을 갖는다면 어떨까요?
현재 나의 생각은 각 노드의 조상을 데이터 구성 요소에 저장하고 상태를 나타내는 데 필요한 데이터를 최소화하는 조상 집합으로 확인 된 상태를 설명하는 것입니다. 아래 나무에서 노드 N의 조상은 n '으로 표현됩니다. 당신이 나무를 분석하고 노드 A의 모든 아이가 선택되어 있는지 확인하고 데이터 요소 노드가 '로 설정되어 간단하게 상태를 설명 할 수 이제
A[0, {a}] -> B[1, {a', b}] -> C[1, {a' b' c}]
|--------------> D[1, {a' b' d}]
|--------------> E[1, {a' b' e}]
: 같은 위의 나무는 지금 뭔가를 보일 것이다 1, 또는 [a ']. 노드 D의 상태가 0으로 전환 된 경우 트리 상태를 [a 'not d]로 설명 할 수 있습니다.
이 유형의 문제를 해결하는 데 사용할 수있는 데이터 구조 또는 알고리즘이 있습니까? 더 나은 접근 방법에 대한 생각? 분석 알고리즘에 대한 생각은 없습니까?
감사합니다.
이 체크 트리가 정확히 무엇입니까? 어떤 종류의 작업이 지원됩니까? 속도 또는 메모리 사용 공간을 최적화합니까? 속도가 가장 많이 사용되는 작업입니까? –
체크 트리는 새 소프트웨어를 설치할 때 나타나는 기능 트리와 마찬가지로 사용자가 선택한 노드 목록입니다. 나중에 재구성해야하는 상태를 나타 내기 위해 사용되며, 이는 생성 시간 후에 삽입 및 삭제가 필요하지 않음을 의미합니다. 메모리는 자유롭고 속도는 상대적으로 무료입니다 (그러나 O (n^2)를 피하기를 원합니다). 최적화해야하는 것은 체크 트리의 상태를 재구성하는 데 필요한 데이터의 양입니다.따라서 노드 B에 100 개의 하위 항목이 있고 99 개의 항목이 선택되면 99 개의 데이터 요소를 사용하여이 상태를 설명하지 않아야합니다. – Victor
트리 구조가 있으므로 이미 부울을 재구성하고 싶습니까? –