[C++] BST Operations

1. Binary Search Tree

: BST에 관한 설명은 아래의 글에서

2023.11.21 - [Python/자료구조] - [python] 이진트리 / 이진 탐색트리(+백준 5639)

[python] 이진트리 / 이진 탐색트리(+백준 5639)

1. 이진트리 모든 노드의 차수가 self.data): if(self.right): self.right.insert(item) else: self.right=Node(item) else: raise IndexError def search(self,item,parent=None): if(itemself.data): if(self.right): return self.right.search(item,self) else

growingupis.tistory.com

1-1. Basic Operations

Query - search (contains, find) , size, height, min/max, succesor, predecessor
grow - insert
trim - delete

BST.h

#pragma once
#include <iostream>
using namespace std;

class TreeNode {
private:
	char key;
	TreeNode* left;
	TreeNode* right;
public:
	TreeNode(char item) : key(item), left(NULL), right(NULL) {}
	TreeNode(char item, TreeNode* l, TreeNode* r) : key(item), left(l), right(r) {}
	char getKey() { return key; }
	TreeNode* getLeft() { return left; }
	TreeNode* getRight() { return right; }
	void setLeft(TreeNode* item) {
		left = item;
	}
	void setRight(TreeNode* item) {
		right = item;
	}
	friend class BST;
};

class BST {
private:
	TreeNode* root;
public:
	BST(TreeNode* item) :root(item) {
	}
	BST() :root(NULL) {
	}
	TreeNode* getRoot() {
		return root;
	}
	void setRoot(TreeNode* item) {
		root = item;
	}
	TreeNode* find(TreeNode* node, char item) {
		if (node == NULL) {
			return NULL;
		}
		else if (node->key == item) {
			return node;
		}

		if (node->key < item) {
			return find(node->right, item);
		}
		else {
			return find(node->left, item);
		}
	}
	bool contains(TreeNode* node, char item) {
		if (node == NULL) {
			return false;
		}
		else if (node->key == item) {
			return true;
		}
		if (node->key < item) {
			return contains(node->right, item);
		}
		else {
			return contains(node->left, item);
		}
	}

	TreeNode* grow(TreeNode* node, char item) {
		if (root == NULL) {
			root = new TreeNode(item);
			return root;
		}

		if (node == NULL) {
			return new TreeNode(item);
		}
		if (node->key < item) {
			node->right = grow(node->right, item);
		}
		else if (node->key > item) {
			node->left = grow(node->left, item);
		}
		return node;
	}

	void trim(char key) {
		if (!contains(root, key)) {
			cout << "해당 key를 data로 가지는 노드가 존재하지 않아 삭제할 수 없습니다\n";
			return;
		}
		else {
			TreeNode* preNode = NULL;
			TreeNode* curNode = root;
			while (curNode != NULL) {
				if (curNode->key == key) {
					break;
				}

				preNode = curNode;
				if (curNode->key < key) {
					curNode = curNode->right;
				}
				else {
					curNode = curNode->left;
				}
			}

			if (curNode->left == NULL && curNode->right == NULL) {
				if (preNode->right == curNode) {
					preNode->right = NULL;
				}
				else {

					preNode->left = NULL;
				}
				delete curNode;
				curNode = NULL;
			}
			else if (curNode->left != NULL && curNode->right != NULL) {
				TreeNode* succ_parent = curNode;
				TreeNode* succ = curNode;
				
				succ = succ->left;
				while (succ->right != NULL) {
					succ_parent = succ;
					succ = succ->right;
				}
				curNode->key = succ->key;
				if (succ_parent->left == succ) {
					succ_parent->left = succ->left;
				}
				else {
					succ_parent->right = succ->left;
				}

				
			}
			else {
				TreeNode* child;
				if (curNode->left != NULL) {
					child = curNode->left;
				}
				else {
					child = curNode->right;
				}
				if (preNode != NULL) {
					if (preNode->left == curNode) {
						preNode->left = child;
					}
					else {
						preNode->right = child;
					}
				}
				
				else {
					root = child;
				}
			}
		}
	}
	void inorder(TreeNode* node) {
		if (node == NULL) {
			return;
		}

		inorder(node->left);
		cout << node->key << " ";
		inorder(node->right);
	}


};

main.cpp

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

