[Dynamic Tree With Subtree Query] 1.개요

 Dynamic Tree 자료구조 중 Link-Cut Tree는 Splay Tree의 특성상 임의의 노드 v의 서브트리의 정보가 올바르게 유지되지 않으며 이진 트리는 최대 2개의 자식만을 가질 수 있기 때문에 서브트리 쿼리를 다룰 수 없다.

 

 체인과 서브트리에 대해 모두 다룰 수 있는 Top Tree와 같은 자료구조는 구현이 매우 복잡하고 시간 복잡도의 상수도 꽤 크기 때문에 실질적으로 잘 사용하지 않는다.

 

 이진 트리의 자식은 최대 2개까지만 존재할 수 있으므로 3개 이상의 자식을 가진 노드를 고려하기 위해 virtual children과 virtual tree라는 개념을 도입하자.

이 때 splay tree 상에서 바로 연결된 자식 노드를 real children이라 부르며 트리에서 노드의 자식 노드는 여러개 존재할 수 있기 때문에 3개 이상의 자식 노드를 가지면 real children이 아닌 자식 노드는 virtual children에 속하거나 자식 virtual tree에 속하게 된다. 이진 트리인 virtual tree의 균형을 유지하기 위해 virtual children이 존재하며 이진 트리의 특성상 여전히 시간복잡도는 amortized $ O(log\:n)$가 유지된다.따라서 노드의 자식 노드는 4개의 상태로 존재할 수 있으며 다음과 같다.

 

1.노드 v의 real children인 경우

이 경우 이 노드는 부모 노드와 solid edge로 연결되었다고 표현한다.

 

2.노드 v의 virtual children인 경우

 

3.노드 v의 자식 virtual tree에 속하는 경우

virtual children이 아닐때 root가 부모와 virtual edge로 연결된 트리에 속하는 경우

 

4.부모 노드가 존재하지 않을 경우

이 경우 이 노드는 실제 트리의 루트가 된다.

 

solid edge로 연결된 모든 노드를 solid tree라 부르며 두 정점간의 경로를 유지하기 위해 solid tree내에서 체인은 LVR 순서의 infix order로 저장된다. 임의의 노드가 부모의 자식 virtual tree에 속할때 이 자식 노드가 속한 트리는 solid tree로 유지되며 3개 이상의 자식을 가질때는 또 다른 virtual children 혹은 자식 virtual tree를 가진다. 이로 인해 자식 노드가 매우 많아져도 접근 횟수는 log번이 유지된다.

 

위의 내용을 적용한다면 다음 그림과 같이 트리를 표현할 수 있다.

fig.1