- Apter Trees in C++
- [노드값, 부모인덱스) 두개의 벡터만 사용하여 단순하게 표현한 트리
- 대부분의 트리는 이진 트리처럼 구현되며,각 노드가 자신의 값과 왼쪽/오른쪽 자식노드에 대한 포인터를 포함
- 이런 데이터 구조는 재귀로 구현해야 하고, 캐시 동작 및 빈번한 malloc()으로 인해 속도가 느려질수 있음
- 누가 트리 노드를 '소유'하는 지에 대한 개념은 멀티레이어 소프트웨어에서는 복잡해 질수 있음
- Apter 트리는 훨씬 빠르고, 추론하기 쉬우며, 구현하기 쉬움
동작 방식
- 크기가 같은 두개의 배열로 구현
- 데이터의 벡터(배열) d
- 부모 인덱스의 벡터 p. d 벡터의 인덱스가 키로 사용됨(c)
- 종종 키/인덱스 c 는 정수형
- Coco 가 Molly 와 Arca의 부모이고, Arca가 Cricket이라는 자식이 있다면 아래와 같은 구조가 됨
tree.d = ["Coco", "Molly", "Arca","Cricket"]
tree.p = [0,0,0,2]
- 부모가 0이면서 키가 0인 노드가 루트노드 (Apter 트리는 루트노드가 필수이거나 또는 -1 이 "부모 없음"을 의미하지만 여기서는 무시)
- 컴퓨터는 벡터를 매우 빠르게 조작할 수 있음. 포인터 연산보다 훨씬 빠르기 때문에 알고리즘에 대한 빅-O 표기법을 비교하는 것은 실제로는 의미가 없음
중요성
- 이 구현 방식은 본인이 본 트리 구현 방식 중 가장 우아함
- 적절한 벡터 연산 라이브러리를 사용하면 이해하기 쉽고 버그를 찾기 쉬움
- 간단함으로 인해 다른 사용 시나리오에 쉽게 적용 가능
- 부모 인덱스 벡터를 무시하고 값들을 빠르게 반복할 수 있으며, 이는 무료로 사용가능한 Deep Map과 같음
- GPU 친화적이며, 임베디드 환경에서 사용하기 쉬움
- 벡터의 크기를 특정 크기 이상으로 성장하지 않게 함으로써 보안을 쉽게 유지할 수 있음
기원
- 이 기술을 발명한 사람을 찾기 위해 노력 중이며, 60년대와 70년대 벡터 지향적인 시기에 이미 이름이 있었을 것으로 추측함.
- Apter가 설명한 대로 처음 완전한 설명을 보았지만, K3에서도 널리 문서화되었음
- APL은 전통적인 방식으로 트리를 구현하지만, 벡터 그래프에 대해 유사한 기술을 사용함
- J 사용자들에게도 알려져 있으며, Rosetta Code의 J 언어 트리 구현에 대한 설명이 있음
- John Earnest는 벡터 트리 구현에 대해 더 자세히 설명하며, "오프셋 인덱스" 접근 방식을 포함하여 삭제 항목에 대해 설명함.
- 더 복잡한 접근 방식은 각 항목의 깊이를 추적하는 것임
다른 일반적인 트리 구현
- FreeBSD의 커널 트리 구현, klib의 트리, Ruby의 트리 클래스, Python 선언적 트리 클래스 등이 있음
- 이들은 Apter 트리와 동일한 기능을 수행하지 않으며, 일부는 일반화로 인해 훨씬 더 큼
이 코드의 현황
- C++17을 배우기 위해 이를 구현해보는 시도를 함.
- 아직 사용 준비가 되지 않았으며, C++에 대해 더 많이 배울 필요가 있음.
GN⁺의 의견
- Apter Trees는 기존의 복잡한 트리 구조를 단순화하여 빠르고 효율적인 데이터 관리를 가능하게 함.
- 벡터 기반의 트리 구현은 메모리 오버헤드를 최소화하고, 선형적인 접근을 통해 성능을 향상시킬 수 있음.
- 이 기사는 소프트웨어 엔지니어링에서 데이터 구조의 혁신적인 접근 방식을 탐구하는 데 흥미로움을 제공함