바이너리 트리를위한 효율적인 어레이 스토리지

Question

바이너리 트리의 노드를 파일에 써야합니다. 바이너리 트리를 작성하는 가장 공간 효율적인 방법은 무엇입니까? 부모 위치가 i이고 자식이 2i, 2i+1 인 배열 형식으로 저장할 수 있습니다. 그러나 이것은 희소 한 이진 나무의 경우에 많은 공간을 낭비 할 것입니다.

Answer 1

내가 선호하는 방법 중 하나는 선주문 탐색을 저장하는 것이지만 거기에는 'null'노드도 포함됩니다. 'null'노드를 저장하면 트리의 inorder를 저장할 필요가 없습니다. 이 방법의

일부 장점

• 당신은 더 나은 저장을 할 수있는 사전/사후에 비해 + 대부분의 실제 경우에 방법 중위.
• 직렬화는 단지 한 번의 탐색을 필요로합니다.
• 직렬화 해제는 한 번에 수행 할 수 있습니다.
• 트리를 구성하지 않고 in-pass 탐색을 한 번 수행 할 수 있습니다. 상황에 따라 호출이 유용 할 수 있습니다.

예를 들어 64 비트 정수의 이진 트리가 있다고 가정하면 각 노드가 다음 노드가 널 노드인지 여부를 나타내는 추가 비트를 저장할 수 있습니다. 첫 번째 노드는 항상 루트입니다. 널 (Null) 노드는 단일 비트로 나타낼 수 있습니다.

n 노드가있는 경우 공간 사용량은 널 노드의 경우 8n 바이트 + n-1 인디케이터 비트 + n + 1 비트 = 66 * n 비트가됩니다.

이전/이후 + inorder에서 16n 바이트 = 128 * n 비트를 사용하게됩니다.

따라서이 pre/post + inorder 메소드에 62 * n 비트의 공간을 절약 할 수 있습니다.

트리를

 100 
    / \ 
    / \ 
    /  \ 
    10  200 
/\  /\ 
. .  150 300 
     /\ /\ 
     . . . . 

고려 '를.' 널 노드입니다.

당신은 지금 100 10 . . 200 150 . . 300 . .

로 직렬화합니다 '널 ​​(null)와 전순 주사'(서브 트리 포함) 널 (null) 노드의 수 = 노드의 수는 1

이것은 당신이 만들 수 있습니다 + 재산이있는 각 최초의 노드가 트리의 루트이기 (위해) 때문에, 직렬화 된 버젼을 1 회의 패스로 지정하면

100 (10 . .) (200 (150 . .) (300 . .)) 

당신이 (노드와 팝을 볼 때 목록에 스택을 사용하고 밀어 중위 순회를 만들려면 : 따라 노드는이 같은 것으로 볼 수있다 바로 다음에 왼쪽 하위 트리입니다) null을 볼 때. 결과리스트는 inorder traversal입니다 (이에 대한 자세한 설명은 여기에서 찾을 수 있습니다 : C++/C/Java: Anagrams - from original string to target;).

Answer 2

파일에 in-order 및 pre/post-order 이진 트리 순회를 저장하고 이러한 통과에서 트리를 재구성 할 수 있습니다.

Answer 3

(거의) 완전한 트리가있는 경우 2i, 2i + 1 (이진 힙) 방법이 실제로 가장 좋은 방법입니다.

그렇지 않으면 각 노드에 부모 색인 (부모 색인)을 저장하지 않아도됩니다.

Answer 4

XML에 대해 생각해보십시오. 그것은 일종의 나무 직렬화입니다. 예 :

<node id="1"> 
    <node id="2">         1 
    </node>          / \ 
    <node id="3">        2  3 
     <node id="4">        /\ 
     </node>          4 5 
     <node id="5"> 
     </node> 
    </node> 
</node> 

그런 다음 공백과 태그가 필요한 이유는 무엇입니까? 우리는 단계로, 단계를 생략 할 수 있습니다 :

<1> 
    <2></> 
    <3> 
    <4></> 
    <5></> 
    </> 
</> 

는 공백을 제거 <1><2></2><3><4></><5></></></>합니다.

제거 꺾쇠 괄호 : 12/34/5///

이제 문제가 : 노드가 비어있는 왼쪽 하위 트리와 비어 있지 않은 권리 서브 트리를 무슨 경우? 그런 다음 다른 특수 문자 '#'을 사용하여 빈 왼쪽 하위 트리를 나타낼 수 있습니다. 예를 들어

: 1#23/// :

1 
/ \ 
     2 
    /\ 
    3 

이 나무는 다음과 같이 직렬화 할 수 있습니다.