Red Black Treeの実装

Red BlackTreeとは?

2.なぜRedBlackTreeが必要なのか

3. RedBlackTree vs AVL Tree

4.n個の内部ノードを有する赤黒木の高さは2 log(2)(n+1)以下である。

5.Red Black Tree計算の実施

1)left-rotate vs right-rotate

insert、削除後に破損した赤と黒の木を復元します.

2)insert

(1)case 1:おじさんノードが赤いノードであれば

(2)case 2:おじさんノードは黒,他のノードは右サブノード

(3)case 3:おじさんノードが黒いノード、その他のノードが左側のサブノード

iterator insert(iterator position, const value_type& value){
			node_pointer new_node = search(value,_root);
			if (new_node)
				return (iterator(new_node));
			new_node = _node_alloc.allocate(1);
			_node_alloc.construct(new_node, Node<value_type>(create_value(value)));
			new_node->left = _nil;
			new_node->right = _nil;
			if (position == begin()){
				if (position != end() && _compare(value, *position))
					_insert_into_tree(new_node, tree_min(_root));
				else
					_insert_into_tree(new_node, _root);
			}
			else if (position == end()){
				if (position != begin() && _compare(*(--position), value))
					_insert_into_tree(new_node, _header->parent);
				else
					_insert_into_tree(new_node, _root);
			}
			else
				_insert_into_tree(new_node, _root);
			_insert_fixup(new_node);
			_size++;
			node_pointer max_of_tree = tree_max(_root);
			max_of_tree->right = _header;
			_header->parent = max_of_tree;
			return (iterator(new_node));
		}

void _insert_fixup(node_pointer node){
			if (node != _root && node->parent != _root){
				while (node != _root && !node->parent->is_black){
					if (node->parent == node->parent->parent->left){
						node_pointer uncle = node->parent->parent->right;
						if (!uncle->is_black){
							node->parent->is_black = true;
							uncle->is_black = true;
							node->parent->parent->is_black = false;
							node = node->parent->parent;
						}
						else {
							if (node == node->parent->right){
								node = node->parent;
								_rotate_left(node);
							}
							node->parent->is_black = true;
							node->parent->parent->is_black = false;
							_rotate_right(node->parent->parent);
						}
					}
					else{
						node_pointer uncle = node->parent->parent->left;
						if (!uncle->is_black){
							node->parent->is_black = true;
							uncle->is_black = true;
							node->parent->parent->is_black = false;
							node = node->parent->parent;
						}
						else{
							if (node == node->parent->left){
								node = node->parent;
								_rotate_right(node);
							}
							node->parent->is_black = true;
							node->parent->parent->is_black = false;
							_rotate_left(node->parent->parent);
						}
					}
				}
			}
			_root->is_black = true;
		}

3)delete

(1)削除するノードが赤の場合は、通常バイナリツリーを削除する場合と同様に削除できます。

(2)削除するノードが黒の場合はredblack tree delete fixが必要

void erase(iterator pos){
			node_pointer y = pos.node(), x, for_free = y;
			bool y_original_is_black = y->is_black;
			if (is_nil(y->left)){
				x = y->right;
				transplant(y, y->right);
			}
			else if (is_nil(y->right)){
				x = y->left;
				transplant(y, y->left);
			}
			else {
				node_pointer z = y;
				y = tree_min(z->right);
				y_original_is_black = y->is_black;
				x = y->right;
				if (y->parent != z){
					transplant(y, y->right);
					y->right = z->right;
					z->right->parent = y;
				}
				transplant(z, y);
				y->left = z->left;
				y->left->parent = y;
				y->is_black = z->is_black;
			}
			free_node(for_free);
			if (y_original_is_black)
				erase_fixup(x);
			_size--;
			_nil->parent = NULL;
			if (_size == 0)
				_root = _header;
			else{
				if (_size != 1)
					x = tree_max(_root);
				else
					x = _root;
				x->right = _header;
				_header->parent = x;
			}
		}
        
        
        void erase_fixup(node_pointer x){
			node_pointer brother;
			while (x != _root && x->is_black){
				if (x == x->parent->left){
					brother = x->parent->right;
					//case 1
					if (!brother->is_black){
						brother->is_black = true;
						x->parent->is_black = false;
						_rotate_left(x->parent);
						brother = x->parent->right;
					}
					//case 2
					if (brother->left->is_black && brother->right->is_black){
						brother->is_black = false;
						x = x->parent;
					}
					else{
					//case 3
						if (brother->right->is_black){
							brother->left->is_black = true;
							brother->is_black = false;
							_rotate_right(brother);
							brother = x->parent->right;
						}
					//case 4
						brother->is_black = x->parent->is_black;
						x->parent->is_black = true;
						brother->right->is_black = true;
						_rotate_left(x->parent);
						x = _root;
					}
				}
				else{
					brother = x->parent->left;
					//case 1
					if (!brother->is_black){
						brother->is_black = true;
						x->parent->is_black = false;
						_rotate_right(x->parent);
						brother = x->parent->left;
					}
					//case 2
					if (brother->right->is_black && brother->left->is_black){
						brother->is_black = false;
						x = x->parent;
					}
					else{
					//case 3
						if (brother->left->is_black){
							brother->right->is_black = true;
							brother->is_black = false;
							_rotate_left(brother);
							brother = x->parent->left;
						}
					//case 4
						brother->is_black = x->parent->is_black;
						x->parent->is_black = true;
						brother->left->is_black = true;
						_rotate_right(x->parent);
						x = _root;
					}
				}
			}
		}

6.RedBlackTreeのクリーンアップ