C++ 二叉搜索树实现与原理详解

二、插入操作

目标

向已有二叉搜索树中添加新节点的同时，且要维持其'左子树节点值 < 根节点值 < 右子树节点值'的特性。

步骤

1. 创建遍历的指针：创建一个进行遍历树的当前节点的指针，创建指向当前遍历节点的父节点的指针。
2. 寻找插入的位置：
   • 情况 1：当前遍历到的节点的键 < 要插入的键 —> '往右子树继续找'。
   • 情况 2：当前遍历到的节点的键 > 要插入的键 —> '往左子树继续找'。
   • 情况 3：当前遍历到的节点的键 = 要插入的键 —> '未找到要插入的位置'（键已存在）。
   • 情况 4：当遍历到空节点仍未找到键为 key 的节点 —> '找到了要插入的位置'。
3. 插入生成的节点：生成要插入的节点，将新节点连接到二叉搜索树中。注意不能简单的进行插入，要先判断新节点和父节点的键之间的大小关系，从而判断出新节点是应该插入到根节点的左子节点还是右子节点。

简述

先从根节点开始搜索插入位置：若目标值小于当前节点值，则向当前节点的左子树移动；若目标值大于当前节点值，则向当前节点的右子树移动；当到达叶子节点时，根据目标值与叶子节点值的大小关系，将新节点作为叶子节点的左子节点或右子节点插入。 平均时间复杂度为 O(log n)，最坏时间复杂度为 O(n)。

三、删除操作

目标

删除节点时需处理三种情况：

1. 删除叶子节点（无左右子树）：直接删除。
2. 删除单分支节点（只有左子树或右子树）：用子树替换该节点。
3. 删除双分支节点（同时有左右子树）：无法直接删除该节点，需要找到替代节点。

删除操作的核心目标是：删除节点后需要确保剩余节点仍满足二叉搜索树的性质：左子树所有节点键值 < 根节点 < 右子树所有节点键值。

步骤

1. 创建遍历的指针：同上。
2. 寻找要删的节点：同查找操作逻辑，直到找到键相等的节点。
3. 删除要删的节点：
   • 情况一（左子树为空）：将要删除节点的右子树托付给父节点。若为根节点，直接将右孩子设置为根节点。
   • 情况二（右子树为空）：将要删除节点的左子树托付给父节点。若为根节点，直接将左孩子设置为根节点。
   • 情况三（左右子树都不为空）：找到后继节点（右子树中最小的节点），用其值替换被删除节点的值，然后删除后继节点。

简述

若要删除的节点是叶子节点，直接删除即可；若节点只有一个子节点，将该节点的父节点与子节点直接连接，然后删除该节点；若节点有两个子节点，通常的做法是找到该节点右子树中的最小节点（即中序遍历下的后继节点），将其值赋给要删除的节点，然后删除该后继节点。 平均时间复杂度为 O(log n)，最坏情况为 O(n)。

代码实现

在二叉搜索树的应用场景中，根据数据存储与使用需求不同，存在两种常见的形式：

1. key 形式的二叉搜索树：每个节点仅存储一个关键值（key）。
2. key_value 形式的二叉搜索树：将关键值与相应的数值（value）关联起来。

一、key 形式的二叉搜索树

头文件：BinarySearchTree.h

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

namespace key {
    template<class K>
    struct BSTNode {
        K _key;
        BSTNode<K>* _left;
        BSTNode<K>* _right;

        BSTNode(const K& key) : _key(key), _left(nullptr), _right(nullptr) {}
    };

    template<class K>
    class BST {
    public:
        using Node = BSTNode<K>;

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

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

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

            Node* current = _root;
            Node* parent = nullptr;

            while (current) {
                if (current->_key < key) {
                    parent = current;
                    current = current->_right;
                } else if (current->_key > key) {
                    parent = current;
                    current = current->_left;
                } else {
                    return false;
                }
            }

            current = new Node(key);
            if (key < parent->_key) {
                parent->_left = current;
            } else {
                parent->_right = current;
            }
            return true;
        }

