从二叉搜索树到 STL：set 容器的本质与用法

引言

关联容器在算法和工程中非常常见且重要。

背景补充

此前讨论的二叉搜索树多为单值结构，实际应用中常涉及键值对存储。类似于 Python 字典，Key 用于检索，Value 存储实际数据。以下通过场景举例说明两者的区别。

Key 搜索场景

例如小区地下车库，系统根据车牌号（Key）判断是否允许进入，仅需关键字查找。

Key/Value 搜索场景

商场停车场计费系统需记录车牌号（Key）和入场时间（Value）。离场时通过 Key 检索 Value 计算费用。Key 是标识符，Value 是关键数据。因此应用场景更为广泛。

源码示例

以下是基于 C++ 模板实现的键值对二叉搜索树结构：

#include <iostream>
#include <vector>
using namespace std;

template<class K, class V>
struct BSTNode {
    K _key;
    V _value;
    BSTNode<K, V>* _left;
    BSTNode<K, V>* _right;
    BSTNode(const K& key, const V& value)
        :_key(key)
        , _value(value)
        , _left(nullptr)
        , _right(nullptr) {}
};

template<class K, class V>
class BSTree {
    typedef BSTNode<K, V> Node;
public:
    BSTree() = default;
    bool Insert(const K& key, const V& value) {
        if (_root == nullptr) {
            _root = new (key, value);
             ;
        }
        Node* parent = ;
        Node* cur = _root;
         (cur) {
             (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            }   (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            }  {
                 ;
            }
        }
        cur =  (key, value);
         (parent->_key < key) {
            parent->_right = cur;
        }  {
            parent->_left = cur;
        }
         ;
    }
    {
        Node* cur = _root;
         (cur) {
             (cur->_key < key) {
                cur = cur->_right;
            }   (cur->_key > key) {
                cur = cur->_left;
            }  {
                 cur;
            }
        }
         ;
    }
    {
        Node* parent = ;
    }
};