장미나무

Rose tree
로도덴드론의 종류는 로도덴드론 최대값을 참조한다.

컴퓨팅에서 로즈 트리는 노드당 지점의 수가 무한하고 가변적인 트리 데이터 구조의 값을 일컫는 말이다.[1]이 용어는 기능 프로그래밍 커뮤니티에서 주로 사용되는데, 예를 들어, 버드-메르텐스 형식주의의 맥락에서 사용된다.[2]다분지 특성과는 별개로 장미나무의 가장 본질적인 특징은 정체성과 이등분하는 우연이다: 뚜렷한 두 개의 장미나무는 결코 이등분하지 않다.

이름 지정

장미 나무라는 이름은 램버트 메어튼스가 유사하게 이름붙여진, 그리고 비슷하게 구조화된 흔한 로덴드론을 환기시키기 위해 만든 것이다.[3]

우리는 이러한 나무를 로덴드론(그리스어 ῥόδ = = 장미, Δέδν = = = 나무)의 문자 그대로 번역한 장미나무라고 부를 것이다. 왜냐하면 이 관목의 습관과 유사하기 때문이다. 다만 후자는 북반구에서 거꾸로 자라지 않는다는 점을 제외하면 말이다.

재귀적 정의

근거가 충분한 장미 나무는 다음과 같은 유형의 실체를 재귀적으로 건설하여 정의할 수 있다.

  1. 기본 엔티티는 사전 정의된 접지 세트 V 값("팁[3]" 값)의 요소다.
  2. 분기 도면요소(대안, 포킹 도면요소 또는 포리스트 도면요소)는 다음 하위 유형 중 하나이다.
    1. 엔티티 집합.
    2. 일련의 엔티티.
    3. 미리 정의된 이름 집합 σ에서 엔티티로 부분 맵.

    (a)(b)(c) 중 어떤 것도 비워 둘 수 있다.(b)는 (c)의 특별한 경우로 볼 수 있으며, 시퀀스는 자연수 ℕ의 초기 세그먼트에서 나온 지도일 뿐이다.

  3. 페어링 엔터티는 F가 분기 엔티티이고 x는 "라벨" 값의 사전 정의된 집합 L의 요소인 순서 쌍(F, x)이다.연결실체는 분업실체만을 그 구성요소로 포함할 수 있으므로, 분업실체의 하위유형에 해당하는 하위유형(3a), (3b) 또는 (3c)로 유도분할이 있다.

일반적으로, 일부 조합의 기업 유형만 건설에 사용된다.원서에서는[3] 1+2b("시퀀스 포킹" 장미 나무)와 1+2a("세트 포킹" 장미 나무)만을 고려한다.후기 문헌에서 1+2b 변종은 보통 다음과 같은 정의로 도입된다.

데이터 트리 a = 노드 리프 [트리 a]

장미나무 [...]는 값을 포함하는 잎이나 임의의 하위 트리 목록을 가질 수 있는 노드 중 하나이다.[4]

기능 프로그래밍(특히 Haskell)에 사용되는 가장 일반적인 정의는 3+2b를 조합한다.

데이터 장미 α = 노드 α [장미 α]

로즈 α의 원소는 하위 트리의 목록과 함께 라벨이 표시된 노드로 구성된다.[1]즉, 장미나무는 짝을 이루는 개체(타입 3)이며, 가지체는 장미나무의 순서(2b타입)이다.

때로는 조합 1+3b도 고려된다.[5][6]다음 표는 가장 확립된 기업결합에 대한 요약을 제공한다.

용어. 사용된 도면요소
근거가 충분한 집합 (2a)
근거가 충분한 중첩 목록 값 (2b)(1)
근거가 충분한 중첩 사전 값 (2c)(1)
근거가 충분한 중첩 데이터 값 (2b)(2c)(1)
강제 실행에서 알려진 L-이름 (2a)(3)[w 1]
가장 상식적으로 근거가 있는 장미나무 (3)(2b)[w 1]

