CPP_어소_78_tree (9)

CJB_ny·2022년 7월 26일

cpp erase tree

CPP_AROTHO

목록 보기

77/83

BST

지금까지 특정 노드를 삭제하는 거 제외하고 거의 다 구현을 함.

삭제하는 경우

삭제할 노드가 단말 노드인 경우
삭제할 노드가 자식노드를 한개를 가진 경우(왼쪽, 또는 오른쪽)
삭제할 노드가 2개의 자식을 가진 경우

1번은 그냥 삭제하면됨.

2번의 경우에는 조부모에게 자신을 연결을 하면됨. 어차피 값은 큰대로 올라가거나 작은대로 올라갈 것이기 때문에

3번의 경우 조금 복잡함.

무슨 기준으로 올릴꺼임? 둘중 누구를 올리냐?

그런데 문제

자식이 두개가 있는데 둘중 누구를 올릴까? 하는 고민부터가 문제임.

당연히 오른쪽이 올라가야지

여기서 특정 노드를 삭제할경우

"중위 순회"에 문제가 없는지를 봐야한다.

"중위 순회" 순서가 이렇게 가야함.

그래서 만약 B가 없어졌다고 하면은

I나 J가 B의 자리에 와야한다.

B의 자식은 D나 E가 오는게 아니라.

그래서 개념이 중위 선행자나 중위 후속자가 와야한다.

근데 I나 J를 어떻게 올릴꺼임? -> 모양이 이상하노

설명

현재 중위 순회 순서로 이렇게 있다고 하고

4라는 노드가 삭제될 노드라고 가정을 하자.

그러면 5번 노드의 데이터만 4노드 자리에 덮어버린다면

이런 모양이 될 것인데 이렇게하면 순서가 어긋나지 않음.

그리고 실제 삭제될 노드는

지금 박스 처놓은 노드이다. 메모리적으로 정리를 해버림.

5번이 자식이 있을 경우

케이스에 따라 또 나뉠 것이다.

그런데 "중위후속자"나 "중위 선행자"의 경우

절대로 자식이 2개 이상 있을 수 없다. 하나까지만 가능함.

왜? => 애초에 "중위 후속자"라는 말이

오른쪽자식으로 가서 왼쪽 자식이 없을 때까지 내려간 것이라서.

OK. 중위 선행자, 후속자는 자식이 하나 또는 없다.

erase 구현

이전의 자료구조 시간에서는 erase(eraseIter); 이렇게 넘겨주면

지우는 iterator의 다음 iterator를 넘겨주는 방식으로 구현했음.

vector든 LinkedList 이든.

bool IsLeaf()
{
	if (nullptr == nodeArrayAddr[(int)NodeType::LeftChild] && nullptr == nodeArrayAddr[(int)NodeType::Rightchild])
			return true;
	return false;
}

bool IsFull()
{
	if (nodeArrayAddr[(int)]NodeType::LeftChild && nodeArrayAddr[(int)NodeType::RightChild])
			return true;
	return false;
}

struct BstNode의 멤버 함수로 두개를 먼저 뚫어 주도록 하자.

template<typename T1, typename T2>
inline typename Cbst<T1, T2>::iterator Cbst<T1, T2>::erase(iterator& eraseIter)
{
	assert(this == eraseIter.m_i_nodeAddr);

	BstNode<T1, T2>* successor = DeleteNode(eraseIter.m_i_nodeAddr);

	return iterator(this, successor);
}

또한 지금 erase함수가 너무 복잡하기 때문에

Delete라는 함수를 따로 만들어서 이렇게 동작하도록 해주도록 하자.

DeleteNode 구현

template<typename T1, typename T2>
inline BstNode<T1, T2>* Cbst<T1, T2>::DeleteNode(BstNode<T1, T2>* targetNodeAddr)
{
	BstNode<T1, T2>* successor = nullptr;
    
	if (targetNodeAddr->IsLeaf())
	{
    	// 삭제시킬 노드의 중위 후속자 노드를 찾아둔다.
    	successor = GetInOrderSuccessor(targetNodeAddr);
        
		if (targetNodeAddr->IsLeftChild())
			targetNodeAddr->nodeArrayAddr[(int)NodeType::PARENT]->nodeArrayAddr[(int)NodeType::LCHILD] = nullptr;
		else
			targetNodeAddr->nodeArrayAddr[(int)NodeType::PARENT]->nodeArrayAddr[(int)NodeType::RCHLID] = nullptr;

		delete targetNodeAddr;
	}
	return nullptr;
}

