fork download
copy 
  1. #include <iostream>
  2.  
  3. template <class T>
  4. class RBTree{
  5. public:
  6. 	typedef enum { BLACK, RED } NodeColor;
  7. 	// Определение сторожевого узла
  8. 	// (фиктивного черного листа красно-черного дерева
  9. 	#define NIL &sentinel
  10. 	// Red Black TREE NODE
  11. 	template <class DATA>
  12. 	struct RBTreeNode{
  13. 		RBTreeNode<DATA> *parent;	// Указатель на родительский узел
  14. 	RBTreeNode<DATA> *left;		// Указатель на узел-корень 
  15. 								// левого поддерева
  16. 	RBTreeNode<DATA> *right;	// Указатель на узел-корень
  17. 								// правого поддерева
  18. 	NodeColor color; // Цвет узла
  19. 	DATA data; // Объект данных, хранящихся в узле дерева
  20. 	RBTreeNode(	const DATA& _data, 
  21. 				RBTreeNode<DATA>* _parent = NULL,
  22. 				RBTreeNode<DATA>* _left = NIL,
  23. 				RBTreeNode<DATA>* _right = NIL,
  24. 				NodeColor _color = RED ){
  25. 					data = _data;
  26. 					parent = _parent;
  27. 					left = _left;
  28. 					right = _right;
  29. 					color = _color;
  30. 		} 
  31. 	};
  32. private:
  33. 	RBTreeNode<T> sentinel; // Сторожевой узел
  34. 	RBTreeNode<T> *root;	// Корень дерева
  35. public:
  36. 	RBTree() : sentinel(0, NULL, NIL, NIL, BLACK){
  37. 		root = NIL;
  38. 	}
  39. 	// Вставка узла
  40. 	RBTreeNode<T> *InsertNode(const T& data) {
  41. 		//Вспомогательные указатели:
  42. 		RBTreeNode<T> *newItem; // на новый элемент
  43. 		RBTreeNode<T> *current; // на обозреваемый элемент
  44. 		RBTreeNode<T> *parent; // на родительский элемент для обозреваемого элемента
  45. 		// Поиск места вставки 
  46. 		current = root;
  47. 		parent = NULL;
  48. 		while(current != NIL){
  49. 			if(data == current->data) return current; // Такой узел уже есть 
  50. 			parent = current; 
  51. 			if(data < current->data)
  52. 				current = current->left;
  53. 			else сurrent = current->right;
  54. 		}
  55. 		// Создание нового узла
  56. 		newItem = new RBTreeNode<T>(data, parent, NIL, NIL, RED);
  57. 		// Привязка нового узла к дереву
  58. 		if(parent == NULL){
  59. 			root = newItem;
  60. 		}else{
  61. 			//Здесь: новый элемент не является корнем дерева
  62. 			if(newItem->data < parent->data)
  63. 					parent->left = newItem;
  64. 			else	parent->right = newItem;
  65. 		}
  66. 		// Восстановление баланса после вставки
  67. 		InsertFixup(newItem);
  68. 		return newItem;
  69. 	}
  70.  
  71. 	// Поиск узла
  72. 	RBTreeNode<T> *FindNode(const T& data){
  73. 		RBTreeNode<T> *current = root;
  74. 		while(true){
  75. 			if(current == NIL) return NULL;
  76. 			if(current->data == data) return current;
  77. 			if(data < current->data)
  78. 					сurrent = current->left;
  79. 			else	current = current->right; 
  80. 		} 
  81. 	}
  82.  
  83. 	// Удаление узла по значению данных
  84. 	void DeleteNode(const T& data){
  85. 		RBTreeNode<T> *toDelete = FindNode(data);
  86. 		DeleteNode(toDelete);
  87. 	}
  88.  
  89. 	// Удаление узла по адресу узла
  90. 	void DeleteNode(RBTreeNode<T> *toDelete){
  91. 		RBTreeNode<T> *x, *y; // Указатели на узлы в ходе спусков влево-вправо
  92. 		if(toDelete == NULL || toDelete == NIL) return;
  93. 		if(toDelete->left == NIL || toDelete->right == NIL){
  94. 			// Хотя бы одно из поддеревьев отсутствует
  95. 			y = toDelete;
  96. 		}else{
  97. 			// Есть оба поддерева
  98. 			y = toDelete->right;
  99. 			while(y->left != NIL) y = y->left;
  100. 		}
  101. 		// Обрабатываем случай, когда у узла "y"
  102. 		// только один потомок
  103. 		if(y->left != NIL)	x = y->left;
  104. 		else				x = y->right;
  105. 		// Исключаем узел "y" из "родительской" цепочки 
  106. 		x->parent = y->parent;
  107. 		if(y->parent != NULL){
  108. 			if(y == y->parent->left)	y->parent->left = x;
  109. 			else						y->parent->right = x;
  110. 		}else root = x;
  111. 		if(y != toDelete){
  112. 			toDelete->data =y->data;
  113. 		}if(y->color == BLACK){
  114. 			// Восстановление баланса после удаления
  115. 			DeleteFixup(x);
  116. 		}
  117. 		delete y; 
  118. 	}
  119.  
  120. private:
  121. 	// Поворот дерева с корнем root вправо относительно узла x
  122. 	void RotateRight( RBTreeNode<T> *x ){
  123. 		RBTreeNode<T> *y = x->left;
  124. 		// Формируем левое поддерево для x
  125. 		x->left = y->right;
  126. 		if(y->right != NIL) y->right->parent = x;
  127. 		if(y != NIL) y->parent = x->parent; 
  128. 		if(x->parent != NULL){
  129. 			if(x == x->parent->right)	x->parent->right = y;
  130. 			else						x->parent->left = y;
  131. 		}else root = y;
  132. 		// Связываем x и y
  133. 		y->right = x;
  134. 		if(x != NIL) x->parent = y;
  135. 	}
  136.  
  137. 	// Поворот дерева с корнем root влево относительно узла x
  138. 	void RotateLeft(RBTreeNode<T> *x){
  139. 		RBTreeNode<T> *y = x->right; 
  140. 		// Формируем правое поддерево для x
  141. 		x->right = y->left;
  142. 		if(y->left != NIL) y->left->parent = x;
  143. 		if(y != NIL) y->parent = x->parent;
  144. 		if(x->parent != NULL){
  145. 			if(x == x->parent->left)	x->parent->left = y;
  146. 			else						x->parent->right = y;
  147. 		}else root = y; 
  148. 		// Связываем x и y
  149. 		y->left = x;
  150. 		if(x != NIL) x->parent = y;
  151. 	}
  152.  
  153. 	// Восстановление баланса после вставки узла x
  154. 	void InsertFixup(RBTreeNode<T> *x){
  155. 		// Двигаемся в направлении root пока не будет восстановлено свойство 3
  156. 		while(x != root && x->parent->color == RED){
  157. 			if(x->parent == x->parent->parent->left){
  158. 				// Родитель в левом поддереве относительно деда
  159. 				RBTreeNode<T> *uncle = x->parent->parent->right;
  160. 				if( uncle->color == RED ){
  161. 					// Перекрашиваем родителя и дядю в черный...
  162. 					x->parent->color = uncle->color = BLACK;
  163. 					// ... а деда – в красный
  164. 					x->parent->parent->color = RED;
  165. 					x = x->parent->parent;	// Теперь дед – это x
  166. 				}else{	// Дядя – черный
  167. 					if(x == x->parent->right){
  168. 						x = x->parent;
  169. 						RotateLeft(x);
  170. 					}
  171. 					x->parent->color = BLACK;
  172. 					x->parent->parent->color = RED;
  173. 					RotateRight(x->parent->parent);
  174. 				}
  175. 			}else{
  176. 				// Родитель в правом поддереве
  177. 				// относительно деда
  178. 				// (зеркальное отражение предыдущего блока)
  179. 				RBTreeNode<T> *uncle = x->parent->parent->left;
  180. 				if(uncle->color == RED){
  181. 					x->parent->color = uncle->color = BLACK;
  182. 					x->parent->parent->color = RED;
  183. 					x = x->parent->parent;
  184. 				}else{
  185. 					if(x == x->parent->left){
  186. 						x = x->parent;
  187. 						RotateRight(x);
  188. 					}
  189. 					x->parent->color = BLACK;
  190. 					x->parent->parent->color = RED;
  191. 					RotateLeft(x->parent->parent);
  192. 				}
  193. 			}
  194. 		}
  195. 		root->color = BLACK;
  196. 	}
  197.  
  198. 	// Восстановление баланса после удаления узла x
  199. 	void DeleteFixup(RBTreeNode<T> *x){
  200. 		while(x != root && x->color == BLACK){
  201. 			if(x == x->parent->left){
  202. 				// Удаляемый элемент – корень левого
  203. 				// поддерева
  204. 				RBTreeNode<T> *brother = x->parent->right;
  205. 				if(brother->color == RED){
  206. 					brother->color = BLACK;
  207. 					x->parent->color = RED;
  208. 					RotateLeft(x->parent);
  209. 					brother = x->parent->right;
  210. 				}
  211. 				if(brother->left->color == BLACK && brother->right->color == BLACK){
  212. 					brother->color = RED;
  213. 					x = x->parent;
  214. 				}else{
  215. 					if(brother->right->color == BLACK){
  216. 						brother->left->color = BLACK;
  217. 						brother->color = RED;
  218. 						RotateRight(brother);
  219. 						brother = x->parent->right;
  220. 					}
  221. 					brother->color = x->parent->color;
  222. 					x->parent->color = BLACK;
  223. 					brother->right->color = BLACK;
  224. 					RotateLeft(x->parent);
  225. 					x = root;
  226. 				}
  227. 			}else{
  228. 				// Удаляемый элемент – корень правого
  229. 				// поддерева
  230. 				RBTreeNode<T> *brother = x->parent->left;
  231. 				if(brother->color == RED){
  232. 					brother->color = BLACK;
  233. 					x->parent->color = RED;
  234. 					RotateRight(x->parent);
  235. 					brother = x->parent->left;
  236. 				}
  237. 				if( brother->right->color == BLACK && brother->left->color == BLACK){
  238. 					brother->color = RED; 
  239. 					x = x->parent;
  240. 				}else{
  241. 					if(brother->left->color == BLACK){
  242. 						brother->right->color = BLACK;
  243. 						brother->color = RED;
  244. 						RotateLeft(brother);
  245. 						brother = x->parent->left;
  246. 					}
  247. 					brother->color = x->parent->color;
  248. 					x->parent->color = BLACK;
  249. 					brother->left->color = BLACK;
  250. 					RotateRight(x->parent);
  251. 					x = root;
  252. 				}
  253. 			}
  254. 		}
  255. 		x->color = BLACK;
  256. 	}
  257.  
  258. 	void DeleteNode(RBTreeNode<T> *&root, RBTreeNode<T> *toDelete){
  259. 		RBTreeNode<T> *x, *y;	// Указатели на узлы в ходе
  260. 								// спусков влево-вправо
  261. 		if(toDelete == NULL || toDelete == NIL) return;
  262. 		if(toDelete->left == NIL || toDelete->right == NIL){
  263. 			// Хотя бы одно из поддеревьев отсутствует
  264. 			y = toDelete;
  265. 		}else{
  266. 			// Есть оба поддерева
  267. 			y = toDelete->right;
  268. 			while(y->left != NIL) y = y->left;
  269. 		}
  270. 		// Обрабатываем случай, когда у узла "y" только
  271. 		// один потомок
  272. 		if(y->left != NIL)	x = y->left;
  273. 		else				x = y->right;
  274. 		// Исключаем узел "y" из "родительской" цепочки
  275. 		x->parent = y->parent;
  276. 		if(y->parent != NULL){
  277. 			if(y == y->parent->left)	y->parent->left = x;
  278. 			else						y->parent->right = x;
  279. 		}else root = x;
  280. 		if(y != toDelete){
  281. 			toDelete->data =y->data;
  282. 		}
  283. 		if(y->color == BLACK){
  284. 			// Восстановление баланса после удаления
  285. 			DeleteFixup( root, x );
  286. 		}
  287. 		delete y;
  288. 	}
  289. };
  290.  
  291. int main() {
  292. 	RBTree<int> rb;
  293. 	rb.InsertNode(3);
  294.  
  295. 	return 0;
  296. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:53:4: error: stray '\321' in program
    else сurrent = current->right;
    ^
prog.cpp:53:4: error: stray '\201' in program
prog.cpp:78:6: error: stray '\321' in program
      сurrent = current->left;
      ^
prog.cpp:78:6: error: stray '\201' in program
prog.cpp:9:15: error: invalid use of non-static data member 'RBTree<T>::sentinel'
  #define NIL &sentinel
               ^
prog.cpp:22:31: note: in expansion of macro 'NIL'
     RBTreeNode<DATA>* _left = NIL,
                               ^
prog.cpp:33:16: note: declared here
  RBTreeNode<T> sentinel; // Сторожевой узел
                ^
prog.cpp:9:15: error: invalid use of non-static data member 'RBTree<T>::sentinel'
  #define NIL &sentinel
               ^
prog.cpp:23:32: note: in expansion of macro 'NIL'
     RBTreeNode<DATA>* _right = NIL,
                                ^
prog.cpp:33:16: note: declared here
  RBTreeNode<T> sentinel; // Сторожевой узел
                ^
prog.cpp: In member function 'RBTree<T>::RBTreeNode<T>* RBTree<T>::InsertNode(const T&)':
prog.cpp:53:11: error: 'urrent' was not declared in this scope
    else сurrent = current->right;
           ^
prog.cpp: In member function 'RBTree<T>::RBTreeNode<T>* RBTree<T>::FindNode(const T&)':
prog.cpp:78:8: error: 'urrent' was not declared in this scope
      сurrent = current->left;
        ^
stdout
copy 
Standard output is empty
https://ideone.com/FMgM77
language:
C++ (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!