[강의] 12월 11일 수업정리

오늘은 이진 검색 트리에 insert 부분, insert 재귀함수, earse에 대한 부분에 대한 수업을 들었다.

 

 

1. 이진 검색 트리 Insert 

bool C_BST::insert(int nData)
{
	if (!m_pRoot)
	{
		m_pRoot = createNode(nData);
		return true;
	}

	bool bCreate{};
	S_NODE* pNode = m_pRoot;

	while (pNode->nData != nData)
	{
		if (nData < pNode->nData) // pL
		{
			if (!pNode->pL)
			{
				pNode->pL = createNode(nData);
				bCreate = true;
			}
			pNode = pNode->pL;
		}
		else if (nData > pNode->nData) // pR
		{
			if (!pNode->pR)
			{
				pNode->pR = createNode(nData);
				bCreate = true;
			}
			pNode = pNode->pR;
		}
	}

	return bCreate;
}

• Bool형을 사용하여 검색 성공 / 실패 유무 추가
• while문의 조건을 pNode-> nData!= nData로 변경
    [ 현재 노드의 데이터가 삽입하려는 데이터와 다를 때만 반복을 계속하도록 설정 ]
  1. 조건이 만족되는 동안 삽입 위치를 찾기 위해 트리를 탐색
  2. 탐색이 끝에 도달하면 while문이 종료되어 결과적으로 삽입 작업은 중복된 데이터 없이 수행

 

2. 이진 검색 트리 Insert ( 재귀 함수 )  

C_BST::S_NODE* C_BST::insertNode(S_NODE* pNode, int nData)
{
	if (!pNode)
		return createNode(nData);

	if (pNode->nData > nData)
	{
		pNode->pL = insertNode(pNode->pL, nData);
	}
	else if (pNode->nData < nData)
	{
		pNode->pR = insertNode(pNode->pR, nData);
	}

	return pNode;
}

bool C_BST::insertR(int nData)
{
	if (!m_pRoot)
	{
		m_pRoot = createNode(nData);
		return true;
	}

	insertNode(m_pRoot, nData);
	return false;
}

• 재귀 함수를 사용하여 삽입 위치를 찾는 방식
• 삽입해야 할 위치가 NULL이라면, 해당 위치에 createNode를 호출하여 새로운 노드 생성 후 데이터 삽입
• 재귀 호출을 통해  트리 구조를 유지, 삽입이 완료되면 부모 노드와의 연결도 자동으로 갱신

3. Earse

Earse 부분은 총 3가지의 경우가 존재한다.

 

1. 자식이 없는 경우
2. 자식이 하나 있는 경우
3. 자식이 둘다 있는 경우

이중 우리는 1, 2 번을 먼저 구현을 해보았다.

void C_BST::earse(int nData)
{
	S_NODE* pFind = m_pRoot;
	S_NODE* pUp{};

	while (pFind && pFind->nData != nData)
	{
		pUp = pFind;

		if (pFind->nData > nData)
			pFind = pFind->pL;
		else
			pFind = pFind->pR;
	}

	if (!pFind)
		return;

	printf("up : %d , find : %d\n", pUp->nData, pFind->nData);

	S_NODE* pChild = nullptr;

	if (pFind->pL && pFind->pR)  // 3. 자식이 둘다 있는 경우 
	{
		return;
	}
	else if (pFind->pL || pFind->pR) // 2. 자식이 하나 있는 경우 
	{
		if (pFind->pL)
			pChild = pFind->pL;
		else
			pChild = pFind->pR;
	}
	// 1. 자식이 없는 경우는 pChild = nullptr;

	if (!pUp) // 부모 노드에 연결 
		m_pRoot = pChild;
	else if (pUp->pL == pFind)
		pUp->pL = pChild;
	else
		pUp->pR = pChild;

	delete pFind;

}

 

3.1 주요 변수

• pFind : 삭제 대상 노드
• pUp : 삭제 대상 노드의 부모 노드
• pChild : 삭제 대상 노드의 자식을 가리키는 포인터 (없으면 nullptr )

 

3.2 처리 순서 

 

1. 삭제할 값을 탐색  

•  while 루프를 사용해 삭제할 값이 있는 노드(pFind)와 그 부모 노드 (pUp)을 찾음 

2. 삭제할 노드의 상태 확인

• 자식이 두 개인 경우: 미구현.
• 자식이 하나인 경우: pChild에 자식을 저장.
• 자식이 없는 경우: pChild는 nullptr.

 

3. 삭제한 노드의 부모와 자식을 연결

• 부모 노드가 없는 경우(루트 노드)에는 m_pRoot를 갱신
• 부모 노드가 있는 경우, pUp의 왼쪽 또는 오른쪽 포인터를 갱신

4. 삭제

• delete를 사용해 pFind를 메모리에서 해제