int main() {
	BST bst;
	bst.grow(bst.getRoot(), 'h');
	bst.grow(bst.getRoot(), 'c');
	bst.grow(bst.getRoot(), 'j');
	bst.grow(bst.getRoot(), 'b');
	bst.grow(bst.getRoot(), 'e');
	bst.grow(bst.getRoot(), 'n');
	bst.grow(bst.getRoot(), 'k');
	bst.grow(bst.getRoot(), 'p');


	while (1) {
		
		cout << "------------------------------------\n";
		cout << "\t\t1 : 트리 출력\n";
		cout << "\t\t2 : 문자 삽입\n";
		cout << "\t\t3 : 문자 삭제\n";
		cout << "\t\t4 : 문자 검색\n";
		cout << "\t\t5 : 종료\n";
		cout << "------------------------------------\n";
		cout << "메뉴입력 >> ";
		int ans;
		cin >> ans;
		char item;
		switch (ans) {
		case 1:
			cout << "\t[이진 트리 출력]";
			bst.inorder(bst.getRoot());
			break;
		case 2:
			cout << "삽입할 문자를 입력하세요 :";
			cin >> item;
			bst.grow(bst.getRoot(), item);
			break;
		case 3:
			cout << "삭제할 문자를 입력하세요 :";
			cin >> item;
			bst.trim(item);
			break;

		case 4:
			cout << "검색할 문자를 입력하세요 :";
			char item;
			cin >> item;
			if (bst.find(bst.getRoot(), item) != NULL) {
				cout << "exist";
			}
			else {
				cout << "no exist\n";
			}
			break;
		case 5:
			cout << "종료";
			return 0;

		}
		cout << "\n\n";
	}



	return 0;
}

1-2. 특수 함수

(1) Convert BT to BST conversion

Store keys of a binary tree into a container like vector or set
Sort the keys in vector. Skip this step if set is used since it is already sorted
Do the inorder traversal of the tree and copy back the elements of the container into the nodes of the tree one by one

1) Convert 수행하는 함수

traverse 함수를 통해 inorder traverse를 하며 노드들을 vector에 삽입
sort 함수를 통해 vector의 원소들을 오름차순으로 정렬
다시 한 번 더 Binary Tree를 inorder traverse를 하며 vector의 원소들 순차적으로 대입하며 변경
(이때, static 변수를 사용하여 vector의 원소들을 순차적으로 접근할 수 있도록 함)
inorder함수는 동작이 잘 수행되었는지 확인하는 용도

void inorder(Node* node) {
    if (node == NULL) {
        return;
    }
    inorder(node->left);
    cout << node->key << " ";
    inorder(node->right);
}

void traverse(Node* node) {
    if (node == NULL) {
        return;
    }
    vt.push_back(node->key);
    traverse(node->left);
    traverse(node->right);
}

void BinaryTreeToBST(Node * node) {
    static int idx= 0;
    if (node == NULL) {
        return;
    }
    BinaryTreeToBST(node->left);
    node->key = vt[idx++];
    BinaryTreeToBST(node->right);
}

void Sort() {
    sort(vt.begin(), vt.end());
}

2) 전체 소스코드

BT.h

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Node {
private:
	int key;
	Node* left;
	Node* right;

public:
	Node(int item, Node * l, Node * r): key(item), left(l), right(r){}
	Node(int item): key(item), left(NULL), right(NULL){}
	void MakeLeftSub(Node * item) {
		left = item;
	}
	void MakeRightSub(Node* item) {
		right = item;
	}
	friend class Tree;
};

class Tree {
private:
	Node* root;
	vector <int> vt;
public:

	Tree(Node *item):root(item){}
	vector<int> getVector() {
		return vt;
	}
	Node* getRoot() {
		return root;
	}
	void setRootLeft(Node* left) {
		root->MakeLeftSub(left);
	}
	void setRootRight(Node* right) {
		root->MakeRightSub(right);
	}
	void inorder(Node* node) {
		if (node == NULL) {
			return;
		}
		inorder(node->left);
		cout << node->key << " ";
		inorder(node->right);
	}

	void traverse(Node* node) {
		if (node == NULL) {
			return;
		}
		vt.push_back(node->key);
		traverse(node->left);
		traverse(node->right);
	}

	void BinaryTreeToBST(Node * node) {
		static int idx= 0;
		if (node == NULL) {
			return;
		}
		BinaryTreeToBST(node->left);
		node->key = vt[idx++];
		BinaryTreeToBST(node->right);
	}

	void Sort() {
		sort(vt.begin(), vt.end());
	}
};

BST.h

#pragma once
#include <iostream>
using namespace std;


