이진 트리의 목록 구현이 확장 가능합니까?

간단한 코덱을 쓰고 있습니다. 트리는 사전 계산되어 빌드가되면 변경되지 않습니다. 그것은 단지 검색 될 것입니다.이진 트리의 목록 구현이 확장 가능합니까?

균형 이진 트리의 모든 리프 노드는 신호 값이고 내부 노드는 근사화 된 압축 된 표현입니다.

잎 노드가 큰 경우 stl 벡터를 사용하여 목록 구현을 확장 할 수 있습니까? 현재 대형 대형 얼마나 큰지 모르겠다.

목록 구현 예. 1,2,3,4,5,6,7 나는 네 잎 노드

이있는 경우 다음

root(1)-> 2,3 
2->4,5 
3->6,7

의 아이들은 그래서 단순히 벡터에서의 위치를 사용하여 아이들에게 이동할 수 있습니다.

출처

2012-05-23 Anonymous

왜이 세부 정보 (목록 구현 방법)를 클래스 '클라이언트에 공개해야합니까? 성능 문제가있는 경우 (현재 또는 미래이지만 테스트는 어떻게 든 필수 사항입니다) 간단히 구현 et-voila를 변경하십시오 (예 : 중개자 포함). –

"목록"또는 "배열"을 사용하면이 경우 트리가 변경되지 않으므로 문제가 발생하지 않습니다. O (log n) 검색의 유일한 요구 사항은 빠른 임의 접근 (즉, 주어진 색인에 대한 O (1) 액세스)입니다.

vector 또는 deque 중 하나를 사용할 수 있습니다. 둘 다 적합합니다. 시스템이 모든 요소를 보유 할만큼 충분한 메모리 블록을 찾지 못한다면, 확장 성 문제로 vector을 실행할 수 있습니다. 그러나 시작은 더 간단해야합니다. 이로드 블록을 쳤다면 deque으로 전환하십시오. 속도가 다소 떨어질 수는 있지만 조각난 성질로 인해 더 커질 수 있습니다.

출처

2012-05-23 07:43:31

deque는 O (1)에서 임의 액세스를 제공하지 않습니다. –

@HimadriChoudhury : 표준에 정확하게 연결할 수 없으므로 최선을 다할 것입니다. SGI [deque] (http://www.sgi.com/tech/stl/Deque.html)는 [랜덤 액세스 컨테이너] (http://www.sgi.com/tech/stl/RandomAccessContainer.html)를 모델로합니다. 복잡성 보장 "요소 액세스의 런타임 복잡성은 상각 된 일정 시간으로 상각됩니다." –

@Matthiew. 링크를 가져 주셔서 감사합니다. 나는 그것이 deque에 대한 무작위 액세스가 어떻게 지정되었는지를 몰랐습니다. 내 경험에 비추어 볼 때, 랜덤 액세스는 벡터보다 deque에서 상당히 느리다. 예를 들어, gcc 3.4.6을 사용하는 제 리눅스 박스에서, 10M int 벡터로부터 10M int를 무작위로 합하는 것은 약 0.4 초에서 돌아 갔고, deque에서는 .9sec였습니다. –

런타임시 빠른 액세스를 위해 모든 트리 노드가 지속적으로 힙에 위치하는 단순한 이유 때문에 MAX_ELEMENTS가 MAX_ELEMENTS 인 트리 노드 (주로 초기화시 malloced)를 선호합니다.

내가 말했다 빠르게 액세스 주로 포인터 (예를 들어 32 비트 수를 넘쳐) 당신은 그것을

볼 수 있습니다 목록에있는 요소의 정말 엄청난 수의 분산 STL 벡터 요소가 일정하지 않을 수 있습니다 점프 때문에 캐시 라인에서 L1 캐쉬 액세스에서 누락 프로세서의 관점.

출처

2012-05-23 07:53:52

이진 트리의 목록 구현이 확장 가능합니까?

답변

관련 문제