Red-black tree source code
Next, we will encapsulate the red-black tree of a KV model, and at the same time simulate and realize the map and set in the C++STL library, the used Red-black tree source code as follows:
//Enumeration defines the color of the node
enum Colour
{
RED,
BLACK
};
//Red-black tree node definition
template<class K, class V>
struct RBTreeNode
{
//trident chain
RBTreeNode<K, V>* _left;
RBTreeNode<K, V>* _right;
RBTreeNode<K, V>* _parent;
//Stored key-value pairs
pair<K, V> _kv;
//node color
int _col; //red/black
//Constructor
RBTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _col(RED)
{}
};
//Implementation of red-black tree
template<class K, class V>
class RBTree
{
typedef RBTreeNode<K, V> Node;
public:
//Constructor
RBTree()
:_root(nullptr)
{}
//copy construction
RBTree(const RBTree<K, V>& t)
{
_root = _Copy(t._root, nullptr);
}
//Assignment operator overloading (modern notation)
RBTree<K, V>& operator=(RBTree<K, V> t)
{
swap(_root, t._root);
return *this;
}
//destructor
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
//lookup function
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_kv.first) //The key value is less than the value of the node
{
cur = cur->_left; //Search in the left subtree of the node
}
else if (key > cur->_kv.first) //The key value is greater than the value of the node
{
cur = cur->_right; //Search in the right subtree of the node
}
else //target node found
{
return cur; //return to this node
}
}
return nullptr; //Find failed
}
//insert function
pair<Node*, bool> Insert(const pair<K, V>& kv)
{
if (_root == nullptr) //If the red-black tree is an empty tree, insert the node directly as the root node
{
_root = new Node(kv);
_root->_col = BLACK; //The root node must be black
return make_pair(_root, true); //Inserted successfully
}
//1. According to the insertion method of the binary search tree, find the position to be inserted
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first < cur->_kv.first) //The key value of the node to be inserted is less than the key value of the current node
{
//Go to the left subtree of the node
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first) //The key value of the node to be inserted is greater than the key value of the current node
{
//Go to the right subtree of the node
parent = cur;
cur = cur->_right;
}
else //The key value of the node to be inserted is equal to the key value of the current node
{
return make_pair(cur, false); //insert failed
}
}
//2. Insert the node to be inserted into the tree
cur = new Node(kv); //Constructs a node from the given value
Node* newnode = cur; //Record the newly inserted node (for subsequent return)
if (kv.first < parent->_kv.first) //The key value of the new node is less than the key value of the parent
{
//Insert to the left of parent
parent->_left = cur;
cur->_parent = parent;
}
else //The key value of the new node is greater than the key value of the parent
{
//Insert to the right of parent
parent->_right = cur;
cur->_parent = parent;
}
//3. If the parent node of the inserted node is red, the red-black tree needs to be adjusted
while (parent&&parent->_col == RED)
{
Node* grandfather = parent->_parent; //parent is red, its parent node must exist
if (parent == grandfather->_left) //parent is grandfather's left child
{
Node* uncle = grandfather->_right; //uncle is the right child of grandfather
if (uncle&&uncle->_col == RED) //Case 1: uncle exists and is red
{
//color adjustment
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//continue to process
cur = grandfather;
parent = cur->_parent;
}
else //Case 2+ Case 3: uncle does not exist + uncle exists and is black
{
if (cur == parent->_left)
{
RotateR(grandfather); //Right monorotation
//color adjustment
grandfather->_col = RED;
parent->_col = BLACK;
}
else //cur == parent->_right
{
RotateLR(grandfather); //Left and right double rotation
//color adjustment
grandfather->_col = RED;
cur->_col = BLACK;
}
break; //After the subtree is rotated, the root of the subtree becomes black, and there is no need to continue to process it
}
}
else //parent is the right child of grandfather
{
Node* uncle = grandfather->_left; //uncle is grandfather's left child
if (uncle&&uncle->_col == RED) //Case 1: uncle exists and is red
{
//color adjustment
uncle->_col = parent->_col = BLACK;
grandfather->_col = RED;
//continue to process
cur = grandfather;
parent = cur->_parent;
}
else //Case 2+ Case 3: uncle does not exist + uncle exists and is black
{
if (cur == parent->_left)
{
RotateRL(grandfather); //right left double rotation
//color adjustment
cur->_col = BLACK;
grandfather->_col = RED;
}
else //cur == parent->_right
{
RotateL(grandfather); //left monorotation
//color adjustment
grandfather->_col = RED;
parent->_col = BLACK;
}
break; //After the subtree is rotated, the root of the subtree becomes black, and there is no need to continue to process it
}
}
}
_root->_col = BLACK; //The color of the root node is black (it may be changed to red by case 1 and needs to be changed back to black)
return make_pair(newnode, true); //Inserted successfully
}
//delete function
bool Erase(const K& key)
{
//for traversing a binary tree
Node* parent = nullptr;
Node* cur = _root;
//Used to mark the actual node to be deleted and its parent node
Node* delParentPos = nullptr;
Node* delPos = nullptr;
while (cur)
{
if (key < cur->_kv.first) //The given key value is less than the key value of the current node
{
//Go to the left subtree of the node
parent = cur;
cur = cur->_left;
}
else if (key > cur->_kv.first) //The given key value is greater than the key value of the current node
{
//Go to the right subtree of the node
parent = cur;
cur = cur->_right;
}
else //Found the node to be deleted
{
if (cur->_left == nullptr) //The left subtree of the node to be deleted is empty
{
if (cur == _root) //The node to be deleted is the root node
{
_root = _root->_right; //Let the right subtree of the root node be the new root node
if (_root)
{
_root->_parent = nullptr;
_root->_col = BLACK; //root node is black
}
delete cur; //Delete the original root node
return true;
}
else
{
delParentPos = parent; //Mark the parent node of the node that was actually deleted
delPos = cur; //mark the actual deleted node
}
break; //Perform red-black tree adjustments and actual deletion of nodes
}
else if (cur->_right == nullptr) //The right subtree of the node to be deleted is empty
{
if (cur == _root) //The node to be deleted is the root node
{
_root = _root->_left; //Let the left subtree of the root node be the new root node
if (_root)
{
_root->_parent = nullptr;
_root->_col = BLACK; //root node is black
}
delete cur; //Delete the original root node
return true;
}
else
{
delParentPos = parent; //Mark the parent node of the node that was actually deleted
delPos = cur; //mark the actual deleted node
}
break; //Perform red-black tree adjustments and actual deletion of nodes
}
else //The left and right subtrees of the node to be deleted are not empty
{
//delete by substitution
//Find the node with the smallest key value in the right subtree of the node to be deleted as the actual deleted node
Node* minParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
minParent = minRight;
minRight = minRight->_left;
}
cur->_kv.first = minRight->_kv.first; //Change the key of the node to be deleted to the key of minRight
cur->_kv.second = minRight->_kv.second; //Change the value of the node to be deleted to the value of minRight
delParentPos = minParent; //Mark the parent node of the node that was actually deleted
delPos = minRight; //mark the actual deleted node
break; //Perform red-black tree adjustments and actual deletion of nodes
}
}
}
if (delPos == nullptr) //delPos has not been modified, indicating that no node to be deleted was found
{
return false;
}
//Record the node to be deleted and its parent node (for subsequent actual deletion)
Node* del = delPos;
Node* delP = delParentPos;
//tuned red-black tree
if (delPos->_col == BLACK) //Deleted is the black node
{
if (delPos->_left) //The node to be deleted has a red left child (it cannot be black)
{
delPos->_left->_col = BLACK; //Just turn the red left child black
}
else if (delPos->_right) //The node to be deleted has a red right child (it cannot be black)
{
delPos->_right->_col = BLACK; //Just turn the red right child black
}
else //The left and right sides of the node to be deleted are empty
{
while (delPos != _root) //may be adjusted all the way to the root node
{
if (delPos == delParentPos->_left) //The node to be deleted is the left child of its parent node
{
Node* brother = delParentPos->_right; //A sibling node is the right child of its parent node
//Case 1: brother is red
if (brother->_col == RED)
{
delParentPos->_col = RED;
brother->_col = BLACK;
RotateL(delParentPos);
//need to continue processing
brother = delParentPos->_right; //Update brother (otherwise there will be an error in executing other codes in this loop)
}
//Case 2: brother is black, and its left and right children are all black nodes or empty
if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))
&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK)))
{
brother->_col = RED;
if (delParentPos->_col == RED)
{
delParentPos->_col = BLACK;
break;
}
//need to continue processing
delPos = delParentPos;
delParentPos = delPos->_parent;
}
else
{
//Case 3: brother is black, and its left child is a red node, and its right child is a black node or empty
if ((brother->_right == nullptr) || (brother->_right->_col == BLACK))
{
brother->_left->_col = BLACK;
brother->_col = RED;
RotateR(brother);
//need to continue processing
brother = delParentPos->_right; //Update brother (otherwise an error will occur when executing the code in case 4 below)
}
//Situation 4: brother is black, and its right child is a red node
brother->_col = delParentPos->_col;
delParentPos->_col = BLACK;
brother->_right->_col = BLACK;
RotateL(delParentPos);
break; //Situation 4: After the implementation is completed, the adjustment must be completed
}
}
else //delPos == delParentPos->_right //The node to be deleted is the left child of its parent node
{
Node* brother = delParentPos->_left; //A sibling node is the left child of its parent node
//Case 1: brother is red
if (brother->_col == RED) //brother is red
{
delParentPos->_col = RED;
brother->_col = BLACK;
RotateR(delParentPos);
//need to continue processing
brother = delParentPos->_left; //Update brother (otherwise there will be an error in executing other codes in this loop)
}
//Case 2: brother is black, and its left and right children are all black nodes or empty
if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))
&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK)))
{
brother->_col = RED;
if (delParentPos->_col == RED)
{
delParentPos->_col = BLACK;
break;
}
//need to continue processing
delPos = delParentPos;
delParentPos = delPos->_parent;
}
else
{
//Case 3: brother is black, and its right child is a red node, and its left child is a black node or empty
if ((brother->_left == nullptr) || (brother->_left->_col == BLACK))
{
brother->_right->_col = BLACK;
brother->_col = RED;
RotateL(brother);
//need to continue processing
brother = delParentPos->_left; //Update brother (otherwise an error will occur when executing the code in case 4 below)
}
//Situation 4: brother is black, and its left child is a red node
brother->_col = delParentPos->_col;
delParentPos->_col = BLACK;
brother->_left->_col = BLACK;
RotateR(delParentPos);
break; //Situation 4: After the implementation is completed, the adjustment must be completed
}
}
}
}
}
//do the actual deletion
if (del->_left == nullptr) //The left subtree of the actually deleted node is empty
{
if (del == delP->_left) //The actual deleted node is the left child of its parent node
{
delP->_left = del->_right;
if (del->_right)
del->_right->_parent = delP;
}
else //The actual deleted node is the right child of its parent node
{
delP->_right = del->_right;
if (del->_right)
del->_right->_parent = delP;
}
}
else //The right subtree of the actually deleted node is empty
{
if (del == delP->_left) //The actual deleted node is the left child of its parent node
{
delP->_left = del->_left;
if (del->_left)
del->_left->_parent = delP;
}
else //The actual deleted node is the right child of its parent node
{
delP->_right = del->_left;
if (del->_left)
del->_left->_parent = delP;
}
}
delete del; //actually delete the node
return true;
}
private:
//copy tree
Node* _Copy(Node* root, Node* parent)
{
if (root == nullptr)
{
return nullptr;
}
Node* copyNode = new Node(root->_data);
copyNode->_parent = parent;
copyNode->_left = _Copy(root->_left, copyNode);
copyNode->_right = _Copy(root->_right, copyNode);
return copyNode;
}
//destructor subfunction
void _Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
//left monorotation
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
//Establish a connection between subRL and parent
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
//Establish a connection between parent and subR
subR->_left = parent;
parent->_parent = subR;
//Establish a connection between subR and parentParent
if (parentParent == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
//Right monorotation
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
//Establish a connection between subLR and parent
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
//Establish a connection between parent and subL
subL->_right = parent;
parent->_parent = subL;
//Establish a connection between subL and parentParent
if (parentParent == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
//Left and right double rotation
void RotateLR(Node* parent)
{
RotateL(parent->_left);
RotateR(parent);
}
//right left double rotation
void RotateRL(Node* parent)
{
RotateR(parent->_right);
RotateL(parent);
}
Node* _root; //The root node of the red-black tree
};
Red-black tree template parameter control
We all know that set is the container of K model, and map is the container of KV model, so how can we use a red-black tree of KV model to realize map and set at the same time?
Here we need to control the template parameters passed to the underlying red-black tree by map and set. In order to distinguish it from the template parameters of the original red-black tree, we change the name of the second template parameter of the red-black tree to T.
template<class K, class T> class RBTree
The T template parameter may only be the key-value Key, or may be a key-value pair composed of Key and Value. If it is a set container, then the template parameters it passes into the underlying red-black tree are Key and Key:
template<class K>
class set
{
public:
//...
private:
RBTree<K, K> _t;
};
But if it is a map container, then the template parameter passed to the underlying red-black tree is Key and the key-value pair composed of Key and Value:
template<class K, class V>
class map
{
public:
//...
private:
RBTree<K, pair<K, V>> _t;
};
Can you not use the first template parameter of the red-black tree, but only keep the second template parameter?
At first glance, it seems to be possible, because at this time the second template parameter of the red-black tree also has a key value Key, but in fact the first template parameter of the red-black tree cannot be omitted.
For the set container, it is of course no problem to omit the first parameter of the red-black tree, because the second parameter of the set passed to the red-black tree is the same as the first parameter. But it doesn't work for the map container, because some of the interfaces provided by the map container only require the key value Key, such as find and erase.
Data stored in red-black tree nodes
Now the template parameters of the red-black tree have become K and T, so what should be stored in the red-black tree nodes?
As mentioned earlier, due to the difference in the upper container, the K and T in the underlying red-black tree are also different:
- set container: K and T both represent the key value Key.
- map container: K represents the key-value Key, and T represents the key-value pair composed of Key and Value.
For the set container, the storage of K and T in the underlying red-black tree node is the same, but for the map container, the underlying red-black tree can only store T. Since the underlying red-black tree does not know whether the upper-level container is a map or a set, it is sufficient to directly store T in the nodes of the red-black tree.
In this way, when the upper-level container is a set, the key-value Key is stored in the node; when the upper-level container is a map, the key-value pair <Key, Value> is stored in the node.
The changed code is as follows:
//Red-black tree node definition
template<class T>
struct RBTreeNode
{
//trident chain
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
//stored data
T _data;
//node color
int _col; //red/black
//Constructor
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
Addition of functors in template parameters
Now because T is stored in the node, this T may be a Key, or it may be a <Key, Value> key-value pair. So when we need to compare the key value of the node, how should we get the key value of the node?
When the upper-level container is a set, T is the key-value Key, which can be compared directly with T, but it will not work when the upper-level container is a map. At this time, we need to extract the key value from the <Key, Value> key-value pair After the Key, the Key value is used for comparison.
Therefore, the upper container map needs to provide a functor to the underlying red-black tree to obtain the key value Key in T. In this way, when the underlying red-black tree needs to compare the key values of two nodes, it can pass This functor is used to get the key value in T.
A functor is what makes a class look like a function. In fact, the implementation is to implement an operator() in the class, and this class has a function-like behavior, which is a functor class.
But for the underlying red-black tree, it does not know whether the upper container is a map or a set, so when it is necessary to compare the key values of two nodes, the underlying red-black tree will obtain the key value Key through the incoming functor , and then compare the key values of the two nodes.
Therefore, the set container also needs to pass in a functor to the underlying red-black tree. Although this functor seems useless alone, it is essential.
template<class K>
class set
{
//functor
struct SetKeyOfT
{
const K& operator()(const K& key) //return Key valueKey
{
return key;
}
};
public:
//...
private:
RBTree<K, K, SetKeyOfT> _t;
};
At this point, what the set container passes into the underlying red-black tree is the functor of set, and what the map container passes into the underlying red-black tree is the functor of map.
In this way, when the underlying red-black tree needs to compare the key value between two nodes, the key value of the corresponding node will be obtained through the incoming functor, and then compared, the following is the red-black tree Take the lookup function as an example:
//lookup function
iterator Find(const K& key)
{
KeyOfT kot;
Node* cur = _root;
while (cur)
{
if (key < kot(cur->_data)) //The key value is less than the value of the node
{
cur = cur->_left; //Search in the left subtree of the node
}
else if (key > kot(cur->_data)) //The key value is greater than the value of the node
{
cur = cur->_right; //Search in the right subtree of the node
}
else //target node found
{
return iterator(cur); //return to this node
}
}
return end(); //Find failed
}
Note: In all places where the node key value is compared, it is necessary to obtain the key value of the corresponding node through the functor and then compare the key value.
Implementation of Forward Iterator
The forward iterator of the red-black tree actually encapsulates the node pointer, so there is actually only one member variable in the forward iterator, which is the pointer of the node encapsulated by the forward iterator.
//forward iterator
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef RBTreeNode<T> Node; //node type
typedef __TreeIterator<T, Ref, Ptr> Self; //the type of the forward iterator
Node* _node; //pointer to the node encapsulated by the forward iterator
};
Therefore, we can construct a forward iterator through a node pointer.
//Constructor
__TreeIterator(Node* node)
:_node(node) //Constructs a forward iterator based on the given node pointer
{}
When dereferencing the forward iterator, we simply return the reference to the corresponding node data.
Ref operator*()
{
return _node->_data; //Returns a reference to the node data
}
When the -> operation is performed on the forward iterator, we can directly return the pointer to the corresponding node data.
Ptr operator->()
{
return &_node->_data; //Returns a pointer to the node data
}
Of course, at least the == and != operators need to be overloaded in the forward iterator, and it is enough to directly judge whether the nodes encapsulated by the two iterators are the same during implementation.
//Determine whether two forward iterators are different
bool operator!=(const Self& s) const
{
return _node != s._node; //Determine whether the nodes encapsulated by two forward iterators are the same
}
//Determine whether two forward iterators are the same
bool operator==(const Self& s) const
{
return _node == s._node; //Determine whether the nodes encapsulated by two forward iterators are the same
}
When the red-black tree forward iterator is implemented, the real difficulty is actually the overloading of the ++ and – operators.
When implementing the forward iterator of the red-black tree, after the forward iterator of a node performs ++ operation, it should find the next node of the current node according to the sequence of in-order traversal of the red-black tree.
The specific logic is as follows:
-
If the right subtree of the current node is not empty, the leftmost node in its right subtree should be found after the ++ operation.
-
If the right subtree of the current node is empty, after the ++ operation, the ancestor node whose child is not on the right of the father should be found in the ancestor node of the node.
//prefix ++ Self operator++() { if (_node->_right) //The right subtree of the node is not empty { //Find the leftmost node in the right subtree of the node Node* left = _node->_right; while (left->_left) { left = left->_left; } _node = left; //++ becomes the node } else //The right subtree of the node is empty { //Find ancestors whose children are not to the right of the father Node* cur = _node; Node* parent = cur->_parent; while (parent&&cur == parent->_right) { cur = parent; parent = parent->_parent; } _node = parent; //++ becomes the node } return *this; }
After the forward iterator is implemented, we need to implement the iterator type in the implementation of the red-black tree typedef. It should be noted that in order to make the external typedef forward iterator type after iterator，we need to be in public Regional conduct typedef.
Then implement member functions in the red-black tree begin and end:
- begin The function returns the forward iterator of the first node in the inorder sequence, which is the leftmost node.
- end The function returns the forward iterator of the next position of the last node in the inorder sequence. Here, a forward iterator is directly constructed with a null pointer.
```cpp
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node; //node type
public:
typedef __TreeIterator<T, T&, T*> iterator; //forward iterator
iterator begin()
{
//Find the leftmost node
Node* left = _root;
while (left&&left->_left)
{
left = left->_left;
}
//Returns a forward iterator to the leftmost node
return iterator(left);
}
iterator end()
{
//returns a forward iterator constructed from nullptr (not rigorous)
return iterator(nullptr);
}
private:
Node* _root; //The root node of the red-black tree
};
In C++STL, the structure used by the underlying red-black tree to implement the forward iterator.
In fact, the iterators implemented above are flawed, because theoretically we perform – operation on the forward iterator at the end() position, and we should get the forward iterator of the last node, but we implement end( ), it directly returns the forward iterator constructed by nullptr, so the code implemented above cannot complete this operation.
Let's take a look at the implementation logic in the C++SLT library:
When the red-black tree is implemented in the C++STL library, a head node is added at the root node of the red-black tree. The left pointer of the head node points to the leftmost node in the red-black tree, and the right pointer points to the red-black tree. The rightmost node in the black tree, the parent pointer points to the root node of the red-black tree.
Under this structure, when implementing begin(), just use the left child of the head node to directly construct a forward iterator; when implementing rbegin(), directly use the right child of the head node to construct a reverse iterator (Actually, first use the node to construct a forward iterator, and then use the forward iterator to construct a reverse iterator), and when implementing end() and rend(), directly use the head node to construct the forward and A reverse iterator will do. Afterwards, through the control of the logic, it is possible to implement end() to perform the – operation to obtain the forward iterator of the last node.
However, implementing this structure requires changing the logic of many current functions. For example, when inserting a node, if it is inserted to the left of the leftmost node of the red-black tree, or to the right of the rightmost node, it is necessary to update the left and right pointers of the head node. , the actual implementation will not be carried out here.
Implementation of reverse iterator
The reverse iterator of the red-black tree is actually a package of the forward iterator, so the reverse iterator of the red-black tree is an iterator adapter.
There is only one member variable in the reverse iterator, which is the forward iterator encapsulated by the reverse iterator. The member functions of the reverse iterator complete the corresponding functions by calling the corresponding function of the forward iterator.
//reverse iterator --- iterator adapter
template<class Iterator>
struct ReverseIterator
{
typedef ReverseIterator<Iterator> Self; //type of reverse iterator
typedef typename Iterator::reference Ref; //References to node pointers
typedef typename Iterator::pointer Ptr; //node pointer
Iterator _it; //Forward iterator wrapped by reverse iterator
//Constructor
ReverseIterator(Iterator it)
:_it(it) //Constructs a reverse iterator from the given forward iterator
{}
Ref operator*()
{
return *_it; //Returns a reference to the node data by calling operator* on the forward iterator
}
Ptr operator->()
{
return _it.operator->(); //By calling the operator->pointer of the forward iterator to return the node data
}
//prefix ++
Self& operator++()
{
--_it; //Invoking the forward iterator's prefix --
return *this;
}
//Pre--
Self& operator--()
{
++_it; //Call forward ++ on forward iterators
return *this;
}
bool operator!=(const Self& s) const
{
return _it != s._it; //Call the forward iterator's operator!=
}
bool operator==(const Self& s) const
{
return _it == s._it; //Call operator== on the forward iterator
}
};
It should be noted that the reverse iterator only receives one template parameter, which is the type of the forward iterator, that is, the reverse iterator does not know the reference type of the node and the pointer type of the node, so we need to typedef these two types in the forward iterator, so that the reverse iterator can obtain the reference type of the node and the pointer type of the node through the forward iterator.
//forward iterator
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef Ref reference; //References to node pointers
typedef Ptr pointer; //node pointer
};
After the reverse iterator is implemented, we also need to typedef the iterator type in the implementation of the red-black tree, and implement the member functions rbegin and rend in the red-black tree:
-
The rbegin function returns the reverse iterator of the last node in the inorder sequence, that is, the rightmost node.
-
The rend function returns the reverse iterator of the position before the first node in the inorder sequence. Here, a null pointer is directly used to construct a reverse iterator.
template<class K, class T, class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; //node type public: typedef ReverseIterator<iterator> reverse_iterator; //reverse iterator reverse_iterator rbegin() { //Find the rightmost node Node* right = _root; while (right&&right->_right) { right = right->_right; } //Returns a reverse iterator to the rightmost node return reverse_iterator(iterator(right)); } reverse_iterator rend() { //returns a reverse iterator constructed from nullptr (not strict) return reverse_iterator(iterator(nullptr)); } private: Node* _root; //The root node of the red-black tree };
<a name="dUany"></a>
# The analog implementation of set
After completing the above operations, set The simulation implementation of is very simple. The member functions in it all need to call the corresponding interface of the underlying red-black tree, but you need to pay attention to changing the node pointers in the return values of the insertion function and the search function into iterators.
```cpp
template<class K>
class set
{
//functor
struct SetKeyOfT
{
const K& operator()(const K& key) //return Key valueKey
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator; //forward iterator
typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator; //reverse iterator
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.rend();
}
//insert function
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
//delete function
void erase(const K& key)
{
_t.Erase(key);
}
//lookup function
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
Simulation implementation of map
The same is true for the analog implementation of map. Its member functions also call the corresponding interface of the underlying red-black tree. An overloaded function that implements the [] operator is required.
template<class K, class V>
class map
{
//functor
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv) //Returns the key-value Key in the key-value pair
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; //forward iterator
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::reverse_iterator reverse_iterator; //reverse iterator
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.rend();
}
//insert function
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
//[] operator overloading function
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
iterator it = ret.first;
return it->second;
}
//delete function
void erase(const K& key)
{
_t.Erase(key);
}
//lookup function
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
Code after packaging
Although the encapsulation process has been explained, there are still many details in the code change process. The complete encapsulation code is given below.
Red-black tree code
//Enumeration defines the color of the node
enum Colour
{
RED,
BLACK
};
//Red-black tree node definition
template<class T>
struct RBTreeNode
{
//trident chain
RBTreeNode<T>* _left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
//stored data
T _data;
//node color
int _col; //red/black
//Constructor
RBTreeNode(const T& data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{}
};
//Implementation of red-black tree
template<class K, class T, class KeyOfT>
class RBTree
{
typedef RBTreeNode<T> Node; //node type
public:
typedef __TreeIterator<T, T&, T*> iterator; //forward iterator
typedef ReverseIterator<iterator> reverse_iterator; //reverse iterator
reverse_iterator rbegin()
{
//Find the rightmost node
Node* right = _root;
while (right&&right->_right)
{
right = right->_right;
}
//Returns a reverse iterator to the rightmost node
return reverse_iterator(iterator(right));
}
reverse_iterator rend()
{
//returns a reverse iterator constructed from nullptr (not strict)
return reverse_iterator(iterator(nullptr));
}
iterator begin()
{
//Find the leftmost node
Node* left = _root;
while (left&&left->_left)
{
left = left->_left;
}
//Returns a forward iterator to the leftmost node
return iterator(left);
}
iterator end()
{
//returns a forward iterator constructed from nullptr (not rigorous)
return iterator(nullptr);
}
//Constructor
RBTree()
:_root(nullptr)
{}
//copy construction
RBTree(const RBTree<K, T, KeyOfT>& t)
{
_root = _Copy(t._root, nullptr);
}
//Assignment operator overloading (modern notation)
RBTree<K, T, KeyOfT>& operator=(RBTree<K, T, KeyOfT> t)
{
swap(_root, t._root);
return *this; //Support for continuous assignment
}
//destructor
~RBTree()
{
_Destroy(_root);
_root = nullptr;
}
//lookup function
iterator Find(const K& key)
{
KeyOfT kot;
Node* cur = _root;
while (cur)
{
if (key < kot(cur->_data)) //The key value is less than the value of the node
{
cur = cur->_left; //Search in the left subtree of the node
}
else if (key > kot(cur->_data)) //The key value is greater than the value of the node
{
cur = cur->_right; //Search in the right subtree of the node
}
else //target node found
{
return iterator(cur); //return to this node
}
}
return end(); //Find failed
}
//insert function
pair<iterator, bool> Insert(const T& data)
{
if (_root == nullptr) //If the red-black tree is an empty tree, insert the node directly as the root node
{
_root = new Node(data);
_root->_col = BLACK; //The root node must be black
return make_pair(iterator(_root), true); //Inserted successfully
}
//1. According to the insertion method of the binary search tree, find the position to be inserted
KeyOfT kot;
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kot(data) < kot(cur->_data)) //The key value of the node to be inserted is less than the key value of the current node
{
//Go to the left subtree of the node
parent = cur;
cur = cur->_left;
}
else if (kot(data) > kot(cur->_data)) //The key value of the node to be inserted is greater than the key value of the current node
{
//Go to the right subtree of the node
parent = cur;
cur = cur->_right;
}
else //The key value of the node to be inserted is equal to the key value of the current node
{
return make_pair(iterator(cur), false); //insert failed
}
}
//2. Insert the node to be inserted into the tree
cur = new Node(data); //Constructs a node from the given value
Node* newnode = cur; //Record the newly inserted node (for subsequent return)
if (kot(data) < kot(parent->_data)) //The key value of the new node is less than the key value of the parent
{
//Insert to the left of parent
parent->_left = cur;
cur->_parent = parent;
}
else //The key value of the new node is greater than the key value of the parent
{
//Insert to the right of parent
parent->_right = cur;
cur->_parent = parent;
}
//3. If the parent node of the inserted node is red, the red-black tree needs to be adjusted
while (parent&&parent->_col == RED)
{
Node* grandfather = parent->_parent; //parent is red, its parent node must exist
if (parent == grandfather->_left) //parent is grandfather's left child
{
Node* uncle = grandfather->_right; //uncle is the right child of grandfather
if (uncle&&uncle->_col == RED) //Case 1: uncle exists and is red
{
//color adjustment
parent->_col = uncle->_col = BLACK;
grandfather->_col = RED;
//continue to process
cur = grandfather;
parent = cur->_parent;
}
else //Case 2+ Case 3: uncle does not exist + uncle exists and is black
{
if (cur == parent->_left)
{
RotateR(grandfather); //Right monorotation
//color adjustment
grandfather->_col = RED;
parent->_col = BLACK;
}
else //cur == parent->_right
{
RotateLR(grandfather); //Left and right double rotation
//color adjustment
grandfather->_col = RED;
cur->_col = BLACK;
}
break; //After the subtree is rotated, the root of the subtree becomes black, and there is no need to continue to process it
}
}
else //parent is the right child of grandfather
{
Node* uncle = grandfather->_left; //uncle is grandfather's left child
if (uncle&&uncle->_col == RED) //Case 1: uncle exists and is red
{
//color adjustment
uncle->_col = parent->_col = BLACK;
grandfather->_col = RED;
//continue to process
cur = grandfather;
parent = cur->_parent;
}
else //Case 2+ Case 3: uncle does not exist + uncle exists and is black
{
if (cur == parent->_left)
{
RotateRL(grandfather); //right left double rotation
//color adjustment
cur->_col = BLACK;
grandfather->_col = RED;
}
else //cur == parent->_right
{
RotateL(grandfather); //left monorotation
//color adjustment
grandfather->_col = RED;
parent->_col = BLACK;
}
break; //After the subtree is rotated, the root of the subtree becomes black, and there is no need to continue to process it
}
}
}
_root->_col = BLACK; //The color of the root node is black (it may be changed to red by case 1 and needs to be changed back to black)
return make_pair(iterator(newnode), true); //Inserted successfully
}
//delete function
bool Erase(const K& key)
{
KeyOfT kot;
//for traversing a binary tree
Node* parent = nullptr;
Node* cur = _root;
//Used to mark the actual node to be deleted and its parent node
Node* delParentPos = nullptr;
Node* delPos = nullptr;
while (cur)
{
if (key < kot(cur->_data)) //The given key value is less than the key value of the current node
{
//Go to the left subtree of the node
parent = cur;
cur = cur->_left;
}
else if (key > kot(cur->_data)) //The given key value is greater than the key value of the current node
{
//Go to the right subtree of the node
parent = cur;
cur = cur->_right;
}
else //Found the node to be deleted
{
if (cur->_left == nullptr) //The left subtree of the node to be deleted is empty
{
if (cur == _root) //The node to be deleted is the root node
{
_root = _root->_right; //Let the right subtree of the root node be the new root node
if (_root)
{
_root->_parent = nullptr;
_root->_col = BLACK; //root node is black
}
delete cur; //Delete the original root node
return true;
}
else
{
delParentPos = parent; //Mark the parent node of the node that was actually deleted
delPos = cur; //mark the actual deleted node
}
break; //Perform red-black tree adjustments and actual deletion of nodes
}
else if (cur->_right == nullptr) //The right subtree of the node to be deleted is empty
{
if (cur == _root) //The node to be deleted is the root node
{
_root = _root->_left; //Let the left subtree of the root node be the new root node
if (_root)
{
_root->_parent = nullptr;
_root->_col = BLACK; //root node is black
}
delete cur; //Delete the original root node
return true;
}
else
{
delParentPos = parent; //Mark the parent node of the node that was actually deleted
delPos = cur; //mark the actual deleted node
}
break; //Perform red-black tree adjustments and actual deletion of nodes
}
else //The left and right subtrees of the node to be deleted are not empty
{
//delete by substitution
//Find the node with the smallest key value in the right subtree of the node to be deleted as the actual deleted node
Node* minParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
minParent = minRight;
minRight = minRight->_left;
}
cur->_data = minRight->_data; //Change the _data of the node to be deleted to the _data of minRight
delParentPos = minParent; //Mark the parent node of the node that was actually deleted
delPos = minRight; //mark the actual deleted node
break; //Perform red-black tree adjustments and actual deletion of nodes
}
}
}
if (delPos == nullptr) //delPos has not been modified, indicating that no node to be deleted was found
{
return false;
}
//Record the node to be deleted and its parent node (for subsequent actual deletion)
Node* del = delPos;
Node* delP = delParentPos;
//tuned red-black tree
if (delPos->_col == BLACK) //Deleted is the black node
{
if (delPos->_left) //The node to be deleted has a red left child (it cannot be black)
{
delPos->_left->_col = BLACK; //Just turn the red left child black
}
else if (delPos->_right) //The node to be deleted has a red right child (it cannot be black)
{
delPos->_right->_col = BLACK; //Just turn the red right child black
}
else //The left and right sides of the node to be deleted are empty
{
while (delPos != _root) //may be adjusted all the way to the root node
{
if (delPos == delParentPos->_left) //The node to be deleted is the left child of its parent node
{
Node* brother = delParentPos->_right; //A sibling node is the right child of its parent node
//Case 1: brother is red
if (brother->_col == RED)
{
delParentPos->_col = RED;
brother->_col = BLACK;
RotateL(delParentPos);
//need to continue processing
brother = delParentPos->_right; //Update brother (otherwise there will be an error in executing other codes in this loop)
}
//Case 2: brother is black, and its left and right children are all black nodes or empty
if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))
&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK)))
{
brother->_col = RED;
if (delParentPos->_col == RED)
{
delParentPos->_col = BLACK;
break;
}
//need to continue processing
delPos = delParentPos;
delParentPos = delPos->_parent;
}
else
{
//Case 3: brother is black, and its left child is a red node, and its right child is a black node or empty
if ((brother->_right == nullptr) || (brother->_right->_col == BLACK))
{
brother->_left->_col = BLACK;
brother->_col = RED;
RotateR(brother);
//need to continue processing
brother = delParentPos->_right; //Update brother (otherwise an error will occur when executing the code in case 4 below)
}
//Situation 4: brother is black, and its right child is a red node
brother->_col = delParentPos->_col;
delParentPos->_col = BLACK;
brother->_right->_col = BLACK;
RotateL(delParentPos);
break; //Situation 4: After the implementation is completed, the adjustment must be completed
}
}
else //delPos == delParentPos->_right //The node to be deleted is the left child of its parent node
{
Node* brother = delParentPos->_left; //A sibling node is the left child of its parent node
//Case 1: brother is red
if (brother->_col == RED) //brother is red
{
delParentPos->_col = RED;
brother->_col = BLACK;
RotateR(delParentPos);
//need to continue processing
brother = delParentPos->_left; //Update brother (otherwise there will be an error in executing other codes in this loop)
}
//Case 2: brother is black, and its left and right children are all black nodes or empty
if (((brother->_left == nullptr) || (brother->_left->_col == BLACK))
&& ((brother->_right == nullptr) || (brother->_right->_col == BLACK)))
{
brother->_col = RED;
if (delParentPos->_col == RED)
{
delParentPos->_col = BLACK;
break;
}
//need to continue processing
delPos = delParentPos;
delParentPos = delPos->_parent;
}
else
{
//Case 3: brother is black, and its right child is a red node, and its left child is a black node or empty
if ((brother->_left == nullptr) || (brother->_left->_col == BLACK))
{
brother->_right->_col = BLACK;
brother->_col = RED;
RotateL(brother);
//need to continue processing
brother = delParentPos->_left; //Update brother (otherwise an error will occur when executing the code in case 4 below)
}
//Situation 4: brother is black, and its left child is a red node
brother->_col = delParentPos->_col;
delParentPos->_col = BLACK;
brother->_left->_col = BLACK;
RotateR(delParentPos);
break; //Situation 4: After the implementation is completed, the adjustment must be completed
}
}
}
}
}
//do the actual deletion
if (del->_left == nullptr) //The left subtree of the actually deleted node is empty
{
if (del == delP->_left) //The actual deleted node is the left child of its parent node
{
delP->_left = del->_right;
if (del->_right)
del->_right->_parent = delP;
}
else //The actual deleted node is the right child of its parent node
{
delP->_right = del->_right;
if (del->_right)
del->_right->_parent = delP;
}
}
else //The right subtree of the actually deleted node is empty
{
if (del == delP->_left) //The actual deleted node is the left child of its parent node
{
delP->_left = del->_left;
if (del->_left)
del->_left->_parent = delP;
}
else //The actual deleted node is the right child of its parent node
{
delP->_right = del->_left;
if (del->_left)
del->_left->_parent = delP;
}
}
delete del; //actually delete the node
return true;
}
private:
//copy tree
Node* _Copy(Node* root, Node* parent)
{
if (root == nullptr)
{
return nullptr;
}
Node* copyNode = new Node(root->_data);
copyNode->_parent = parent;
copyNode->_left = _Copy(root->_left, copyNode);
copyNode->_right = _Copy(root->_right, copyNode);
return copyNode;
}
//destructor subfunction
void _Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
//left monorotation
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
//Establish a connection between subRL and parent
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
//Establish a connection between parent and subR
subR->_left = parent;
parent->_parent = subR;
//Establish a connection between subR and parentParent
if (parentParent == nullptr)
{
_root = subR;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
}
//Right monorotation
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
//Establish a connection between subLR and parent
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
//Establish a connection between parent and subL
subL->_right = parent;
parent->_parent = subL;
//Establish a connection between subL and parentParent
if (parentParent == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
}
//Left and right double rotation
void RotateLR(Node* parent)
{
RotateL(parent->_left);
RotateR(parent);
}
//right left double rotation
void RotateRL(Node* parent)
{
RotateR(parent->_right);
RotateL(parent);
}
Node* _root; //The root node of the red-black tree
};
Forward iterator code
//forward iterator
template<class T, class Ref, class Ptr>
struct __TreeIterator
{
typedef Ref reference; //References to node pointers
typedef Ptr pointer; //node pointer
typedef RBTreeNode<T> Node; //node type
typedef __TreeIterator<T, Ref, Ptr> Self; //the type of the forward iterator
Node* _node; //pointer to the node encapsulated by the forward iterator
//Constructor
__TreeIterator(Node* node)
:_node(node) //Constructs a forward iterator based on the given node pointer
{}
Ref operator*()
{
return _node->_data; //Returns a reference to the node data
}
Ptr operator->()
{
return &_node->_data; //Returns a pointer to the node data
}
//Determine whether two forward iterators are different
bool operator!=(const Self& s) const
{
return _node != s._node; //Determine whether the nodes encapsulated by two forward iterators are the same
}
//Determine whether two forward iterators are the same
bool operator==(const Self& s) const
{
return _node == s._node; //Determine whether the nodes encapsulated by two forward iterators are the same
}
//prefix ++
Self operator++()
{
if (_node->_right) //The right subtree of the node is not empty
{
//Find the leftmost node in the right subtree of the node
Node* left = _node->_right;
while (left->_left)
{
left = left->_left;
}
_node = left; //++ becomes the node
}
else //The right subtree of the node is empty
{
//Find ancestors whose children are not to the right of the father
Node* cur = _node;
Node* parent = cur->_parent;
while (parent&&cur == parent->_right)
{
cur = parent;
parent = parent->_parent;
}
_node = parent; //++ becomes the node
}
return *this;
}
//Pre--
Self operator--()
{
if (_node->_left) //The left subtree of the node is not empty
{
//Find the rightmost node in the left subtree of the node
Node* right = _node->_left;
while (right->_right)
{
right = right->_right;
}
_node = right; //-- then become the node
}
else //The left subtree of the node is empty
{
//Find ancestors whose children are not to the father's left
Node* cur = _node;
Node* parent = cur->_parent;
while (parent&&cur == parent->_left)
{
cur = parent;
parent = parent->_parent;
}
_node = parent; //-- then become the node
}
return *this;
}
};
code for reverse iterator
//reverse iterator --- iterator adapter
template<class Iterator>
struct ReverseIterator
{
typedef ReverseIterator<Iterator> Self; //type of reverse iterator
typedef typename Iterator::reference Ref; //References to node pointers
typedef typename Iterator::pointer Ptr; //node pointer
Iterator _it; //Forward iterator wrapped by reverse iterator
//Constructor
ReverseIterator(Iterator it)
:_it(it) //Constructs a reverse iterator from the given forward iterator
{}
Ref operator*()
{
return *_it; //Returns a reference to the node data by calling operator* on the forward iterator
}
Ptr operator->()
{
return _it.operator->(); //By calling the operator->pointer of the forward iterator to return the node data
}
//prefix ++
Self& operator++()
{
--_it; //Invoking the forward iterator's prefix --
return *this;
}
//Pre--
Self& operator--()
{
++_it; //Call forward ++ on forward iterators
return *this;
}
bool operator!=(const Self& s) const
{
return _it != s._it; //Call the forward iterator's operator!=
}
bool operator==(const Self& s) const
{
return _it == s._it; //Call operator== on the forward iterator
}
};
set code
namespace cl //prevent naming conflicts
{
template<class K>
class set
{
//functor
struct SetKeyOfT
{
const K& operator()(const K& key) //return Key valueKey
{
return key;
}
};
public:
typedef typename RBTree<K, K, SetKeyOfT>::iterator iterator; //forward iterator
typedef typename RBTree<K, K, SetKeyOfT>::reverse_iterator reverse_iterator; //reverse iterator
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.rend();
}
//insert function
pair<iterator, bool> insert(const K& key)
{
return _t.Insert(key);
}
//delete function
void erase(const K& key)
{
_t.Erase(key);
}
//lookup function
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, K, SetKeyOfT> _t;
};
}
map code
namespace cl //prevent naming conflicts
{
template<class K, class V>
class map
{
//functor
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv) //Returns the key-value Key in the key-value pair
{
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::iterator iterator; //forward iterator
typedef typename RBTree<K, pair<K, V>, MapKeyOfT>::reverse_iterator reverse_iterator; //reverse iterator
iterator begin()
{
return _t.begin();
}
iterator end()
{
return _t.end();
}
reverse_iterator rbegin()
{
return _t.rbegin();
}
reverse_iterator rend()
{
return _t.rend();
}
//insert function
pair<iterator, bool> insert(const pair<const K, V>& kv)
{
return _t.Insert(kv);
}
//[] operator overloading function
V& operator[](const K& key)
{
pair<iterator, bool> ret = insert(make_pair(key, V()));
iterator it = ret.first;
return it->second;
}
//delete function
void erase(const K& key)
{
_t.Erase(key);
}
//lookup function
iterator find(const K& key)
{
return _t.Find(key);
}
private:
RBTree<K, pair<K, V>, MapKeyOfT> _t;
};
}