class TreeNode {
private:
	int key;
	TreeNode* left;
	TreeNode* right;
public:
	TreeNode(int item) : key(item), left(NULL), right(NULL) {}
	TreeNode(int item, TreeNode* l, TreeNode* r) : key(item), left(l), right(r) {}
	int getKey() { return key; }
	TreeNode* getLeft() { return left; }
	TreeNode* getRight() { return right; }
	void setLeft(TreeNode* item) {
		left = item;
	}
	void setRight(TreeNode* item) {
		right = item;
	}
	friend class BST;
};

class BST {
private:
	TreeNode* root;
public:
	BST(TreeNode* item) :root(item) {
	}
	BST() :root(NULL) {
	}
	TreeNode* getRoot() {
		return root;
	}
	void setRoot(TreeNode* item) {
		root = item;
	}
	TreeNode* find(TreeNode* node, int item) {
		if (node == NULL) {
			return NULL;
		}
		else if (node->key == item) {
			return node;
		}

		if (node->key < item) {
			return find(node->right, item);
		}
		else {
			return find(node->left, item);
		}
	}
	bool contains(TreeNode* node, int item) {
		if (node == NULL) {
			return false;
		}
		else if (node->key == item) {
			return true;
		}
		if (node->key < item) {
			return contains(node->right, item);
		}
		else {
			return contains(node->left, item);
		}
	}

	TreeNode* grow(TreeNode* node, int item) {
		if (root == NULL) {
			root = new TreeNode(item);
			return root;
		}

		if (node == NULL) {
			return new TreeNode(item);
		}
		if (node->key < item) {
			node->right = grow(node->right, item);
		}
		else if (node->key > item) {
			node->left = grow(node->left, item);
		}
		return node;
	}

	void trim(int key) {
		if (!contains(root, key)) {
			cout << "해당 key를 data로 가지는 노드가 존재하지 않아 삭제할 수 없습니다\n";
			return;
		}
		else {
			TreeNode* preNode = NULL;
			TreeNode* curNode = root;
			while (curNode != NULL) {
				if (curNode->key == key) {
					break;
				}

				preNode = curNode;
				if (curNode->key < key) {
					curNode = curNode->right;
				}
				else {
					curNode = curNode->left;
				}
			}

			if (curNode->left == NULL && curNode->right == NULL) {
				if (preNode->right == curNode) {
					preNode->right = NULL;
				}
				else {

					preNode->left = NULL;
				}
				delete curNode;
				curNode = NULL;
			}
			else if (curNode->left != NULL && curNode->right != NULL) {
				TreeNode* succ_parent = curNode;
				TreeNode* succ = curNode;
				
				succ = succ->left;
				while (succ->right != NULL) {
					succ_parent = succ;
					succ = succ->right;
				}
				curNode->key = succ->key;
				if (succ_parent->left == succ) {
					succ_parent->left = succ->left;
				}
				else {
					succ_parent->right = succ->left;
				}

				
			}
			else {
				TreeNode* child;
				if (curNode->left != NULL) {
					child = curNode->left;
				}
				else {
					child = curNode->right;
				}
				if (preNode != NULL) {
					if (preNode->left == curNode) {
						preNode->left = child;
					}
					else {
						preNode->right = child;
					}
				}
				
				else {
					root = child;
				}
			}
		}
	}
	void inorder(TreeNode* node) {
		if (node == NULL) {
			return;
		}

		inorder(node->left);
		cout << node->key << " ";
		inorder(node->right);
	}


};

main.cpp

#include <iostream>
using namespace std;
#include "BST.h"
#include "BT.h"

int main() {

	
	Tree tr(new Node(0));
	Node* node1 = new Node(1);
	Node* node2= new Node(2);
	Node* node3 = new Node(3);
	Node* node4 = new Node(4);
	Node* node5 = new Node(5);
	Node* node6 = new Node(6);
	Node* node7 = new Node(7);
	Node* node8 = new Node(8);

	tr.setRootLeft(node1);
	tr.setRootRight(node2);
	node1->MakeLeftSub(node3);
	node1->MakeRightSub(node4);
	node2->MakeLeftSub(node5);
	node5->MakeRightSub(node7);
	node3->MakeRightSub(node6);
	node6->MakeRightSub(node8);
	cout << "\n[Binary Tree 출력]\n";
	tr.inorder(tr.getRoot());


	cout << "\n[Binary Tree 원소들 Vector에 삽입한 Vecotr 결과]\n";
	tr.traverse(tr.getRoot()); //순회하며 벡터에 원소 삽입
	for (int i = 0; i < tr.getVector().size(); i++) {
		cout << tr.getVector()[i] << " ";
	}

	cout << "\n[Vector 원소들 오름차순한 결과]\n";
	tr.Sort();
	for (int i = 0; i < tr.getVector().size(); i++) {
		cout << tr.getVector()[i] << " ";
	}

	cout << "\n[Vector 원소들 기존 Binary Tree inorder하며 데이터 변경한 결과]\n";
	tr.BinaryTreeToBST(tr.getRoot());
	tr.inorder(tr.getRoot());





	

	return 0;
}

