좌자 우회전 바이너리 트리

Left-child right-sibling binary tree
바이너리 트리로 표현되는 육엽수

컴퓨터 과학에서 연구된 모든 다방향 또는 k-ary 트리 구조는 이진 트리로서의 표현을 허용하며, 이는 아이-자매 표현,[1] 왼쪽-자매 표현, 오른쪽-자매 이진 트리,[2] 이중 사슬 트리 또는 효자 사슬을 [3]포함한 다양한 이름으로 통한다.

멀티웨이 트리 T를 나타내는 바이너리 트리에서 각 노드는 T의 노드에 대응하고 2개의 포인터를 가진다.하나는 노드의 첫 번째 아이에, 다른 하나는 T의 다음 형제에게.따라서 노드의 자녀는 단일 링크 리스트를 형성합니다.노드 n의 k번째 아이를 찾으려면 다음 목록을 탐색해야 합니다.

프로시저 kth-child(n, k): child ← n.child 반면 k and 0 및 child ≠ null: child ← child.next-child k ← k - 1 return child //가 0을 반환할 수 있습니다.
이중 체인 트리로 구현된 트라이: 수직 화살표는하위 포인터, 점선된 수평 화살표는 다음 포인터입니다.시행은 에지 레이블로 지정되며, 이 표현에서는 에지 레이블이 이진 노드에서 노드 레이블이 됩니다.

k-ary 트리에서 LC-RS 이진 트리로 변환하는 프로세스를 Knuth [4]변환이라고도 합니다.이 방법으로 임의의 k-ary 트리에서 바이너리 트리를 형성하려면 원래 트리의 루트가 바이너리 트리의 루트가 됩니다.그런 다음 루트에서 시작하여 원본 트리에서 각 노드의 왼쪽 끝자리가 이진 트리에서 왼쪽 자식으로, 원본 트리에서 오른쪽 가장 가까운 형제자리가 이진 트리에서 오른쪽 자식으로 됩니다.

이중 사슬 나무들은 에드워드 H에 의해 묘사되었다. 1963년 [5]서센구스.

k-ary 트리를 LC-RS 바이너리 트리로 처리하면 모든 노드가 링크되고 왼쪽 자식과 정렬되며 다음으로 가까운 노드가 형제입니다.예를 들어, 아래에는 삼원 트리가 있습니다.

1                  / \                 /   \                /     \               2   3   4              / \                    5   6     7                      / \                     8   9

왼쪽 자식 노드를 부모 노드보다 한 단계 아래, 형제 노드를 같은 수준으로 자식 옆에 배치하면 선형(같은 선)으로 다시 쓸 수 있습니다. 

1                  /                 /                /               2---3---4              /       /             5---6   7                    /                   8---9

각 형제자매를 [6]시계 방향으로 45° 돌리면 이 트리를 이진 트리로 변환할 수 있습니다. 

1                /               2              / \             5   3              \   \               6   4                  /                 7                /               8                \                 9

사용 사례

LCRS 표현은 기존 멀티웨이 트리보다 공간 효율이 높지만 노드의 하위 항목을 인덱스로 조회하는 데 시간이 걸립니다.따라서 LCRS의 표현은 다음과 같은 경우에 바람직하다.

  1. 메모리 효율이 중요.
  2. 노드의 하위 항목에 대한 랜덤 액세스는 필요하지 않습니다.

사례 (1)은 대규모 다방향 트리가 필요한 경우, 특히 트리에 대량의 데이터 세트가 포함되어 있는 경우에 적용된다.예를 들어 계통수를 저장할 경우 LCRS 표현이 적합할 수 있습니다.

사례 (2)는 트리 구조가 매우 구체적인 방법으로 사용되는 특수한 데이터 구조에서 발생한다.예를 들어 멀티웨이 트리를 사용하는 많은 유형의 힙 데이터 구조는 LCRS 표현을 사용하여 공간을 최적화할 수 있습니다(예: 피보나치 힙, 페어링 힙 및 취약 힙).그 주된 이유는 힙 데이터 구조에서 가장 일반적인 조작은

  1. 트리의 루트를 제거하고 각 트리의 하위 항목을 처리합니다.
  2. 한 나무를 다른 나무의 아이로 만들어 두 나무를 결합하라.

조작 (1) 매우 효율적입니다.LCRS 표현에서는 형제자매가 없기 때문에 트리가 올바른 아이를 가지도록 구성되므로 루트를 쉽게 제거할 수 있습니다.

조작(2)도 효율적입니다.두 나무를 [7]결합하는 것은 쉽다.

레퍼런스

  1. ^ Fredman, Michael L.; Sedgewick, Robert; Sleator, Daniel D.; Tarjan, Robert E. (1986). "The pairing heap: a new form of self-adjusting heap" (PDF). Algorithmica. 1 (1): 111–129. doi:10.1007/BF01840439.
  2. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 214–217. ISBN 0-262-03293-7.
  3. ^ Public Domain이 문서에는 NIST 문서의 퍼블릭 도메인 자료가 포함되어 있습니다.
  4. ^ 컴퓨터 데이터 구조존 L. 팔츠
  5. ^ Sussenguth, Edward H. (May 1963). "Use of tree structures for processing files". Communications of the ACM. 6 (5): 272–279. doi:10.1145/366552.366600.
  6. ^ "binary tree representation of trees". xlinux.nist.gov. Retrieved 2015-11-24.
  7. ^ "What is the left-child, right-sibling representation of a tree? Why would you use it?". stackoverflow.com. Retrieved 2016-12-12.