[코딩인터뷰 완전정복] 4.11 임의의 노드

Q : 이진 트리 클래스를 바닥부터 구현하려고 한다. 노드의 삽입, 검색, 삭제 뿐만 아니라 임의의 노드를 반환하는 getRandomNode() 메서드도 구현한다. 모든 노드를 같은 확률로 선택해주는 getRandomNode() 메서드를 설계하고 구현하라. 또한 나머지 메서드는 어떻게 구현할지 설명하라.

 

구현 요소 : 

1. 노드
2. 노드의 삽입
3. 노드의 검색
4. 노드의 삭제
5. getRandomNode() -> 임의의 노드를 선택하여 반환해준다. 모든 노드가 같은 확률로 선택된다.

 

 

// node.h
template <class T>
class TreeNode{
public:
	T data;
	TreeNode* parent;
	TreeNode* left;
	TreeNode* right;

	TreeNode(T data) {
		this->data = data;
	}

	void addLeft(TreeNode<T>* left) {
		this->left = left;
		left->parent = this;
	}

	void addLeft(T data) {
		TreeNode<T> *left = new TreeNode<T>(data);
		addLeft(left);
	}

	void addRight(TreeNode<T>* right) {
		this->right = right;
		right->parent = this;
	}

	void addRight(T data) {
		TreeNode<T> *right = new TreeNode<T>(data);
		addRight(right);
	}
};

#include <iostream>
#include <queue>
#include <deque>
#include <cstdlib>
#include <ctime>
#include "Node.h"

template<class T>
class BinaryTree {
private:
	int count;
	TreeNode<T>* TopNode;
	std::deque<TreeNode<T>*> LeafNodeQueue;

public :
	BinaryTree(){
		count = 0;
		LeafNodeQueue = new std::deque<TreeNode<T>*>();
	}

	BinaryTree(T data) {
		BinaryTree();
		insert(data);
	}

	void insert(T data) {
		if (count == 0) {
			TopNode = new TreeNode<T>(data);
			LeafNodeQueue.push_back(TopNode);
		}
		else {
			TreeNode<T>* parent = LeafNodeQueue.front();
			TreeNode<T>* newNode = new TreeNode<T>(data);
			if (parent->left == NULL) {
				parent->addLeft(newNode);
				LeafNodeQueue.push_back(newNode);
			}
			else if(parent->right == NULL) {
				parent->addRight(newNode);
				LeafNodeQueue.push_back(newNode);
				LeafNodeQueue.pop_front();
			}
			else {
				LeafNodeQueue.pop_front();
				insert(data);
				return;
			}
		}
		count++;
	}

	TreeNode<T>* search(T data) {
		if (count == 0) return NULL;
		if (TopNode->data == data) return TopNode;
		std::queue<TreeNode<T>*> searchNodeQueue = new std::queue<TreeNode<T>*>();
		searchNodeQueue.push(TopNode);
		while (searchNodeQueue.size != 0) {
			TreeNode<T>* searchNode = searchNodeQueue.front();
			if (searchNode->data == data) return searchNode;
			if (searchNode->left != NULL) searchNodeQueue.push(searchNode->left);
			if (searchNode->right != NULL) searchNodeQueue.push(searchNode->right);
			searchNodeQueue.pop();
		}
		return NULL;
	}