주의:

  1. ^ a b (2)a(3)와 (3)(2b) 조합의 경우, 두 번째 명시적 실체 유형은 중간 정도일 뿐이며, 첫 번째 명시적 실체인 "최종" 실체의 정의에 사용될 뿐이다.더욱이 유형들은 엄격히 교대로 이루어지며, 즉, 분업실체는 조합원으로써만 결합실체를 포함할 수 있다.

일반적 정의

일반 장미 나무는 노드와 화살표가 적절히 표시되어 있는 접근 가능한 뾰족한 다중 글자의 이등분선을 통해 정의할 수 있다.이러한 구조는 근거가 없는 집합 이론에서 접근 가능한 뾰족한 그래프(apg로 약칭)의 개념을 일반화한 것이다.우리는 아래에 설명된 다중글자 구조에 apq 약자를 사용할 것이다.이는 "접근 가능한 포인트 떨림"의 약어로, 여기서 떨림이 "멀티그래프"와 동의어로 정의된다.

재귀적 정의에 사용된 실체의 유형에 대한 대응에서 apq의 각 노드에는 유형(1), (2a), (2b), (2c) 또는 (3)이 할당된다.apqs는 재귀적으로 구성된 실체의 특성을 모방한 조건의 적용을 받는다.

    1. (1) 유형의 노드는 접지 값의 사전 정의된 집합 V의 요소다.
    2. (1) 유형의 노드는 화살표의 원본으로 나타나지 않는다.
    1. (3) 유형의 노드는 정확히 하나의 화살표의 소스로 나타난다.
    2. (a)에서 언급된 화살표의 대상은 (2) 유형의 노드다.
  3. 유형(2a)의 동일한 소스 노드가 있는 두 개의 구별되는 화살표는 구별되는 대상을 가진다.
  4. 노드는 유형 (3)인 경우 라벨을 표시한다.라벨은 사전 정의된 세트 L에 속한다.
    1. 화살표는 원본 노드가 유형(2b)인 경우 ℕ의 색인으로 라벨을 표시한다.
    2. 화살표의 소스 노드가 유형(2c)인 경우 화살표는 사전 정의된 집합 σ의 이름으로 라벨을 표시한다.
    3. 그렇지 않으면 화살표에 라벨이 표시되지 않는다.
  6. 동일한 소스 노드를 가진 화살표의 라벨은 구별된다.
  7. 타입(2b)의 동일한 소스 노드가 있는 화살표 라벨은 ℕ의 초기 세그먼트를 형성한다.

apqs 𝒳 = (X, ...)와 𝒴 = (Y, ...) 사이의 이등 유사성은 𝒳과 𝒴의 루트가 R과 관련되도록 노드 사이의 R ⊆ X × Y 관계이며, R 관련 노드의 모든 쌍(x,y)에 대해 다음과 같이 만족한다.

  1. x와 y 노드의 유형이 동일하다.
  2. x와 y가 (1) 유형이면 동일하다.
  3. x와 y가 (3) 유형인 경우, 동일한 라벨을 가진다.
  4. 소스 노드가 x인 𝒳의 모든 화살표 a에 대해 arrow의 화살표 b가 있으며, 소스는 y 및
    1. 의 대상 노드bR과 관련이 있고
    2. 와의 라벨b정의되는 경우 동일하다.

    대칭조건은 and과 𝒴의 상호교환으로 만족한다.

ap과 𝒴 두 개의 apqs는 그들을 위한 이등관계 R이 존재한다면 이등관계라고 한다.이것은 모든 apq의 등급에 동등성 관계를 설정한다.

장미 나무는 주어진 apq 𝒳과 이등분하는 apq의 class 등급을 고정적으로 표현한 것이다.𝒳의 루트 노드가 (1) 유형인 경우 𝒞 = {𝒳}이므로 𝒞은 이 루트 노드로 나타낼 수 있다.그렇지 않으면, Ⅱ는 적절한 등급이다. 이 경우, 최하위 등급의 Ⅱ의 요소 집합이 되는 스콧의 속임수로 대표성을 제공할 수 있다.

