Red-black tree package set and map (insert part)

Article directory

• foreword
• 1. General idea of design
• 2. Transform and package red-black tree
• • 1. Insert a node
  • 2. Implementation of iterators
• 3. Encapsulation of map and set
• • 1. Code implementation
  • 2. Simple test

Foreword

We have implemented the insertion part of the red-black tree before. This article mainly introduces the packaging of the previously implemented red-black tree into map and set. We encapsulate the container from the perspective of learning, and we don’t have to realize all the functions of the container in the library. Our main purpose is to learn the code design skills and template reuse ideas in the library.

1. General idea of design

Before we implement it, we still go to see how it is implemented in the library as before. Here is a brief introduction to the idea of container implementation in the library. The general idea of the design in the library is: Design a red-black tree as a class template. Our map and set directly reuse a red-black tree, and encapsulate the interface of the red-black tree to form its own interface. This is equivalent to reusing a code for both map and set. We only need to maintain the code of the red-black tree to realize the relevant container.

Let’s think about it, the biggest difference between map and set is the storage nodes. set is only a single key value stored, but a key-val key-value pair is stored. So we know that there must be a template parameter to control what value the red-black tree node stores. At the same time, because we need to know the type of the key because of the find and erase interfaces, we also need to have a separate template parameter to identify the key.

At the same time, the stored node value is uncertain, we need to define a functor to control the comparison logic when comparing node key values, and what value we use for comparison. That is to say, the third keyOft is used to control the comparison logic. When encapsulating in map and set, just pass in the corresponding functor.

After having this idea, we changed the previous red-black tree into a class template.

2. Transform and package red-black tree

We take the previously written red and black and transform it. We don’t need to change the rotation and color adjustment logic. The only thing we need to change is the insertion logic. Let’s take the general framework of the red-black tree first.

Node construction

enum Color
{<!-- -->
RED,
BLACK,
};

template<class T>
struct RBTreeNode
{<!-- -->
RBTreeNode<T>*_left;
RBTreeNode<T>* _right;
RBTreeNode<T>* _parent;
T_data;
Colour_col;

RBTreeNode(const T & data)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _data(data)
, _col(RED)
{<!-- -->}
};

template<class K, class T, class KeyOft>
class RBTree
{<!-- -->
public:
typedef RBTreeNode<T> Node;
Node* Find(const T & amp; key)
{<!-- -->
Node* cur = _root;
while (cur)
{<!-- -->
if (cur->_kv.first < key)
{<!-- -->
cur = cur->_right;
}
else if (cur->_kv.first > key)
{<!-- -->
cur = cur->_left;
}
else
{<!-- -->
return cur;
}
}
return nullptr;
}

void InOrder()
{<!-- -->
_InOrder(_root);
}

bool IsBalance()
{<!-- -->
if (_root & & _root->_col == RED)
{<!-- -->
cout << "The color of the root node is red" << endl;
return false;
}

int benchmark = 0;
Node* cur = _root;
while (cur)
{<!-- -->
if (cur->_col == BLACK)
{<!-- -->
+ + benchmark;
}
cur = cur->_left;
}


return _Check(_root, 0, benchmark);
}

int Height()
{<!-- -->
return _Height(_root);
}

private:
void _Destroy(Node* root)
{<!-- -->
if (root == nullptr)
{<!-- -->
return;
}

_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}

int _Height(Node* root)
{<!-- -->
if (root == NULL)
return 0;

int leftH = _Height(root->_left);
int rightH = _Height(root->_right);

return leftH > rightH ? leftH + 1 : rightH + 1;
}

bool _Check(Node* root, int blackNum, int benchmark)
{<!-- -->
if (root == nullptr)
{<!-- -->
if (benchmark != blackNum)
{<!-- -->
cout << "The number of black nodes in a certain path is not equal" << endl;
return false;
}

return true;
}

if (root->_col == BLACK)
{<!-- -->
+ + blackNum;
}

if (root->_col == RED
& amp; & amp; root->_parent
& amp; & amp; root->_parent->_col == RED)
{<!-- -->
cout << "There are continuous red nodes" << endl;
return false;
}

return _Check(root->_left, blackNum, benchmark)
& amp; & amp; _Check(root->_right, blackNum, benchmark);
}

void _InOrder(Node* root)
{<!-- -->
if (root == nullptr)
{<!-- -->
return;
}

_InOrder(root->_left);
cout << root->_kv. first << " ";
_InOrder(root->_right);
}

void RotateL(Node* parent)
{<!-- -->
Node* subR = parent->_right;
Node* subRL = subR->_left;

parent->_right = subRL;
if (subRL)
{<!-- -->
subRL->_parent = parent;
}

Node* ppnode = parent->_parent;

subR->_left = parent;
parent->_parent = subR;

if (ppnode == nullptr)
{<!-- -->
_root = subR;
_root->_parent = nullptr;
}
else
{<!-- -->
if (ppnode->_left == parent)
{<!-- -->
ppnode->_left = subR;
}
else
{<!-- -->
ppnode->_right = subR;
}

subR->_parent = ppnode;
}
}

void RotateR(Node* parent)
{<!-- -->
Node* subL = parent->_left;
Node* subLR = subL->_right;

parent->_left = subLR;
if (subLR)
{<!-- -->
subLR->_parent = parent;
}
Node* ppnode = parent->_parent;

subL->_right = parent;
parent->_parent = subL;

if (parent == _root)
{<!-- -->
_root = subL;
_root->_parent = nullptr;
}
else
{<!-- -->
if (ppnode->_left == parent)
{<!-- -->
ppnode->_left = subL;
}
else
{<!-- -->
ppnode->_right = subL;
}
subL->_parent = ppnode;
}
}

private:
Node* _root = nullptr;
};