(2) LCA

: LCA 설명은 아래 글 참고

2023.10.12 - [Python/알고리즘] - 최소 공통 조상(Lowest Common Ancestor)

최소 공통 조상(Lowest Common Ancestor)

1. 최소 공통 조상 : 두 노드의 가장 가까운 공통 조상 노드를 구하는 것 1-1. 단순 LCA 알고리즘 1-1-1. 알고리즘 동작 과정 모든 노드에 대한 깊이 계산 최소 공통 조상을 찾을 두 노드 확인 - 두 노

growingupis.tistory.com

1) LCA 구현하는 함수

TreeNode* LCA(TreeNode* node, TreeNode* p, TreeNode* q) {
	if (node == NULL) {
		return NULL;
	}
	if (node == p || node == q) {
		return node;
	}

	TreeNode* left = LCA(node->left, p, q);
	TreeNode* right = LCA(node->right, p, q);

	if (left != NULL && right != NULL) {
		return node;
	}
	else if (left != NULL) {
		return left;
	}
	else if (right != NULL) {
		return right;
	}
	else {
		return NULL;
	}
}

cf. 만약 트리가 아래와 같이 되어있고 2와 5의 LCA를 구하는 경우

: 2를 찾았으므로 2 노드를 반환하여 더이상 2의 후손 노드들에 대하여 재귀문을 수행할 수 없어서 5를 찾지 못한다

: 하지만, 어차피 6의 오른쪽 후손 노드들에서 5를 찾지 못하여 NULL이 반환되기에 5는 2의 후손 노드들에 속한다는 의미이므로 굳이 재귀문을 5에 다다를때까지 수행할 필요가 없음

1-1) 전체 소스코드

BST.h

#pragma once
#include <iostream>
using namespace std;


class TreeNode {
private:
	int key;
	TreeNode* left;
	TreeNode* right;
public:
	TreeNode(int item) : key(item), left(NULL), right(NULL) {}
	TreeNode(int item, TreeNode* l, TreeNode* r) : key(item), left(l), right(r) {}
	int getKey() { return key; }
	TreeNode* getLeft() { return left; }
	TreeNode* getRight() { return right; }
	void setLeft(TreeNode* item) {
		left = item;
	}
	void setRight(TreeNode* item) {
		right = item;
	}
	friend class BST;
};

class BST {
private:
	TreeNode* root;
public:
	BST(TreeNode* item) :root(item) {
	}
	BST() :root(NULL) {
	}
	TreeNode* getRoot() {
		return root;
	}
	void setRoot(TreeNode* item) {
		root = item;
	}
	TreeNode* find(TreeNode* node, int item) {
		if (node == NULL) {
			return NULL;
		}
		else if (node->key == item) {
			return node;
		}

		if (node->key < item) {
			return find(node->right, item);
		}
		else {
			return find(node->left, item);
		}
	}
	bool contains(TreeNode* node, int item) {
		if (node == NULL) {
			return false;
		}
		else if (node->key == item) {
			return true;
		}
		if (node->key < item) {
			return contains(node->right, item);
		}
		else {
			return contains(node->left, item);
		}
	}

	TreeNode* grow(TreeNode* node, int item) {
		if (root == NULL) {
			root = new TreeNode(item);
			return root;
		}

		if (node == NULL) {
			return new TreeNode(item);
		}
		if (node->key < item) {
			node->right = grow(node->right, item);
		}
		else if (node->key > item) {
			node->left = grow(node->left, item);
		}
		return node;
	}

