[알고리즘] 이진 탐색(Binary Search), 이진 탐색 트리(Binary Search Tree)

글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자를 적어주세요. 글의 요약 설명 부분. 150자입니다

 

목차

 

 

인프런 Rookiss님의 '자료구조와 알고리즘' 강의를 기반으로 정리한 필기입니다. 
😎 [C++과 언리얼로 만드는 MMORPG 게임 개발 시리즈] Part3: 자료구조와 알고리즘 강의 들으러 가기!

---

이진 탐색 Binary Search

본문내용넣기

 

---

이진 탐색 특징

정렬된 배열을 이용해서 이진 탐색 가능 (numbers[mid])

BUT 중간 삽입/삭제가 느리다.

정렬된 연결 리스트로는 불가능하다. (임의접근이 불가능하다).

 

이진 탐색의 최대 반복 횟수는 log2 N이다.

 

이진 탐색 수행 과정 4단계

1. 데이터의 중앙 요소를 고른다.
2. 중앙값과 목표값을 비교한다.
3. '목표값 < 중앙값'이면 중앙을 기준으로 왼편으로, '목표값 > 중앙값'이면 오른쪽으로 이진 탐색을 새로 수행한다.
4. 찾는 값이 나올 때까지 1~3단계를 반복한다.

 

이진 탐색 코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

#include <iostream> #include <vector> #include <list> #include <stack> #include <queue> using namespace std;   // Q) 82라는 숫자가 배열에 있습니까? // A) // [1][8][15][23][32][44][56][63][81][91]   vector<int> numbers;   void BinarySearch(int N) {     int left = 0;     int right = (int)numbers.size() - 1;       while (left <= right)     {         cout << "탐색 범위: " << left << "-" << right << endl;           int mid = (left + right) / 2;           if (N < numbers[mid])         {             cout << N << " < " << numbers[mid] << endl;             right = mid - 1;         }         else if (N > numbers[mid])         {             cout << N << " > " << numbers[mid] << endl;             left = mid + 1;         }         else         {             cout << "찾음!" << endl;             break;         }     } }   int main() {     numbers = vector<int>{ 1, 8, 15, 23, 32, 44, 56, 63, 81, 91 };     BinarySearch(82); } Colored by Color Scripter

cs

 

 

 

---

 

이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리는 '이진 탐색을 위한 이진 트리'이다.

※ 이진 탐색 트리는 이진 트리와 구조는 같지만 반드시 아래의 특성을 갖추고 있어야 한다.

 

이진 탐색 트리의 각 노드는 왼쪽 자식 노드보다 크고 오른쪽 자식 노드보다 작다.

 

 

 

---

 

이진 탐색 트리 코드

 

BinarySearchTree.h

struct Node
{
	Node* parent = nullptr;
	Node* left = nullptr;
	Node* right = nullptr;
	int	  key = {};

	bool external;
};

class BinarySearchTree
{
public:
	void  Print() { Print(_root, 10, 0); } //트리 모양으로 변환된것을 출력
	void  Print(Node* node, int x, int y); //트리 모양으로 만듬
	void  Print_Inorder() { Print_Inorder(_root); }
	void  Print_Inorder(Node* node);

	Node* Search(Node* node, int key); // 재귀 방식
	Node* Search2(Node* node, int key); // Search와 같지만 스택에 덜 쌓이기 때문에 성능적으로 유리하다

	Node* Min(Node* node);
	Node* Max(Node* node);
	Node* Next(Node* node);

	void  Insert(int key);

	void  Delete(int key);
	void  Delete(Node* node);

	void  Replace(Node* u, Node* v);

private:
	Node* _root = nullptr;
};

 

 

BinarySearchTree.cpp

#include "BinarySearchTree.h"
#include <iostream>
#include <windows.h>
using namespace std;

void SetCursorPosition(int x, int y)
{
	HANDLE output = ::GetStdHandle(STD_OUTPUT_HANDLE);
	COORD pos = { static_cast<SHORT>(x), static_cast<SHORT>(y) };
	::SetConsoleCursorPosition(output, pos);
}

void BinarySearchTree::Print(Node* node, int x, int y)
{
	if (node == nullptr)
		return;

	SetCursorPosition(x, y);

	cout << node->key;
	Print(node->left, x - (5 / (y + 1)), y + 1);
	Print(node->right, x + (5 / (y + 1)), y + 1);
}

void BinarySearchTree::Print_Inorder(Node* node)
{
	// 전위 순회 (preorder traverse)
	// 중위 순회 (inorder)
	// 후위 순회 (postorder)

	if (node == nullptr)
		return;

	// 전위 : [중]이 앞에 온다
	// 중위 : [중]이 중간에 온다
	// 후위 : [중]이 마지막에 온다.

	cout << node->key << endl;
	Print_Inorder(node->left);
	Print_Inorder(node->right);
}

Node* BinarySearchTree::Search(Node* node, int key) // 재귀방식
{
	if (node == nullptr || key == node->key)
		return node;

	if (key < node->key)
		return Search(node->left, key);

	else
		return Search(node->right, key);
}

Node* BinarySearchTree::Search2(Node* node, int key)
{
	while (node && key != node->key)
	{
		if (key < node->key)
			node = node->left;
		else
			node = node->right;
	}

	return node;
}

Node* BinarySearchTree::Min(Node* node)
{
	while (node->left)
		node = node->left;

	return node;
}


Node* BinarySearchTree::Max(Node* node)
{
	while (node->right)
		node = node->right;

	return node;
}

Node* BinarySearchTree::Next(Node* node)
{
	if (node->right)
		return Min(node->right);

	Node* parent = node->parent;

	while (parent && node == parent->right)
	{
		node = parent;
		parent = parent->parent;
	}

	return parent;
}

void BinarySearchTree::Insert(int key)
{
	Node* newNode = new Node();
	newNode->key = key;

	if (_root == nullptr) // 데이터가 아무것도 없는 상태
	{
		_root = newNode;
		return;
	}

	Node* node = _root;
	Node* parent = nullptr;

	while (node)
	{
		parent = node;
		if (key < node->key)
			node = node->left;
		else
			node = node->right;
	}

	newNode->parent = parent;

	if (key < parent->key)
		parent->left = newNode;
	else
		parent->right = newNode;

}

void BinarySearchTree::Delete(int key)
{
	Node* deleteNode = Search(_root, key); // 뿌리에서 키값의 위치를 찾아준다
	Delete(deleteNode);                    // 찾은 노드를 아래의 Delete방식으로 제거한다. 
}

void BinarySearchTree::Delete(Node* node)
{
	if (node == nullptr)
		return;

	if (node->left == nullptr)      // 왼쪽이 비어있거나
		Replace(node, node->right); 
	else if (node->right == nullptr) // 오른쪽이 비어있거나
		Replace(node, node->left); 
	else                            // 왼쪽, 오른쪽 다 있는 경우
	{
		// 다음 데이터 찾기
		Node* next = Next(node);
		node->key = next->key;
		Delete(next);
	}
}

// u 서브트리를 v 서브트리로 교체
// 그리고 delete u
void BinarySearchTree::Replace(Node* u, Node* v)
{
	if (u->parent == nullptr)
		_root = v;
	else if (u == u->parent->left) // 부모노드의 left자식노드였을 경우
		u->parent->left = v;       // 부모노드 위치에 left자식노드를 대입
	else                           // 부모노드의 right자식노드였을 경우
		u->parent->right = v;      // 부모노드 위치에 right자식노드를 대입

	if (v)
		v->parent = u->parent;

	delete u;
}

 

 

 

 

---

 

전체코드