        bool Erase(const K& key) {
            if (_root == nullptr) {
                return false;
            }

            Node* current = _root;
            Node* parent = nullptr;

            while (current) {
                if (current->_key < key) {
                    parent = current;
                    current = current->_right;
                } else if (current->_key > key) {
                    parent = current;
                    current = current->_left;
                } else {
                    if (current->_left == nullptr) {
                        if (current == _root) {
                            _root = current->_right;
                        } else {
                            if (parent->_left == current) {
                                parent->_left = current->_right;
                            } else {
                                parent->_right = current->_right;
                            }
                        }
                        delete current;
                    } else if (current->_right == nullptr) {
                        if (current == _root) {
                            _root = current->_left;
                        } else {
                            if (parent->_left == current) {
                                parent->_left = current->_left;
                            } else {
                                parent->_right = current->_left;
                            }
                        }
                        delete current;
                    } else {
                        Node* replace = current->_right;
                        Node* replaceParent = current;
                        while (replace->_left) {
                            replaceParent = replace;
                            replace = replace->_left;
                        }
                        current->_key = replace->_key;
                        if (replace == replaceParent->_left) {
                            replaceParent->_left = replace->_right;
                        } else {
                            replaceParent->_right = replace->_right;
                        }
                        delete replace;
                    }
                    return true;
                }
            }
            return false;
        }

    private:
        Node* _root = nullptr;

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

测试文件：Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include "BinarySearchTree.h"
#include <iostream>
using namespace std;

void Test01() {
    cout << "===== 测试基本功能 =====" << endl;
    key::BST<int> bst;
    int arr[] = { 50, 30, 70, 20, 40, 60, 80 };
    cout << "插入数据：";
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); ++i) {
        cout << arr[i] << " ";
        bst.Insert(arr[i]);
    }
    cout << endl;
    cout << "中序遍历结果 (应有序): ";
    bst.InOrder();
    cout << "查找存在的元素 50: " << (bst.Find(50) ? "存在" : "不存在") << endl;
    cout << "查找不存在的元素 90: " << (bst.Find(90) ? "存在" : "不存在") << endl;
}

void Test02() {
    cout << "\n===== 测试删除操作 =====" << endl;
    key::BST<int> bst;
    int arr[] = { 50, 30, 70, 20, 40, 60, 80 };
    for (int val : arr) {
        bst.Insert(val);
    }
    cout << "原始树中序遍历：";
    bst.InOrder();

    cout << "删除叶子节点 20 后：";
    bst.Erase(20);
    bst.InOrder();

    cout << "删除只有右子树的节点 30 后：";
    bst.Erase(30);
    bst.InOrder();

    cout << "删除只有左子树的节点 70 后：";
    bst.Erase(70);
    bst.InOrder();

    cout << "删除有左右子树的节点 50 后：";
    bst.Erase(50);
    bst.InOrder();
}

int main() {
    Test01();
    Test02();
    return 0;
}

二、key_value 形式的二叉搜索树

头文件：BinarySearchTree.h

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

namespace key_value {
    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 BST {
    public:
        using Node = BSTNode<K, V>;

        BST() = default;

        BST(const BST& t) {
            _root = Copy(t._root);
        }

        BST& operator=(BST tmp) {
            swap(_root, tmp._root);
            return *this;
        }

        ~BST() {
            Destroy(_root);
            _root = nullptr;
        }

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

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

            Node* current = _root;
            Node* parent = nullptr;

            while (current) {
                if (current->_key < key) {
                    parent = current;
                    current = current->_right;
                } else if (current->_key > key) {
                    parent = current;
                    current = current->_left;
                } else {
                    return false;
                }
            }

            current = new Node(key, value);
            if (key < parent->_key) {
                parent->_left = current;
            } else {
                parent->_right = current;
            }
            return true;
        }

