efsdfs

#pragma once

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;
};