C++ 二叉搜索树原理与实战：插入查找删除及 key/value 场景

最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为 logN；最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为 N。所以综合而言二叉搜索树增删查改时间复杂度为 O(N)。

这样的效率显然无法满足我们需求，因此后面会介绍二叉搜索树的变形——平衡二叉搜索树 AVL 树和红黑树，才能适用于我们在内存中存储和搜索数据。

2.2 二分查找的局限性

另外需要说明的是，二分查找也可以实现 O(logN) 级别的查找效率，但是二分查找有两大缺陷：

1. 需要存储在支持下标随机访问的结构中，并且有序；
2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。

1. 数据越有序，插入结果越坏——高度高、递归深、效率低；
2. 插入越无序的数据，左右会平衡一点，结果反而越好。

3 实现二叉搜索树的定义

3.1 命名规范

二叉搜索树常简写为 BST，提高代码可读性。二叉搜索树也叫搜索二叉树。

3.2 定义节点

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

3.3 实践：完整的类定义

提供插入、查找、删除等基本操作的接口设计。

4 二叉搜索树的插入操作详解

4.1 插入算法流程

从根节点开始，根据键值大小选择左子树或右子树，直到找到空位置插入新节点。

插入分成以下三种情况：

1. 树为空，则直接新增结点，赋值给 root 指针；
2. 树不空，按二叉搜索树性质，插入值比当前结点大就往右走，插入值比当前结点小就往左走，找到空位置，插入新结点；
3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点（要注意保持逻辑一致性）。

4.2 代码实践

4.2.1 代码演示

我们定义这样一个数组：

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

实现插入的代码如下：

// 不允许相等的值输入
template<class K> class BSTree {
    typedef BSTreeNode<K> Node;
public:
    // 不允许相等的值插入
    // 也可以允许相等的值插入，这样就要继续插入下去，但是要统一一下插入到左边还是右边
    bool Insert(const K& key) {
        if (_root == nullptr) {
            _root = new Node(key);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false; // 相等就返回 false
            }
        }
        cur = new Node(key);
        if (parent->_key < key) {
            parent->_right = cur;
        } else {
            parent->_left = cur;
        }
        return true;
    }
private:
    Node* _root = nullptr;
};

这里写的是不允许相等的值输入条件下的写法。

4.2.2 测试用例设计

在 Test.cpp 文件里面包一下头文件，给一个数组，再定义出一棵树，因为数组也是支持范围 for 的，这里我们用范围 for 把数据插入进去。

4.2.3 C++ 递归的麻烦之处

C++ 递归很麻烦，这里要传根，但是根是私有的。在类里面的递归基本上要这样玩，尤其是树的递归，因为树的递归起始条件一般是根，都要套一层（内部/外部），套一层，因为外部拿不到根，内部是可以拿到根的，这种方式是最推荐的拿根方式。

调的是不需要传根的，再去调用这个子函数，把根传过去，这样外面就不需要传了，也不需要提供 get root，不过 get root 调用的时候也方便。

4.3 InOrder：中序遍历验证

利用 BST 的中序遍历必然有序的特性验证插入正确性。

要写成这样套一层的结构，原因上面已经提到了，这里不再赘述。

写成中序遍历的好处：

1. 中序遍历：最简单的递归；
2. 中序遍历有序，并且数据都在，并且能够很好地验证功能。

4.4 运行演示

运行一下，成功插入进去了，并且因为是中序遍历，结果是有序的。

4.5 实现要点

平衡和旋转这一块非常复杂，仅凭三言两语是说不清楚的，我们后面会详细介绍。

5 查找操作实现

5.1 查找算法

利用 BST 的排序特性，通过比较键值快速定位目标节点。

1. 从根开始比较，查找 x，x 比根的值大则往右边走查找，x 比根值小则往左边走查找；
2. 最多查找高度次，走到到空，还没找到，这个值不存在；
3. 如果不支持插入相等的值，找到 x 即可返回；
4. 如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。

5.2 代码实践

查找的代码也可以递归写，这里没有用递归写。

5.3 测试用例设计

我们就查找一下 1 这个数据。

5.4 运行

运行一下，查找成功。

6 删除操作深度解析

6.1 删除前的定位：要先查找一下

首先需要找到待删除节点及其父节点。

6.1.1 查找元素存在分四种情况

首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。

如果查找元素存在则分以下四种情况需要分别处理一下（假设要删除的结点为 N）：

1. 要删除结点 N 左右孩子均为空；
2. 要删除的结点 N 左孩子位空，右孩子结点不为空；
3. 要删除的结点 N 右孩子位空，左孩子结点不为空；
4. 要删除的结点 N 左右孩子结点均不为空。

6.1.2 对应以上四种情况的解决方案

