티스토리 뷰

Code

쿼드트리 구현

천유하 2016.02.17 07:52

작년 자료구조 강의에서 쿼드트리 과제가 나와 좀 당황스러웠던 기억이 있다.

물론 약 3주의 제출 기한이 있었지만, 당연히 마지막날 했다.


이진트리 구성보다는 까다로웠으나 자식 노드를 배열로 선언하면 사실 다를건 없다. 문제는 파일을 읽어와 쿼드트리를 구성하면서 겪는 어려움인데


input.in 예시

11,0

5,11

2,11

3,11

1,2

8,11

4,2

6,3

9,8


당연히 11은 element이고 0은 부모 노드의 element인데 0이면 root로 간주한다. 즉 여기서는 11이 root 노드가 된다.

해당 쿼드트리를 도식화하면

     11

5  2   3  8

  1 4  6  9


형태가 된다.


파일에서 라인마다 읽어오면서 쿼드트리를 구성하다보면 11의 자식노드를 만들다가 11의 자식의 자식(...)노드를 만들게 되는 때가 있다. 그러다가 다시 11의 자식 노드로 돌아오기도 하는데, 이럴경우 추가할 노드의 위치를 찾는데 애먹게 된다.


난 그냥 노드를 추가할때마다 부모 노드를 찾기 위해 쿼드트리 전체 탐색을 돌려버렸다. 무식하지만, 확실하다. 그러나 좋은 점수를 기대하기 어렵다. 트리의 볼륨이 커질수록 퍼포먼스가 막장이 되는건 당연.


해당 쿼드 트리의 클래스를 구현해보았다.


 // quadtree.h
class QNode {
public:
	int elem;
	int parentelem;
	QNode* child[4];
	QNode* parent;

	QNode() {
		elem = NULL;
		parentelem = NULL;
		parent = NULL;
		for (int i = 0; i < 4; i++) {
			child[i] = NULL;
		}
	}

	QNode(int element) {
		elem = element;
		parentelem = NULL;
		parent = NULL;
		for (int i = 0; i < 4; i++) {
			this->child[i] = NULL;
		}
	}
};

class QTree {
public:
	QNode* root;
	int height = 0;

	QTree() { root = NULL; }
	QTree(QNode* root) { this->root = root; }

	void addNode(int element, int pelement) {
		QNode* alpha = new QNode(element);
		Link(find(pelement, root), alpha);
	}

	QNode* find(int element, QNode* qnode) {
		if (qnode->elem == element) {
			return qnode;
		}
		else {
			for (int i = 0; i < 4; i++) {
				if (qnode->child[i] != NULL) {
					if (find(element, qnode->child[i]) != NULL) {
						return find(element, qnode->child[i]);
					}
				}
				else {
					break;
				}
			}
		}
		return NULL;
	}

	void Link(QNode* ParentNode, QNode* ChildNode) {
		for (int i = 0; i < 4; i++) {
			if (ParentNode->child[i] == NULL) {
				ParentNode->child[i] = ChildNode;
				break;
			}
		}
		ChildNode->parent = ParentNode;
		ChildNode->parentelem = ParentNode->elem;
	}
};


창피하지만, 어쩔수 없었다. 지금이야 이것보다 낫게 만들겠지만...

댓글
댓글쓰기 폼