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

어제 했던 더미노드에 대한 복습과 이진 검색 트리에 대한 수업을 들었다.

 

1. 더미노드 복습 

// node.h
#pragma once

class C_LIST;

class C_NODE
{
	friend C_LIST;
private:
	int m_nData;
	C_NODE* m_pPrev;
	C_NODE* m_pNext;

private:
	C_NODE* linkNode(C_NODE* pNext);

public:
	C_NODE() = default;
	int getData();
	C_NODE* getNext();
	void init(int nData);
};

// node.cpp
#include "node.h"

C_NODE* C_NODE::linkNode(C_NODE* pNext)
{
    m_pNext = pNext;
    pNext->m_pPrev = this;

    return pNext;

    //return this; // 이거 이렇게 하는게 연속되게 체이닝 할수있게 하게끔 하는거
    //// 이걸 만듬으로써 insertNode를 만들지 않음 
}

int C_NODE::getData()
{
    return m_nData;
}

C_NODE* C_NODE::getNext()
{
    return m_pNext;
}

void C_NODE::init(int nData)
{
    m_nData = nData;
    m_pPrev = nullptr;
    m_pNext = nullptr;
}

// list.h
#pragma once
#include "node.h"

class C_LIST
{
private:
	C_NODE* m_pBegin;
	C_NODE* m_pEnd;

private:
	C_NODE* createNode(int nData);
	void insertNode(C_NODE* m_prev, C_NODE* pNode, C_NODE* pNext);
public:
	C_LIST();
	void pushBack(int nData);
	void pushfront(int nData);
	void erase(C_NODE* pNode);
	C_NODE* getBegin();
	C_NODE* getEnd();
};

// list.cpp
#include "list.h"

C_NODE* C_LIST::createNode(int nData)
{
    C_NODE* pNode = new C_NODE{};
    pNode->init(nData);

    return pNode;
}

//void C_LIST::insertNode(C_NODE* pPrev, C_NODE* pNode, C_NODE* pNext)
//{
//    pPrev->linkNode(pNode);
//    pNode->linkNode(pNext);
//}

void C_LIST::insertNode(C_NODE* pPrev, C_NODE* pNode, C_NODE* pNext)
{
    pPrev->linkNode(pNode)->linkNode(pNext); // return pNext;
    //pPrev->linkNode(pNode->linkNode(pNext));  // return this;
}

C_LIST::C_LIST():
    m_pBegin{},
    m_pEnd{}
{
    m_pBegin = createNode(0);
    m_pEnd = createNode(0);
    m_pBegin->linkNode(m_pEnd);
}

void C_LIST::pushBack(int nData)
{
    insertNode(m_pEnd->m_pPrev, createNode(nData), m_pEnd);
}

void C_LIST::pushfront(int nData)
{
    insertNode(m_pBegin, createNode(nData), m_pBegin->m_pNext);
}

void C_LIST::erase(C_NODE* pNode)
{
    pNode->m_pPrev->linkNode(pNode->m_pNext);
    delete pNode;
}

C_NODE* C_LIST::getBegin()
{

    return m_pBegin->m_pNext;
}

C_NODE* C_LIST::getEnd()
{

    return m_pEnd;
}


//main.cpp
#include <iostream>
#include "list.h"

void print(C_NODE* pBegin, C_NODE* pEnd);

int main()
{
    C_LIST cList{};

    cList.pushBack(1);
    cList.pushBack(2);
    cList.pushBack(3);
    cList.pushBack(4);
    cList.pushBack(5);
    cList.pushBack(6);
    cList.pushBack(7);
    cList.pushfront(11);
    cList.pushfront(12);
    cList.pushfront(13);
    cList.pushfront(14);

    print(cList.getBegin(), cList.getEnd());

    C_NODE* pNode = cList.getBegin();
    while(pNode != cList.getEnd())
    {
        C_NODE* pNext = pNode->getNext(); // 백업을 해야함 안그러면 아래 PNode가 이미 삭제되어있는 상태기 때문에 코드가 터짐 ( 삭제되었는데어떻게 연결을 하는가 )

        if (pNode->getData() > 5)
            cList.erase(pNode);

        pNode = pNext;
    }
    print(cList.getBegin(), cList.getEnd());
}

void print(C_NODE* pBegin, C_NODE* pEnd)
{
    for (C_NODE* pNode = pBegin; pNode != pEnd; pNode = pNode->getNext())
    {
        printf("%d ", pNode->getData());
    }
    printf("\n");
}

 

 

2. 이진 검색 트리 ( Binart Search Tree, BST )

2.1 이진 검색 트리 특징

• 노드 수 : 각 노드는 최대 2개의 자식 노드를 가질수 있으며, 기본적으로 노드는 2개 이상이다.
• 구조 :
  1. Root가 존재한다.
  2. 각 노드의 값은 왼쪽 자식노드는 Root값보다 작고, 오른쪽 자식노드는 Root값보다 크다 .

2.2 이진 검색 트리의 목적

• 이진 검색 트리는 특정 값이 컨테이너에 존재 여부를 확인하기 위한 목적
• 즉, 단순히 데이터를 저장하거나 순서대로 나열하여 검색하는게 목적이 아니다.

2.3 이진 검색 트리의 한계 ( 잘못된 경우 )

• 검색 성능 저하 :
  입력 데이터가 정렬된 상태 ( 1, 2, 3, 4, 5, 6 )로 삽입되면 트리가 한쪽으로 치우치게 된다. 그럼 결과적으로 Linked List와 동일한 구조가 되어 검색 속도가 저하된다. 
• 이 경우, 시간 복잡도가 O(log n)에서 O(n)으로 저하된다. 그렇기에 트리의 균형을 유지해야 검색 속도가 보장된다.

2.4 변종 이진 검색 트리

검색 성능 저하 문제를 해결하기 위해 균형을 유지하는 변종 트리들이 존재한다.

1. AVL 트리
   - 이진 검색 트리의 균형을 유지하기 위해 각 노드의 높이 차이( 왼쪽과 오른쪽 서브트리 높이 ) 를 제한한다.
   - 삽입 / 삭제 시 트리가 불균형해지면 회전연산을 통해 자동으로 균형을 맞춘다.
2. 레드 블랙 트리 
   - 각 노드에 생상( 레드 / 블랙 ) 을 추가로 저장해 트리의 균형을 유지한다.
   - AVL 트리보다 약간 덜 엄격한 균형 규칙을 사용해 삽입 / 삭제 성능이 더 빠르다.

 

2.5 이진 검색 트리 ( Insert 구현 )

// 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);
public:
	C_BST() = default;
	void insert(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;
}
void C_BST::insert(int nData)
{
	if (!m_pRoot)
	{
		m_pRoot = createNode(nData);
		return;
	}

	S_NODE* pNode = m_pRoot;

	while (pNode)
	{
		if (nData < pNode->nData)
		{
			if (pNode->pL == nullptr)
			{
				pNode->pL = createNode(nData);
				return;
			}
			pNode = pNode->pL;
		}

		else if (nData > pNode->nData)
		{
			if (pNode->pR == nullptr)
			{
				pNode->pR = createNode(nData);
				return;
			}
			pNode = pNode->pR;
		}
	}
}

void C_BST::print()
{
	printNode(m_pRoot);
}

// main.cpp
#include <iostream>
#include "bst.h"

int main()
{
	C_BST cBst{};

	cBst.insert(1);
	cBst.insert(2);
	cBst.insert(3);
	cBst.insert(4);
	cBst.insert(5);

	cBst.print();
}