1. 把 N 结点的父亲对应孩子指针指向空，直接删除 N 结点（情况 1 可以当成 2 或者 3 进行处理，效果是一样的）；
2. 把 N 结点的父亲对应孩子指针指向 N 的右孩子，直接删除 N 结点；
3. 把 N 结点的父亲对应孩子指针指向 N 的左孩子，直接删除 N 结点；
4. 无法直接删除 N 结点，因为 N 的两个孩子无处安放，只能用替换法删除。找 N 左子树的值最大结点 R（最右结点）或者 N 右子树的值最小结点 R（最左结点）替代 N，因为这两个结点中任意一个，放到 N 的位置，都满足二叉搜索树的规则。替代 N 的意思就是 N 和 R 的两个结点的值交换，转而变成删除 R 结点，R 结点符合情况 2 或情况 3，可以直接删除。

6.2 示例分析

接下来我们通过具体例子来看看各种删除情况。

6.3 实践：代码实现

6.3.1 节点定位：查找要删除的节点

实现高效的节点查找逻辑。

查找过程图示：假设要删除 key = 6，如下图所示。

查找路径： cur = 8, 6 < 8 → 向左 cur = 3, 6 > 3 → 向右 cur = 6, 6 == 6 → 找到！ 此时：parent = 节点 3, cur = 节点 6

6.3.2 左子树为空的情况

6.3.3 右子树为空的情况

6.3.4 左右子树都存在的情况

6.3.5 完整的 Erase 实现

// 搜索二叉树这个部分，删除是很麻烦的，先找到再删除，找到不难，但是删除很难
// 面试如果考，一定不会考插入、查找，肯定会考删除
bool Erase(const K& key) {
    Node* parent = nullptr; // 记录当前节点的父节点
    Node* cur = _root; // 从根节点开始搜索
    // 1、查找要删除的节点
    while (cur) {
        if (cur->_key < key) { // 目标 key 比当前节点大，向右子树搜索
            parent = cur;
            cur = cur->_right;
        } else if (cur->_key > key) { // 目标 key 比当前节点小，向左子树搜索
            parent = cur;
            cur = cur->_left;
        } else { // 找到要删除的节点 cur——要干掉的节点
            // 情况 1：要删除的节点左子树为空（只有右子树或没有子树）
            // 左为空
            if (cur->_left == nullptr) {
                if (cur == _root) { // 如果要删除的是根节点，（改变根节点）让孩子自己变成根
                    _root = cur->_right;
                } else {
                    if (cur == parent->_left) {
                        parent->_left = cur->_right;
                    } else {
                        parent->_right = cur->_right;
                    }
                }
                delete cur;
                return true;
            }
            // 情况 2：要删除的节点右子树为空（只有左子树）
            // 右为空
            else if (cur->_right == nullptr) {
                if (cur == _root) {
                    _root = cur->_left;
                } else {
                    if (cur == parent->_left) {
                        parent->_left = cur->_left;
                    } else {
                        parent->_right = cur->_left;
                    }
                }
                delete cur;
                return true;
            }
            // 情况 3：要删除的节点左右子树都不为空（最复杂的情况！！！）
            else {
                // 策略：用右子树的最小节点（中序后继）来替代当前节点
                // 找 cur 右子树的最小节点替代
                Node* replaceParent = cur; // 替代节点的父节点
                Node* replace = cur->_right; // 从右子树开始找
                // 在右子树中一直向左找，找到最小的节点（最左节点）
                while (replace->_left) {
                    replaceParent = replace;
                    replace = replace->_left;
                }
                // 用替代节点的值覆盖要删除节点的值
                cur->_key = replace->_key;
                // 需要判断一下
                // 删除替代节点（替代节点要么是叶子节点，要么只有右子树）
                if (replaceParent->_left == replace) {
                    replaceParent->_left = replace->_right;
                } else {
                    replaceParent->_right = replace->_right;
                }
                delete replace;
                return true;
            }
        }
    }
    return false; // 没找到删除的节点，直接 return false
}

6.4 测试用例设计

这里是删 8 是会出问题的！我们要改一改。

6.4.1 替代节点的父节点就是当前节点：replace 的 parent 就是 cur

6.4.2 需要判断一下：连接判断逻辑

改变根节点，让这个孩子自己变成根。

6.5 访问 for 重新删

需要全部再删一次，重复删不会报错。

6.6 运行

运行一下，成功删掉了，功能顺利验证。

6.7 实现技巧

7 二叉搜索树的完整代码示例与实践演示

SearchBinaryTree.h：

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

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

template<class K> class BSTree {
    typedef BSTreeNode<K> Node;
public:
    bool Insert(const K& key) {
        if (_root == nullptr) {
            _root = new Node(key);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false;
            }
        }
        cur = new Node(key);
        if (parent->_key < key) {
            parent->_right = cur;
        } else {
            parent->_left = cur;
        }
        return true;
    }

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

    bool Erase(const K& key) {
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            } else {
                if (cur->_left == nullptr) {
                    if (cur == _root) {
                        _root = cur->_right;
                    } else {
                        if (cur == parent->_left) {
                            parent->_left = cur->_right;
                        } else {
                            parent->_right = cur->_right;
                        }
                    }
                    delete cur;
                    return true;
                } else if (cur->_right == nullptr) {
                    if (cur == _root) {
                        _root = cur->_left;
                    } else {
                        if (cur == parent->_left) {
                            parent->_left = cur->_left;
                        } else {
                            parent->_right = cur->_left;
                        }
                    }
                    delete cur;
                    return true;
                } else {
                    Node* replaceParent = cur;
                    Node* replace = cur->_right;
                    while (replace->_left) {
                        replaceParent = replace;
                        replace = replace->_left;
                    }
                    cur->_key = replace->_key;
                    if (replaceParent->_left == replace) {
                        replaceParent->_left = replace->_right;
                    } else {
                        replaceParent->_right = replace->_right;
                    }
                    delete replace;
                    return true;
                }
            }
        }
        return false;
    }

    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }

private:
    void _InOrder(Node* root) {
        if (root == nullptr) return;
        _InOrder(root->_left);
        cout << root->_key << " ";
        _InOrder(root->_right);
    }

private:
    Node* _root = nullptr;
};

Test.cpp：

#define _CRT_SECURE_NO_WARNINGS 1
#include"SearchBinaryTree.h"
int main() {
    int a[] = { 8,3,1,10,1,6,4,7,14,13 };
    BSTree<int> t;
    for (auto e : a) {
        t.Insert(e);
    }
    t.InOrder();
    t.Find(1);
    t.InOrder();
    t.Erase(3);
    t.Erase(8);
    t.InOrder();
    t.Erase(1);
    t.InOrder();
    t.Erase(10);
    t.InOrder();
    for (auto e : a) {
        t.Insert(e);
    }
    return 0;
}

运行演示

8 二叉搜索树 key 和 key / value 使用场景

8.1 key 搜索场景

只有 key 作为关键码，结构中只需要存储 key 即可，关键码即为需要搜索到的值，搜索场景只需要判断 key 在不在。key 的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改 key 破坏搜索树结构了。

场景 1：小区无人值守车库，小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌在不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。

场景 2：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。

8.2 key / value 使用场景

每一个关键码 key，都有与之对应的值 value，value 可以任意类型对象。树的结构中（结点）除了需要存储 key 还要存储对应的 value，增/删/查还是以 key 为关键字走二叉搜索树的规则进行比较，可以快速查找到 key 对应的 value。key/value 的搜索场景实现的二叉搜索树支持修改，但是不支持修改 key，修改 key 破坏搜索树性质了，可以修改 value。

场景 1：简单中英互译字典，树的结构中（结点）存储 key(英文）和 vlaue（中文），搜索时输入英文，则同时查找到了英文对应的中文。

场景 2：商场无人值守车库，入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间 - 入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。

场景 3：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现，( 单词 , 1），单词存在，则++单词对应的次数。

8.3 实践：key / value 代码实现

key / value 场景下的代码实现如下所示：

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

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

        Node* Find(const K& key) {
            Node* cur = _root;
            while (cur) {
                if (cur->_key < key) {
                    cur = cur->_right;
                } else if (cur->_key > key) {
                    cur = cur->_left;
                } else {
                    return cur;
                }
            }
            return nullptr;
        }

        bool Erase(const K& key) {
            Node* parent = nullptr;
            Node* cur = _root;
            while (cur) {
                if (cur->_key < key) {
                    parent = cur;
                    cur = cur->_right;
                } else if (cur->_key > key) {
                    parent = cur;
                    cur = cur->_left;
                } else {
                    if (cur->_left == nullptr) {
                        if (cur == _root) {
                            _root = cur->_right;
                        } else {
                            if (cur == parent->_left) {
                                parent->_left = cur->_right;
                            } else {
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                        return true;
                    } else if (cur->_right == nullptr) {
                        if (cur == _root) {
                            _root = cur->_left;
                        } else {
                            if (cur == parent->_left) {
                                parent->_left = cur->_left;
                            } else {
                                parent->_right = cur->_left;
                            }
                        }
                        delete cur;
                        return true;
                    } else {
                        Node* replaceParent = cur;
                        Node* replace = cur->_right;
                        while (replace->_left) {
                            replaceParent = replace;
                            replace = replace->_left;
                        }
                        cur->_key = replace->_key;
                        cur->_value = replace->_value;
                        if (replaceParent->_left == replace) {
                            replaceParent->_left = replace->_right;
                        } else {
                            replaceParent->_right = replace->_right;
                        }
                        delete replace;
                        return true;
                    }
                }
            }
            return false;
        }

        void InOrder() {
            _InOrder(_root);
            cout << endl;
        }

    private:
        void _InOrder(Node* root) {
            if (root == nullptr) return;
            _InOrder(root->_left);
            cout << root->_key << " ";
            _InOrder(root->_right);
        }

    private:
        Node* _root = nullptr;
    };
}

8.4 设计测试用例

8.4.1 测试用例一

8.4.2 测试用例二

8.5 运行演示

8.5.1 测试用例一运行演示

运行一下。

8.5.2 测试用例二运行演示

运行一下。

8.5.3 取消运行

^Z：Ctrl + Z + Enter（回车），就能取消运行。

8.6 博主手记