Can we implement Red Black Tree in c++ by STL containers?

Article by: Manish Methani

Last Updated: September 7, 2021 at 8:04am IST
9 min 46 sec

Red-Black Trees are essential self-balancing binary search trees widely used in computer science. Fortunately, C++ provides easy-to-use Standard Template Library (STL) containers that implement Red-Black Trees. In this step-by-step guide, we'll walk you through the process of implementing and utilizing Red-Black Trees using C++ STL containers, complete with example code and frequently asked questions.

Table of Contents:

The key properties of a Red-Black Tree are as follows:

1. Every node is either red or black.
2. The root node is always black.
3. Every leaf (NIL) node is black.
4. If a node is red, then both its children are black.
5. Every simple path from a node to its descendant leaves contains an equal number of black nodes.

These properties guarantee that a Red-Black Tree is balanced, and its height remains logarithmic, ensuring efficient search, insertion, and deletion operations.

Step 1: Include Necessary Headers

To get started with Red-Black Trees in C++, include the required headers from the C++ Standard Library:

#include <iostream>
#include <map>
#include <set>

Step 2: Implement Red-Black Trees using STL Containers

Example 1: Using std::map

std::map is ideal for implementing Red-Black Trees for key-value pairs:

std::map myMap;

myMap[1] = "One";
myMap[2] = "Two";
myMap[3] = "Three";

// Access and print values
std::cout << myMap[2] << std::endl; // Output: "Two"

Example 2: Using std::set

std::set is perfect for maintaining a collection of unique elements:

std::set mySet;

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

// Check for element existence
if (mySet.find(2) != mySet.end()) {
    std::cout << "Element 2 exists in the set." << std::endl;
} else {
    std::cout << "Element 2 does not exist in the set." << std::endl;
}

Full Example Code:

Certainly! Here is an example of how to implement a Red-Black Tree in C++ using both std::map and std::set containers from the C++ Standard Template Library (STL). We will create Red-Black Trees to store and retrieve unique elements, demonstrating how to insert, delete, and search for elements within the trees.

#include <iostream>
#include <map>
#include <set>
int main() {
    // Create a Red-Black Tree using std::map
    std::map redBlackMap;

    // Insert key-value pairs into the Red-Black Tree (std::map)
    redBlackMap[3] = "Three";
    redBlackMap[1] = "One";
    redBlackMap[4] = "Four";
    redBlackMap[2] = "Two";

    // Display the Red-Black Tree (std::map)
    std::cout << "Red-Black Tree (std::map) elements:" << std::endl;
    for (const auto& pair : redBlackMap) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    // Create a Red-Black Tree using std::set
    std::set redBlackSet;

    // Insert unique elements into the Red-Black Tree (std::set)
    redBlackSet.insert(3);
    redBlackSet.insert(1);
    redBlackSet.insert(4);
    redBlackSet.insert(2);

    // Display the Red-Black Tree (std::set)
    std::cout << "
Red-Black Tree (std::set) elements:" << std::endl;
    for (const auto& element : redBlackSet) {
        std::cout << "Element: " << element << std::endl;
    }

    // Search for a specific key (std::map)
    int searchKey = 2;
    auto searchResultMap = redBlackMap.find(searchKey);

    if (searchResultMap != redBlackMap.end()) {
        std::cout << "
Key " << searchKey << " found in the Red-Black Tree (std::map). Value: " << searchResultMap->second << std::endl;
    } else {
        std::cout << "
Key " << searchKey << " not found in the Red-Black Tree (std::map)." << std::endl;
    }

    // Search for a specific element (std::set)
    int searchElement = 2;
    auto searchResultSet = redBlackSet.find(searchElement);

    if (searchResultSet != redBlackSet.end()) {
        std::cout << "Element " << searchElement << " found in the Red-Black Tree (std::set)." << std::endl;
    } else {
        std::cout << "Element " << searchElement << " not found in the Red-Black Tree (std::set)." << std::endl;
    }

    // Delete an element from the Red-Black Tree (std::map)
    int deleteKey = 3;
    size_t elementsRemovedMap = redBlackMap.erase(deleteKey);

    if (elementsRemovedMap > 0) {
        std::cout << "
Key " << deleteKey << " removed from the Red-Black Tree (std::map)." << std::endl;
    } else {
        std::cout << "
Key " << deleteKey << " not found in the Red-Black Tree (std::map). No elements removed." << std::endl;
    }

    // Delete an element from the Red-Black Tree (std::set)
    int deleteElement = 3;
    size_t elementsRemovedSet = redBlackSet.erase(deleteElement);

    if (elementsRemovedSet > 0) {
        std::cout << "Element " << deleteElement << " removed from the Red-Black Tree (std::set)." << std::endl;
    } else {
        std::cout << "Element " << deleteElement << " not found in the Red-Black Tree (std::set). No elements removed." << std::endl;
    }

    // Display the updated Red-Black Trees (std::map and std::set)
    std::cout << "
Updated Red-Black Tree (std::map) elements:" << std::endl;
    for (const auto& pair : redBlackMap) {
        std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
    }

    std::cout << "
Updated Red-Black Tree (std::set) elements:" << std::endl;
    for (const auto& element : redBlackSet) {
        std::cout << "Element: " << element << std::endl;
    }

    return 0;
}

Output

Red-Black Tree (std::map) elements:
Key: 1, Value: One
Key: 2, Value: Two
Key: 3, Value: Three
Key: 4, Value: Four

Red-Black Tree (std::set) elements:
Element: 1
Element: 2
Element: 3
Element: 4

Key 2 found in the Red-Black Tree (std::map). Value: Two
Element 2 found in the Red-Black Tree (std::set).

Key 3 removed from the Red-Black Tree (std::map).
Element 3 removed from the Red-Black Tree (std::set).

Updated Red-Black Tree (std::map) elements:
Key: 1, Value: One
Key: 2, Value: Two
Key: 4, Value: Four

Updated Red-Black Tree (std::set) elements:
Element: 1
Element: 2
Element: 4

Conclusion

Implementing Red-Black Trees in C++ using STL containers, such as std::map and std::set, is a straightforward and efficient process. The STL abstracts away the complexities of Red-Black Tree implementation, providing you with well-optimized and standardized containers for various use cases. Whether you need to store key-value pairs or maintain a unique set of elements, the STL containers offer a reliable solution for your data structure needs.