텐더민트 IAVL 트리에 대해서 알아보자(1)

IAVL 트리의 특징

IAVL트리는 코스모스/텐더민트 생태계에서 이더리움의 패트리샤 트라이와 같은 역할을 하는 자료구조입니다. IAVL 트리는 스냅샷을 찍을 수 있으며 AVL 트리의 알고리즘을 응용해서 정렬되어 있고 언제나 균형을 유지할 수 있도록 고안되었습니다. 복잡도는 O(lon(n))입니다. IAVL 트리는 데이터 저장소임과 동시에 머클트리로써의 기능도 있습니다. IAVL 트리는 간편한 이진 트리이기 때문에 머클 패트리샤 트라이보다 머클 증명을 더 효율적으로 할 수 있습니다.

패트리샤 트라이와의 차이점

패트리샤 트라이는 이더리움에서 사용됩니다. 패트리샤 트라이는 스마트 컨트랙트에서 공격자가 트라이의 균형을 의도적으로 최악의 경우로 만들어서 read/write 시 부하를 주는 공격이 가능합니다. 그래서 이더리움의 스마트 컨트랙트에서는 이를 방지하기 위해서 값을 저장할 때 key를 해쉬하고 저장하게 됩니다. 그래서 key를 해쉬할 때 약간의 오버헤드가 있으며 이터레이터의 사용이 불가능합니다. 하지만 IAVL트리는 자동으로 균형을 유지하기 때문에 이러한 문제가 없습니다.

알고리즘

IAVL 트리는 일반적인 트리와는 다르게 값은 오직 잎 노드만이 가지고 있습니다.

처음 키가 3인 값을 넣었을 때의 경우 당연히 이렇게 될 것입니다.

그 후 키가 4인 값을 넣으면 어떻게 될까요?

키가 3인 노드의 오른쪽 자식으로 새로운 노드를 만드는게 아니라 새로운 루트 노드를 만들면서 각각의 노드를 루트 노드의 자식으로 만들었습니다. 오직 잎 노드만이 값을 가진다는 것을 기억하세요.

그 이후 키가 1인 값과 키가 2인 값을 순서대로 넣어보겠습니다.

이렇게 될 것입니다. 하지만 이 시점에서 균형이 무너졌습니다.

이 경우는 LL(Left Left)의 경우입니다. 이때 서브트리에서 불균형이 발생한 노드를 오른쪽으로 회전시켜줍니다.

이렇게 하면 균형이 맞춰집니다.

LR(Left Right)의 경우를 살펴보기 위해서 새로운 IAVL 트리를 만들고 키가 1, 4, 2, 3인 값을 순서대로 넣는다고 생각해봅시다. 그러면 이렇게 불균형한 트리가 만들어질 것입니다.

이 트리를 균형을 맞추기 위해서 먼저 불균형이 발생한 노드의 왼쪽 노드를 왼쪽으로 회전시켜줍니다.

그러면 이렇게 될 것입니다. 하지만 여기서 오른쪽 결과물도 여전히 불균형합니다. 하지만 이것은 위의 LL의 경우와 동일합니다. 그러므로 LL에서 했던 것처럼 오른쪽으로 회전시켜줍니다.

이러면 균형이 맞춰지게 됩니다.

RR(Right Right)와 RL(Right Left)는 위의 경우와 정확히 반대이기 때문에 생략하겠습니다.

IAVL 트리에 대해 간략히 알아보았습니다. IAVL 트리는 블록체인을 위해 고안된 트리로 자동으로 균형이 맞춰지는 것과 머클 트리 이외에도 Immutable한 속성과 스냅샷 기능 등이 있습니다. 또한 일반적인 이진 머클 트리에서는 불가능한 비존재 증명이 가능합니다. 다음 시간에 이에 대해서 더 자세히 알아보겠습니다.

감사합니다.