핑거 트리

Finger tree
이진 검색 트리는 핑거 검색 트리를 참조하십시오.

컴퓨터 과학에서 핑거 트리는 다른 기능 데이터 구조를 효율적으로 구현하는 데 사용될 수 있는 순수 기능 데이터 구조다.핑거 트리는 상각된 상각된 시간 동안 데이터가 저장되는 트리의 "손가락" (leaves)에 대한 액세스 권한을 부여하고, 로그 시간을 작은 조각 크기로 연결 및 분할한다.또한 각 내부 노드에 그 후손에 대해 일부 연관 작업을 적용한 결과를 저장한다.내부 노드에 저장된 이 "요약" 데이터는 나무 이외의 데이터 구조의 기능을 제공하는 데 사용될 수 있다.

개요

상각 O(1) put & get 작업이 있는 단순 대기열로 사용되는 핑거 트리.1에서 21까지의 정수를 오른쪽에 삽입하여 왼쪽에서 추출한다.사각형 블록은 값을 나타내며, "Digit"(하늘색)은 1-4명의 자녀를 가질 수 있고, "Node"(노드)는 2-3명의 자녀를 가질 수 있으며, 흰색 원은 "Flem"을 나타내며, 빨간색 노드는 "Single" 값을 나타내며 녹색 노드는 "Deep" 값을 나타낸다.각 단계에 대해 단일 값과 자릿수 아이들은 새로운 수준의 노드로 내포된다는 점에 유의하십시오.

Ralf Hinze와 Ross Paterson은 핑거 트리는 상각된 상각된 일정한 시간 안에 끝부분에 접근할 수 있는 영구적인 시퀀스의 기능적 표현이라고 말했다.연결과 분할은 로그 시간으로 작은 조각의 크기로 이루어질 수 있다.구조는 또한 일반적인 형태로 분할 연산을 정의함으로써 범용 데이터 구조로 만들 수 있으며, 추상적인 데이터 유형의 다른 종류 중에서 시퀀스, 우선 순위 대기열, 검색 트리 또는 우선 순위 검색 대기열로 작용할 수 있다.[1]

손가락은 데이터 구조의 일부에 접근할 수 있는 지점이다. 명령어로는 이것을 포인터라고 부른다.[2]핑거 트리에서 손가락은 시퀀스 끝, 즉 잎 마디를 가리키는 구조다.손가락이 원래 트리에 추가되어 손가락에 일정한 시간 동안 접근할 수 있도록 한다.아래 그림에서 손가락은 척추에서 노드로 뻗은 선이다.

핑거 트리는 척추를 따라 있는 노드로 식별할 수 있는 서로 다른 층으로 구성되어 있다.나무의 척추는 나무들이 잎과 뿌리를 가진 것과 같은 방식으로 줄기로 생각할 수 있다.손가락 나무는 종종 척추와 가지들이 옆구리에서 떨어져 나와 보여지지만, 실제로 이 중심 척추를 만들기 위해 쌍을 이룬 각 레벨의 척추에는 두 개의 노드가 있다.접두사는 척추 왼쪽에 있고 접미사는 오른쪽에 있다.각각의 노드는 뿌리에 도달할 때까지 다음 단계의 척추에 연결된다.[2]

2-3 tree and it transformed into a finger tree
2-3 트리(상단)를 핑거 트리(하단)로 끌어올릴 수 있음을 나타냄

트리의 첫 번째 레벨은 오직 값, 트리의 잎 노드만을 포함하고 있으며 깊이는 0이다.두 번째 단계는 깊이 1이다.세 번째는 깊이 2 등이다.뿌리에 가까울수록 노드가 가리키는 원목(손가락 트리 이전의 나무)의 하위 트리는 깊다.이렇게 해서, 나무를 내려가는 일은 나뭇잎에서 나무의 뿌리까지 가는 것인데, 이는 전형적인 나무 데이터 구조와는 정반대인 것이다.이렇게 멋지고 특이한 구조를 얻기 위해서는 원목의 깊이가 균일하게 되도록 해야 한다.깊이가 균일하도록 하려면 노드 개체를 선언할 때 하위 개체의 유형에 따라 매개 변수를 지정해야 한다.깊이 1 이상의 척추에 있는 노드는 나무를 가리키며, 이 매개변수를 사용하면 중첩된 노드로 나타낼 수 있다.[3]

