fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5. class node {
  6. private:
  7. 	int data;
  8. 	node* left;
  9. 	node* right;
  10.  
  11. 	int cnt = 1;
  12.  
  13. public:
  14. 	node(int d, node* l, node* r) {
  15. 		data = d;
  16. 		left = l;
  17. 		right = r;
  18. 	}
  19. 	~node() {}
  20.  
  21. 	int getData() { return data; }
  22. 	node* getLeft() { return left; }
  23. 	node* getRight() { return right; }
  24. 	int getcnt() { return cnt; }
  25.  
  26. 	void setLeft(node* le) { left = le; }
  27. 	void setRight(node* ri) { right = ri; }
  28. 	void upcnt() { cnt += 1; }
  29. 	void downcnt() { cnt -= 1; }
  30. 	void setData(int d) { data = d; }
  31.  
  32. 	bool isLeaf() { return left == nullptr && right == nullptr; }
  33. };
  34.  
  35. class bst {
  36. private:
  37. 	node* root = nullptr;
  38.  
  39. private:
  40. 	node* find_impl(node* current, int value) { // private 탐색 메소드
  41. 		while (true) {
  42. 			if (current == nullptr) { // 현재 탐색하는 노드가 NULL인 경우
  43. 				cout << "No matching value found for " << value << ".\n";
  44. 				return NULL;
  45. 			}
  46.  
  47. 			if (current->getData() == value) { // 원하는 값 찾음
  48. 				cout << value << " has been found.\n";
  49. 				return current;
  50. 			}
  51. 			else if (value < current->getData()) { // 원하는 값이 더 작음
  52. 				cout << "current is " << current->getData() << ". pointer moved to left.\n";
  53. 				current = current->getLeft(); // 왼쪽 서브트리로 이동
  54. 			}
  55. 			else { // 위의 모든 선택문을 패스했다면 원하는 값이 더 큰 경우임
  56. 				cout << "current is " << current->getData() << ". pointer moved to right.\n";
  57. 				current = current->getRight(); // 오른쪽 서브트리로 이동
  58. 			}
  59. 		}
  60. 	}
  61.  
  62. 	void insert_impl(node* current, int value) { // private 삽입 메소드
  63. 		while (true) {
  64. 			current->upcnt(); // 노드가 삽입되는 경로를 따라 카운트 증가
  65.  
  66. 			if (value < current->getData()) { // 삽입할 값이 현재 탐색하는 노드보다 작음
  67. 				if (current->getLeft() == nullptr) { // 왼쪽 서브트리 없음
  68. 					current->setLeft(new node{ value, NULL, NULL }); // 바로 붙임
  69. 					cout << "current is " << current->getData() << ", " << value << " is inserted left\n";
  70. 					return;
  71. 				}
  72. 				else { // 왼쪽 서브트리 있음
  73. 					current = current->getLeft(); // 왼쪽 서브트리로 이동
  74. 				}
  75. 			}
  76. 			else { // else: 삽입할 값이 현재 탐색하는 노드보다 크거나 같음
  77. 				if (current->getRight() == nullptr) { // 오른쪽 서브트리 없음
  78. 					current->setRight(new node{ value, NULL, NULL }); // 바로 붙임
  79. 					cout << "current is " << current->getData() << ", " << value << " is inserted right\n";
  80. 					return;
  81. 				}
  82. 				else { // else: 오른쪽 서브트리 있음
  83. 					current = current->getRight(); // 오른쪽 서브트리로 이동
  84. 				}
  85. 			}
  86. 		}
  87. 	}
  88.  
  89. 	void inorder_impl(node* start) { // private 중위순회(LDR) 메소드
  90. 		if (start == nullptr) // 현재 탐색중인 노드가 NULL
  91. 			return; // 돌아감
  92.  
  93. 		inorder_impl(start->getLeft()); // L: 왼쪽 서브트리 순회 호출
  94. 		cout << start->getData() << "(" << start->getcnt() << ") "; // D: 현재 노드 데이터 출력
  95. 		inorder_impl(start->getRight()); // R: 오른쪽 서브트리 순회 호출
  96. 	}
  97.  
  98. 	node* delete_impl(node* start, int value) { // private 특정 값 삭제 메소드
  99. 		cout << "current node is " << (start ? to_string(start->getData()) : "NULL") << ".\n";
  100.  
  101. 		if (!start) { // 현재 노드가 NULL
  102. 			cout << "No value matches " << value << ".\n";
  103. 			return NULL; // 삭제한 노드 없음, NULL 반환
  104. 		}
  105.  
  106. 		if (value < start->getData()) // 삭제할 값이 현재 노드보다 작음
  107. 			start->setLeft(delete_impl(start->getLeft(), value)); // 왼쪽 서브트리에 삭제 메소드 다시 호출
  108. 		else if (value > start->getData()) // else if: 삭제할 값이 현재 노드보다 큼
  109. 			start->setRight(delete_impl(start->getRight(), value)); // 오른쪽 서브트리에 삭제 메소드 다시 호출
  110. 		else { // else: 삭제할 값이 현재 노드와 같음
  111. 			if (!start->getLeft()) { // 왼쪽 서브트리가 없음
  112. 				cout << "there is no left subtree. bring the right subtree.\n";
  113. 				auto tmp = start->getRight(); // 현재 노드의 오른쪽 서브트리를 가져옴
  114. 				cout << "delete " << value << ".\n";
  115. 				delete start; // 현재 노드를 지움
  116. 				return tmp; // 아까 가져온 오른쪽 서브트리 반환
  117. 			}
  118.  
  119. 			if (!start->getRight()) { // 오른쪽 서브트리가 없음
  120. 				cout << "there is no right subtree. bring the left subtree.\n";
  121. 				auto tmp = start->getLeft(); // 현재 노드의 왼쪽 서브트리 가져옴
  122. 				cout << "delete " << value << ".\n";
  123. 				delete start; // 현재 노드를 지움
  124. 				return tmp; // 아까 가져온 왼쪽 서브트리 반환
  125. 			}
  126. 		}
  127.  
  128. 		return start;
  129. 	}
  130.  
  131. 	void recount(node* value) { // 노드 삭제를 위해 누적 노드 개수를 수정하는 메소드
  132. 		node* current = root; // 루트에서 시작
  133.  
  134. 		while (true) {
  135. 			if (!current) { // 현재 탐색하는 노드가 NULL인 경우
  136. 				cout << "error: No matching value found for " << value->getData() << ".\n";
  137. 				return; // 끝
  138. 			}
  139.  
  140. 			current->downcnt(); // 현재 노드의 카운트 감소
  141.  
  142. 			if (value->getData() > current->getData()) { // 원하는 값이 더 큼
  143. 				cout << "current is " << current->getData() << ". pointer moved to right.\n";
  144. 				current = current->getRight(); // 오른쪽 서브트리로 이동
  145. 				continue;
  146. 			}
  147.  
  148. 			if (value->getData() < current->getData()) { // 원하는 값이 더 작음
  149. 				cout << "current is " << current->getData() << ". pointer moved to left.\n";
  150. 				current = current->getLeft(); // 왼쪽 서브트리로 이동
  151. 				continue;
  152. 			}
  153.  
  154. 			/*
  155. 			원하는 값 찾음:
  156. 			후계자가 선정되어 값이 바뀌었거나 값이 같은 노드가 중복하여 존재하는 경우,
  157. 			삭제할 노드를 헷갈리지 않기 위해 객체 자체를 비교함
  158. 			*/
  159. 			if (current == value) {
  160. 				cout << value->getData() << " has been found.\n";
  161. 				return;
  162. 			}
  163.  
  164. 			// 원래 삭제하려던 노드의 후계자가 대신 삭제되어야 하는 경우
  165. 			// data는 같지만 노드 자체는 달라서 위의 선택문을 모두 통과하는 경우가 있음
  166. 			// 그럴 때는 후계자 선정 규칙에 따라 오른쪽 서브트리로 이동
  167. 			cout << "current is " << current->getData() << ". pointer moved to right.\n";
  168. 			current = current->getRight(); // 오른쪽 서브트리로 이동
  169. 			continue;
  170. 		}
  171. 	}
  172.  
  173. public:
  174. 	node* getRoot() { return root; }
  175.  
  176. 	node* find(int value) { // 특정 값 탐색 메소드
  177. 		return find_impl(root, value); // 따로 구현된 private 탐색 메소드 호출
  178. 	}
  179.  
  180. 	void insert(int value) { // 삽입 메소드
  181. 		if (root == nullptr) { // 루트가 비어있다면
  182. 			root = new node{ value, nullptr, nullptr }; // 루트에 바로 넣음
  183. 			cout << value << " is inserted into root\n";
  184. 		}
  185. 		else // else: 루트가 비어있지 않다면
  186. 			insert_impl(root, value); // 따로 구현된 private 삽입 메소드 호출
  187. 	}
  188.  
  189. 	void inorder() { // 중위순회 메소드
  190. 		inorder_impl(root); // private 중위순회 메소드 호출
  191. 	}
  192.  
  193. 	node* successor(node* start) { // 후계자 반환 메소드
  194. 		auto current = start->getRight(); // 현재 노드의 오른쪽 서브트리 가져옴
  195.  
  196. 		while (current != nullptr && current->getLeft() != nullptr) // 지금 갖고있는 노드와 그 노드의 왼쪽 서브트리가 모두 존재하는 동안 반복
  197. 			current = current->getLeft(); // 왼쪽 서브트리로 이동
  198.  
  199. 		cout << "successor is " << (current != nullptr ? to_string(current->getData()) : "NULL") << ".\n";
  200. 		return current; // 결과: 오른쪽 서브트리 왼쪽 맨 아래 리프노드 반환
  201. 	}
  202.  
  203. 	void deleteValue(int value) { // 특정 값 삭제
  204. 		node* del_node = find(value); // 삭제할 노드 찾기
  205. 		node* succ;
  206.  
  207. 		if (del_node != NULL) { // 삭제할 노드가 있다면
  208. 			if (del_node->getLeft() != NULL && del_node->getRight() != NULL) { // 후계 필요
  209. 				succ = successor(del_node); // 후계 선정
  210. 				recount(succ); // 노드 삭제를 위해 누적 노드 개수를 수정하는 메소드
  211. 				del_node->setData(succ->getData()); // 삭제할 노드의 데이터를 후계의 데이터로 대체
  212. 				root->setRight(delete_impl(root->getRight(), succ->getData())); // 후계 노드 삭제
  213. 			}
  214. 			else { // 후계 필요 없음
  215. 				recount(del_node); // 노드 삭제를 위해 누적 노드 개수를 수정하는 메소드
  216. 				root = delete_impl(root, value); // private 삭제 메소드 호출
  217. 			}
  218. 		}
  219. 		else { // 삭제할 노드가 없음
  220. 			cout << "delete error: No value matches " << value << ".\n";
  221. 			return; // 돌아감
  222. 		}
  223. 	}
  224.  
  225. 	int countGreater(int key) { // 특정 값(key)보다 큰 요소의 개수 셈
  226. 		int cnt = 0;
  227. 		node* current = root;
  228.  
  229. 		while (true) { // 반복 탐색
  230. 			cout << "current value is " << (current != NULL ? to_string(current->getData()) : "NULL") << "\n";
  231.  
  232. 			if (current == NULL) // 더 탐색할 노드가 없음
  233. 				break; // 반복 종료
  234.  
  235. 			if (key == current->getData()) { // key와 같은 값 찾음
  236. 				// 오른쪽에 더 큰 값이 남아있을 수 있으므로 오른쪽으로 이동
  237. 				cout << "find key value. go right.\n";
  238. 				current = current->getRight();
  239. 				continue;
  240. 			}
  241. 			else if (key < current->getData()) { // key보다 큰 값 찾음
  242. 				cnt += 1; // 일단 현재 노드를 카운트에 추가
  243.  
  244. 				if (current->getRight() != NULL) // 오른쪽 서브트리가 있다면
  245. 					cnt += current->getRight()->getcnt(); // 오른쪽 서브트리의 노드 수도 추가
  246.  
  247. 				// 왼쪽에 더 큰 값이 남아있을 수 있으므로 왼쪽으로 이동
  248. 				cout << "current value " << current->getData() << " is greater than key value. add right count and go left\n";
  249. 				current = current->getLeft();
  250. 				continue;
  251. 			}
  252. 			else if (key > current->getData()) { // key보다 작은 값 찾음
  253. 				// 오른쪽에 더 큰 값이 남아있을 수 있으므로 오른쪽으로 이동
  254. 				cout << "current value " << current->getData() << " is lesser than key value. Don't add count and go right\n";
  255. 				current = current->getRight();
  256. 				continue;
  257. 			}
  258. 		}
  259.  
  260. 		return cnt; // 반복 종료 후 결과 반환
  261. 	}
  262.  
  263. 	int countLesser(int key) { // 특정 값(key)보다 작은 요소의 개수 셈
  264. 		int cnt = 0;
  265. 		node* current = root;
  266.  
  267. 		while (true) { // 반복 탐색
  268. 			cout << "current value is " << (current != NULL ? to_string(current->getData()) : "NULL") << "\n";
  269.  
  270. 			if (current == NULL) // 더 탐색할 노드가 없음
  271. 				break; // 반복 종료
  272.  
  273. 			if (key == current->getData()) { // key와 같은 값 찾음
  274. 				// 왼쪽에 더 작은 값이 남아있을 수 있으므로 왼쪽으로 이동
  275. 				cout << "find key value. go left.\n";
  276. 				current = current->getLeft();
  277. 				continue;
  278. 			}
  279. 			else if (key > current->getData()) { // key보다 작은 값 찾음
  280. 				cnt += 1; // 현재 노드를 카운트에 추가
  281.  
  282. 				if (current->getLeft() != NULL) // 왼쪽에 서브트리가 있다면
  283. 					cnt += current->getLeft()->getcnt(); // 왼쪽 서브트리의 노드 수도 추가
  284.  
  285. 				// 오른쪽에 더 작은 값이 남아있을 수 있으므로 오른쪽으로 이동
  286. 				cout << "current value " << current->getData() << " is lesser than key value. add left count and go right.\n";
  287. 				current = current->getRight();
  288. 				continue;
  289. 			}
  290. 			else if (key < current->getData()) {
  291. 				// 왼쪽에 더 작은 값이 남아있을 수 있으므로 왼쪽으로 이동
  292. 				cout << "current value " << current->getData() << " is greater than key value. Don't add count and go left\n";
  293. 				current = current->getLeft();
  294. 				continue;
  295. 			}
  296. 		}
  297.  
  298. 		return cnt; // 반복 종료 후 결과 반환
  299. 	}
  300. };
  301.  
  302. int main()
  303. {
  304. 	bst tree;
  305. 	int tmp = 11;
  306. 	int tmp_res;
  307.  
  308. 	tree.insert(12);
  309. 	tree.insert(10);
  310. 	tree.insert(20);
  311. 	tree.insert(8);
  312. 	tree.insert(11);
  313. 	tree.insert(11);
  314. 	tree.insert(15);
  315. 	tree.insert(28);
  316. 	tree.insert(4);
  317. 	tree.insert(2);
  318. 	tree.insert(27);
  319. 	cout << "\n";
  320.  
  321. 	tmp_res = tree.countGreater(tmp);
  322. 	cout << "count value greater than " << tmp << " : " << tmp_res << "\n";
  323. 	cout << "\n";
  324. 	tmp_res = tree.countLesser(tmp);
  325. 	cout << "count value lesser than " << tmp << " : " << tmp_res << "\n";
  326. 	cout << "\n";
  327.  
  328. 	cout << "Inorder Traversal: ";
  329. 	tree.inorder();
  330. 	cout << "\n";
  331.  
  332. 	tree.deleteValue(12);
  333. 	cout << "Delete 12 and Do Inorder Traversal: ";
  334. 	tree.inorder();
  335. 	cout << "\n";
  336.  
  337. 	if (tree.find(12))
  338. 		cout << "Value 12 is in the tree.\n";
  339. 	else
  340. 		cout << "Value 12 is not in the tree.\n";
  341. 	cout << "\n";
  342.  
  343. 	tree.deleteValue(11);
  344. 	tree.deleteValue(4);
  345. 	tree.deleteValue(0);
  346. 	tree.inorder();
  347. }
