의문점
- 데이터가 입력될떄 1 -> 2 -> 3 -> 4 -> 5 -> 6을 넣었는데 이거 데이터 6을 찾을려면 O(N)이 아니냐?
- 이진탐색트리는 한쪽으로 쭉 늘어져 있으면 연결형 리스트랑 다를게 없다.
- 그래서 순서가 잘못되어버리면 늘어져서 될수도 있당.
- 해결 : 자가 균형 이진 탐색 트리
- 그래서 O(logN)이 될려면 트리가 밸러스에 맞게 정렬이 되어있어야 한다.
- 트리가 균형잡혀있다고 가정해야 O(logN)이다.
- 퀵소트, 머지소트, 힙소트
- O(N logN)
- 3개는 빅오 효율이 같지만 구현의 관점에서는 효율이 다르다.
- 자가균형 이진탐색트리(Self Balanced Binary Search Tree)
- set, map 표쥰 라이브러리는 자가균형 이진탐색트리로 구현되어있다.
- Red-Block, AVL 이다.
- 코드로 구현관점에서 Red-Block이 더 AVL보다 빠르다.
- 수업은 이진탐색트리까지 구현하고 레드블랙트리는 내가 블로그 정리한거 보고 구현해보기
map 사용해보깅.
template<typename T, typename T2>
class MyTemplateClass
{
T m_Data1;
T2 m_Data2;
};
MyTemplateClass<int, float> obj;
#include <set>
#include <map>
using std::set;
using std::map;
using std::make_pair; // 1
int main()
{
map<int, int> intmap;
intmap.insert(make_pair(100, 1)); // 2
intmap.insert(make_pair(150, 2));
intmap.insert(make_pair(170, 3));
intmap.insert(make_pair(125, 4));
intmap.insert(make_pair(80, 5));
intmap.insert(make_pair(90, 6));
intmap.insert(make_pair(50, 7));
return 0;
}- set이랑 다르게 typename을 2개를 지정해야 한다.
- set
- 넣는 데이터를 크기 비교 용도로 사용한다.
- map
- 첫번째를 입력을 할떄 대소를 비교하는 용도(기준)이고 비교할 키값이다.
- 두번쨰를 자리 찾아서 들어갈 데이터의 실제 값.
- set
- set 안쓰는 이유
- 내가 넣을 데이터가 비교용도로도 동시에 쓰인다는 보장이 없다.
- 유저의 정보를 저장할건대 정보끼리 데이터 1개로 어떻게 비교함?
- 넣을 데이터 자체가 기준이 없어서 1개는 유저의 고유한 키값 2번째로 들어갈 데이터는 실제 들어간 데이터를 넣어서 사용해야 하기 때문에 set을 사용안하고 map을 사용한다.
- 1번인 make_pair가 입력된 두타입으로 하나의 pair를 만든다.
- 2번은 100과 1을 make pair로 만들어준다는 것이고 인자 두개를 저렇게 받으면 된다.
100-1
/ \
80-5 150-2
/ \ / \
50-7 90-6 125-4 170-3- insert하면 이런식으로 구현이 된다.
map용 템플릿.
template<typename T1, typename T2>
struct BSTNode
{
T1 first;
T2 second;
BSTNode* pParent;
BSTNode* pLeftChild;
BSTNode* pRightChild;
};- 이런식으로 구조체 BSTNode에 다 적어놓을수 있지만 구분을 위해 분리해줘야 된다.
template<typename T1, typename T2>
struct BSTPair
{
T1 first;
T2 second;
};
template<typename T1, typename T2>
struct BSTNode
{
BSTPair<T1, T2> pair;
BSTNode* pParent;
BSTNode* pLeftChild;
BSTNode* pRightChild;
};- BSTPair 구조체 템플릿을 만들어서 T1,T2를 하나의 pair로 사용할수 있겠되었다.
map<int, int>::iterator mapiter = intmap.find(50);
if (mapiter == intmap.end());
{
//*mapiter; // 1
(*mapiter).first;
(*mapiter).second;
}- set이랑 다르게 iterator도 사용법이 다르다.
- 1번은
.을 눌러서 pair에 접근 가능 first, second 나온다.- first에 접근하면 50이 나옴
- second에 접근하면 7이 나옴
- 1번은
BST클래스 구현
template <typename T1, typename T2>
class BST
{
private:
BSTNode<T1, T2>* m_Root; // 1
int m_CurCount; // 2
public:
void insert();
};- 1번은 루트 노드 주소
- 2번은 현재 데이터 개수
template<typename T1, typename T2> BSTPair<T1, T2> make_bstpair(const T1& _first, const T2& _second) { // 1 BSTPair<T1, T2> pair; pair.first = _first; pair.second = _second; // 2 BSTPair<T1, T2> pair = { _first ,_second } return pair; // 3 return BSTPair<T1, T2>(_first, _second); } - 입력된 T1, T2 타입의 데이터를 묶어서 BSTPair<T1. T2'> 타입 구조체 반환 하는 코드
- 2번은 1번의 축약 시킨 버전이고
- 3번은 2번을 임시객체로(지역변수 이름 안주는거) 바로 BSTPiar를 반환하고 있당.
template<typename T1, typename T2>
struct BSTPair
{
T1 first;
T2 second;
// 1
BSTPair(const T1& _first, const T2& _second)
: first(_first)
, second(_second)
{
}
};- 반환해주는 코드에서 바로 인자를 받아서 초기화 할려면 1번처럼 BSTpair에 생성자를 미리 만들어 두면 된다.
map의 insert함수 구현.
class BST
{
private:
BSTNode<T1, T2>* m_Root;
int m_CurCount;
public:
//void insert();
void insert(const BSTPair<T1, T2>& _pair);- BST클래스의 insert의 선언부의 인자(_pair)를 준다.
template<typename T1, typename T2>
void BST<T1, T2>::insert(const BSTPair<T1, T2>& _pair)
{
BSTNode<T1, T2>* pNewNode = new BSTNode<T1, T2>(_pair);
// 2.1
if (nullptr == m_Root)
{
this->m_Root = pNewNode;
}
else
{
BSTNode<T1, T2>* pNode = m_Root;
while (true)
{
if (pNewNode->pair.first < pNode->pair.first)
{
if (nullptr == pNode->pLeftChild)
{
pNode->pLeftChild = pNewNode;
pNewNode->pParent = pNode;
break;
}
pNode = pNode->pLeftChild;
}
else if (pNode->pair.first < pNewNode->pair.first)
{
if (nullptr == pNode->pRightChild)
{
pNode->pRightChild = pNewNode;
pNewNode->pParent = pNode;
break;
}
pNode = pNode->pRightChild;
}
}
}
++m_CurCount;
}- insert구현코드 아래부터 분석할거임
pair.first;
pair.second;- pair타입으로 받은거는 들어오면 first와 second가 존재한다.
if (nullptr == m_Root)
{
}
else- 데이터가 최초로 들어올떄 조건을 걸어야함.
- m_Root가 nullptr이라면
BST()
: m_Root(nullptr)
, m_CurCount(0)
{}
~BST()
{
// 모든 노도들 삭제
}- BST클래스안에 기본 생성자와 소멸자를 만들어 둬야한다.
- 소멸자로 모든 노드를 삭제하는 코드는 입력을 다 만들고 만들겠다.(내일수업)
BSTNode<T1, T2>* pNewNode = new BSTNode<T1, T2>(_pair,nullptr,nullptr,nullptr);- 힙메모리 영역에 노드를 생성시키는 코드다.
- T1,T2타입의 pair를 힙에 넣어둿당 가리키는 포인터는 nullptr이당
template<typename T1, typename T2>
struct BSTNode
{
BSTPair<T1, T2> pair;
BSTNode* pParent;
BSTNode* pLeftChild;
BSTNode* pRightChild;
// 1
BSTNode()
//: pair(_pair)
: pParent(nullptr)
, pLeftChild(nullptr)
, pRightChild(nullptr)
{}
// 2
BSTNode(const BSTPair<T1, T2>& _pair, BSTNode* _Parent, BSTNode* _LeftChild, BSTNode* _RightChild)
: pair(_pair)
, pParent(_Parent)
, pLeftChild(_LeftChild)
, pRightChild(_RightChild)
{}
};- BSTnode 기본생성자와 인자를 받는 생성자를 안만들어 둿으니 만든다.
- 1번에서 pair(_pair)는 이것도 BSTPair구조체에 생성자가 있으니 굳이 명시안해도 된다.
- 1번에서 포인터 타입들은 nullptr로 초기화안해두면 쓰레기값으로 채워져있을수도 있으니 정확하게 초기화 시킨다.
- 2번은 생성자 버전을 따로 만들어서 받는다.
BSTNode(const BSTPair<T1, T2>& _pair, BSTNode* _Parent = nullptr, BSTNode* _LeftChild = nullptr, BSTNode* _RightChild = nullptr)
: pair(_pair)
, pParent(_Parent)
, pLeftChild(_LeftChild)
, pRightChild(_RightChild)
{}- 2번 코드 개선사항으로 값을 생성자에 인자를 전달할떄 _pair만 주면 3개의 포인터 값들에는 초기값을 넣어버릴수 있당.
BSTNode<T1, T2>* pNewNode = new BSTNode<T1, T2>(_pair);- 디폴트 인자를 넣어서 nullptr을 입력할 필요가없다.
if (nullptr == m_Root)
{
this->m_Root = pNewNode;
}
++m_CurCount;- 최초의 데이터를 넣을때의 케이스는 완성
- 새로생긴노드의 주소값을 m_Root포인터에 넣는다.
- 데이터 카운트 1증가.
else
{
BSTNode<T1, T2>* pNode = m_Root; // 1
while (true) // 6
{
if (pNewNode->pair.first < pNode->pair.first) // 2
{
if (nullptr == pNode->pLeftChild) // 7
{
pNode->pLeftChild = pNewNode; // 8
pNewNode->pParent = pNode; // 9
break; // 10
}
pNode = pNode->pLeftChild; // 3
}
else if (pNode->pair.first < pNewNode->pair.first) // 4
{
if (nullptr == pNode->pRightChild) // 11
{
pNode->pRightChild = pNewNode; // 12
pNewNode->pParent = pNode; // 13
break; // 14
}
pNode = pNode->pRightChild; // 5
}
}
}
++m_CurCount; // 15-
문제는 최초일떄말고 두번째 데이터 넣을때부터의 코드다.
-
1번은
m_Root부터 시작해서 지역변수pNode에m_Root를 대입한다.- 지역변수에 넣는 이유는 반복문 조건문에 사용할 지역변수를 만든것.
-
2번은
입력된 first값이현재 노드의 first값보다 작은 경우- 3번처럼 왼쪽으로 내려간다.
-
4번은
입력된 first값이현재 노드의 first값보다 큰 경우- 5번처럼 오른족으로 내려간다.
-
저 2~5번 작업을 반복해야되니 6번처럼
while문으로 조건문을 둘른다. -
7번은 왼쪽 방향으로 이미 정해졌으므로 내려갈 되가
nullptr이라면 멈추는 조건문- 8,9번은 부모 자식을 연결한 코드고 입력된 노드의 왼쪽으로 연결하는 코드다.
- 10번은 이제 마지막에 왔으니
while문을 탈출한다.
-
11번은 오른쪽 방향으로 이미 정해졌으므로 내려갈 되가
nullptr이라면 멈추는 조건문- 12,13번은 부모 자식을 연결한 코드고 입력된 노드의 오른쪽으로 연결하는 코드다.
- 14번은 이제 마지막에 왔으니
while문을 탈출한다.
-
15 하나를 채워넣으면 현재값을 증가.
BST insert 테스트
BST<int, float> bst;
bst.insert(make_bstpair<int, float>(100, 1.1f));
bst.insert(make_bstpair<int, float>(150, 2.2f));
bst.insert(make_bstpair<int, float>(50, 2.2f));
- 잘들어가있다.
template <typename T1, typename T2>
class BST
{
private:
BSTNode<T1, T2>* m_Root;
int m_CurCount;
public:
void insert(const BSTPair<T1, T2>& _pair);
// 1
class iterator;
iterator find(const T1& _ket);
public:
BST()
: m_Root(nullptr)
, m_CurCount(0)
{}
// 3
~BST()
{
// 모든 노도들 삭제
}
// 2
class iterator
{
};
};- 데이터를 입력과 탐색은 비슷하지만 탐색이 문제다. 새로운 노드를 안받들 뿐이지 비교하는건 똑같다.
- find는 숫자가 없다는 것을 end iterator를 반환해야하고 있다면 숫자에 iterator을 반환해야한다.
- 그래서 우리도 탐색을 위해 iterator을 구현해야한다.
- 1번처럼 T1값을 받아서 잇었으면 해당 노드를 가리키는 이터레이터 반환 없었다면 end이터레이터 반환
- 2번은 그래서 iteator BST에 이너클래스로 만들어야 한다.
- 3번에서 모든 노드 삭제하는 방법은 크게 2가지이다.
1.쉬운방법 재귀함수(계층할떄 굿->트리다.)- ?
재귀함수를 이용해서 모든 함수를 순회하는 Circit함수 구현
// 2
public:
void Circit()
{
Circit(m_Root);
}
// 1
private:
void Circit(BSTNode<T1, T2>* _Node);- 1번은 서킷함수에서 입력인자로는 내가 방문할 노드의 주소를 받을것이다.
- private으로 공개하지않고
- 2번처럼 실제 공개는 2번에서한다.
- 입력인자로 m_Root노드를 방문할것이다.
template<typename T1, typename T2>
inline void BST<T1, T2>::Circit(BSTNode<T1, T2>* _Node)
{
// 3
if (nullptr == _Node)
{
return;
}
std::cout << _Node->pair.first << std::endl;
Circit(_Node->pLeftChild); // 1
Circit(_Node->pRightChild); // 2
}- 실제 Circit 구현부분
- 1.2번에 들어오면 Node안에는 왼쪽아이,오른쪽아이 존재한다.
- 왼쪽 오른쪽 확인햇는데 nullptr일수도 있으니 3번처럼 nullptr이면 바로 돌아오는 코드(종료조건)를 설계함.
BST<int, float> bst;
bst.insert(make_bstpair<int, float>(100, 1.1f));
bst.insert(make_bstpair<int, float>(150, 2.2f));
bst.insert(make_bstpair<int, float>(50, 2.2f));
bst.Circit();- 전위, 중위, 후위 순회 코드 만들기
100
50 150- 전위
if (nullptr == _Node)
{
return;
}
std::cout << _Node->pair.first << std::endl;
Circit(_Node->pLeftChild);
Circit(_Node->pRightChild);-
서킷이라는 함수가 호출되면 루트노드(100)이다.
-
첫번째 호출스택에서 왼쪽을 호출한다.
- 두번쨰 지역변수에 들어온 호출스택에서 주소값은 루트노드의 왼쪽값이 들어왔을것이다.
-
다시 방문할 왼쪽을 함수를 호출하면 3번째 호출스택은 50의 왼쪽은 없으니까 입력으로 nullptr반환되서 호출 종료
-
2번째 코드로 호출스택이 돌아와서 오른쪽 호출스택을 확인하고 거기도 없으니 nullptr반환해서 호출 종료
-
100에 오른쪽을 확인 150(출력)
-
150에서 왼쪽 호출하면 없으니까 nullptr하고 오른쪽도 호출해서 없으니까 nullptr하고 재귀함수가 종료된다.
제공하신 코드는 이진 탐색 트리(Binary Search Tree, BST)의 전위 순회(pre-order traversal)를 위한
Circit함수입니다. 전위 순회에서는 루트 노드를 먼저 처리한 후, 왼쪽 서브트리와 오른쪽 서브트리를 순차적으로 방문합니다. 함수는 재귀적으로 구현되어 있습니다.
-
gpt
-
Circit함수의 첫 번째 호출 (루트 = 100):- 현재 노드(
100)를 처리합니다 (출력). - 왼쪽 자식(
50)으로 재귀 호출을 합니다. - 오른쪽 자식(
150)으로 재귀 호출을 합니다.
- 현재 노드(
-
Circit함수의 두 번째 호출 (루트 = 50):- 현재 노드(
50)를 처리합니다 (출력). 50의 왼쪽 자식은 없으므로, 왼쪽 자식에 대한 호출은 무시됩니다.50의 오른쪽 자식도 없으므로, 오른쪽 자식에 대한 호출도 무시됩니다.- 첫 번째 호출로 돌아갑니다.
- 현재 노드(
-
첫 번째 호출로 돌아옴 (루트 = 100), 오른쪽 자식 처리:
- 오른쪽 자식(
150)으로 재귀 호출을 합니다.
- 오른쪽 자식(
-
Circit함수의 세 번째 호출 (루트 = 150):- 현재 노드(
150)를 처리합니다 (출력). 150의 왼쪽 자식은 없으므로, 왼쪽 자식에 대한 호출은 무시됩니다.150의 오른쪽 자식도 없으므로, 오른쪽 자식에 대한 호출도 무시됩니다.- 모든 재귀 호출이 완료되고, 스택이 완전히 풀립니다.
- 현재 노드(
-
-
전위 순회의 결과로서, 노드들은 다음 순서로 처리됩니다:
100,50,150. 이 순서는 루트를 먼저 방문하고, 그 다음으로 왼쪽 및 오른쪽 서브트리를 방문하는 전위 순회의 특징을 반영합니다.
BST<int, float> bst;
bst.insert(make_bstpair<int, float>(100, 1.1f));
bst.insert(make_bstpair<int, float>(150, 2.2f));
bst.insert(make_bstpair<int, float>(50, 2.2f));
bst.insert(make_bstpair<int, float>(170, 1.1f));
bst.insert(make_bstpair<int, float>(125, 2.2f));
bst.insert(make_bstpair<int, float>(25, 2.2f));
bst.insert(make_bstpair<int, float>(75, 2.2f));
bst.Circit();
100
50 150
25 75 125 170- 노드를 더 추가함.
- 전위
- 100 -> 50 -> 25 -> 75 -> 150 -> 125 -> 170(출력)
if (nullptr == _Node)
{
return;
}
Circit(_Node->pLeftChild);
std::cout << _Node->pair.first << std::endl;
Circit(_Node->pRightChild);- 중위
- 25 -> 50 -> 75 -> 100 -> 125 -> 150 -> 175(출력)
- 이진탐색트리로 정렬되서 중위 순회하면 오름차순으로 출력된다.
if (nullptr == _Node)
{
return;
}
Circit(_Node->pLeftChild);
Circit(_Node->pRightChild);
std::cout << _Node->pair.first << std::endl;- 후위
- 25 -> 75 -> 50 -> 125 -> 170 -> 150 -> 100(출력)
- 전위 중위 후위는 외울필요없이 재귀함수로 생각해서 출력하는 위치를 고려하면 된다.
- 정말 재귀함수 방식은 전위 순회 방식이다.
강의 코드
main.cpp
#include <iostream>
#include "BST.h"
template<typename T1, typename T2>
class MyTemplateClass
{
T1 m_Data1;
T2 m_Data2;
};
MyTemplateClass<int, float> obj;
#include <set>
#include <map>
using std::set;
using std::map;
using std::make_pair;
int main()
{
set<int> intset;
intset.insert(100);
intset.insert(150);
intset.insert(170);
intset.insert(125);
intset.insert(80);
intset.insert(90);
intset.insert(50);
// 100
// / \
// 80 150
// /\ /\
// 50 90 125 170
set<int>::iterator iter = intset.find(125);
iter = intset.find(124);
if (iter != intset.end())
{
}
else
{
}
// map 사용
map<int, int> intmap;
intmap.insert(make_pair(100, 1));
intmap.insert(make_pair(150, 2));
intmap.insert(make_pair(170, 3));
intmap.insert(make_pair(125, 4));
intmap.insert(make_pair(80, 5));
intmap.insert(make_pair(90, 6));
intmap.insert(make_pair(50, 7));
// 100-1
// / \
// 80-5 150-2
// / \ / \
// 50-7 90-6 125-4 170-3
map<int, int>::iterator mapiter = intmap.find(50);
if (mapiter != intmap.end())
{
(*mapiter).first;
(*mapiter).second;
}
// BST insert 테스트
BST<int, float> bst;
bst.insert(make_bstpair(100, 1.1f));
bst.insert(make_bstpair(150, 2.2f));
bst.insert(make_bstpair(50, 2.2f));
bst.insert(make_bstpair(170, 1.1f));
bst.insert(make_bstpair(125, 2.2f));
bst.insert(make_bstpair(25, 2.2f));
bst.insert(make_bstpair(75, 2.2f));
// 100
// 50 150
// 25 75 125 170
bst.Circit();
return 0;
}BST.h;
#pragma once
#include <iostream>
// Binary Search Tree(BST)
template<typename T1, typename T2>
struct BSTPair
{
T1 first;
T2 second;
BSTPair()
{}
BSTPair(const T1& _first, const T2& _second)
: first(_first)
, second(_second)
{
}
};
template<typename T1, typename T2>
struct BSTNode
{
BSTPair<T1, T2> pair;
BSTNode* pParent;
BSTNode* pLeftChild;
BSTNode* pRightChild;
BSTNode()
: pParent(nullptr)
, pLeftChild(nullptr)
, pRightChild(nullptr)
{}
BSTNode(const BSTPair<T1, T2>& _pair, BSTNode* _Parent = nullptr, BSTNode* _LeftChild = nullptr, BSTNode* _RightChild = nullptr)
: pair(_pair)
, pParent(_Parent)
, pLeftChild(_LeftChild)
, pRightChild(_RightChild)
{}
};
template<typename T1, typename T2>
class BST
{
private:
BSTNode<T1, T2>* m_Root;
int m_CurCount;
public:
void insert(const BSTPair<T1, T2>& _pair);
public:
void Circit()
{
Circit(m_Root);
}
private:
void Circit(BSTNode<T1, T2>* _Node);
//class iterator;
//iterator find(const T1& _key);
public:
BST()
: m_Root(nullptr)
, m_CurCount(0)
{}
~BST()
{}
/*class iterator
{
};*/
};
template<typename T1, typename T2>
BSTPair<T1, T2> make_bstpair(const T1& _first, const T2& _second)
{
return BSTPair<T1, T2>(_first, _second);
}
template<typename T1, typename T2>
void BST<T1, T2>::insert(const BSTPair<T1, T2>& _pair)
{
BSTNode<T1, T2>* pNewNode = new BSTNode<T1, T2>(_pair);
if (nullptr == m_Root)
{
m_Root = pNewNode;
}
else
{
BSTNode<T1, T2>* pNode = m_Root;
while (true)
{
if (pNewNode->pair.first < pNode->pair.first)
{
if (nullptr == pNode->pLeftChild)
{
pNode->pLeftChild = pNewNode;
pNewNode->pParent = pNode;
break;
}
pNode = pNode->pLeftChild;
}
else if (pNode->pair.first < pNewNode->pair.first)
{
if (nullptr == pNode->pRightChild)
{
pNode->pRightChild = pNewNode;
pNewNode->pParent = pNode;
break;
}
pNode = pNode->pRightChild;
}
}
}
++m_CurCount;
}
template<typename T1, typename T2>
inline void BST<T1, T2>::Circit(BSTNode<T1, T2>* _Node)
{
if (nullptr == _Node)
{
return;
}
std::cout << _Node->pair.first << std::endl;
Circit(_Node->pLeftChild);
Circit(_Node->pRightChild);
}1차 24.01.04
2차 24.01.05
3차 24.01.09
4차 24.01.10
5차 24.01.11
:D