이진 탐색 트리 (1)

대표적인 트리

• 원도우에서 파일 관리하는 방식
• 부모가 있고 또 폴더 밑에 폴더가 있공 계층적으로 설계된다.
• 순환이 없는 그래프가 트리다.
• 순회란 한 바퀴를 돌아서 오는것

요약

• 그래프
  • 노드간의 연결관계를 표현
• 트리
  • 순환이 불가능한 그래프
• 이진트리
  • 자식의 개수를 2개로 제한한 트리
• 이진탐색트리
  • 입력 데이터를 크기에 따라 좌우(작은것을 왼쪽, 큰것을 오른쪽)로 정렬하는 트리

탐색

• 순차 탐색
  • O(N)
  • 10만명중에 한명 찾을려고 0번부터 10만명까지 나올떄까지 뒤지는 것.)
• 이진 탐색
  • O(logN)
    • logN에서 밑은 2가 생략된 것이다.
    • 데이터가 1024개면 10번만에 해결, 4096개면 12번만에 해결
  • O(1) -> O(logN)은 드라마틱하게 효율 차이가 안난다.
  • O(logN) -> O(N)은 엄청난 효율 차이가 존재한다.
  • 이진탐색은 데이터가 정렬되어 있어야 한다.
    • 정렬이 되어있어야 절반날릴떄 날리는 절반을 안볼수 있기 떄문이당.
    • N(문제의 크기)를 절반씩 줄여나가는 방식.

트리용어 정리 및 특징

• 루트 노드
  • 부모 존재하지않는 노드, 최상단 노드
• 단말 노드(Leaf Node)
  • 자식이 존재하지 않는 노드, 최하단 노드
• 트리의 계층을 레벨이라하고 트리가 4레벨이라면 Height(높이)는 4라고 한다.
• 정렬이 끝났다면 왼쪽은 나보다 작은것, 오른쪽은 나보다 큰값이 들어간다.
• 입력을 받을때 값하나가 들어가는 작업이 O(logN)이다.

컨테이너	vector	list	map,set
자료구조	동적배열	연결형 리스트	이진탐색트리
입력	O(1)	O(1)	O(logN)
삭제	O(N)	O(1)	O(1)
인덱싱	O(1)	O(N)	O(N)
탐색	O(N)	O(N)	O(logN)

• 코드를 짤 상황에 맞게 장단점을 생각해서 컨테이너를 선택하자.

코드

	set<int> intset;

	intset.insert(100);
	intset.insert(150);
	intset.insert(170);
	intset.insert(125);
	intset.insert(80);
	intset.insert(90);
	intset.insert(50);

	set<int>::iterator iter = intset.find(125);
	iter = intset.find(125);					// 1
    iter = intset.find(124);					// 2
	if (iter != intset.end())
	{

	}
	else
	{

	}

• fine 함수는 입력된 데이터랑 동일한 데이터가 있는지 찾아서 그 데이터를 가리키는 iterator를 반환.
• 만약 해당 데이터가 컨테이너 안에 없었다면, end iterator를반환

                		100
			   		   /   \
					80		150
					/\		 /\
		  		  50  90  125 170

• 코드는 이렇게 되어야 한다.

#pragma once

template<typename T>
struct BSTNode
{
	T	Data;

	BSTNode* pParent;
	BSTNode* pLeftChild;
	BSTNode* pRightChild;
};

• 위에서 부터 순서대로
  • 데이터 값
  • 부모노드
  • 왼쪽자식노드
  • 오른쪽자식노드

강의코드

main.cpp

#include <iostream>

#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);
	set<int>::iterator iter = intset.find(125);
	iter = intset.find(125);
	iter = intset.find(124);
	if (iter != intset.end())
	{}
	else
	{}
    
	return 0;
}

BST.h

#pragma once


// Binary Search Tree(BST)

template<typename T>
struct BSTNode
{
	T	Data;

	BSTNode* pParent;
	BSTNode* pLeftChild;
	BSTNode* pRightChild;
};

1차 23.01.03
2차 24.01.04
3차 24.01.05
4차 24.01.09
5차 24.01.10