위의 설정-이론적 구성의 결과, 모든 장미 나무의 등급 Ⅱ는 확정 성분으로 설정된 V(접지 값), Ⅱ(화살표 이름), L(노드 라벨)에 따라 정의된다.그 후에 apq의 구조는 ℛ 위에 라벨이 붙은 다중글자 구조로 옮겨질 수 있다.즉, ℛ의 요소 자체는 유도형식 할당, 노드 라벨링 및 화살표가 있는 "노드"로 간주할 수 있다.화살의 등급 𝒜은 ( ( × ℛ) ∪ ( ( × ( ( × ×) × ×)의 하위 등급이다. 즉 화살표는 출처 유형에 따른 소스 대상 커플 또는 소스 라벨 대상 트리플이다.

ℛ의 모든 요소 r에는 ap의 루트 노드인 유도 apq , = (X, A, r, ...)가 있고, 𝒳의 각 세트 X와 𝒳의 노드와 화살표는 r과 𝒜의 요소들이 r에서 시작되는 화살의 경로를 통해 접근할 수 있다.유도 apq 𝒳은 r의 구성에 사용되는 apqs와 이등분하다.

경로명 맵

세트브랜칭 노드(타입 2a)가 없는 로즈 트리는 경로명 맵으로 나타낼 수 있다.경로 이름은 화살표 레이블의 유한 시퀀스에 불과하다.화살표 경로 a→ = [a1, ..., a](연속 화살표의 유한 순서)의n 경우 p의 경로명은 화살표 라벨의 해당 순서 σ(a→) = [ [(a1), ..., σ(an)]이다.여기서는 각 화살표에 라벨이 붙어 있는 것으로 가정한다(이것은 라벨링 함수를 나타낸다.일반적으로 각 화살표 경로는 먼저 페어링 노드(타입 3)에서 소싱되는 모든 화살표를 제거하여 축소해야 한다.

경로명 p는 루트 기원 화살표 경로 a→ 경로명이 p인 경우 확인 가능하다.그러한 a→는 라벨이 부착되지 않은 마지막 화살표(페어링 노드에서 제공)까지 고유하게 주어진다.비어 있지 않은 확인 가능한 경로의 대상 노드는 통신원 루트 기원 화살표 경로의 마지막 화살표의 대상 노드로서, 라벨링되지 않은 화살표로 끝나지 않는다.빈 경로의 대상은 루트 노드.

설정 지점화 노드를 포함하지 않는 장미 트리 r이 주어진 경우, r의 경로명 맵은 다음과 같은 일반적인 방식에 따라 각 확인 가능한 경로명 p 값을 할당하는 맵 t이다.

(ℕ dom dom dom)⁎ ⊇ 돔(t) t———→ (V ∪ {⊥} ∪ L) × T

ℕ ∪ ∪은 화살표 라벨의 집합( (은 자연수 집합, σ은 화살표 이름의 집합) L은 노드 라벨의 집합, V는 접지 값의 집합임을 상기한다.추가 기호 ⊥과 T는 각각 확인 가능한 경로명과 유형 태그 집합 T = {'1', '2b', '2c', '2c', '3b', '3c'의 표시기를 의미한다.t맵은 다음과 같은 처방으로 정의된다(x는 p의 대상을 나타낸다).

t(p) = (x, '1') x가 (1) 유형인 경우
(1998, '2b') 또는 (1998, '2c') x가 각 유형(2b) 또는 (2c)인 경우
(1998, '3b') 또는 (1998, '3c') x가 각 유형(3b) 또는 (3)c인 경우, and ℓ L은 x의 라벨이다.

장미나무마다 경로명 지도가 다르다는 것을 알 수 있다."동종" 장미 나무의 경우 유형 태그 지정이 필요하지 않으며, 그 경로 이름 맵 t는 아래에 요약한 것과 같이 정의할 수 있다.

용어. 계략
중첩 목록 값
ℕ⁎ ⊇ 돔(t)t———→V v {⊥}
중첩 사전 값 σ⁎ ⊇ 돔(t)t———→V v {⊥}
Haskell 옆 장미 나무, L 위로[7][8] 나무 ℕ dom⁎ 돔(t)t———→L[p 1]
L 값 트리,[9] L로[10] 표시된 트리 σ dom⁎ 돔(t)t———→L[p 1]

각 경우에 경로명의 관점에서 다음과 같은 간단한 공리화가 있다.

  1. 돔(t)은 ℕ⁎ 또는 σ의⁎ 비 빈 접두사 폐쇄 하위 집합이다.ℕ의⁎ 경우, 트리 도메인을 형성하려면 돔(t)도 "좌측 시블링-폐쇄"해야 한다. 자세한 내용은 시퀀스별 인코딩을 참조하십시오.
  2. 중첩된 목록이나 중첩된 사전 값의 경우, p가 돔(t)에서 최대값이 아닌 경로 이름인 경우 t(p) = ⊥.[p 2]

특히 가장 보편적인 "하스켈" 의미에서의 장미나무는 비 빈 접두사-폐쇄형 및 좌시블-폐쇄형 자연수의 유한 염기서열 집합에서 집합 L에 이르는 지도일 뿐이다.이러한 정의는 대부분 기능 프로그래밍의 분기 밖에서 사용된다. 트리(자동화 이론)를 참조하십시오.일반적으로 이 정의를 사용하는 문서에는 "장미나무"라는 용어가 전혀 언급되어 있지 않다.

주의:

  1. ^ a b 만일 돔(t)이 ℕ 또는 σ의 하위 집합에 대해 M이라면⁎, 경로명 맵 t는 입력 기호의 시퀀스를 무어 기계의 출력 기호로 매핑한 것이다.특히 입력 기호의 M 설정치가 initial의 초기 구간이고 모든 상태에 도달할 수 있는 무어 기계는 하스켈 감각의 장미 나무와 이등분한다. 근거가 없는 장미 나무의 예를 보라.중첩 사전(또는 목록)과 몰리 컴퓨터 간에 유사한 관계를 확인할 수 있다. 중첩 사전을 참조하십시오.
  2. ^ 중첩된 목록이나 중첩된 사전이 각각 목록이나 사전이 되도록 하려면 빈 경로명 p에 대해 t(p) = ⊥ 조건을 명시적으로 보유해야 한다.이것은 다음과 같은 경우를 단언한다.x = 5"나무 값"으로 간주되지 않는다.

예

아래 도표는 통신원 하스켈 코드와 함께 장미 나무의 두 가지 예를 보여준다.두 경우 모두 데이터.트리 모듈은[11] Haskell 컨테이너 패키지에 의해 제공되기 때문에 사용된다.[12]이 모듈은 다음과 같은 정의에 의해 장미나무를 페어링 실체로 도입한다.

자료 나무 a = 노드 {         rootLabel :: a,         -- ^ 라벨 값         하위 포리스트 :: [나무 a]   - ^ 0그 이상의 어린이 나무     }

두 사례 모두 장미나무의 특색인 "하위구조물 공유"[13]의 개념을 증명하기 위해 고안되었다.두 경우 모두 라벨링 함수는 주입식(레이블링)이다.'a','b','c'또는'd'일반적으로 충족될 필요가 없는 하위 트리/노드)를 고유하게 식별한다.화살표를 따라 있는 자연수(0,1,2 또는 3)는 나무가 나타나는 영점위치를 나타낸다.subForest특정 "슈퍼 트리"의 순서다음에서 가능한 반복의 결과로subForest노드 사이에 여러 개의 화살표가 있을 수 있다.각각의 예에서 문제의 장미나무는 다음과 같은 라벨을 붙인다.'a'그리고 그 가치와 같다.a암호에 있어서 가변적두 도표에서 모두 나무는 출처가 없는 화살표로 가리킨다.

Well-founded rose tree

근거가 있는 장미나무
수입하다 데이터.트리 본래의 :: IO () 본래의 = 하다 하게 하다 d = 노드 { rootLabel = 'd', 하위 포리스트 = [] } 하게 하다 c = 노드 { rootLabel = 'c', 하위 포리스트 = [d] } 하게 하다 b = 노드 { rootLabel = 'b', 하위 포리스트 = [d,c] } 하게 하다 a = 노드 { rootLabel = 'a', 하위 포리스트 = [b,c,c,c] } 인쇄하다 a

Non-well-founded rose tree

근거가 미비한 장미나무
수입하다 데이터.트리 본래의 :: IO () 본래의 = 하다 하게 하다 뿌리를 내리다 x = 케이스 x 의      'a' -> (x,[x,'b'])      'b' -> (x,[x,'c'])      'c' -> (x,[x,'a']) 하게 하다 a = explayTree 뿌리를 내리다 'a' putStrLn (받아들이다 900 (보여 주다 a)   ++ "…… (등등등)")

첫 번째 예는 근거가 있는 장미 나무를 보여준다.a증분 공사로 얻은먼저d구성, 그 다음c그때b그리고 마침내a장미나무는 왼쪽에 보이는 경로명 지도로 나타낼 수 있다.

두 번째 예는 근거가 없는 장미 나무를 보여준다.a광대한 제1의 건설자에 의해 건설된.unfoldTree장미 나무는 무어 기계 입니다. 위의 노트를 참조하십시오.경로명 맵 t : {0,⁎1} → {'a'',b'',c'}은(는) n mod 3에 따라 각각 'a' 또는 'b' 또는 'c'와 같도록 정의된다. 여기서 n은 p in 1의 발생 횟수다.

트리 데이터 구조 관련

일반 정의는 트리 데이터 구조에 대한 연결을 제공한다.

장미나무는 나무 구조로 이등분이다.

Values of tree data structures

트리 데이터 구조를 해당 값에 매핑

"나무 구조물"은 각 노드가 고유한 화살표 경로를 통해 접근할 수 있는 apqs이다.모든 장미나무는 그러한 나무 구조와 2등분하고(모든 apq는 펼쳐지는 것과 2등분하기 때문에), 모든 그러한 나무 구조는 정확히 하나의 장미 나무와 2등분하여 나무 구조의 가치로 간주될 수 있다.

오른쪽의 도표는 그러한 구조 대 가치 매핑의 예를 보여준다.다이어그램 상단에는 23개의 노드를 포함하는 노드 라벨 순서 트리 T가 표시된다.하단에는 T의 값인 장미 나무 R이 표시된다(T와 R 모두에서 형제 화살표는 왼쪽에서 오른쪽으로 암묵적으로 정렬된다).파란색 화살표로 부분적으로 표시되는 유도 하위 트리 대 하위 값 매핑이 있다.

매핑이 다대일 수 있는지 확인하십시오. 구별되는 트리 데이터 구조는 동일한 값을 가질 수 있다.특정한 결과로서, 일반적으로 장미 나무는 그 하위 값 사이의 "하위 값" 관계 측면에서 나무가 아니다. 자세한 내용은 #Terminological_controversis를 참조하십시오.

트리 데이터 유형

위에서 설명한 값 매핑을 사용하여 "나무 데이터 구조"와 "나무 데이터 유형" 사이의 차이를 명확히 할 수 있다.

트리 데이터 유형은 트리 데이터 구조의 값 집합이다.[dt 1]

용어 사이에는 2도의 차이가 있다는 점에 유의하십시오.이는 단일 트리 데이터 유형을 단일 트리 데이터 구조와 비교할 때 명백해진다.단일 트리 데이터 유형은 (무한) 많은 값을 포함하며, 각 값은 (무한) 많은 트리 데이터 구조로 표현된다.

예를 들어 L = {'a',b',c',d'}개의 라벨이 설정된 경우, L에서 가져온 라벨이 있는 하스켈 감지(3b)의 장미 나무 세트는 단일 트리 데이터 유형이다.위의 장미 나무의 모든 예는 이 데이터 유형에 속한다.

주의:

  1. ^ 그러나 트리 데이터 구조의 모든 값 집합이 트리 데이터 유형인 것은 아니다.

용어논란

위의 텍스트와 도표에서 볼 수 있듯이 장미나무라는 용어가 논란이 되고 있다.두 가지 상호 관련 문제가 있다.

  1. "노드"의 모호한 의미.
  2. "나무"와 "하위구조물 공유" 사이의 불일치.

흥미롭게도, "노드"라는 용어는 20페이지의 비공식 단락에서 "노드"가 단 한 번 발생하는 것을 제외하고는 원래의 논문에[3] 나타나지 않는다.후기 문헌에서는 그 말이 풍부하게 쓰인다.이는 이미 다음 정의에 대한 인용된 설명에서 확인할 수 있다.

  • 장미나무 [...]는 잎 [...] 또는 노드 [...][4]이다.
  • Rose α의 원소는 라벨로 표시된 노드[...][1]로 구성된다.

특히 가장 흔한 하스켈 의미에서의 장미나무의 정의는 (담론의 맥락 안에서) "노드"와 "나무"가 동의어임을 시사한다.그것은 모든 장미 나무가 그 뿌리 노드와 일치한다는 것을 의미하는가?그렇다면 그러한 성질은 장미나무에만 해당되는 것으로 간주되는가, 아니면 다른 나무에도 적용되는가?그런 질문은 풀리지 않고 있다.

(B) 문제는 위의 예시들을 보면 명백해진다.두 도표는 모두 각 노드가 정확히 한 번 그려진다는 점에서 충실하다.기초 그래프는 나무가 아님을 바로 알 수 있다.트리(그래프 이론)의 인용문 사용

컴퓨터 과학에서 나무라고 하는 다양한 종류의 데이터 구조는 그래프 이론에서 나무인 기초 그래프를 가지고 있다 [...]

일반적으로 장미 나무는 컴퓨터 과학에서 알려진 일반적인 의미의 나무가 아니라고 결론 내릴 수 있다.

베이시안 장미나무

컴퓨터 과학에서 "하위 구조의 공유"가 배제되는 "장미 나무"라는 용어가 적어도 한 가지 채택되고 있다.베이지안 장미 나무의 개념은 장미 나무의 다음과 같은 정의에 기초한다.

T는 일부 데이터 지점 x에 대해 T = {x}이거나 데이터 지점의 분리 집합i 위에 있는 T = {T1nT, ... ,T}인 경우 장미 트리입니다.[14]

참조

  1. ^ a b c Bird, Richard (1998). Introduction to Functional Programming using Haskell. Hemel Hempstead, Hertfordshire, UK: Prentice Hall Europe. p. 195. ISBN 0-13-484346-0.
  2. ^ Malcolm, Grant (1990). "Data structures and program transformation". Science of Computer Programming. 14 (2): 255–279. doi:10.1016/0167-6423(90)90023-7.
  3. ^ a b c d Meertens, Lambert (January 1988). "First steps towards the Theory of Rose Trees" (PDF). {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)
  4. ^ a b Bird, Richard; Gibbons, Jeremy (2020). Algorithm Design with Haskell. Cambridge University Press. ISBN 9781108491617.
  5. ^ Skillicorn, David B. (1996). "Parallel implementation of tree skeletons" (PDF). Journal of Parallel and Distributed Computing. 39 (2): 115–125. doi:10.1006/jpdc.1996.0160.
  6. ^ Seemann, Mark. "Church-encoded rose tree".
  7. ^ Morawietz, Frank (2008). Two-Step Approaches to Natural Language Formalism. Walter de Gruyter. ISBN 9783110197259.
  8. ^ Kosky, Anthony (1995). Transforming Databases with Recursive Data Structures (Thesis).
  9. ^ Niwiński, Damian (1997). "Fixed point characterization of infinite behavior of finite-state systems" (PDF). Theoretical Computer Science. 189 (1–2): 1–69. doi:10.1016/S0304-3975(97)00039-X.
  10. ^ Dagnino, Francesco (2020). "Coaxioms: flexible coinductive definitions by inference systems". Logical Methods in Computer Science. 15. arXiv:1808.02943. doi:10.23638/LMCS-15(1:26)2019. S2CID 51955443.
  11. ^ "Data.Tree".
  12. ^ "containers: Assorted concrete container types".
  13. ^ Gibbons, Jeremy (1991). Algebras for Tree Algorithms (PDF) (Ph.D.). Oxford University.
  14. ^ Blundell, Charles; Whye Teh, Yee; Heller, Katherine A. (2010). Bayesian rose trees (PDF). 26th Conference on Uncertainty in Artificial Intelligence.