LC-RS는 Left Child Right Sibling Binary Tree를 줄여서 부르는 용어이다.
LC-RS는 k-ary 트리를 binary tree로 표현하는 방법이다.
예를 들어 k-ary 트리가 다음과 같다.
k-ary트리의 객체구조는 다음과 같다.
이것을 lc-rs로 바꾸면 다음과 같다.
lc-rs의 객체구조는 다음과 같다.
time-complexity의 기준에서는 k-ary
space-complexity의 기준에서는 lc-rs
참고자료
1. Left-Child Right-Sibling Binary Tree - 위키피디아
'Algorithm' 카테고리의 다른 글
LC-RS - Left Child Right Sibling Binary Tree (0) | 2013.05.02 |
---|