C++二叉搜索树：从插入到删除，以及Key/Value模型实现

Key 模型 vs Key/Value 模型

Key 模型 只存储键，用来判断某个键是否存在。比如车牌识别、拼写检查、编译器保留字检查。C++ 里的 set/multiset 就属于这一类，键值不可改。

Key/Value 模型 每个键挂一个值，通过键快速拿到值。中英文词典、停车场计费、词频统计都是典型场景。对应 map/multimap，可以改值但键动不得。

代码实现

下面给出两个完整的 C++ 实现，都放在 twg 命名空间里。

Key 模型（类似 set）

支持去重，主要展示插入、删除、查找。删除部分对单孩子情况做了统一处理，两个孩子时采用替代法。

#pragma once
#include <assert.h>
#include <iostream>
using namespace std;

namespace twg {
    template<class K>
    struct BSTnode {
        K _key;
        BSTnode* left;
        BSTnode* right;

        BSTnode(const K& key = K()) : _key(key), left(nullptr), right(nullptr) {}
    };

    template<class K>
    class set {
        typedef BSTnode<K> Node;
    public:
        bool Insert(const K& key) {
            if (_root == nullptr) {
                _root = new Node(key);
                return true;
            }

            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key < cur->_key) {
                    parent = cur;
                    cur = cur->left;
                } else if (key > cur->_key) {
                    parent = cur;
                    cur = cur->right;
                } else {
                    return false; // 重复键
                }
            }

            cur = new Node(key);
            if (parent->_key > key) {
                parent->left = cur;
            } else {
                parent->right = cur;
            }
            return true;
        }

        bool Erase(const K& key) {
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key < cur->_key) {
                    parent = cur;
                    cur = cur->left;
                } else if (key > cur->_key) {
                    parent = cur;
                    cur = cur->right;
                } else {
                    // 找到了，开始删除
                    if (cur->left == nullptr) {
                        // 左空或全空
                        if (parent == nullptr) {
                            _root = cur->right;
                        } else {
                            if (parent->left == cur) parent->left = cur->right;
                            else parent->right = cur->right;
                        }
                        delete cur;
                        return true;
                    } else {
                        // 两个孩子，找左子树最大
                        Node* rightMinf = cur;
                        Node* rightMin = cur->left;
                        while (rightMin->left) {
                            rightMinf = rightMin;
                            rightMin = rightMin->left;
                        }

                        if (parent->left == cur) parent->left = rightMin;
                        else parent->right = rightMin;

                        rightMinf->left = rightMin->right;
                        rightMin->left = cur->left;
                        rightMin->right = cur->right;

                        delete cur;
                        return true;
                    }
                }
            }
            return false;
        }

        bool Find(const K& key) {
            Node* cur = _root;
            while (cur) {
                if (key < cur->_key) cur = cur->left;
                else if (key > cur->_key) cur = cur->right;
                else return true;
            }
            return false;
        }

        void Inorder() {
            assert(_root);
            inorder(_root);
        }

    private:
        void inorder(const Node* root) {
            if (!root) return;
            inorder(root->left);
            cout << root->_key << endl;
            inorder(root->right);
        }

        Node* _root = nullptr;
    };
}

Key/Value 模型（类似 map）

多了值的存储，并实现了 operator[]：如果键不存在就插入一个默认值并返回引用。

#pragma once
#include <iostream>
using namespace std;

namespace twg {
    template<class K, class V>
    struct BSTnode {
        K _key;
        V _val;
        BSTnode* left;
        BSTnode* right;

        BSTnode(const K& key, const V& val) : _key(key), _val(val), left(nullptr), right(nullptr) {}
    };

    template<class K, class V>
    class map {
        typedef BSTnode<K, V> Node;
    public:
        map(const map& other) {
            _root = Copy(other._root);
        }

        ~map() {
            Destory(_root);
        }

        bool Insert(const K& key, const V& val) {
            if (_root == nullptr) {
                _root = new Node(key, val);
                return true;
            }

            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key <= cur->_key) {
                    parent = cur;
                    cur = cur->left;
                } else {
                    parent = cur;
                    cur = cur->right;
                }
            }

            cur = new Node(key, val);
            if (key <= parent->_key) parent->left = cur;
            else parent->right = cur;
            return true;
        }

        bool Find(const K& key) {
            Node* cur = _root;
            while (cur) {
                if (key < cur->_key) cur = cur->left;
                else if (key > cur->_key) cur = cur->right;
                else return true;
            }
            return false;
        }

        bool Erase(const K& key) {
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key < cur->_key) {
                    parent = cur;
                    cur = cur->left;
                } else if (key > cur->_key) {
                    parent = cur;
                    cur = cur->right;
                } else {
                    if (cur->right != nullptr) {
                        if (parent == nullptr) _root = cur->right;
                        else {
                            if (parent->left == cur) parent->left = cur->right;
                            else parent->right = cur->right;
                        }
                        delete cur;
                        return true;
                    } else {
                        Node* leftMax = cur->left;
                        Node* leftMaxf = cur;
                        while (leftMax->right) {
                            leftMaxf = leftMax;
                            leftMax = leftMax->right;
                        }
                        cur->_key = leftMax->_key;
                        cur->_val = leftMax->_val;
                        leftMaxf->right = leftMax->left;
                        delete leftMax;
                        return true;
                    }
                }
            }
            return false;
        }

        V& operator[](const K& key) {
            Node* cur = _root;
            Node* parent = nullptr;
            while (cur) {
                if (key < cur->_key) {
                    parent = cur;
                    cur = cur->left;
                } else if (key > cur->_key) {
                    parent = cur;
                    cur = cur->right;
                } else {
                    return cur->_val;
                }
            }
            cur = new Node(key, V());
            if (parent == nullptr) _root = cur;
            else {
                if (key < parent->_key) parent->left = cur;
                else parent->right = cur;
            }
            return cur->_val;
        }

    private:
        Node* Copy(const Node* root) {
            if (!root) return nullptr;
            Node* newNode = new Node(root->_key, root->_val);
            newNode->left = Copy(root->left);
            newNode->right = Copy(root->right);
            return newNode;
        }

        void Destory(Node* root) {
            if (!root) return;
            Destory(root->left);
            Destory(root->right);
            delete root;
        }

        void _inorder(const Node* root) {
            if (!root) return;
            _inorder(root->left);
            cout << root->_key << ": " << root->_val << endl;
            _inorder(root->right);
        }

        Node* _root = nullptr;
    };
}

二叉搜索树的核心全在'左小右大'这一条性质上。查询比链表快，插入删除比有序数组快，但它的弱点是不平衡时会严重退化。搞懂这里的增删逻辑，特别是删除时的替代法，后面再看 AVL、红黑树会轻松很多。