트리를 핑거 트리로 변환

우리는 균형 잡힌 2-3 나무로 이 과정을 시작할 것이다.핑거 트리가 작동하려면 모든 리프 노드도 수평이 되어야 한다.

손가락은 "특이한 위치 근처의 나무 노드에 효율적으로 접근할 수 있는 구조"[1]이다.핑거 트리를 만들기 위해서는 나무의 오른쪽과 왼쪽 끝에 손가락을 대고 지퍼처럼 변형시켜야 한다.이것은 우리에게 연속적으로 상각된 시간들이 수열의 끝에 접근할 수 있게 해준다.

변환하려면 균형 잡힌 2-3 트리부터 시작하십시오.

나무의 가장 왼쪽과 가장 오른쪽 내부 노드를 잡고 위로 당겨서 나머지 노드가 오른쪽 이미지에 표시된 대로 그 사이에 매달려 있도록 하십시오.

가시를 결합하여 표준 2-3 핑거 트리를 만든다.

이를 다음과 같이 설명할 수 있다.[1]

자료 핑거트리 a = 비어 있음                        싱글 a                        깊은 (숫자 a) (핑거트리 (노드 a)) (숫자 a) 자료 노드 a = 노드2 a a   노드3 a a a

표시된 예제의 숫자는 문자가 있는 노드들이다.각 목록은 척추에 있는 각 노드의 접두사 또는 접미사로 나눈다.변환된 2-3 트리에서, 최상위 단계의 숫자 목록은 길이가 2, 3이고 하위 레벨의 길이는 1, 2인 것으로 보인다.핑거 트리의 일부 적용이 매우 효율적으로 실행되기 위해 핑거 트리는 각 레벨에서 1-4개의 하위 트리 사이를 허용한다.핑거 트리의 자릿수는 다음과 같은 목록으로 변환할 수 있다.[1]

타자를 치다 숫자 a = 하나 a   두 개 a a   셋 a a a   4개 a a a a

그리고 이미지에서, 상단 레벨은 타입 a의 요소를 가지고 있고, 그 다음 레벨은 척추와 잎사귀 사이에 있는 노드가 있기 때문에 타입 node a의 요소를 가지고 있으며, 이것은 일반적으로 트리의 n번째 레벨은 타입 d 깊이 n의 2-3 트리를 가지고 있다는 것을 의미할 것이다.이는 n 원소의 시퀀스가 깊이 θ(log n)의 트리로 표현됨을 의미한다.더욱이 가장 가까운 끝에서 원소 d가 위치하는 것은 트리의 depth(log d) 깊이에 저장된다.[1]

할인

디큐 작업

핑거 트리는 또한 효율적인 데케를 만든다.구조가 지속적이든 아니든, 모든 영업은 Ⅱ(1) 상각시간이 걸린다.이 분석은 오카사키의 암묵적인 데케와 비교할 수 있는데, 유일한 차이점은 핑거트리 타입이 쌍 대신 노드를 저장한다는 것이다.[1]

적용

핑거 트리는 다른 나무를 만드는 데 사용될 수 있다.[4]예를 들어, 우선 순위 대기열은 트리에 있는 하위 노드의 최소 우선순위로 내부 노드에 라벨을 붙여 구현하거나, 인덱스 목록/어레이는 하위 노드의 잎 수를 기준으로 노드 라벨링으로 구현할 수 있다.다른 애플리케이션은 아래에서 설명하는 랜덤 액세스 시퀀스, 순서 순서 및 인터벌 트리가 있다.[1]

핑거 트리는 상각된 O(1) 푸시, 후진, 펑핑, O(log n) 추가 및 분할을 제공할 수 있으며, 색인화 또는 순서 순서에 맞게 조정할 수 있다.그리고 모든 기능적 데이터 구조와 마찬가지로, 그것은 본질적으로 지속적이다; 즉, 오래된 버전의 트리는 항상 보존된다.

