제이슨 키스 마크가 OCaml의에 대한 튜토리얼을 읽고 여기에 짧은 나무를 구축 제안 된 방법입니다거야 구축 새 요소가 삽입 된 트리의 일부로이 새 복사본에 오래된 트리의 일부를 연결 하시겠습니까?OCaml의 이진 트리
그렇다면 각각의 삽입이 O(height(tree)) 노드 만 제대로 생성한다는 내 평가입니까?
많은 비트 값을 하나씩 삽입하면 노드 그룹의 모든 이전 사본이 GC에 의해 효율적으로 삭제된다는 사실에 의존합니까?
이 접근법은 트리의 새 요소가 삽입 된 부분의 복사본을 만들고 이전 트리의 일부를이 새 복사본에 연결한다는 것을 올바르게 이해합니까?
그렇다면 각 삽입은 O (높이 (트리)) 노드 만 제대로 생성한다는 내 평가입니까?
예. 트리의 균형을 제대로 맞추면 (예 : 빨강 - 검정 나무) 삽입이 O (log (n))임을 의미합니다.
많은 비트 값을 하나씩 삽입하는 경우 노드 그룹의 모든 이전 사본이 GC에 의해 효율적으로 삭제된다는 사실에 의존하고 있습니까?
예. 함수형 프로그래밍 언어는 일반적으로 수명이 짧은 쓰레기를 많이 생성합니다. 튜플, 클로저 및 작은 데이터 유형 값이 포함됩니다. 그러나 구현을 매우 저렴하게 (예 : 경량 힙 표현, 포인터 범프 할당 및 세대 별 수집을 통해) 최적화합니다.
또한이 접근법에는 하나의 근본적인 이점이 있습니다. 기능적 데이터 구조는 자동으로 으로 지속됩니다. 즉, 이전 버전이 유효하고 여러 버전의 데이터 구조가 동시에 사용될 수 있습니다. 명령형 데이터 구조를 사용하면 이전 버전을 "복원"해야 할 때 두 가지 옵션이 있습니다. (1) 전체 구조 구조를 미리 복사하거나 (2) 변경 로그를 유지하고이를 뒤로 실행하십시오. 두 가지 옵션 모두 지속성이 무료 인 기능적 구조를 사용하는 것보다 비용이 많이 든다.
복잡성, 상각 된 비용 및 다양한 기능적 데이터 구조의 다양한 측면에 대한 자세한 내용은 Chris Okasaki의 우수 도서 Purely Functional Data Structures을 참조하십시오. (그의 내용은 대부분 thesis이며, 무료로 제공됩니다.)