20. 우선순위 큐(Priority Queue) -a. 이진탐색트리 기반

우선순위 큐

  # 큐가 들어온 시간에 따라 우선순위를 정한 것이고, 스택이 들어온 시간의 역순으로 우선순위를 정해 우선순위가 높은 것을 먼저 내보내는 자료구조라면

     우선순위 큐는 데이터에 따라 다르게 정해지는 우선순위에 따라 먼저 내보낼 자료구조를 정하는 자료구조이다.

  # 우선순위 큐는 들어온 순서에 상관없이 우선순위가 높은 것을 가장 먼저 내보낸다는 것만 지켜지면 되는 추상적인 자료구조이다.

  # 우선순위 큐는 데이터의 값을 대소비교해서 우선순위를 정할 수도 있고, 우선순위를 따로 표시하는 태그를 가질수도 있다.

  # 우선순위 큐의 ADT

    Add : 우선순위 큐에 데이터 삽입하기. 

    Remove : 가장 우선순위가 높은 데이터 삭제하기. (혹은 내보내기)

    Retrieve : 가장 우선순위가 높은 데이터 확인하기. 

    Count : 큐에 들어있는 데이터 수 확인하기.

    

 C++로 구현한 이진탐색트리 기반의 우선순위 큐

 #pragma once
//일단 구현에 집중하기 위해서 데이터형을 정수로 고정.

struct node
{
	int data;
	node* left;
	node* right;
};


class PQ_BST
{
public:
	node* TreePointer;

private:
	node* &RootNode = TreePointer;
	int   iCount;

	int*  tRet;

private:
	node* MakeNode(int data);

public:
	void Add(int data);
	int Remove();
	int Retrieve();
	int Count();

public:
	PQ_BST();
	virtual	~PQ_BST();
};

//----------------------------->>

node* PQ_BST::MakeNode(int data)
{
	node* nn = new node;
	nn->data = data;
	nn->left = nullptr;
	nn->right = nullptr;

	return nn;
}

//----------------------------->>

PQ_BST::PQ_BST()
{
	TreePointer = nullptr;
	iCount = 0;
	tRet = new int;
}

void PQ_BST::Add(int data)
{
	node* nptr = nullptr;
	
	iCount++;

	if (RootNode == nullptr) {
		RootNode = MakeNode(data);
	}
	else {
		nptr = RootNode;
		node* nNode = MakeNode(data);
	
		while (true) {
			if (nNode->data < nptr->data) {  			// 새로운 데이터가 현재 위치의 노드의 데이터보다 작을 경우
				if (nptr->left != nullptr) {            // 현재 위치의 노드에 왼쪽 노드가 이미 있으면
					nptr = nptr->left;                  // 현재 노드의 위치를 왼쪽 노드로 이동
				}										   
				else {				                    // 왼쪽 노드가 없으면
					nptr->left = nNode;                 // 현재 위치의 왼쪽 노드에 새로운 데이터를 붙인다.
					break;
				}
			}
			else if (nNode->data > nptr->data) {        // 새로운 데이터가 현재 위치의 노드의 데이터보다 크거나 같을 경우
				if (nptr->right != nullptr) {           // 현재 위치의 노드에 오른쪽 노드가 이미 있으면
					nptr = nptr->right;                 // 현재 노드의 위치를 오른쪽 노드로 이동
				}
				else {                                  // 오른쪽 노드가 없으면
					nptr->right = nNode;                // 현재 위치의 오른쪽 노드에 새로운 데이터를 붙인다. 
					break;    
				}
			}
		}
	}
}

int PQ_BST::Remove()
{
	iCount--;

	node* nptr = RootNode;
	node* delNode;

	if (nptr->left == nullptr) {
		*tRet = nptr->data;

		delNode = nptr;

		if (nptr->right != nullptr) {
			RootNode = nptr->right;
		}
		else {
			RootNode = nullptr;
		}
	}
	else {

		while (nptr->left != nullptr && nptr->left->left != nullptr) {
			nptr = nptr->left;
		}

		*tRet = nptr->left->data;

		delNode = nptr->left;

		if (nptr->left->right != nullptr) {
			nptr->left = nptr->left->right;
		}
		else {
			nptr->left = nullptr;
		}
	}

	delete delNode;

	return *tRet;
}

int PQ_BST::Retrieve()
{
	node* nptr = RootNode;

	if (nptr->left == nullptr) {
		*tRet = nptr->data;
	}
	else {
		while (nptr->left != nullptr && nptr->left->left != nullptr) {
			nptr = nptr->left;
		}
		*tRet = nptr->left->data;
	}

	return *tRet;
}

int PQ_BST::Count()
{
	return iCount;
}

PQ_BST::~PQ_BST()
{
	delete tRet;
}