笔记大全

C++红黑树应用之set和map怎么使用

更新时间：2023-11-07

红黑树简介

红黑树是一种自平衡的二叉查找树，它在插入和删除节点时通过节点的颜色变换和树的旋转操作来保持树的平衡。红黑树的平衡性和查找操作的高效性使得它在实际应用中得到广泛使用，例如在C++标准库中的set和map容器中就使用了红黑树来实现。

set的使用

在C++中，set是一种有序的关联容器，它存储唯一的元素，并且按照元素的大小进行排序。set底层使用红黑树来实现，所以插入和查找操作的平均时间复杂度都是O(logN)。

下面是一个使用set的例子：

#include 
#include 

int main() {
    std::set mySet;

    mySet.insert(5);
    mySet.insert(3);
    mySet.insert(1);
    mySet.insert(4);
    mySet.insert(2);

    for (const auto& element : mySet) {
        std::cout << element << " ";
    }
    std::cout << std::endl;

    return 0;
}

运行结果为：1 2 3 4 5，说明set会自动对元素进行排序。

map的使用

在C++中，map也是一种关联容器，它存储键值对，并且按照键的大小进行排序。map底层同样使用红黑树来实现。

下面是一个使用map的例子：

#include 
#include 

int main() {
    std::map myMap;

    myMap["apple"] = 3;
    myMap["banana"] = 2;
    myMap["orange"] = 4;

    std::cout << "The value of apple is: " << myMap["apple"] << std::endl;
    std::cout << "The value of banana is: " << myMap["banana"] << std::endl;
    std::cout << "The value of orange is: " << myMap["orange"] << std::endl;

    return 0;
}

运行结果为：

The value of apple is: 3
The value of banana is: 2
The value of orange is: 4

说明map可以通过键来查找对应的值。

总结

通过使用set和map这两种基于红黑树的容器，C++提供了一种高效的存储和查找数据的方式。set可以让我们方便地进行元素的插入和查找，并且自动进行排序；而map则提供了根据键查找值的功能，使得我们可以通过键值对的方式来存储和访问数据。

但是需要注意的是，在插入和删除元素时，红黑树会进行颜色变换和旋转操作来保持树的平衡，这会导致一些额外的开销。所以在一些性能要求较高的场景下，可能需要考虑使用其他的数据结构，或者对红黑树进行优化。

c语言编程笔录