C++11封装Linux内核版红黑树

发表于 分类于

红黑树是一种非常重要的数据结构，典型的用途是实现关联数组，STL中Map和Set的底层数据结构就是红黑树。

红黑树理解起来不算难，但写出正确且高效的实现却不容易。Linux内核中有份C语言版本的红黑树，我将其做了C++封装，并基于此实现了Map作为用法演示。

比较重要的定义如下。

RBTreeNode: 红黑树节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template<typename ValueType>
struct RBTreeNode {
    using Value_t = ValueType;

    enum Color{
        RED = 0,
        BLACK,
    };

    RBTreeNode* m_parent = nullptr;
    RBTreeNode* m_right = nullptr;
    RBTreeNode* m_left = nullptr;
    Color m_color = RED;

    Value_t m_value;

    ...

RBTree: 红黑树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template<typename NodeType
, typename CompareType>
class RBTree {
    DISALLOW_COPY_AND_ASSIGN(RBTree)

    using Node_t = NodeType;
    using Compare_t = CompareType;
    using Value_t = typename Node_t::Value_t;

    ...

    Node_t* m_root;
    int m_size;
    Compare_t m_compare;

    ...

Map：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template<typename KeyType
, typename ValueType
, typename CompareType
, typename AllocatorFamily = HeapAllocator<>
>
class Map {
    DISALLOW_COPY_AND_ASSIGN(Map)

    using Key_t = KeyType;
    using Value_t = ValueType;
    using Compare_t = CompareType;
    using Data_t = Pair<Key_t, Value_t>;
    using DataCompare_t = PairCompare<Data_t, Compare_t>;
    using Node_t = RBTreeNode<Data_t>;
    using Tree_t = RBTree<Node_t, DataCompare_t>;
    using Allocator_t = typename AllocatorFamily::template Rebind<sizeof(Node_t)>;

    ...

完整代码放在了Github上。