Success #stdin #stdout 0.01s 5392KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
12 is inserted into root
current is 12, 10 is inserted left
current is 12, 20 is inserted right
current is 10, 8 is inserted left
current is 10, 11 is inserted right
current is 11, 11 is inserted right
current is 20, 15 is inserted left
current is 20, 28 is inserted right
current is 8, 4 is inserted left
current is 4, 2 is inserted left
current is 28, 27 is inserted left

current value is 12
current value 12 is greater than key value. add right count and go left
current value is 10
current value 10 is lesser than key value. Don't add count and go right
current value is 11
find key value. go right.
current value is 11
find key value. go right.
current value is NULL
count value greater than 11 : 5

current value is 12
current value 12 is greater than key value. Don't add count and go left
current value is 10
current value 10 is lesser than key value. add left count and go right.
current value is 11
find key value. go left.
current value is NULL
count value lesser than 11 : 4

Inorder Traversal: 2(1) 4(2) 8(3) 10(6) 11(2) 11(1) 12(11) 15(1) 20(4) 27(1) 28(2) 
12 has been found.
successor is 15.
current is 12. pointer moved to right.
current is 20. pointer moved to left.
15 has been found.
current node is 20.
current node is 15.
there is no left subtree. bring the right subtree.
delete 15.
Delete 12 and Do Inorder Traversal: 2(1) 4(2) 8(3) 10(6) 11(2) 11(1) 15(10) 20(3) 27(1) 28(2) 
current is 15. pointer moved to left.
current is 10. pointer moved to right.
current is 11. pointer moved to right.
current is 11. pointer moved to right.
No matching value found for 12.
Value 12 is not in the tree.

current is 15. pointer moved to left.
current is 10. pointer moved to right.
11 has been found.
current is 15. pointer moved to left.
current is 10. pointer moved to right.
11 has been found.
current node is 15.
current node is 10.
current node is 11.
there is no left subtree. bring the right subtree.
delete 11.
current is 15. pointer moved to left.
current is 10. pointer moved to left.
current is 8. pointer moved to left.
4 has been found.
current is 15. pointer moved to left.
current is 10. pointer moved to left.
current is 8. pointer moved to left.
4 has been found.
current node is 15.
current node is 10.
current node is 8.
current node is 4.
there is no right subtree. bring the left subtree.
delete 4.
current is 15. pointer moved to left.
current is 10. pointer moved to left.
current is 8. pointer moved to left.
current is 2. pointer moved to left.
No matching value found for 0.
delete error: No value matches 0.
2(1) 8(2) 10(4) 11(1) 15(8) 20(3) 27(1) 28(2)
https://ideone.com/PCGu4u
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!