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

오늘은 이진 검색 트리 삭제 부분 완성과 2중 포인터를 사용하여 만든 이진 검색 트리에 대한 수업을 들었다.

 

1. 이진 검색 트리 삭제 ( 3가지 전부 )

// bst.h

#pragma once
#include <stdio.h>

class C_BST
{
private:
	struct S_NODE
	{
		int nData;

		S_NODE* pL;
		S_NODE* pR;
	};

private:
	S_NODE* m_pRoot;

private:
	void printNode(S_NODE* pNode);
	S_NODE* createNode(int nData);
	S_NODE* insertNode(S_NODE* pNode, int nData);
	void findMaxNode(S_NODE*& pMin, S_NODE* pUp);

public:
	C_BST() = default;
	bool insert(int nData);
	bool insertR(int nData);
	void earse(int nData);
	void print();
};

// bst.cpp
#include "bst.h"

void C_BST::printNode(S_NODE* pNode)
{
	if (!pNode)
		return;

	printf("%d ", pNode->nData);
	printNode(pNode->pL);
	printNode(pNode->pR);
}

C_BST::S_NODE* C_BST::createNode(int nData)
{
	S_NODE* pNode = new S_NODE{};
	pNode->nData = nData;
	pNode->pL = nullptr;
	pNode->pR = nullptr;

	return pNode;
}

bool C_BST::insert(int nData) // 문제 root를 대신할 방법이 없음
{
	if (!m_pRoot)
	{
		m_pRoot = createNode(nData);
		return true;
	}

	bool bCreate{};
	S_NODE* pNode = m_pRoot;

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

		else if (nData > pNode->nData)
		{
			if (pNode->pR)
			{
				pNode = pNode->pR;
			}
			else
			{
				pNode->pR = createNode(nData);
				bCreate = true;
			}
		}
	}

	return bCreate;
}

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

	insertNode(m_pRoot, nData);
	return false;
}

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

	while (pFind && pFind->nData != nData) // pFind가 있고 nData가 아닐떄 까지 돌아라 
	{
		pUp = pFind; // 따라오게 만드는 것 

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

	if (!pFind)
		return;

	if (pFind->pL && pFind->pR)
	{
		S_NODE* pMinUp = pFind;
		S_NODE* pMin = pFind->pL;
		findMaxNode(pMin, pMinUp);
		//printf("up : %d, min : %d \n", pMinUp->nData, pMin->nData);

		pFind->nData = pMin->nData;
		pFind = pMin;
		pUp = pMinUp;
	}
	

	S_NODE* pNext = pFind->pL;  

	if (pFind->pR)
		pNext = pFind->pR;


	S_NODE* pDel = pFind;

	if (!pUp) // 이게 1, 2를 지우게 되면 m_pRoot를 보장해준 것 -> 그림 그려봐서 해볼 것 
		m_pRoot = pNext;
	else if (pUp->nData >= pFind->nData)
		pUp->pL = pNext;
	else
		pUp->pR = pNext;

	delete pDel;
	
}

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;
}

void C_BST::findMaxNode(S_NODE*& pMin, S_NODE* pUp)
{
	if (!pMin->pR)
		return;

	pUp = pMin;
	pMin = pMin->pR;
	findMaxNode(pMin, pUp);
}

void C_BST::print()
{
	printNode(m_pRoot);
	printf("\n");
}

2. 이중 포인터로 만든 이진 검색 트리 

// bst.h
#pragma once

#include <stdio.h>

class C_BST
{
private:
	struct S_NODE
	{
		int nData;
		S_NODE* pL;
		S_NODE* pR;
	};

private:
	S_NODE* m_pRoot;
private:
	S_NODE** findNode(S_NODE** ppNode, int nData); // 대상을 선택하는 코드 
	void printNode(S_NODE* pNode);
	S_NODE* createNode(int nData);

public:
	C_BST() = default;
	bool insert(int nData);
	bool earse(int nData);
	void earseNode(S_NODE** ppNode);
	void print();
};

// bsh.cpp
#include "bst.h"

C_BST::S_NODE** C_BST::findNode(S_NODE** ppNode, int nData) // 일부로 재귀함수로 만들 예정, 주의 -> ppNode는 절대 NULL이 되면 안됨 ( 내용물이 없을순 있지만 경로가 없을수는 없음 )
{
    if (!*ppNode)  // 있어도 return ppNode, 없어도 return ppNode;
        return ppNode;

    if ((*ppNode)->nData < nData)
        return findNode(&(*ppNode)->pL, nData);

    if ((*ppNode)->nData > nData)
        return findNode(&(*ppNode)->pR, nData);

    return ppNode;
}

void C_BST::printNode(S_NODE* pNode)
{
    if (!pNode)
        return;

    printf("%d ", pNode->nData);
    printNode(pNode->pL);
    printNode(pNode->pR);
}

C_BST::S_NODE* C_BST::createNode(int nData)
{
    S_NODE* pNode = new S_NODE{};
    pNode->nData = nData;

    return pNode;
}

bool C_BST::insert(int nData)
{
    S_NODE** ppFind = findNode(&m_pRoot, nData);

    if (*ppFind) // 있으면 중복이니까 실패임 
        return false;

    *ppFind = createNode(nData);
    return true;
}

bool C_BST::earse(int nData)
{
    S_NODE** ppFind = findNode(&m_pRoot, nData);

    if (!*ppFind) // 없으면 삭제할께 없으니 실패
        return false;

    earseNode(ppFind);

    return true;
}

void C_BST::earseNode(S_NODE** ppNode)
{
    S_NODE* pNext = (*ppNode)->pL;
    if ((*ppNode)->pR)
        pNext = (*ppNode)->pR;

    S_NODE* pDel = *ppNode;
    *ppNode = pNext;
    delete pDel;
}

void C_BST::print()
{
    printNode(m_pRoot);
    printf("\n");
}

// main.cpp
#include <iostream>

#include "bst.h"

int main()
{
	C_BST cBst{};

	cBst.insert(5);
	cBst.insert(4);
	cBst.insert(8);
	cBst.insert(9);
	cBst.insert(2);
	cBst.insert(3);
	cBst.insert(1);
	cBst.insert(6);
	cBst.insert(7);

	cBst.print();
	cBst.earse(9);
	cBst.print();
}