初学二叉搜索树踩坑多？C++ 从原理到代码，搞定增删查全流程

Ne0inhk

— 14 min read
初学二叉搜索树踩坑多？C++ 从原理到代码，搞定增删查全流程

个人主页



🎬 个人主页：Vect个人主页

🎬 GitHub：Vect的代码仓库
🔥 个人专栏: 《数据结构与算法》《C++学习之旅》《计算机基础》

⛺️Per aspera ad astra.

文章目录

1. 二叉搜索树相关概念

如下图所示，二叉搜索树(binary search tree)满足下列条件：

  1. 对于根节点，左子树中所有节点的值<根节点的值<右子树中所有节点的值
  2. 任意节点的左、右字数也是二叉搜索树，同样满足条件1
在这里插入图片描述

而下图就不是二叉搜索树：

在这里插入图片描述

2. 二叉搜索树的操作

我们将二叉搜索树封装为一个类BSTree，并声明一个_root变量，指向树的根节点

// 节点类template<classK>structBSTNode{ BSTNode<K>* _left; BSTNode<K>* _right; K _key;// 构造BSTNode(const K& val):_left(nullptr),_right(nullptr),_key(val){}};// 二叉搜索树类template<classK>classBSTree{public:typedef BSTNode<K> Node;private: Node* _root;};

2.1. 查找节点

给定目标val，可以声明一个节点cur，从二叉搜索树的根节点_root出发，循环比较cur._key和val之间的大小关系：

  • 若val < cur._key，说明目标节点在cur的左子树，执行cur = cur._left
  • 若val > cur._key，说明目标节点在cur的右子树，执行cur = cur._right
  • 若val == cur._key，说明找到目标节点，跳出循环并返回该节点

与二分查找原理一致，每轮排除一半的情况，当二叉树平衡时，循环次数最多为二叉树的高度， O ( l o g n ) O(logn) O(logn)

// 查找节点  Node*find(const K& val){ Node* cur = _root;while(cur){if(val < cur->_key) cur = cur->_left;elseif(val > cur->_key) cur = cur->_right;elsebreak;}return cur;}

2.2. 插入节点

给定一个待插入元素val，为了保持左子树<根节点<右子树的性质，插入流程如下：

  1. 查找插入位置： 与查找操作相同逻辑，从根节点出发，根据当前节点值和val的大小关系循环向下搜索，直到越过叶子节点（遍历到None）跳出循环
  2. 在该位置插入节点：new一个新节点，将新节点置于None的位置

注意：

  • 二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。
  • 为了实现插入节点，我们需要借助节点pre 保存上一轮循环的节点。这样在遍历至 None时，我们可以获取到其父节点，从而完成节点插入操作。
