23일차 (1/12)

재귀함수

어떤 함수가 자신과 완전히 동일한 함수를 내부에서 다시 실행하는 것을 재귀함수라고 부른다.

그래서 그냥 사용하면 자기자신을 계속 호출하면서 스택 오버플로우가 터진다.

종료되는 시점을 정해주고 return을 시켜야한다.

---

Map

map은 <int, int>와 같이 값을 2개 받는다. 각각 <key, value>를 맡는다.

map은 자동으로 오름차순 정렬이 된다. (작은 수 -> 큰 수로 정렬)

 

map은 자료가 무작위일 때 효율을 발휘한다.

이미 정렬된 상태로 자료가 들어간다면 대부분의 자료구조가 map보다 빠르다.

 

insert()

map에 자료를 추가하는 방법은 보통 4가지 정도가 사용한다.

첫번째는 Pair로 하는 방법이다.

NewMap.insert(std::pair<int, int>(5, 12));

 

두번째는 make_pair로 하는 방법이다.

NewMap.insert(std::make_pair(2, 12));

 

세번째는 배열 연산자를 사용하는 방법이다.

NewMap[3] = 1;

 

네번째는 value_type을 사용하는 방법이다.

NewMap.insert(std::map<int, int>::value_type(7, 10));

3번째는 제외하고는 원리도 같은데 표현 방식만 다른 것들이다.

insert의 대략적인 원리를 구현한 코드는 다음과 같다.

void insertNode(MapNode* _Node)
{
	_Node->Parent = this;
	if (this->Pair.Key > _Node->Pair.Key)
	{
		if (nullptr == this->LeftChild)
		{
			this->LeftChild = _Node;
			return;
		}

		this->LeftChild->insertNode(_Node);
	}

	if (this->Pair.Key < _Node->Pair.Key)
	{
		if (nullptr == this->RightChild)
		{
			this->RightChild = _Node;
			return;
		}

		this->RightChild->insertNode(_Node);
	}

	return;
}

void insert(const MyPair& _Value)
{
	MapNode* NewNode = new MapNode();
	NewNode->Pair = _Value;

	if (nullptr == Root)
	{
		Root = NewNode;
		return;
	}

	Root->insertNode(/*Root, */NewNode);
}

 

만약 이미 존재하는 key와 같은 키를 입력한다면 무시된다. 동적할당으로 입력했다면 무시된 노드는 Leak이 된다.

 

contains()

C++20에서만 있는 함수로 contains()가 있는데 이 함수는 노드가 있는지 없는지를 bool로 리턴한다.

만들어본다면 다음과 같다.

bool containsNode(const KeyType& _Key) 
{
	if (this->Pair.Key == _Key)
	{
		return true;
	}

	if (this->Pair.Key > _Key)
	{
		if (nullptr != this->LeftChild)
		{
			return this->LeftChild->containsNode(_Key);
		}
	}

	if (this->Pair.Key < _Key)
	{
		if (nullptr != this->RightChild)
		{
			return this->RightChild->containsNode(_Key);
		}
	}
	return false;
}

bool contains(const KeyType& _Key)
{
	if (nullptr == Root)
	{
		return false;
	}

	return Root->containsNode(_Key);
}

 

 

minnode, maxnode

MapNode* minnode()
{
	if (nullptr == this->LeftChild)
	{
		return this;
	}
	
	return LeftChild->minnode();
}

MapNode* maxnode()
{
	if (nullptr == this->RightChild)
	{
		return this;
	}

	return RightChild->maxnode();
}

부모보다 작은 값은 left, 부모보다 큰 값은 right 노드로 가기 때문에 최소와 최대를 구하려면 위와 같이 왼쪽 끝 노드나 오른쪽 끝 노드를 구하면된다. 한쪽 방향으로만 가서 자식 노드가 nullptr이면 끝 노드이다.

 

find()

MapNode* findNode(const KeyType& _Key)
{
	if (this->Pair.Key == _Key)
	{
		return this;
	}

	if (this->Pair.Key > _Key)
	{
		if (nullptr != this->LeftChild)
		{
			return this->LeftChild->findNode(_Key);
		}
	}

	if (this->Pair.Key < _Key)
	{
		if (nullptr != this->RightChild)
		{
			return this->RightChild->findNode(_Key);
		}
	}


	return nullptr;
}

리턴과 동시에 재귀를 하는 것을 꼬리 재귀라고 한다. 꼬리 재귀를 사용하면 가능한 경우에 컴파일러가 while로 바꿔준다. inline과 비슷하게 생각하면 된다.

 

