BST

erase 구현

else 자식이 1개일 경우

// 자식이 1개인 경우
	else
	{
		// 삭제시킬 노드의 중위 후속자 노드를 찾아둔다.
		successor = GetInOrderSuccessor(targetNodeAddr);

		// 삭제시킬 노드의 자식이 오른쪽인지 왼쪽인지 확인하는 작업.
		NodeType childType = NodeType::LCHILD;
		if (targetNodeAddr->nodeArrayAddr[(int)NodeType::RCHLID])
			childType = NodeType::RCHLID;

		// 삭제 시킬 노드가 루트노드일 경우
		if (targetNodeAddr == m_rootNode)
		{
			// 자식 노드(1개)를 루트로노드로 올린다. (만든다)
			m_rootNode = targetNodeAddr->nodeArrayAddr[(int)childType];
            targetNodeAddr->nodeArrayAddr[(int)childType]->nodeArrayAddr[(int)NodeType::PARENT] = nullptr; // 부모를 nullptr로 한다 자기 자신이 루트가 되었으니까.
		}
		else
		{
			// 삭제될 노드의 부모와, 삭제될 노드의 자식을 연결해준다.
			// 그전에 삭제할 노드가 부모의 왼쪽 자식인지 오른쪽 자식인지 확인 해야됨.
			if (targetNodeAddr->IsLeftChild() )
			{
				// 삭제될 노드가 왼쪽 자식일 경우
				targetNodeAddr->nodeArrayAddr[(int)NodeType::PARENT]->nodeArrayAddr[(int)NodeType::LCHILD] = targetNodeAddr->nodeArrayAddr[(int)childType];
			}
			else
			{
				targetNodeAddr->nodeArrayAddr[(int)NodeType::PARENT]->nodeArrayAddr[(int)NodeType::RCHLID] = targetNodeAddr->nodeArrayAddr[(int)childType];
			}

			// 삭제될 노드의 자식과 삭제될 노드의 부모를 연결 해주어야한다.
			targetNodeAddr->nodeArrayAddr[(int)childType]->nodeArrayAddr[(int)NodeType::PARENT] = targetNodeAddr->nodeArrayAddr[(int)NodeType::PARENT];
		}

		delete targetNodeAddr;
	}

삭제될 노드의 부모와 삭제될 노드의 자식을 연결을 잘해주면된다.

if (targetNodeAddr == m_rootNode)
{
	// 자식 노드(1개)를 루트로노드로 올린다. (만든다)
	m_rootNode = targetNodeAddr->nodeArrayAddr[(int)childType];
}

지금 이부분에서의 배열 포인터는

nodeArrayAddr[(int)childType];
// childType에 따라 (int)NodeType::LCHILD 가 오면
// 이것은 enum값이라 nodeArrayAddr의 1번 인덱스에 접근한 값을 
// m_rootNode에다가 집어 넣는다는 말이다.
// nodeArrayAddr은 배열 포인터라 인덱스에 접근을 하면
// 16진수의 메모리 주소 값이 들어가 있는 상태이다.

그러면 이제 erase를 하게되면 dataCount는 5개가 남아야하고

100과 25가 잘 연결되면 된다.

ㅇㅇ. 연결 잘되었다.

100의 왼쪽 자식의 first가 25이고ㅓ

25의 부모의 first값도 100으로 연결이 잘됨.

또한 중위 후속자도

50의 중위 후속자는 100이니까

받아온 myIter를 보면 pair의 first값을 100을 잘 들고있다.

지금 데이터 2개있을 경우에도 100삭제하면

150이 루트로 올라가고 부모 자식 다 없는 상태로 잘되는 거 확인함.

elif 자식이 2개인 경우

지금 이런 BST 상태라고 하자.

150이 삭제가 된다면 125, 175 둘중에 아무나 올라와도 된다.

그런데

100이 삭제될 경우는..?? 125, 75 둘중에 아무나 와도 된다.

그래서 중위 후속자나 선행자 둘중 하나가 와도 상관없다.

그냥 정하기 나름이다.

Cbst<int, int> cbs;

	Pair<int, int> p;

	cbs.insert(make_bstPair(100, 0));//        100
	cbs.insert(make_bstPair(150, 0));//    50        150
	cbs.insert(make_bstPair(50, 0));//  25    75  125    175
	cbs.insert(make_bstPair(25, 0));
	cbs.insert(make_bstPair(75, 0));
	cbs.insert(make_bstPair(125, 0));
	cbs.insert(make_bstPair(175, 0));

	// begin()  하면 50 을 가르키는 노드가 되어야함
	Cbst<int, int>::iterator myIter = cbs.begin();

	myIter = cbs.findData(150);

	myIter = cbs.erase(myIter); // myiter는 50을 가르켜야한다.

	wcout << myIter->first << endl;

이론모양에서 150을 지우면

        100
    50        175
25    75  125    

이런 모양이 되면 된다.

잘된다. 굿굿

tree부분 한번 더 듣자.