Algorithm - left child right sibling(LCMS) tree

tree란?

tree란 아래와 같은 구조로 여러 node가 한 node를 가르킬 수 없는 구조입니다.

다중트리

2진 트리

LCMS 구조

LCMS는 다중 트리의 구현 중 하나의 알고리즘 입니다.

다중트리 구현은 코드상 구현이 복잡하기 때문에 LCMS와 같이 2진 트리 형태로 구현을 하면 코드 복잡도를 줄일 수 있습니다.

LCMS는 말 그대로 왼쪽 노드에 자식을 추가하고 오른쪽 노드에는 같은 레벨의 형제를 추가합니다.

다중트리는 아래와 같이 자식이 여러개가 될 수 있습니다.

LCMS구조로 왼쪽 노드로는 자식, 오른쪽 노드는 형제를 추가하면 아래와 같습니다.

위의 그림은 어디서 본것같은 그림이지 않나요?

그림을 조금 바꿔서 그려보면 2진트리와 완벽하게 동일합니다.

즉 다중 트리를 2진화해서 단순하게 사용할 수 있는 방식이 LCMS라 할 수 있습니다.

code 구현 C++

Add

노드를 2개 생성한 뒤 부모,자식을 연결해서 add합니다.

동일 부모로 노드를 생성한 뒤 add할 수 있습니다.

 

동일 노드로 생성되었다면 같은 부모를 갖는 두 노드는 오른쪽으로 이어지며 형제 관계입니다.

void LCRS_tree::addNode(lcrs* parent, lcrs* child)
{
	if(mlcrs == NULL) {
		mlcrs = child;
		cout << "create root" << endl;
		return;
	}

	if(parent->leftchild == NULL) {
		parent->leftchild = child;
		//cout << "add left" << endl;
	} else {
		lcrs* mchild = parent->leftchild;
		while(mchild->rightsibling != NULL) {
			mchild = mchild->rightsibling;
		}
		mchild->rightsibling = child;
		//cout << "add right" << endl;
	}
}

순회

자식->형제 노드 순으로 순회하면 모든 노드를 순회할 수 있습니다.

첫번째 순회

두번째 순회

세번째 순회

void LCRS_tree::printinfo(lcrs* node)
{
	if(node->leftchild) {
		printinfo(node->leftchild);
		cout << endl;
	}

	if(node->rightsibling) {
		printinfo(node->rightsibling);
	}

	cout << node->index << ":item(" << *(string*)node->item << ")    ,";
}

전체 소스는 아래 github을 참고해주시기 바랍니다.

https://github.com/juwith/jsutilspp/blob/master/tree-lcrs/src/hello.cpp