begin()

 

 

 

erase()

맵의 삭제의 핵심은 어떤 노드가 삭제된다면 삭제된 노드의 대체 노드를 찾아야된다는 것이다.

단, 리프 노드면 찾을 필요가 없다.  대신 부모 노드에 삭제된 것을 알려야한다.

자식이 있는 노드가 삭제된 경우에는 해당 노드의 prev나 next중 아무거나 올라오면 된다.

바꿔줄 노드는 삭제할 노드의 left의 max노드나 right의 min노드와 바꿔준다.

바꿔줄 때의 순서가 있다.

1. left와 right 노드의 부모를 nullptr로 만든다.
2. 바꿔줄 노드로 이전 자식 노드들을 연결한다.
3. 바꿔줄 노드로 부모노드를 연결한다.

iterator erase(iterator& _Iter)
{
	iterator Return;

	if (nullptr == _Iter.CurNode)
	{
		MsgBoxAssert("유효하지 않은 원소를 삭제하려고 했습니다.");
		return Return;
	}

	MapNode* NextNode = _Iter.CurNode->NextNode();

	Return.CurNode = NextNode;

	// 일단 처리되면 끝나면 
	if (true == _Iter.CurNode->IsLeaf())
	{
		MapNode* ParentNode = _Iter.CurNode->Parent;
		_Iter.CurNode->Release();
		delete _Iter.CurNode;
		return Return;
	}
	
	// 교체를 해줘야 한다.
	// 자식이 하나라도 있는 노드이다.
	MapNode* ChangeNode = nullptr;
	MapNode* CurNode = _Iter.CurNode;

	ChangeNode = CurNode->RightChild->minnode();
	if (nullptr == ChangeNode)
	{
		ChangeNode = CurNode->LeftChild->maxnode();
	}

	if (nullptr == ChangeNode)
	{
		MsgBoxAssert("체인지 노드 에러.");
		return Return;
	}
	ChangeNode->Release();

	MapNode* LeftChild = CurNode->LeftChild;
	MapNode* RightChild = CurNode->RightChild;

	if (nullptr != LeftChild)
	{
		LeftChild->Parent = nullptr;
	}

	if (nullptr != RightChild)
	{
		RightChild->Parent = nullptr;
	}

	if (nullptr != LeftChild)
	{
		LeftChild->Parent = ChangeNode;
		if (CurNode->LeftChild != ChangeNode)
		{
			ChangeNode->LeftChild = LeftChild;
		}
	}

	if (nullptr != RightChild)
	{
		RightChild->Parent = ChangeNode;
		if (CurNode->RightChild != ChangeNode)
		{
			ChangeNode->RightChild = RightChild;
		}
	}

	ChangeNode->Parent = CurNode->Parent;
	MapNode* Parent = ChangeNode->Parent;
	if (nullptr != Parent && Parent->LeftChild == CurNode)
	{
		Parent->LeftChild = ChangeNode;
	}

	if (nullptr != Parent && Parent->RightChild == CurNode)
	{
		Parent->RightChild = ChangeNode;
	}

	if (Root == CurNode)
	{
		Root = ChangeNode;
	}

	delete CurNode;

	return Return;

}

 

map의 노드의 개수가 많으면 많을수록 map을 순회돌리는것은 효율적이지 못하다.

하지만 Leak이 남지 않게 전부 삭제를 하기위해선 모든 노드를 다 순환해야한다.

모든 노드를 순환하는 3가지 방식이 있다. map에는 없는 함수이다.

전위 : root - left - right

중위 : left - root - right

후위 : left - right - root

void firstOrderPrint()
{
	std::cout << Pair.Key << std::endl;
	if (nullptr != LeftChild)
	{
		LeftChild->firstOrderPrint();
	}
	if (nullptr != RightChild)
	{
		RightChild->firstOrderPrint();
	}
	return;
}

void midOrderPrint()
{
	if (nullptr != LeftChild)
	{
		LeftChild->midOrderPrint();
	}
	std::cout << Pair.Key << std::endl;
	if (nullptr != RightChild)
	{
		RightChild->midOrderPrint();
	}
	return;
}

void lastOrderPrint()
{
	if (nullptr != LeftChild)
	{
		LeftChild->lastOrderPrint();
	}
	if (nullptr != RightChild)
	{
		RightChild->lastOrderPrint();
	}
	std::cout << Pair.Key << std::endl;
	return;
}