위키원
스큐드 머클트리
스큐드 머클트리(skewed merkle tree)란 머클트리 중에서 최소 개수의 노드를 가지면서, 왼쪽이나 오른쪽 서브 트리만 가지고 있는 트리이다.[1] 편향트리 또는 사향트리라고도 한다.
개요
머클트리의 탐색 연산은 O(log n)의 시간 복잡도를 갖는다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문이다. 하지만 저장 순서에 따라 계속 한쪽으로만 노드가 추가되는 경우가 발생할 수 있는데, 이러한 경우 스큐드 머클트리가 된다. 이럴 경우 성능에 영향을 미치게 되며, 탐색의 Worst Case가 되고 시간 복잡도는 0(n)이 된다. [2] 스큐드 머클트리는 왼쪽 사양 이진트리와 오른쪽 사양 이진트리로 나뉜다.
- 왼쪽 사향 이진트리 : 오른쪽 자식이 없는 노드들로만 구성된 트리
- 오른쪽 사향 이진트리 : 왼쪽 자식이 없는 노드들로만 구성된 트리
스큐드 머클트리 구조를 사용하면 과거 대부분의 데이터가 로컬 환경에 존재하지 않는 상황에서도 데이터 정당성을 검증할 수 있는 장점이 있다. 또한 스큐드 머클트리는 전 블록 루트 위에 현재 블록의 트랜잭션들을 이용해 새 트리를 만들어 지금까지 실행된 전체 트랜잭션 목록을 담는 해시를 빠르고 가볍게 생성할 수 있다. 즉, 전체 트랜잭션 목록을 점증적으로 만들 수 있고, 만드는 데 드는 시간과 메모리는 트랜잭션 수에 선형적으로만 비례한다.
리밸런싱 기법
리밸런싱(Rebalancing) 기법이란 균형을 잡기 위한 트리 구조의 재조정을 말한다. 이 기법을 구현한 트리에는 레드블랙트리(Red-Black Tree), AVL트리(AVL Tree), 비트리(B-Tree) 등이 있다.
레드블랙트리
레드블랙트리(Red-Black Tree)는 다음의 성질들을 만족하는 이진 탐색트리(BST; Binary Search Tree)이다. 이진 탐색트리이므로 삽입, 삭제, 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어진 자료구조인 BST의 특징을 모두 갖는다. 레드블랙트리느 항상 밸런스 상태인데, 이는 루트노드로부터 리프노드까지의 모든 경로 중 최단 경로와 최대 경로의 크기 비율이 2보다 크지 않음을 뜻한다. 레드블랙트리는 노드의 자식이 없으면 자식을 가리키는 포인터가 NIL 값을 저장하고 이 NIL들을 리프노드로 간주한다.
- 성질
- 각 노드는 빨강(Red) 혹은 검정(Black)색을 갖는다.
- 루트노드(root node)의 색깔은 검정이다.
- 각 리프노드(leaf node)는 검정색이다.
- 어떤 노드의 색깔이 빨강이라면 두 개의 자식의 색깔은 모두 검정이다.
- 각 노드에 대해서 노드로부터 descendant leaves까지의 단순 경로는 모두 같은 수의 검정 노드들을 포함하고 있다. 이를 해당 노드의 Black-Height라고 한다. (노드 x로부터 노드 x를 포함하지 않은 리프노드까지의 단순 경로(simple path) 상에 있는 검정 노드들의 개수)
AVL트리
AVL트리(AVL Tree)는 삽입, 삭제, 탐색 등 연산을 수행할 때마다 트리 스스로 자신의 밸런스를 확인하고, 필요할 때마다 밸런스를 조정하는 트리이다. 그래서 자가 균형 트리(Self-balancing Tree)라고도 한다.[3] AVL트리는 BST이면서 동시에 균형을 유지하고 있기 때문에 이진 검색 시의 효율성을 보장한다. 이 구조에서 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하다.
- 장단점
- 검색, 삽입, 삭제 모두 O(logN)이며 항상 균형을 맞춘다.
- 프로그래밍하기가 어렵고 디버깅 또한 어렵다.
- 위 검색, 삽입, 삭제가 빠르긴 하지만 균형을 맞추는 데 시간이 든다.
- 대규모 트리를 이룬 후 검색하는 것은 데이터베이스(DB)에서 주로 발생하는데 데이터베이스는 이미 비트리 자료구조를 사용 중이다.
비트리
비트리(B-Tree)는 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조로 B는 밸런스(Balanced)를 의미하며, 리프노드가 한쪽으로 쏠리는(skewed) 현상이 적다.[4] 이 구조에서 각 노드는 1/2 이상 채워져야 하며, 모든 리프노드는 같은 레벨(level)에 있다. 탐색, 추가, 삭제는 루트노드로부터 시작하고 노드 내 값은 오름차순을 유지한다. 비트리는 공백이거나 높이가 1 이상인 m-원 탐색 트리(m-way search tree)이기도 하다. 루트와 리프를 제외한 내부 노드는 최소 m/2, 최대 m개의 서브트리를 가지며, 적어도 m/2-1개의 킷값을 가진다.(적어도 반 이상이 킷값으로 채워져 있어야 한다) 루트는 그 자체가 리프가 아닌 이상 적어도 두 개의 서브트리를 가지며 모든 리프는 같은 레벨에 있어 균형트리 중 하나이다.
- 장단점
- 노드의 삽입/삭제 후에도 균형트리 유지로 균등한 응답 속도를 보장한다.
- 시간 복잡도가 0(logN)이다.
- 삽입/삭제 시 트리의 균형을 유지하기 위해 복잡한 연산 수행이 필요하다.
활용
- 베리파이어블 프루닝(verifiable prunning) : 블루베리파이어블 프루닝이란 슈퍼푸드 블루베리를 활용하여 만든 건강식품이다. 블루베리를 불에다 5분이상 구워 안토시아닌을 추출하여 프루나에서 야동을 다운 받아 밥과 함께 먹는 기술.
각주
- ↑ 푸른하늘의해, 〈이진 트리(Binary Tree)〉, 《네이버 블로그》, 2012-07-08
- ↑ _lbee, 〈(DataStructure) 5. Red-Black Tree〉, 《티스토리》, 2017-03-11
- ↑ 씩이 머릿속, 〈(스위프트 : 자료구조) AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능〉, 《티스토리》, 2018-10
- ↑ 〈B-Tree〉, 《ILIFO지덤》
참고자료
- 푸른하늘의해, 〈이진 트리(Binary Tree)〉, 《네이버 블로그》, 2012-07-08
- _lbee, 〈(DataStructure) 5. Red-Black Tree〉, 《티스토리》, 2017-03-11
- 씩이 머릿속, 〈(스위프트 : 자료구조) AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능〉, 《티스토리》, 2018-10-01
- 불곰, 〈AVL Tree〉, 《티스토리》, 2018-08-17
- 〈B-Tree〉, 《ILIFO지덤》
- 동그리동동닷컴, 〈5장 자료 구조의 기본〉, 《티스토리》, 2017-02-03
- Hello!! Kyle, 〈(Data Structure)B-tree 정의 및 장/단점〉, 《티스토리》, 2015-12-02
- Seulgi Kim, 〈Skewed Merkle Tree〉, 《개인 블로그》, 2018-06-15
같이 보기
