fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4.  
  5. class Tree
  6. {
  7. public:
  8. 	Tree() : root(NONE) { }
  9. 	~Tree() { }
  10.  
  11. 	void add(const string& data);
  12. 	void remove(const string& data);
  13. 	string dump();
  14.  
  15. private:
  16. 	typedef uint32_t index;
  17. 	static const index NONE = static_cast<index>(-1);
  18.  
  19. 	class Node
  20. 	{
  21. 	public:
  22. 		Node(const string& data, index parent, index left, index right) :
  23. 			data(data), parent(parent), left(left), right(right)
  24. 		{
  25. 		}
  26.  
  27. 		string data;
  28. 		index parent, left, right;
  29. 	};
  30. 	index find(const string& data, index& parent, bool& left);
  31. 	void remove_replace(index inode);
  32. 	index leftmost(index inode);
  33. 	string dump(index inode, const string& tab, const string& tabs);
  34.  
  35. 	vector<Node> nodes;
  36. 	index root;
  37. };
  38.  
  39. const Tree::index Tree::NONE;
  40.  
  41. void Tree::add(const string& data)
  42. {
  43. 	index inode = nodes.size(), iparent;
  44. 	bool left;
  45. 	if (find(data, iparent, left) != NONE) throw runtime_error("дубликат: " + data);
  46.  
  47. 	nodes.emplace_back(data, iparent, NONE, NONE);
  48. 	(iparent == NONE ? root : left ? nodes[iparent].left : nodes[iparent].right) = inode;
  49. }
  50.  
  51. void Tree::remove(const string& data)
  52. {
  53. 	index inode, iparent;
  54. 	bool left;
  55. 	if ((inode = find(data, iparent, left)) == NONE) throw runtime_error("не найдено: " + data);
  56.  
  57. 	Node& node = nodes[inode];
  58. 	if (node.left != NONE && node.right != NONE)
  59. 	{
  60. 		// удаление элемента с 2 детьми
  61. 		index rlm = leftmost(node.right), rlmp = nodes[rlm].parent, rlmr = nodes[rlm].right;
  62. 		node.data = move(nodes[rlm].data);
  63. 		(rlm == nodes[rlmp].left ? nodes[rlmp].left : nodes[rlmp].right) = rlmr;
  64. 		if (rlmr != NONE) nodes[rlmr].parent = rlmp;
  65. 		remove_replace(rlm);
  66. 	} else
  67. 	{
  68. 		// удаление элемента с 0 или 1 детьми
  69. 		index maybe_child = node.left != NONE ? node.left : node.right;
  70. 		(iparent == NONE ? root : left ? nodes[iparent].left : nodes[iparent].right) = maybe_child;
  71. 		if (maybe_child != NONE) nodes[maybe_child].parent = iparent;
  72. 		remove_replace(inode);
  73. 	}
  74. }
  75.  
  76. string Tree::dump()
  77. {
  78. 	return root == NONE ? "<пусто>" : dump(root, "\t", "");
  79. }
  80.  
  81. Tree::index Tree::find(const string& data, index& iparent, bool& left)
  82. {
  83. 	iparent = NONE;
  84. 	index inode = root;
  85. 	while (inode != NONE)
  86. 	{
  87. 		Node& node = nodes[inode];
  88. 		int cmp = data.compare(node.data);
  89. 		if (cmp == 0) break;
  90. 		iparent = inode;
  91. 		inode = cmp < 0 ? node.left : node.right;
  92. 		left = cmp < 0;
  93. 	}
  94. 	return inode;
  95. }
  96.  
  97. // Удаляет узел inode из хранилища узлов,
  98. // заменяя его последним и исправляя индексы ссылавшихся на последний.
  99. void Tree::remove_replace(index inode)
  100. {
  101. 	index ilast = nodes.size() - 1;
  102. 	if (inode != ilast)
  103. 	{
  104. 		Node& node = nodes[inode];
  105. 		node = move(nodes[ilast]);
  106.  
  107. 		if (node.parent == NONE)
  108. 			root = inode;
  109. 		else
  110. 		{
  111. 			Node& parent = nodes[node.parent];
  112. 			(ilast == parent.left ? parent.left : parent.right) = inode;
  113. 		}
  114. 		if (node.left != NONE) nodes[node.left].parent = inode;
  115. 		if (node.right != NONE) nodes[node.right].parent = inode;
  116. 	}
  117. 	nodes.pop_back();
  118. }
  119.  
  120. Tree::index Tree::leftmost(index inode)
  121. {
  122. 	for (index next; (next = nodes[inode].left) != NONE; inode = next) ;
  123. 	return inode;
  124. }
  125.  
  126. string Tree::dump(index inode, const string& tab, const string& tabs)
  127. {
  128. 	Node& node = nodes[inode];
  129. 	string r = node.data + " (#" + to_string(inode) + ", parent = " + (node.parent == NONE ? "NONE" : "#" + to_string(node.parent)) + ")";
  130. 	for (int ic = 0; ic < 2; ic++)
  131. 	{
  132. 		index child = ic == 0 ? node.left : node.right;
  133. 		if (child != NONE)
  134. 			r += "\n" + tabs + tab + (ic == 0 ? "L" : "R") + " = " + dump(child, tab, tabs + tab);
  135. 	}
  136. 	return r;
  137. }
  138.  
  139. int main()
  140. {
  141. 	string ops[] =
  142. 	{
  143. 		"+555",
  144. 		"+444",
  145. 		"+666",
  146. 		"+321",
  147. 		"+445",
  148. 		"+777",
  149. 		"+600",
  150. 		"-гетеросексуальность",
  151. 		"+600",
  152. 		"-555",
  153. 		"-777",
  154. 		"-444",
  155. 		"-445",
  156. 		"-600",
  157. 		"-321",
  158. 		"-666",
  159. 	};
  160.  
  161. 	Tree tree;
  162. 	cout << tree.dump() << endl << endl;
  163. 	for (const auto& op : ops)
  164. 	{
  165. 		bool add = op[0] == '+';
  166. 		string arg = op.substr(1);
  167. 		cout << (add ? "Добавление" : "Удаление") << " " << arg << endl;
  168.  
  169. 		try
  170. 		{
  171. 			if (add)
  172. 				tree.add(arg);
  173. 			else
  174. 				tree.remove(arg);
  175. 		} catch (const exception& err)
  176. 		{
  177. 			cout << err.what() << endl << endl;
  178. 			continue;
  179. 		}
  180.  
  181. 		cout << tree.dump() << endl << endl;
  182. 	}
  183. 	return 0;
  184. }