The above code has not been changed except for the addition of 3 template parameters, so there is a general framework. We then implement the insertion logic and iterators.

1. Insert node

What value is stored in the node here is what value is inserted. The value stored by the node is determined by this second template parameter. The parameters of this insert section function are determined, const T & amp;data. Let’s take a look at the implementation in the library for the return value of this insertion node.

The return value here is a pair, which stores the iterator and insertion status of the node at the corresponding position. The bool value indicates whether the insertion is successful. If there is already an equal key, the iterator returned is the iterator pointing to this key. If the insertion is successful, the iterator returned is pointing to the newly inserted node.

pair< iterator, bool> Insert(const T & amp; data)
{<!-- -->
KeyOft kot;
if (_root == nullptr)
{<!-- -->
_root = new Node(data);
_root->_col = BLACK;
return make_pair(iterator(_root), true);
}

Node* parent = nullptr;
Node* cur = _root;
while (cur)
{<!-- -->
if (kot(cur->_data) < kot(data))
{<!-- -->
parent = cur;
cur = cur->_right;
}
else if (kot(cur->_data) > kot(data))
{<!-- -->
parent = cur;
cur = cur->_left;
}
else
{<!-- -->
return make_pair(iterator(cur), false);
}
}

cur = new Node(data);
Node* newnode = cur;
if (kot(parent->_data) > kot(data))
{<!-- -->
parent->_left = cur;
}
else
{<!-- -->
parent->_right = cur;
}
cur->_parent = parent;

while (parent & amp; & amp; parent->_col == RED)
{<!-- -->
Node* grandfather = parent->_parent;
if (grandfather->_left == parent)
{<!-- -->
Node* uncle = grandfather->_right;
if (uncle & amp; & amp; uncle->_col == RED)
{<!-- -->
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;
cur = grandfather;
parent = cur->_parent;
}
else
{<!-- -->

if (cur == parent->_left)
{<!-- -->
RotateR(grandfather);
parent->_col = BLACK;
grandfather->_col = RED;
}
else
{<!-- -->
RotateL(parent);
RotateR(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}

break;
}
}
else // (grandfather->_right == parent)
{<!-- -->

Node* uncle = grandfather->_left;
// Situation 1: u exists and is red, change color, and continue to process upwards
if (uncle & amp; & amp; uncle->_col == RED)
{<!-- -->
parent->_col = BLACK;
uncle->_col = BLACK;
grandfather->_col = RED;

// Continue to adjust upwards
cur = grandfather;
parent = cur->_parent;
}
else
{<!-- -->

if (cur == parent->_right)
{<!-- -->
RotateL(grandfather);
grandfather->_col = RED;
parent->_col = BLACK;
}
else
{<!-- -->

RotateR(parent);
RotateL(grandfather);
cur->_col = BLACK;
grandfather->_col = RED;
}

break;
}
}
}

_root->_col = BLACK;
return make_pair(iterator(newnode), true);
}

The only difference is to save this newnode in advance, because this node may be adjusted, and after saving, construct an anonymous object iterator through this node, insert it into the pair and return it. The iterator is not implemented here, we write it like this first, and then implement the iterator. The bool value returned here is to know the situation of inserting the node more clearly.

What needs to be noticed here is the third template parameter. The third template parameter is used to control the comparison logic. In fact, it is to overload the operator () and use the corresponding object to Controls this comparison logic. Therefore, where we compare, we use the third parameter to control it.

2. Implementation of iterator

The implementation of the iterator is combined with the iterator of the linked list that we have implemented before, and it is also solved by implementing the iterator class template. Both our const iterators and ordinary iterators can reuse this set of templates. Combined with the previous experience, we still use node pointers to simulate the behavior of native pointers. We need 3 template parameters, one parameter is used to determine the type of value stored in the node, and the other parameter is to simulate the operation of native pointer -> , as the return value of the overloaded ->, there is another parameter used to simulate the & amp; raw pointer operation, as the return value of the operation & amp;. Because we want the const iterator to also reuse this code, we use a template to implement it.

template<class T,class Ref,class Ptr>
struct _RBTreeIterator
{<!-- -->
typedef RBTreeNode<T> Node;
typedef _RBTreeIterator<T, Ref, Ptr> Self;
Node* _node;
_RBTreeIterator(Node* node)
:_node(node)
{<!-- -->}
Ref operator*()
{<!-- -->
return _node->_data;
}
Ptr operator->()
{<!-- -->
return &_node->_data;
}
bool operator!=(const Self & s)
{<!-- -->
return _node != s._node;
}
Self & operator ++ ()
{<!-- -->
if (_node->_right)
{<!-- -->
Node* subRight = _node->_right;
// the leftmost node in the right subtree
while (subRight->_left)
{<!-- -->
subRight=subRight->_left;
}
_node = subRight;
}
else
{<!-- -->
Node* cur = _node;
Node* parent = _node->_parent;
while (parent & amp; & amp; parent->_right == cur)
{<!-- -->
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}
Self & operator--()
{<!-- -->
if (_node->_left)
{<!-- -->
Node* subLeft = _node->_left;
// the rightmost node in the left subtree
while (subLeft->_right)
{<!-- -->
subLeft = subLeft->_right;
}
_node = subLeft;
}
else
{<!-- -->
Node* cur = _node;
Node* parent = _node->_parent;
while (parent & amp; & amp; parent->_left = cur)
{<!-- -->
cur = parent;
parent = parent->_parent;
}
_node = parent;
}
return *this;
}


};

There is nothing to say about -> and * and & amp;, The focus is on the operation of the pre-++ and pre--. Regarding this ++ and –, we still need the above picture Let’s analyze it.

The ++ operation here needs to be viewed in conjunction with the diagram, and the code is very clear after understanding the diagram. This + +it still determines the moving direction of the node pointer according to the characteristics of the binary search tree.

The – operation and ++ operation are actually symmetrical. For this node movement, we can analyze the best analysis first, and then move the pointer in combination with the graph. For example, the node pointed to by it has a left subtree, which is the best situation to analyze.

After the iterator class is implemented, we declare and rename the iterator type in the red-black tree template class.

iterator begin()
{<!-- -->
Node* cur = _root;
while (cur & amp; & amp; cur->_left)
{<!-- -->
cur = cur->_left;
}

return iterator(cur);
}

iterator end()
{<!-- -->
return iterator(nullptr);
}
const_iterator begin() const
{<!-- -->
Node* cur = _root;
while (cur & amp; & amp; cur->_left)
{<!-- -->
cur = cur->_left;
}
return const_iterator(cur);
}

const_iterator end() const
{<!-- -->
return const_iterator(nullptr);
}
\t

Then we implement the corresponding iterator interface. This begin points to the smallest element in the red-black tree, that is, the leftmost node in the left subtree of the red-black tree. After finding this node, return the iterator corresponding to its construction. For this end interface, we just set it to empty, and construct the corresponding iterator through a null pointer. In this case, we have implemented the class template of the red-black tree, and the map and set can be simply packaged and reused directly.

3. Encapsulation of map and set

1. Code implementation

The encapsulation of map and set here is actually to reuse the class template of red-black tree, and let this class template instantiate the corresponding container

template<class K,class V>
class map
{<!-- -->
\t
public:
struct MapKeyOft
{<!-- -->
const K & amp; operator () (const pair<K, V> & amp; kv)
{<!-- -->
return kv.first;
}
};
public:
typedef typename RBTree<K, pair<const K, V>, MapKeyOft>::iterator iterator;
iterator begin()
{<!-- -->
return _t.begin();
}

iterator end()
{<!-- -->
return _t. end();
}

V & amp; operator[](const K & amp; key)
{<!-- -->
pair<iterator, bool> ret = _t. Insert(make_pair(key, V()));
return ret.first->second;
}

pair<iterator, bool> insert(const pair<const K, V> & kv)
{<!-- -->
return _t. Insert(kv);
}
\t
private:
RBTree<K, pair<const K, V>, MapKeyOft> _t;

};

For map, you can directly reuse the interface of the red-black tree. We define an inner class to overload () and pass this class into the red-black tree as the third template parameter of the instantiation. We add a typename to modify the iterator when renaming it, telling the compiler that this is a type rather than a variable in the class. Here, the map focuses on implementing this [ ] overload, which is implemented by calling the insert function, so that the corresponding val value can be searched, new key-value pairs can be inserted, and the corresponding val value can also be modified. , is simply wonderful.

template<class K>
class set
{<!-- -->

public:
struct SetKeyOft
{<!-- -->
const K & amp; operator()(const K & amp; key)
{<!-- -->
return key;
}
};

public:
  typedef typename RBTree<K, K, SetKeyOft>::iterator iterator;
  iterator begin()
  {<!-- -->
return _t.begin();
  }

  iterator end()
  {<!-- -->
return _t. end();
  }

  pair<iterator, bool> insert(const K & amp; key)
  {<!-- -->
return _t. Insert(key);
  }
private:
RBTree<K, K, SetKeyOft> _t;
};

The same is true for Set, just reuse the interface of the red-black tree. Here, an internal class is also implemented as the third parameter of the instantiation of the red-black tree to control the comparison logic. Here, map, set and internal classes are used to control who is compared with whom in the nodes in the red-black tree. For set, there is only key, which must be compared with key, but map is a key-value pair, which is used to control the red-black tree. The pair nodes in the black tree are compared by key. If we want to implement comparison logic, we can also add a template parameter to receive the comparison functor.

2. Simple test

#include<iostream>
#include "Map.h"
#include "Set.h"
using namespace std;
void test_Set1()
{<!-- -->
int a[] = {<!-- --> 11, 1, 7, 10, 14, 11, 22, 14, 15,89 };
Set<int>s;
for (auto e : a)
{<!-- -->
s. insert(e);
}

Set<int>::iterator it = s.begin();
while (it != s.end())
{<!-- -->
cout << *it << " ";
+ + it;
}
cout << endl;
for (auto e : s)
{<!-- -->
cout << e << " ";
}
cout << endl;
}
void test_Map1()
{<!-- -->
Map<string, string> dict;
dict.insert(make_pair("sort", "sort"));
dict.insert(make_pair("string","string"));
dict.insert(make_pair("count", "count"));
dict.insert(make_pair("left", "left"));

Map<string, string>::iterator it = dict.begin();
while (it != dict. end())
{<!-- -->
cout << it->first << ":" << it->second << endl;
+ + it;
}
\t
cout << endl;

for (auto & kv : dict)
{<!-- -->
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}

void test_Map2()
{<!-- -->
string arr[] = {<!-- --> "apple", "apple", "pear", "pear", "banana", "banana", "banana", "cantaloupe", "strawberry", " pitaya" };
Map<string, int> countMap;
for (auto & e : arr)
{<!-- -->
countMap[e] + + ;
}

for (auto & kv : countMap)
{<!-- -->
cout << kv.first << ":" << kv.second << endl;
}
}
int main()
{<!-- -->
test_Map1();
test_Map2();
test_Set1();
}

From the print results, the map and set we encapsulate basically implement the function of inserting nodes, and the iterator is also implemented correctly. The above is a simple encapsulation of map and set. Generally speaking, it means that the template is covered by a template. The innermost part is the shell of the red-black tree, through which different containers are instantiated. The template reuse skills here are very worth learning, such as the determination of red-black tree template parameters and related meanings. Why it is designed in this way is worth pondering carefully.

If you have any questions about the above content, please correct me!