[C++] 10 - 기초 문법 공부 일지(Tree)

• BinarySearchTree
  • 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드만 포함
  • 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드만 포함
  • 왼쪽 및 오른쪽 하위 트리도 각각 이진 검색 트리
  • 중복 된 키 허용X

10, 15, 5, 9, 3, 2, 11

• Node Create
  • parent, left, right, key

class Node
{
public:
	Node(int key) : parent(nullptr), left(nullptr), right(nullptr), key(key) {}
	~Node() {}

public:
	Node* parent;
	Node* left;
	Node* right;
	int key;
};

• BSTree Create

#pragma once
class BSTree
{
public:
	void	Print();
	void	Insert(int key);
	Node*	Search(Node* node, int key);

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

	void	Replace(Node* node, Node* replace);
private:
	class	Node* root = nullptr; // 전방선언
};

1. Insert

     - 첫 데이터가 nullptr일 경우 root에 첫데이터 넣음

     - node의 키 값을 찾으면서 입력된 key 값과 node의 key를 비교 및 부모 노드 저장

     - 입력된 key가 node의 key보다 작으면 left, 크면 right로 이동

     - 부모노드의 key 값과 입력된 key 값을 비교 후 위와 같은 방식으로 이동 후 newNode 저장

void BSTree::Insert(int key)
{
	Node* newNode = new Node(key);
	if (root == nullptr) { root = newNode; return; }

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

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

2. Search

     - 값을 찾으면 node 반환

     - 입력된 key 값과 node의 key값 비교 후 작으면 left, 크면 right로 재귀 함수 사용

Node* BSTree::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);
}

3. Replace

     - Delete을 하기 위한 함수

     - 삭제하는 부모와 replace를 비교하여 left 및 right로 대체

     - 대체한 node를 부모 다시 연결

void BSTree::Replace(Node* node, Node* replace)
{
	if (node->parent == nullptr) root = replace;
	else if (node == node->parent->left) node->parent->left = replace;
	else node->parent->right = replace;

	if (replace) replace->parent = node->parent;
	delete node;
}

4. Delete - 1

     - key를 받아와서 deleteNode Search

     - Search한 node가 왼쪽노드가 없는 경우 오른쪽과 replace 후 삭제

     - Search한 node가 오른쪽 노드가 없는 경우 왼쪽과 replace 후 삭제

     - 노드가 둘다 있는 경우 다음 노드를 삭제

void BSTree::Delete(int key)
{
	Node* deleteNode = Search(root, key);
	Delete(deleteNode);
}

void BSTree::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
	{
		// TODO
		// 다음 노드를 삭제
	}
}

5. NextNode

     - node의 right가 있는경우 right로 한번 이동후 왼쪽 노드가 없을 때 까지 이동

     - node의 parent를 구해 노드가 parent의 right 노드 일때까지 이동

9 -> 10을 구하는 경우 및 11에서 15를 구하는 경우

Node* BSTree::NextNode(Node* node)
{
	if (node->right)
	{
		Node* nextNode = node->right;
		while (nextNode) nextNode->left;
		return nextNode;
	}

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

5. Delete - 2

     -  nextNode를 찾은 후 두 key 값을 변경후 nextNode 삭제

void BSTree::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 = NextNode(node);
		node->key = next->key;
		Delete(next);
	}
}