Success #stdin #stdout 0s 4272KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
<пусто>

Добавление 555
555 (#0, parent = NONE)

Добавление 444
555 (#0, parent = NONE)
	L = 444 (#1, parent = #0)

Добавление 666
555 (#0, parent = NONE)
	L = 444 (#1, parent = #0)
	R = 666 (#2, parent = #0)

Добавление 321
555 (#0, parent = NONE)
	L = 444 (#1, parent = #0)
		L = 321 (#3, parent = #1)
	R = 666 (#2, parent = #0)

Добавление 445
555 (#0, parent = NONE)
	L = 444 (#1, parent = #0)
		L = 321 (#3, parent = #1)
		R = 445 (#4, parent = #1)
	R = 666 (#2, parent = #0)

Добавление 777
555 (#0, parent = NONE)
	L = 444 (#1, parent = #0)
		L = 321 (#3, parent = #1)
		R = 445 (#4, parent = #1)
	R = 666 (#2, parent = #0)
		R = 777 (#5, parent = #2)

Добавление 600
555 (#0, parent = NONE)
	L = 444 (#1, parent = #0)
		L = 321 (#3, parent = #1)
		R = 445 (#4, parent = #1)
	R = 666 (#2, parent = #0)
		L = 600 (#6, parent = #2)
		R = 777 (#5, parent = #2)

Удаление гетеросексуальность
не найдено: гетеросексуальность

Добавление 600
дубликат: 600

Удаление 555
600 (#0, parent = NONE)
	L = 444 (#1, parent = #0)
		L = 321 (#3, parent = #1)
		R = 445 (#4, parent = #1)
	R = 666 (#2, parent = #0)
		R = 777 (#5, parent = #2)

Удаление 777
600 (#0, parent = NONE)
	L = 444 (#1, parent = #0)
		L = 321 (#3, parent = #1)
		R = 445 (#4, parent = #1)
	R = 666 (#2, parent = #0)

Удаление 444
600 (#0, parent = NONE)
	L = 445 (#1, parent = #0)
		L = 321 (#3, parent = #1)
	R = 666 (#2, parent = #0)

Удаление 445
600 (#0, parent = NONE)
	L = 321 (#1, parent = #0)
	R = 666 (#2, parent = #0)

Удаление 600
666 (#0, parent = NONE)
	L = 321 (#1, parent = #0)

Удаление 321
666 (#0, parent = NONE)

Удаление 666
<пусто>
https://ideone.com/9ZOgFD
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

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!