	void remove(T data) {
		if (count == 0) return;
		std::queue<TreeNode<T>*> searchNodeQueue = new std::queue<TreeNode<T>*>();
		TreeNode<T>* replaceNode = LeafNodeQueue.back();
		
		if (replaceNode->data == data) {
			count--;
			if (replaceNode == TopNode) {
				TopNode = NULL;
				return;
			}
			if (replaceNode->parent->right == replaceNode)
				LeafNodeQueue.push_front(replaceNode->parent);
			LeafNodeQueue.pop_back();
			replaceNode->remove();
			return;
		}

		searchNodeQueue.push(TopNode);
		while (searchNodeQueue.size != 0) {
			TreeNode<T>* searchNode = searchNodeQueue.front();
			if (searchNode->data == data) {

				searchNode->data = replaceNode->data;

				if (replaceNode->parent->right == replaceNode)
					LeafNodeQueue.push_front(replaceNode->parent);
				LeafNodeQueue.pop_back();
				replaceNode->remove();
				count--;
				return;
			}
			if (searchNode->left != NULL) searchNodeQueue.push(searchNode->left);
			if (searchNode->right != NULL) searchNodeQueue.push(searchNode->right);
			searchNodeQueue.pop();
		}
	}

	TreeNode<T>* getRandomNode() {
		if (count == 0) return NULL;
		int ran = srand((unsigned int)time(NULL)) % count;

		std::queue<TreeNode<T>*> searchNodeQueue = new std::queue<TreeNode<T>*>();
		TreeNode<T>* searchNode;
		searchNodeQueue.push(TopNode);
		while (ran != -1) {
			searchNode = searchNodeQueue.front();
			if (searchNode->left != NULL) searchNodeQueue.push(searchNode->left);
			if (searchNode->right != NULL) searchNodeQueue.push(searchNode->right);
			searchNodeQueue.pop();
			ran--;
		}

		return searchNode;
	}
};

 

1. 노드

노드는 트리를 구성하는 자료의 컨테이너 이다.
트리를 구성하는 각 노드는 템플릿 자료형의 데이터, 부모 노드, 왼쪽 자식노드와 오른쪽 자식노드의 정보를 가지고 있어야 한다.

2. 노드의 삽입

노드를 삽입 할 때, 노드를 어디에 삽입할지를 정해야만 한다. 이미 다른 노드가 있는 자리에 삽입하거나, 한쪽 방향으로만 삽입해서는 안된다.
필자는 리프 노드들을 큐에 담아서 순서대로 채워넣는 방법을 사용했다.
시간복잡도는 O(1)이다.

3. 노드의 검색

이진탐색트리의 경우에는 현재 탐색하고 있는 노드의 자료값을 보고, 탐색하고자 하는 노드가 어디에 있는지 대략적으로 추측할 수 있다.
하지만 위의 트리는 이진탐색트리로 구성하지 않아 모든 노드를 탐색해야하므로 시간복잡도는 O(N)이다.

* N은 트리가 가지고 있는 노드의 갯수이다.

4. 노드의 삭제

노드를 삭제 할 때 트리의 중간에 있는 노드를 삭제해 버릴시, 해당 노드의 하위노드에 접근 할 수 없으므로, 자식노드를 한단계씩 올려서 빈공간을 채우거나, 리프노드를 그 자리에 채워넣어서 자료의 손실을 막아야한다.
필자는 리프노드의 자료값을 삭제할 노드에 채워넣고 리프노드를 제거하는 방법을 사용했다.
이때, 삽입 대기열에 있는 리프노드를 제거해주고 해당 리프노드를 자식으로 가지고 있던 부모노드의 자식이 비었으므로, 삽입 대기열에 부모노드를 다시 넣어주어야 한다.
노드를 삭제하기 위해서는 우선 해당노드를 탐색해야하므로 시간복잡도는 O(N)이다.

5. getRandomNode()

모든 노드를 같은 확률로 선택해주는 함수를 만들기 위해선, 트리가 가지고 있는 노드의 갯수를 알아야 했다.
따라서 노드의 갯수를 저장하는 count 맴버를 만들고 삽입 삭제가 일어날때, 그 수를 변경해주는 기능을 삽입했다.
노드의 갯수를 알고 있다면, 1부터 노드의 갯수 N(또는 0~N-1)까지의 숫자를 랜덤으로 얻어낸 뒤 그 숫자만큼 트리를 탐색하여 getRandomNode()함수를 구현한다.
시간복잡도는 O(N)이다.