	void trim(int key) {
		if (!contains(root, key)) {
			cout << "해당 key를 data로 가지는 노드가 존재하지 않아 삭제할 수 없습니다\n";
			return;
		}
		else {
			TreeNode* preNode = NULL;
			TreeNode* curNode = root;
			while (curNode != NULL) {
				if (curNode->key == key) {
					break;
				}

				preNode = curNode;
				if (curNode->key < key) {
					curNode = curNode->right;
				}
				else {
					curNode = curNode->left;
				}
			}

			if (curNode->left == NULL && curNode->right == NULL) {
				if (preNode->right == curNode) {
					preNode->right = NULL;
				}
				else {

					preNode->left = NULL;
				}
				delete curNode;
				curNode = NULL;
			}
			else if (curNode->left != NULL && curNode->right != NULL) {
				TreeNode* succ_parent = curNode;
				TreeNode* succ = curNode;
				
				succ = succ->left;
				while (succ->right != NULL) {
					succ_parent = succ;
					succ = succ->right;
				}
				curNode->key = succ->key;
				if (succ_parent->left == succ) {
					succ_parent->left = succ->left;
				}
				else {
					succ_parent->right = succ->left;
				}

				
			}
			else {
				TreeNode* child;
				if (curNode->left != NULL) {
					child = curNode->left;
				}
				else {
					child = curNode->right;
				}
				if (preNode != NULL) {
					if (preNode->left == curNode) {
						preNode->left = child;
					}
					else {
						preNode->right = child;
					}
				}
				
				else {
					root = child;
				}
			}
		}
	}
	void inorder(TreeNode* node) {
		if (node == NULL) {
			return;
		}

		inorder(node->left);
		cout << node->key << " ";
		inorder(node->right);
	}

	TreeNode* LCA(TreeNode* node, TreeNode* p, TreeNode* q) {
		if (node == NULL) {
			return NULL;
		}
		if (node == p || node == q) {
			return node;
		}

		TreeNode* left = LCA(node->left, p, q);
		TreeNode* right = LCA(node->right, p, q);

		if (left != NULL && right != NULL) {
			return node;
		}
		else if (left != NULL) {
			return left;
		}
		else if (right != NULL) {
			return right;
		}
		else {
			return NULL;
		}
	}

};

main.cpp

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

int main() {


	BST bst;
	bst.grow(bst.getRoot(), 6);
	bst.grow(bst.getRoot(), 2);
	bst.grow(bst.getRoot(), 8);
	bst.grow(bst.getRoot(), 0);
	bst.grow(bst.getRoot(), 4);
	bst.grow(bst.getRoot(), 3);
	bst.grow(bst.getRoot(), 5);
	bst.grow(bst.getRoot(), 7);
	bst.grow(bst.getRoot(), 9);


	cout << "\n\n[2와 5의 최소공통조상 찾기]\n";
	cout << bst.LCA(bst.getRoot(), bst.find(bst.getRoot(), 2), bst.find(bst.getRoot(), 5))->getKey();


	cout << "\n\n[9와 7의 최소공통조상 찾기]\n";
	cout << bst.LCA(bst.getRoot(), bst.find(bst.getRoot(), 9), bst.find(bst.getRoot(), 7))->getKey();


	cout << "\n\n[0와 4의 최소공통조상 찾기]\n";
	cout << bst.LCA(bst.getRoot(), bst.find(bst.getRoot(), 0), bst.find(bst.getRoot(), 4))->getKey();


	cout << "\n\n[0와 5의 최소공통조상 찾기]\n";
	cout << bst.LCA(bst.getRoot(), bst.find(bst.getRoot(), 0), bst.find(bst.getRoot(), 5))->getKey();


	cout << "\n\n[2와 7의 최소공통조상 찾기]\n";
	cout << bst.LCA(bst.getRoot(), bst.find(bst.getRoot(), 2), bst.find(bst.getRoot(), 7))->getKey();

	return 0;
}

'C++ > 알고리즘' 카테고리의 다른 글

[C++] Merging Sort (1)	2023.12.14
[C++] 이분 그래프(Bigraph) (0)	2023.12.13
[C++] Binary Tree Operations (1)	2023.12.05
[C++]Shuffle Doubly linked list (0)	2023.11.30
[C++]Split Doubly Linked List (0)	2023.11.29

이정표

[C++] BST Operations

1. Binary Search Tree

1-1. Basic Operations

1-2. 특수 함수

(1) Convert BT to BST conversion

(2) LCA

'C++ > 알고리즘' 카테고리의 다른 글

티스토리툴바

[C++] BST Operations

1. Binary Search Tree

1-1. Basic Operations

1-2. 특수 함수

(1) Convert BT to BST conversion

(2) LCA

'C++ > 알고리즘' 카테고리의 다른 글

관련글

티스토리툴바