그런데 delete targetNodeAddr을 하기전에

"중위 후속자"를 찾아 두어야한다.

BstNode<T1, T2>* successor = nullptr;

	// 1. 자식이 하나도 없는 경우 (제일간단)
	// 부모를 먼저 삭제를 하면 접근할 방법 사라짐!
	if (targetNodeAddr->IsLeaf())
	{
		// 삭제시킬 노드의 중위 후속자 노드를 찾아둔다.
		successor = GetInOrderSuccessor(targetNodeAddr);

		// 부모노드로 접근 -> 삭제 될 자식노드의 주소를 nullptr로 만든다.
		// 1. 삭제될 노드(eraseIter.m_nodeAddr이 오른쪽 자식인지 왼쪽 자식인지 확인.
		if (targetNodeAddr->IsLeftChild())
			targetNodeAddr->nodeArrayAddr[(int)NodeType::PARENT]->nodeArrayAddr[(int)NodeType::LCHILD] = nullptr;
		else
			targetNodeAddr->nodeArrayAddr[(int)NodeType::PARENT]->nodeArrayAddr[(int)NodeType::RCHLID] = nullptr;

		// 2. 부모의 오른쪽 또는 왼쪽 자식을 nullptr로 막았기 때문에 이제 자식을 진짜 삭제를 하는 작업.
		delete targetNodeAddr;
	}
	// 자식이 2개인 경우
	else if (targetNodeAddr->IsFull() )
	{
		


	}
	// 자식이 1개인 경우
	else
	{
		
	}

예외사항

루트 노드를 삭제하려고할 경우

Cbst에서는 노드를 가르키는 쪽을 nullptr로 막아야한다.

즉, 데이터를 하나만 넣고 그 데이터를 삭제한 경우이다.

if (targetNodeAddr->IsLeaf())
{
	// 삭제시킬 노드의 중위 후속자 노드를 찾아둔다.
	successor = GetInOrderSuccessor(targetNodeAddr);

	// targetNodeAddr이 루트노드일 경우 rootNode를 nullptr로 막는다.
	if (targetNodeAddr == m_rootNode)
	{
		m_rootNode = nullptr;
	}
	else
	{
		// 부모노드로 접근->삭제 될 자식노드의 주소를 nullptr로 만든다.
		// 1. 삭제될 노드(eraseIter.m_nodeAddr이 오른쪽 자식인지 왼쪽 자식인지 확인.
		if (targetNodeAddr->IsLeftChild())
			targetNodeAddr->nodeArrayAddr[(int)NodeType::PARENT]->nodeArrayAddr[(int)NodeType::LCHILD] = nullptr;
		else
			targetNodeAddr->nodeArrayAddr[(int)NodeType::PARENT]->nodeArrayAddr[(int)NodeType::RCHLID] = nullptr;
	}
    
	// 2. 부모의 오른쪽 또는 왼쪽 자식을 nullptr로 막았기 때문에 이제 자식을 진짜 삭제를 하는 작업.
	delete targetNodeAddr;
	
}

나의 실수 ❗❗


template <typename T1, typename T2>
inline typename Cbst<T1, T2>::iterator Cbst<T1, T2>::findData(const T1& find)
{
	// rootNode가 훼손될 가능성을 없애기 위한 지역변수 (루트는 고정되어야 하기 때문에)
	BstNode<T1, T2>* pNode = m_rootNode;

	// 가야할 방향 (오른쪽인지 왼쪽인지)를 enum으로 정해주자
	NodeType nodeType = NodeType::END; // 아직 갈 방향 안정해서 END로 놔둠.

	while (true)
	{
		if (pNode->pair.first < find)
			nodeType = NodeType::RCHLID;
		else if (pNode->pair.first > find)
			nodeType = NodeType::LCHILD;
		else
		{
			// 찾은 경우
			break;
		}

		if (nullptr == pNode->nodeArrayAddr[(int)nodeType])
		{
			// 못찾은 경우
			pNode = nullptr;
			break;
		}
		else
			pNode = pNode->nodeArrayAddr[(int)nodeType];
	}

	return iterator(this, pNode);
}