boolinsert(const K& val){// 空树 直接插入if(_root ==nullptr){ Node* newNode =newNode(val); _root = newNode;returntrue;}// 非空树 先找待插入节点的位置 Node* cur = _root; Node* curPre =nullptr;// 保存cur的父节点 while(cur){if(val == cur->_key)returnfalse;// 重复值 不插入elseif(val < cur->_key){// 小于键值 往左走 同时更新cur的父节点 curPre = cur; cur = cur->_left;}else{// 大于键值 往右走 同时更新cur的父节点 curPre = cur; cur = cur->_right;}}// cur的位置是待插入位置 Node* newNode =newNode(val);// 判断cur在curPre的左边还是右边 确定新节点位置if(curPre->_left == cur) curPre->_left = newNode;else curPre->_right = newNode;returntrue;}

2.3. 删除节点

先在二叉树中查找到目标节点，再将其删除。与插入节点一样，我们需要保证在删除操作完成后，保证二叉搜索树的“左子树 < 根节点 < 右子树”的性质不变

根据待删除节点的孩子数量，分0、1和2三种情况

  • 待删除结点是叶子节点，直接删除
在这里插入图片描述
  • 待删除节点有一个孩子，将待删除节点的子节点和其替换即可
在这里插入图片描述
  • 待删除节点2个孩子，不能直接删除，需要用一个节点替换该节点，保持“左子树 < 根节点 < 右子树”的性质不变，可以选择右子树最小节点或左子树最大节点

假设我们选择右子树最小节点，如下流程：

  1. 找到待删除节点cur的右子树最小节点rightMin
  2. 用rightMin的值覆盖cur，并删除rightMin
在这里插入图片描述

总共有如下几种情况：

cur 有两个孩子；rightMin 在更下方；rightMin 只有右孩子（B1）触发：cur->_right有左孩子，沿左链找到 rightMin，且 rightMin->_right != nullptr操作：cur->_key = rightMin->_key；令 rightMinPre->_left = rightMin->_right；删除 rightMin。示意：

cur(•) \ ... / rightMin \ X

cur 有两个孩子；rightMin 在更下方；rightMin 无右孩子（B0）触发：cur->_right有左孩子，沿左链找到 rightMin，且 rightMin->_right == nullptr操作：cur->_key = rightMin->_key；令 rightMinPre->_left = nullptr；删除 rightMin。示意：

cur(•) \ ... / rightMin

cur 有两个孩子；rightMin 就是 cur->_right；rightMin 只有右孩子（A1）触发：cur->_right没有左孩子，且 cur->_right->_right != nullptr操作：cur->_key = rightMin->_key；令 cur->_right = rightMin->_right；删除 rightMin。示意：

cur(•) / \ (...) rightMin \ X

cur 有两个孩子；右子树最小节点 rightMin 就是 cur->_right；rightMin 无右孩子（A0）触发：cur->_right没有左孩子，且 cur->_right->_right == nullptr操作：cur->_key = rightMin->_key；令 cur->_right = nullptr；删除 rightMin。示意：

cur(•) / \ (...) rightMin 
boolerase(const K& val){// 空树无法删除if(_root ==nullptr)returnfalse;// 查找待删除节点 Node* cur = _root; Node* curPre =nullptr;while(cur){if(val < cur->_key){// 向左找 curPre = cur; cur = cur->_left;}elseif(val > cur->_key){// 向右找 curPre = cur; cur = cur->_right;}elsebreak;// 命中}// cur为空 无法删除if(cur ==nullptr)returnfalse;// 找到cur了// 孩子0/1个的情况if(cur->_left ==nullptr|| cur->_right ==nullptr){// 找到待删除节点的孩子 Node* curNext = cur->_left ==nullptr? cur->_right : cur->_left;if(cur != _root){// 删除的不是根节点if(curPre->_left == cur) curPre->_left = curNext;else curPre->_right = curNext;}else{// 删除的是根节点 _root = curNext;}delete cur;}else{// 2个孩子// 1. 找右子树最小节点 Node* rightMin = cur->_right; Node* rightMinPre = cur;while(rightMin->_left){ rightMinPre = rightMin; rightMin = rightMin->_left;}// 2. 用rightMin的值覆盖待删除节点的值 cur->_key = rightMin->_key;// 3. 删除rightMin 要处理rightMin的孩子 Node* rightMinNext = rightMin->_right;if(rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;else rightMinPre->_right = rightMinNext;// 右子树最小节点是cur->_right的情况delete rightMin;}returntrue;}

再次总结：

查找阶段

  • 用 cur 定位待删，curPre 记录父。
  • 终止条件：命中或走到空。
  • 注意：若支持自定义比较器，等价判断应为“!(val<key) && !(key<val)”。

0/1 个孩子：真正移除 cur 节点

  • curNext = (cur->_left ? cur->_left : cur->_right)。
  • 若 cur != _root：把 curPre 的相应孩子指向 curNext。
  • 若 cur == _root：_root = curNext。
  • delete cur。
  • 要点：这是必须对“根”特判的地方（根没有父指针可改）。

2 个孩子：值覆盖 + 删后继（不移动 cur 本体）

  • 覆盖键值：cur->_key = rightMin->_key;（若有 value，一并拷/搬移）。
  • 要点：这里不需要根特判，因为根节点对象没被删除，只是“值被改写”。

删除 rightMin：

Node* rightMinNext = rightMin->_right; // 只可能有右孩子或空 if (rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext; else rightMinPre->_right = rightMinNext; // 当 rightMin 就是 cur->_right delete rightMin;

找右子树最小：

Node* rightMin = cur->_right; Node* rightMinPre = cur; while (rightMin->_left) { rightMinPre = rightMin; rightMin = rightMin->_left; }

3. 二叉搜索树的实现

#pragmaonce#include<iostream>#include<vector>usingnamespace std;namespace BSTKey {template<classK>structBSTNode{ BSTNode<K>* _left; BSTNode<K>* _right; K _key;// 构造BSTNode(const K& val):_left(nullptr),_right(nullptr),_key(val){}};template<classK>classBSTree{public:typedef BSTNode<K> Node;BSTree()=default;// 析构 需要辅助析构函数~BSTree(){destroy(_root); _root =nullptr;}// 查找节点  Node*find(const K& val){ Node* cur = _root;while(cur){if(val < cur->_key) cur = cur->_left;elseif(val > cur->_key) cur = cur->_right;elsebreak;}return cur;}boolinsert(const K& val){// 空树 直接插入if(_root ==nullptr){ Node* newNode =newNode(val); _root = newNode;returntrue;}// 非空树 先找待插入节点的位置 Node* cur = _root; Node* curPre =nullptr;// 保存cur的父节点 while(cur){if(val == cur->_key)returnfalse;// 重复值 不插入elseif(val < cur->_key){// 小于键值 往左走 同时更新cur的父节点 curPre = cur; cur = cur->_left;}else{// 大于键值 往右走 同时更新cur的父节点 curPre = cur; cur = cur->_right;}}// cur的位置是待插入位置 Node* newNode =newNode(val);// 判断cur在curPre的左边还是右边 确定新节点位置if(curPre->_left == cur) curPre->_left = newNode;else curPre->_right = newNode;returntrue;}boolerase(const K& val){// 空树无法删除if(_root ==nullptr)returnfalse;// 查找待删除节点 Node* cur = _root; Node* curPre =nullptr;while(cur){if(val < cur->_key){// 向左找 curPre = cur; cur = cur->_left;}elseif(val > cur->_key){// 向右找 curPre = cur; cur = cur->_right;}elsebreak;// 命中}// cur为空 无法删除if(cur ==nullptr)returnfalse;// 找到cur了// 孩子0/1个的情况if(cur->_left ==nullptr|| cur->_right ==nullptr){// 找到待删除节点的孩子 Node* curNext = cur->_left ==nullptr? cur->_right : cur->_left;if(cur != _root){// 删除的不是根节点if(curPre->_left == cur) curPre->_left = curNext;else curPre->_right = curNext;}else{// 删除的是根节点 _root = curNext;}delete cur;}else{// 2个孩子// 1. 找右子树最小节点 Node* rightMin = cur->_right; Node* rightMinPre = cur;while(rightMin->_left){ rightMinPre = rightMin; rightMin = rightMin->_left;}// 2. 用rightMin的值覆盖待删除节点的值 cur->_key = rightMin->_key;// 3. 删除rightMin 要处理rightMin的孩子 Node* rightMinNext = rightMin->_right;if(rightMinPre->_left == rightMin) rightMinPre->_left = rightMinNext;else rightMinPre->_right = rightMinNext;// 右子树最小节点是cur->_right的情况delete rightMin;}returntrue;}voidinOrder(){_inOrder(_root); cout << endl;}private: Node* _root;// 后续析构voiddestroy(Node* root){if(root ==nullptr)return;destroy(root->_left);destroy(root->_right);delete root;}void_inOrder(Node* root){if(root ==nullptr)return;_inOrder(root->_left); cout << root->_key <<" ";_inOrder(root->_right);}};voidtestBST(){ BSTree<int> bst; vector<int> arr ={8,3,10,1,6,14,5,7,13}; cout <<"=== 1. 创建二叉搜索树 ===\n"; cout <<"初始数据：-> ";for(constauto& e : arr) cout << e <<" "; cout <<"\n创建完成数据：-> ";for(constauto& e : arr) bst.insert(e); bst.inOrder(); cout <<"=== 2. 查找数据 ===\n"; cout <<"查找不存在数据：28 查找结果："<< bst.find(28)<< endl; cout <<"查找存在数据：14 查找结果："<< bst.find(14)<< endl; cout <<"\n=== 3. 删除数据 ===\n"; cout <<"删除前的序列：->"; bst.inOrder(); cout <<"删除节点6后的序列：->"; bst.erase(6); bst.inOrder(); cout <<"删除不存在的节点86后的序列：->"; bst.erase(86); bst.inOrder(); cout <<"\n销毁二叉树：->"; bst.~BSTree(); bst.inOrder();}}

4. 二叉搜索树的应用

4.1. K模型

只有key作为关键码（需要搜索到的值），结构中只存储key即可

例如：给一个单词word，判断该单词是否正确

  • 以词库中所有单词集合中的每个单词作为key，构建一颗二叉搜索树
  • 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

又比如门禁系统，只关注对象在不在

第三节实现的就是K模型

4.2. KV模型

每个关键码key，都有与之对应的值value，即<key，value>的键值对，例如：

  • 简单英汉词典中英文和中文是相互对应的关系，通过英文可快速找到其对应的中文，例如：<book,书>就是一种键值对
  • 车库收费系统，一个键值记录车牌号，另一个键值记录停留时间，随后交给收费系统处理缴费事宜
  • 统计单词出现次数，统计成功之后，给定单词就可快速找到其出现的次数，单词与其出现的次数就是<word,count>一种键值对

我们将K模型改造成KV模型

template<classK,classV>structBSTNode{ K _key; V _value; BSTNode<K, V>* _left; BSTNode<K, V>* _right;BSTNode(const K& k,const V& v):_key(k),_value(v),_left(nullptr),_right(nullptr){}};template<classK,classV>classBSTree{public:typedef BSTNode<K, V> Node;// ... 接口实现private: Node* _root =nullptr;// ...辅助接口实现}};
// 输入中文 输出对应英文voiddictionary(){ BSTree<string, string> dict; dict.insert("书包","bag"); dict.insert("水果","fruit"); dict.insert("钢笔","pen"); dict.insert("书","book"); dict.insert("树","tree");// 插入词库中所有单词 string str;while(cin >> str){auto ret = dict.find(str);if(ret ==nullptr) cout <<"输入错误或词库中未包含该词"<< str << endl;else cout << str <<"英文单词：->"<< ret->_value << endl;}}// 计数voidcount(){ string arr[]={"苹果","西瓜","苹果","西瓜","苹果","苹果","西瓜","苹果","香蕉","苹果","香蕉"}; BSTree<string,int> cntTree;for(constauto& s : arr){// 先查找水果在不在搜索树中// 1. 不在，说明水果第一次出现，则插入<水果, 1>// 2. 在，则查找到的节点中水果对应的次数++auto ret = cntTree.find(s);if(ret ==nullptr) cntTree.insert(s,1);else ret->_value++;} cntTree.inOrder();}

完整代码请详见此链接：二叉搜索树
二叉搜索树的核心价值，在于用 “左子树 < 根节点 < 右子树” 的简单规则，换来了查找、插入、删除操作的高效性 —— 平衡状态下$ O (logn)$ 的时间复杂度，让它成为处理动态数据查找场景的基础选择。无论是仅需判断 “存在性” 的 K 模型，还是需键值关联的 KV 模型，都能通过其核心操作快速适配，覆盖词典查询、计数统计等常见需求。

但需注意，二叉搜索树的性能依赖结构平衡：若插入数据有序，会退化为单链表，此时操作复杂度飙升至 O ( n ) O(n) O(n)。这也催生了 AVL 树、红黑树等平衡二叉搜索树 —— 它们通过自平衡机制维持树的高度，兼顾了二叉搜索树的简洁性与稳定高效的性能，是后续深入学习的重要方向。

Read more

超详细图文教程：用vscode+copilot(代理模式)便捷使用mcp+一个范例：用自然语言进行3d建模

超详细图文教程：用vscode+copilot(代理模式)便捷使用mcp+一个范例：用自然语言进行3d建模

在vscode使用claude mcp吧！ 在vscode更新到最新版本（注意，这是前提）后，内置的copilot可以使用mcp了！！！ 关于mcp（Model Context Protocol 模型上下文协议），可以参考我的上一篇文章： MCP个人理解+示例+集成管理+在python中调用示例，给AI大模型装上双手-ZEEKLOG博客 以下是使用教程： 1.点击左下角的齿轮状设置按钮，点击设置 2.在输入面板输入chat.agent.enabled，勾上勾选框 3.点击Ctrl+shift+P，输入reload，点击重新加载窗口，刷新窗口 4.打开copilot后，在右下角将模式改为代理即可。 5.点击工具按钮，开始安装mcp 先去github找到自己想要添加的mcp服务，以blender MCP为例，打开https://github.com/ahujasid/blender-mcp，可以在readme文档里看到详细的安装过程。可以看到，

By Ne0inhk
02-mcp-server案例分享-Excel 表格秒变可视化图表 HTML 报告，就这么简单

02-mcp-server案例分享-Excel 表格秒变可视化图表 HTML 报告，就这么简单

1.前言 MCP Server（模型上下文协议服务器）是一种基于模型上下文协议（Model Context Protocol，简称MCP）构建的轻量级服务程序，旨在实现大型语言模型（LLM）与外部资源之间的高效、安全连接。MCP协议由Anthropic公司于2024年11月开源，其核心目标是解决AI应用中数据分散、接口不统一等问题，为开发者提供标准化的接口，使AI模型能够灵活访问本地资源和远程服务，从而提升AI助手的响应质量和工作效率。 MCP Server 的架构与工作原理 MCP Server 采用客户端-服务器（Client-Server）架构，其中客户端（MCP Client）负责与服务器建立连接，发起请求，而服务器端则处理请求并返回响应。这种架构确保了数据交互的高效性与安全性。例如，客户端可以向服务器发送请求，如“查询数据库中的某个记录”或“调用某个API”，而服务器则根据请求类型，调用相应的资源或工具，完成任务并返回结果。 MCP Server 支持动态发现和实时更新机制。例如，当新的资源或工具被添加到服务器时，

By Ne0inhk
将现有 REST API 转换为 MCP Server工具 -higress

将现有 REST API 转换为 MCP Server工具 -higress

Higress 是一款云原生 API 网关，集成了流量网关、微服务网关、安全网关和 AI 网关的功能。 它基于 Istio 和 Envoy 开发，支持使用 Go/Rust/JS 等语言编写 Wasm 插件。 提供了数十个通用插件和开箱即用的控制台。 Higress AI 网关支持多种 AI 服务提供商，如 OpenAI、DeepSeek、通义千问等，并具备令牌限流、消费者鉴权、WAF 防护、语义缓存等功能。 MCP Server 插件配置 higress 功能说明 * mcp-server 插件基于 Model Context Protocol (MCP)，专为 AI 助手设计，

By Ne0inhk
MCP 工具速成：npx vs. uvx 全流程安装指南

MCP 工具速成：npx vs. uvx 全流程安装指南

在现代 AI 开发中，Model Context Protocol（MCP）允许通过外部进程扩展模型能力，而 npx（Node.js 生态）和 uvx（Python 生态）则是两种即装即用的客户端工具，帮助你快速下载并运行 MCP 服务器或工具包，无需全局安装。本文将从原理和对比入手，提供面向 Windows、macOS、Linux 的详细安装、验证及使用示例，确保你能在本地或 CI/CD 流程中无缝集成 MCP 服务器。 1. 工具简介 1.1 npx（Node.js/npm） npx 是 npm CLI（≥v5.2.0）

By Ne0inhk