在 C++ 中，一个红黑树的节点类型是看成是一个关于任意全序类型 KeyT 和任意类型 ValT 的范型，为了方便我们也可以放松对 KeyT 的约束，不再要求 TotalOrdered KeyT, 仅仅要求 KeyT 是一个 typename KeyT, 这样把可能的报错（不支持 <, > , == 操作）推迟到模板实例化第二阶段的时候：
/** 表颜色 */
enum class LinkType {
RED, BLACK
};
/** 节点对象基类 */
template <typename KeyT, typename ValT>
struct Node {
Node(std::shared_ptr<KeyT> key, std::shared_ptr<ValT> value)
: key(key), value(value), left(nullptr), right(nullptr), size(1) { }
std::shared_ptr<KeyT> key;
std::shared_ptr<ValT> value;
std::shared_ptr<Node<KeyT, ValT>> left;
std::shared_ptr<Node<KeyT, ValT>> right;
size_t size;
};
/** 红黑树节点 */
template <typename KeyT, typename ValT>
struct RedBlackNode : public Node<KeyT, ValT> {
RedBlackNode(const std::shared_ptr<KeyT>& k, const std::shared_ptr<ValT>& v)
: Node<KeyT, ValT>(k, v), color(LinkType::BLACK), left(nullptr), right(nullptr) { }
RedBlackNode(const std::shared_ptr<KeyT>& k, const std::shared_ptr<ValT>& v, LinkType color)
: Node<KeyT, ValT>(k, v), color(color), left(nullptr), right(nullptr) { }
LinkType color;
std::shared_ptr<RedBlackNode<KeyT, ValT>> left;
std::shared_ptr<RedBlackNode<KeyT, ValT>> right;
};
/** 红黑树节点指针 */
template <typename KeyT, typename ValT>
using RedBlackNodePtr = std::shared_ptr<RedBlackNode<KeyT, ValT>>;
很显然，一个红黑树节点实例很多时候往往并不需要独占存储在它身上的 key 实例或者 value 实例，因此用 std::shared_ptr<KeyT> 和 std::shared_ptr<ValT> 来分别建模节点对 key 实例和 value 实例的所有权就足够了。这个时候 insert 操作仅仅是把 key 和 value 添加到索引（建立索引），供 search 操作时快速得到结果，而 delete 操作仅仅是将数据从索引中移除，并没有真正地移除数据本身（因为 std::shared_ptr 是对于被指对象的所有权是非独占的）。
不过也有用 std::unique_ptr 的时候，这个时候红黑树的实现还兼具存储管理的功能，这个时候，当我们删除 一个 key, 也相当于真实地永远地删除了这个 key 还有它对应的 value, 并且把这些对象占有的内存都返还给操作系统。
同样地，为了操作简便，并且，显然红黑树中几乎不会出现循环引用的情形，所以用 std::shared_ptr<RedBlackNode<KeyT, ValT>> 来作为 RedBlackNodePtr 的定义是合适的。
数据结构实际上是一个定义好的数据类型，外加工作在这个数据类型的实例上的一系列函数。在 C++ 语言中，我们可以把这一系列配合紧密的函数都放到一个 class 中，使得软件设计上的模块化水平更高一些。
/** 红黑树操作句柄 */
template <typename KeyT, typename ValT>
class RedBlackTreeHandle {
using RedBlackNode = RedBlackNode<KeyT, ValT>;
using NodePtr = RedBlackNodePtr<KeyT, ValT>;
using KeyPtr = std::shared_ptr<KeyT>;
using ValuePtr = std::shared_ptr<ValT>;
public:
/** 红黑树的操作函数都写在这儿 */
private:
/** 实现 public 函数要用到的哪些辅助函数都写在这儿 */
};
因为在 class RedBlackTreeHandle 中我们定义了那些 using RedBlackNode, using NodePtr 之类的，这可以省去敲不少字。
本文主要来实现左旋与右旋函数，一步一步地讲解，先放上左旋和右旋函数的完整代码：
/** 从左到右旋转，右旋 */
static NodePtr rotateRight(NodePtr root) {
assert((root->left));
NodePtr result { root->left };
root->left = result->right;
result->right = root;
result->color = root->color;
root->color = LinkType::RED;
result->size = root->size;
root->size = 1 + RedBlackTreeHandle::getSize(root->left) + RedBlackTreeHandle::getSize(root->right);
return result;
}
/** 从右到左旋转，左旋 */
static NodePtr rotateLeft(NodePtr root) {
assert((root->right));
NodePtr result { root->right };
root->right = result->left;
result->left = root;
result->color = root->color;
root->color = LinkType::RED;
result->size = root->size;
root->size = 1 + RedBlackTreeHandle::getSize(root->left) + RedBlackTreeHandle::getSize(root->right);
return result;
}
我们以右旋为例，右旋是说当前我们拿到的是一个红边朝左的节点，我们想弄到一个红边朝右的节点（指针），就这么简单。
具体来说，右旋操作可以被实现为一个函数，你传给它一个朝左的红黑树节点指针，它返给你一个朝右的红黑树节点指针，我们后面在实现红黑树的 insert 操作会发现，这种方式（相比原地修改的方式）用起来更加方便一些。
假设 leftHandle 是我们拿到的可以用于右旋操作的红黑树节点指针，假设 leftHandle 的左边是红边。a, b, c 是什么无所谓。e 的父节点到它自身的边的颜色是什么也无所谓。
具体的右旋操作过程如下图所示：
进入函数后，初始格局如第一幅子图所示。
在函数作用域中，执行：
NodePtr rightHandle = leftHandle->leftPtr;
然后，结果如第二幅图所示。
普通二叉树节点的类型再加上一个 color 属性即可作为红黑树的节点类型来使用，这个 color 属性的含义你可以理解为是其父节点到它自身的边的颜色，因此此时 rightHandle 还有 e -> d 皆为红边。
每一幅图是其右边的代码执行完毕后内存的布局（谁指向谁）的图形化表示。
在最后我们还要通过
rightHandle->color = leftHandle->color;
这一句来使得该函数返回的那个节点指针指向的节点的 color 属性的值与原来 leftHandle 指向的一致，按照我们给 color 属性赋予的含义，这也就是说「一次右旋操作不会改变该节点父节点到其自身的边的颜色。」
最后一句
leftHandle->color = ::LinkColor::RED;
使我们最终得到一个朝右的红黑树节点，从而完成了右旋的主要过程。
不难发现，红黑树的这种实现下的右旋操作与左旋操作：1）都是可逆的；2）且是互逆的。
我们无需去记忆这个过程，我们只需理解 leftHandle 还有 rightHandle 还有它们各自的左右边的指向即可，即可结合图示就可知道如何写出红黑树的左旋操作。