        bool Erase(const K& key) {
            if (_root == nullptr) {
                return false;
            }

            Node* current = _root;
            Node* parent = nullptr;

            while (current) {
                if (current->_key < key) {
                    parent = current;
                    current = current->_right;
                } else if (current->_key > key) {
                    parent = current;
                    current = current->_left;
                } else {
                    if (current->_left == nullptr) {
                        if (current == _root) {
                            _root = current->_right;
                        } else {
                            if (parent->_left == current) {
                                parent->_left = current->_right;
                            } else {
                                parent->_right = current->_right;
                            }
                        }
                        delete current;
                    } else if (current->_right == nullptr) {
                        if (current == _root) {
                            _root = current->_left;
                        } else {
                            if (parent->_left == current) {
                                parent->_left = current->_left;
                            } else {
                                parent->_right = current->_left;
                            }
                        }
                        delete current;
                    } else {
                        Node* replace = current->_right;
                        Node* replaceParent = current;
                        while (replace->_left) {
                            replaceParent = replace;
                            replace = replace->_left;
                        }
                        current->_key = replace->_key;
                        if (replace == replaceParent->_left) {
                            replaceParent->_left = replace->_right;
                        } else {
                            replaceParent->_right = replace->_right;
                        }
                        delete replace;
                    }
                    return true;
                }
            }
            return false;
        }

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

    private:
        Node* _root = nullptr;

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

        Node* Copy(const Node* root) {
            if (root == nullptr) {
                return nullptr;
            }
            Node* newRoot = new Node(root->_key, root->_value);
            newRoot->_left = Copy(root->_left);
            newRoot->_right = Copy(root->_right);
            return newRoot;
        }

        void Destroy(Node* root) {
            if (root == nullptr) {
                return;
            }
            Destroy(root->_left);
            Destroy(root->_right);
            delete root;
        }
    };
}

测试文件：Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include "BinarySearchTree.h"
#include <iostream>
using namespace std;

void Test01() {
    cout << "========= 测试基本功能 =========" << endl;
    key_value::BST<string, string> dict;
    dict.Insert("apple", "苹果");
    dict.Insert("banana", "香蕉");
    dict.Insert("cherry", "樱桃");
    dict.Insert("date", "枣");
    cout << "插入后的中序遍历（按键排序）：" << endl;
    dict.InOrder();

    auto node = dict.Find("banana");
    if (node) cout << "查找 'banana' 成功，值为：" << node->_value << endl;
    else cout << "查找 'banana' 失败" << endl;

    node = dict.Find("grape");
    if (node) cout << "查找 'grape' 成功，值为：" << node->_value << endl;
    else cout << "查找 'grape' 失败（预期结果）" << endl;
}

void Test02() {
    cout << "\n========= 测试删除操作 =========" << endl;
    key_value::BST<int, string> bst;
    bst.Insert(50, "五十");
    bst.Insert(30, "三十");
    bst.Insert(70, "七十");
    bst.Insert(20, "二十");
    bst.Insert(40, "四十");
    bst.Insert(60, "六十");
    bst.Insert(80, "八十");
    cout << "原始树中序遍历：" << endl;
    bst.InOrder();

    cout << "删除叶子节点 20 后：" << endl;
    bst.Erase(20);
    bst.InOrder();

    cout << "删除只有右子树的节点 30 后：" << endl;
    bst.Erase(30);
    bst.InOrder();

    cout << "删除只有左子树的节点 70 后：" << endl;
    bst.Erase(70);
    bst.InOrder();

    cout << "删除有左右子树的节点 50 后：" << endl;
    bst.Erase(50);
    bst.InOrder();

    cout << "删除根节点 40 后：" << endl;
    bst.Erase(40);
    bst.InOrder();
}

void Test03() {
    cout << "\n========= 测试拷贝构造和赋值运算符 =========" << endl;
    key_value::BST<string, int> original;
    original.Insert("张三", 18);
    original.Insert("李四", 20);
    original.Insert("王五", 22);
    original.Insert("赵六", 24);
    cout << "原始树中序遍历：" << endl;
    original.InOrder();

    cout << "\n--------测试拷贝构造--------" << endl;
    key_value::BST<string, int> copy1(original);
    cout << "拷贝构造后的树中序遍历：" << endl;
    copy1.InOrder();

    cout << "\n--------测试赋值运算符--------" << endl;
    key_value::BST<string, int> copy2;
    copy2 = original;
    cout << "赋值运算符后的树中序遍历：" << endl;
    copy2.InOrder();

    cout << "\n--------修改原树，验证深拷贝--------" << endl;
    original.Insert("钱七", 26);
    cout << "修改原树后，原树中序遍历：" << endl;
    original.InOrder();
    cout << "拷贝树中序遍历（应不受影响）：" << endl;
    copy1.InOrder();
}

int main() {
    Test01();
    Test02();
    Test03();
    return 0;
}