공부/알고리즘 (c++)

이진 탐색 트리

원클릭쓰리버그 2022. 2. 19. 18:58
728x90

BinarySearchTree.h

 

#pragma once

struct Node
{
	Node* parent = nullptr;
	Node* left = nullptr;
	Node* right = nullptr;
	int key = {};
};
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);

	Node* Max(Node* node);
	Node* Min(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)
{
	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)
		Search(node->left, key);
	else
		Search(node->right, key);
}

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

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

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


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

	Node* parent = node->parent;
	
	while (node == parent->right && parent)
	{
		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;
}

//3가지 경우의수
//1. 지우는 노드에 자식이 없는 경우
//2. 지우는 노드에 자식이 1개만 있는경우.
//3. 지누은 노드에 자식이 양 방향 있는 경우.
void BinarySearchTree::Delete(int key)
{
	Node* deleteNode = Search(_root, key);
	Delete(deleteNode);
}

void BinarySearchTree::Delete(Node* node)
{
	//지울 Node가 없는 경우.
	if (node == nullptr)
		return;

	//왼쪽 자식이 없을 경우. 
	//만약 오른쪽 노드도 없을 경우, 오른쪽 노드는 nullptr이므로 Replace(node, nullptr)로 이루어지게된다.
	//그러므로 자식이 없을 경우와 왼쪽 자식이 없을 경우 2가지를 동시에 실행할 수 있다.
	if (node->left == nullptr)
		Replace(node, node->right);
	// 오른쪽 자식 이 없을 경우.
	else if (node->right == nullptr)
		Replace(node, node->left);
	else 
	{
		// 양쪽에 있는 경우. 지우고 싶은 Node의 다음 순번을 찾아 서로 값을 바꾼 후, 지워준다.
		Node* next = Next(node);
		node->key = next->key;
		Delete(next);
	}

}

// u 노드에서 v 노드로 교체하는 작업
void BinarySearchTree::Replace(Node* u, Node* v)
{
	// 만약 부모가 없다면 최상단이다.
	if (u->parent == nullptr)
		_root = v;
	// u의 부모의 왼쪽 노드가 u일 경우
	else if (u == u->parent->left)
		u->parent->left = v;
	else // u의 부모의 오른쪽 노드가 u일 경우
		u->parent->right = v;
	//v를 u의 부모와 연결시켜준다.
	if (v)
		v->parent = u->parent;

	delete u;
}

 

Insert (삽입)

 

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 Print_Inorder(Node* node)

 

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

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

 

 

Node* [Max / Min / Next] (Node* node)

 

//가장 큰값은 루트에서 오른쪽 노드를 쭉 타고 가면 찾을 수 있다.
Node* BinarySearchTree::Max(Node* node)
{
	while (node->right)
	{
		node = node->right;
	}
	return node;
}
//가장 작은값은 루트에서 왼쪽 노드를 쭉 타고 가면 찾을 수 있다.
Node* BinarySearchTree::Min(Node* node)
{
	while (node->left)
	{
		node = node->left;
	}
	return node;
}


Node* BinarySearchTree::Next(Node* node)
{
// 만약 오른쪽 노드가 있다면 오른쪽 노드의 Min값을 출력하면 된다.
	if (node->right)
		return Min(node->right);
// 오른쪽 노드가 없다면, 
// 부모노드를 체크하여 자신이 왼쪽에 있는 자식이 맞는지 탐색한다.
	30
25		40
  26
//만약 26의 Next를 찾는다면, 
//25를 체크하여 node가 왼쪽자식인지 체크
//아닐시, 다시 25를 tempnode로 잡고, 30과 25를 체크하여 왼쪽자식인지 체크
//맞다면, 그게 Next노드 임으로 반환시켜준다.
	Node* parent = node->parent;
	
	while (node == parent->right && parent)
	{
		node = parent;
		parent = parent->parent;
	}

	return parent;
}

 

 

 

Node* Search(Node* node, int key)

 

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

	if (key < node->key)
		Search(node->left, key);
	else
		Search(node->right, key);
}

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

 

 

void Delete(int key) 와 void Replace(Node* u, Node* v)

 

//3가지 경우의수
//1. 지우는 노드에 자식이 없는 경우
//2. 지우는 노드에 자식이 1개만 있는경우.
//3. 지누은 노드에 자식이 양 방향 있는 경우.
void BinarySearchTree::Delete(int key)
{
	Node* deleteNode = Search(_root, key);
	Delete(deleteNode);
}

void BinarySearchTree::Delete(Node* node)
{
	//지울 Node가 없는 경우.
	if (node == nullptr)
		return;

	//왼쪽 자식이 없을 경우. 
	//만약 오른쪽 노드도 없을 경우, 오른쪽 노드는 nullptr이므로 Replace(node, nullptr)로 이루어지게된다.
	//그러므로 자식이 없을 경우와 왼쪽 자식이 없을 경우 2가지를 동시에 실행할 수 있다.
	if (node->left == nullptr)
		Replace(node, node->right);
	// 오른쪽 자식 이 없을 경우.
	else if (node->right == nullptr)
		Replace(node, node->left);
	else 
	{
		// 양쪽에 있는 경우. 지우고 싶은 Node의 다음 순번을 찾아 서로 값을 바꾼 후, 지워준다.
		Node* next = Next(node);
		node->key = next->key;
		Delete(next);
	}

}

// u 노드에서 v 노드로 교체하는 작업
void BinarySearchTree::Replace(Node* u, Node* v)
{
	// 만약 부모가 없다면 최상단이다.
	if (u->parent == nullptr)
		_root = v;
	// u의 부모의 왼쪽 노드가 u일 경우
	else if (u == u->parent->left)
		u->parent->left = v;
	else // u의 부모의 오른쪽 노드가 u일 경우
		u->parent->right = v;
	//v를 u의 부모와 연결시켜준다.
	if (v)
		v->parent = u->parent;

	delete u;
}
저작자표시 비영리 변경금지 (새창열림)

'공부 > 알고리즘 (c++)' 카테고리의 다른 글

퀵 정렬 (Quick Sort)  (0) 2022.03.16
정렬 (버블 정렬, 선택 정렬, 삽입 정렬)  (0) 2022.03.09
AStar 알고리즘  (0) 2022.02.14
우선순위 큐 (PriorityQueue)  (0) 2022.02.14
힙 이론  (0) 2022.02.09

'공부/알고리즘 (c++)'의 다른글

  • 현재글이진 탐색 트리

관련글

티스토리툴바