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

오늘은 이진 검색 트리 이중 포인터 earse에 대한 수업과 순회에 대한 수업을 들었다.

 

1.  이진 검색 트리 Earse ( 이중 포인터 완성 )

- 다른 코드는 똑같으니 달라진 부분의 코드만 올릴 예정 

// 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);
	S_NODE** findMax(S_NODE** ppNode);
	void earseNode(S_NODE** ppNode);

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

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

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

    if ((*ppFind)->pL && (*ppFind)->pR)
    {
       S_NODE **ppMax = findMax(&(*ppFind)->pL);
       (*ppFind)->nData = (*ppMax)->nData;
       ppFind = ppMax;
    }

    earseNode(ppFind);

    return true;
}

C_BST::S_NODE** C_BST::findMax(S_NODE** ppNode)
{
    if (!(*ppNode)->pR)
        return ppNode;


    return findMax(&(*ppNode)->pR);
}

 

2. 이진 검색 트리 순회

 

1. 전위 순회 : 현재 노드 - 왼쪽 노드 - 오른쪽 노드

2. 중위 순회 : 왼쪽 노드 - 현재 노드 - 오른쪽 노드

3. 후위 순회 : 왼쪽 노드 - 오른쪽 노드 - 현재 노드

• 보통 이진 검색 트리를 사용할때는 중위 순회를 보통 사용을 한다. ( 정렬 되어있는것 처럼 보이기 때문, 하지만 실제로는 정렬된 것은 아니기에 착각하지 말 것)

 

 

자료 구조의 핵심 

 

우리가 자료구조를 설계하거나 구현할 때 가장 중요한 세 가지는 삽입, 삭제, 검색이다.

이 부분의 로직이 얼마나 깔끔하고 효율적으로 작성되었는지가 코드의 품질을 결정한다. 이를 위해 다양한 예시를 작성하고, 여러 접근 방식을 비교하면서 최적의 방식을 찾아보자.

 

이진 검색 트리 (Binary Search Tree, BST)의 사용 목적

 

이진 검색 트리는 데이터의 검색 보다는 데이터 확인 및 중복 방지에 더 적합한 자료구조로 볼 수 있다.

즉, 내가 데이터를 넣었던가? 와 같은 질문에 대해 확인하기 위해 사용되는 경우가 많다. 

 

결론 및 학습 방향

1. 자료구조의 삽입, 삭제, 검색 로직을 명확히 이해하고 효율적인 코드 작성을 목표로 삼는다.
2. 여러 예시를 만들어 보고, 서로 다른 구현 방식을 비교 분석하여 장단점을 파악한다.
3. 이진 검색 트리처럼 특정 자료구조의 실제 사용 목적과 특징을 제대로 이해하고 올바른 상황에서 사용하도록 한다.