fork(2) download
copy 
  1. #include <memory>
  2. #include <iostream>
  3.  
  4. /// Binary Search Tree
  5. template<class T> class bstree {
  6. // I will make use of protected, feel free to use private only
  7. // ... can be used to create another template
  8. // ... or for debug purposes - printouts in such derived class
  9. // ... but remember to never inherit publicly
  10. // ... because it has public non-virtual destructor
  11. //================================================================== node
  12. protected:
  13. 	struct node;	// forward declaration
  14. 	typedef std::unique_ptr<node>
  15. 		ptr;		///< managed pointer to node
  16. 	struct node {
  17. 		ptr left;	///< left node (if any)
  18. 		ptr right;	///< right node (if any)
  19. 		T value;	///< stored value
  20. 	//------------------------------------------------ node: construction
  21. 		node() {}
  22. 		node(
  23. 		  const T& value,
  24. 		  node* left = nullptr,
  25. 		  node* right = nullptr)
  26. 		: left(left), right(right), value(value) {}
  27. 		node(
  28. 		  T&& value,
  29. 		  node* left = nullptr,
  30. 		  node* right = nullptr)
  31. 		: left(left), right(right), value(value) {}
  32. 	//--------------------------------------------------- node: deep copy
  33. 	///	Make a deep copy of all nodes. May be called on null as well.
  34. 		node* copy() {
  35. 			return !this ? nullptr :
  36. 			  new node(value,
  37. 			  left->copy(),
  38. 			  right->copy());
  39. 		}
  40. 	//-------------------------------------------------- node: find value
  41. 	/// Find node with specified value. May be called on null as well.
  42. 		node* find(const T& what) {
  43. 			node* it = this;
  44. 			while(it) {
  45. 				if(what < value)
  46. 					it = it->left.get();
  47. 				else if(value < what)
  48. 					it = it->right.get();
  49. 				else break;
  50. 			}
  51. 			return it;
  52. 		}
  53. 	//------------------------------------------------- node: place value
  54. 	/// Find place for new node \return null if already there
  55. 		ptr* where(const T& what) {
  56. 			node* it = this;
  57. 			ptr* where;
  58. 			for(;;) {
  59. 				if(what < it->value) {
  60. 					if(!it->left) return &it->left;
  61. 					it = it->left.get();
  62. 				} else if(it->value < what) {
  63. 					if(!it->right) return &it->right;
  64. 					it = it->right.get();
  65. 				} else return nullptr;
  66. 			}
  67. 		}
  68. 	};
  69. //================================================================== data
  70. protected:
  71. 	ptr root;		///< root node
  72. 	size_t count;	///< total number of nodes
  73. //====================================================== ctor, copy, move
  74. public:
  75. ///	Default constructor for empty tree
  76. 	bstree(): root(), count(0) {}
  77. //note: no need for a destructor, we use managed pointers
  78. //	~bstree() {}
  79. ///	Copy constructor
  80. 	bstree(const bstree& src)
  81. 	: root(src.root->copy()), count(src.count) {}
  82. ///	Move constructor
  83. 	bstree(bstree&& rhs)
  84. 	: root(std::move(rhs.root)), count(rhs.count) {
  85. 		rhs.count = 0; }
  86. ///	Move assignment
  87. 	bstree& operator = (bstree&& rhs) {
  88. 		root.swap(rhs.root);
  89. 		std::swap(count, rhs.count);
  90. 		return *this; }
  91. ///	Copy assignment
  92. 	bstree& operator = (const bstree& rhs) {
  93. 		if (this != &rhs) {// no self-copy
  94. 			root.reset(rhs.root->copy());
  95. 			count = rhs.count; }
  96. 		return *this; }
  97. //=============================================================== methods
  98. public:
  99. 	bool contains(const T& value) {
  100. 		return root && root->find(value); }
  101. 	bool insert(const T& value) {
  102. 		ptr* where = &root;
  103. 		if(root) {
  104. 			where = root->where(value);
  105. 			if(!where) return false; }
  106. 		where->reset(new node(value));
  107. 		++count; return true;
  108. 	}
  109. 	bool insert(T&& value) {
  110. 		ptr* where = &root;
  111. 		if(root) {
  112. 			where = root->where(value);
  113. 			if(!where) return false; }
  114. 		where->reset(new node(value));
  115. 		++count; return true;
  116. 	}
  117. };
  118.  
  119. //#######################################################################
  120.  
  121. using std::cout;
  122. using std::endl;
  123.  
  124. class test: protected bstree<int> {
  125. 	typedef bstree<int> base;
  126. 	void print(node* it) {
  127. 		if(!it) return;
  128. 		cout << '<' << it->value << ':';
  129. 		print(it->left.get()); cout << '|';
  130. 		print(it->right.get()); cout << '>';
  131. 	}
  132. public:
  133. 	using base::contains;
  134. 	using base::insert;
  135. public:
  136. 	test() { cout << "new" << endl; }
  137. 	test(test&& rhs): base(rhs) { cout << "move .ctor" << endl; }
  138. 	test(const test& src): base(src) { cout << "copy .ctor" << endl; }
  139. 	test& operator = (test&& rhs) {
  140. 		cout << "move assign" << endl;
  141. 		base::operator = ((base&&)rhs);
  142. 		return *this; }
  143. 	test& operator = (const test& src) {
  144. 		cout << "copy assign" << endl;
  145. 		base::operator = (src);
  146. 		return *this; }
  147. 	void print() {
  148. 		print(root.get()); cout << endl; }
  149. };
  150.  
  151. int main() {
  152. 	test tree;
  153. 	tree.insert(3);
  154. 	tree.insert(2);
  155. 	tree.insert(4);
  156. 	cout << std::boolalpha << tree.insert(2) << endl;
  157. 	cout << tree.contains(3) << ' ' << tree.contains(1) << endl;
  158. 	tree.print();
  159. 	tree = tree;
  160. 	tree = std::move(tree);
  161. 	tree.print();
  162. 	tree.insert(1);
  163. 	tree.insert(5);
  164. 	tree.print();
  165. }
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
new
false
true false
<3:<2:|>|<4:|>>
copy assign
move assign
<3:<2:|>|<4:|>>
<3:<2:<1:|>|>|<4:|<5:|>>>
https://ideone.com/v5Cucj
Basics of Binary Search Tree
language:
C++14 (gcc 8.3)
created:
9 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!