랜덤 액세스 시퀀스

핑거 트리는 랜덤 액세스 시퀀스를 효율적으로 구현할 수 있다.이것은 n번째 요소에 접근하고 특정 위치에서 시퀀스를 분할하는 것을 포함한 신속한 위치 조작을 지원해야 한다.이를 위해 손가락 나무의 크기에 주석을 달았다.[1]

뉴타입의 크기 = 크기{ getSize :: N }   기발한 (이크, 서드)  예시 모노이드 크기 어디에   ∅ = 크기 0   크기 m ⊕ 크기 n = 크기 (m + n)

N은 자연수를 위한 것이다.그 타입은 서로 다른 모노이드의 운반체이기 때문에 새로운 타입이 필요하다.아래에 표시된 순서의 원소에는 여전히 또 다른 새로운 유형이 필요하다. 

뉴타입의 엘렘 a = 엘렘{ getElem :: a } 뉴타입의 Seq a = Seq (핑거트리 크기 (엘렘 a))  예시 측정했다. (엘렘 a) 크기 어디에     엘렘   = 크기 1

이 코드 선들은 인스턴스가 크기 측정에 기본 케이스가 되고 원소가 크기 1이라는 것을 보여준다.새로운 유형의 사용은 하스켈에서 런타임 페널티를 유발하지 않는다. 왜냐하면 도서관에서 사이즈와 엘렘 타입은 래퍼 기능이 있는 사용자로부터 숨겨지기 때문이다.

이러한 변화로, 시퀀스의 길이는 이제 일정한 시간으로 계산될 수 있다.

초간행물

핑거 트리는 레오니다스 J. 기바스에 의해 1977년에 처음 출판되었고,[5] 그 이후로 주기적으로 정제되었다(예: AVL 트리를 사용한 버전,[6] 레이지 않은 핑거 트리, 여기에 표시된 보다 단순한 2~3개의 핑거 트리,[1] B-Trees 등).

구현

핑거 트리는 그 이후 Haskell 핵심 라이브러리에서 사용되어 왔다(데이터 구현 시).시퀀스) 및 OCaml에서의 구현이 존재하며[7], 이는 검증된 Coq 구현에서 도출되었다.[8]하스켈어 등(기능적) 언어의 프로그램이 생성될 수 있는 ISabelle(proof assistant)에서도 검증된 구현이 있다.[9]핑거 트리는 게으른 평가가 있든 없든 구현이 가능하지만 게으름 때문에 구현이 간단하다.[10]

참고 항목

참조

  1. ^ a b c d e f g h i Hinze, Ralf; Paterson, Ross (2006), "Finger Trees: A Simple General-purpose Data Structure" (PDF), Journal of Functional Programming, 16 (2): 197–217, doi:10.1017/S0956796805005769.
  2. ^ a b Gibiansky, Andrew. "Finger Trees - Andrew Gibiansky". andrew.gibiansky.com. Retrieved 2017-10-26.
  3. ^ "Finger Trees Done Right (I hope)". Good Math, Bad Math. Retrieved 2017-10-26.
  4. ^ Sarkar, Abhiroop. "Finger Tree - The ultimate data structure?". abhiroop.github.io. Retrieved 2017-10-26.
  5. ^ Guibas, L. J.; McCreight, E. M.; Plass, M. F.; Roberts, J. R. (1977), "A new representation for linear lists", Conference Record of the Ninth Annual ACM Symposium on Theory of Computing, pp. 49–60.
  6. ^ Tsakalidis, A. K. (1985), "AVL-trees for localized search", Information and Control, 67 (1–3): 173–194, doi:10.1016/S0019-9958(85)80034-6.
  7. ^ 캠 위클리 뉴스
  8. ^ 마티외 소조 : Coq의 의존형 핑거트리
  9. ^ Nordhoff, Benedikt; Körner, Stefan; Lammich, Peter. "Finger Trees". Archive of Formal Proofs. Retrieved 26 November 2021.
  10. ^ Kaplan, H.; Tarjan, R. E. (1995), "Persistent lists with catenation via recursive slow-down", Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pp. 93–102.

외부 링크