欢迎光临
我们一直在努力
        找回密码
当前位置：171主机测评 > 服务器技术 > 正文

《一文通透二叉搜索树：从原理到实战，手撕BST》

2026-06-11 分类：服务器技术 阅读(45) 评论(0)

在算法面试中，二叉搜索树（BST）是高频手写考点，也是理解平衡二叉树（AVL树、红黑树）的基础。很多面试官不会直接考察复杂的平衡树原理，但一定会要求候选人手写BST的增删查改、理解其核心特性与复杂度问题。

本文将从底层原理、核心性质、手把手代码实现、复杂度分析、面试易错点、应用场景全方位讲解BST，帮你彻底吃透这一面试必考知识点，轻松应对手写代码、原理问答、场景分析类面试题。

⭐具体的动态效果可在该网站演示：Data Structure Visualization

一、引言：为什么需要二叉搜索树？

我们先从基础数据结构的痛点出发，理解BST存在的核心价值。数组和链表是最基础的线性数据结构，但二者都存在明显的性能短板：

  • 数组：支持随机访问，查找效率极高（有序数组二分查找O(log n)），但插入、删除元素需要移动大量元素，效率极低（O(n)），不适合频繁更新的动态数据。

  • 链表：采用链式存储，插入、删除仅需修改指针，效率极高（O(1)），但不支持随机访问，查找元素必须从头遍历，效率极低（O(n)）。

而二叉搜索树（BST）完美结合了二者的优势，将二分查找思想落地为树形动态结构。既保留了动态插入、删除的灵活性，又能通过树形二分特性，将查找效率大幅优化，是动态数据场景下最优的基础查找结构。

二、二叉搜索树（BST）的定义与核心性质

1. 基本概念与核心规则

二叉搜索树是一种特殊的有序二叉树，除了满足二叉树的基本结构（每个节点最多两个子节点），还必须严格遵守BST有序规则，这是所有操作的核心依据：

  • 节点左子树中所有节点值 严格小于 当前根节点值；

  • 节点右子树中所有节点值 严格大于 当前根节点值；

  • 左右子树必须同时满足上述规则，即所有子树也都是二叉搜索树；

  • 默认不允许存储重复节点值（可根据业务场景自定义重复值存储规则）。

2. 节点结构定义

BST的基础单元是树节点，每个节点包含数据域、左孩子指针、右孩子指针，以下是面试最常用的C++ 节点结构定义：

typedef int ElemType;

//三叉链表
typedef struct BSTNode {
ElemType data; //1.数据域
struct BSTNode* leftchild; //2.左孩子指针
struct BSTNode* rightchild; //3.右孩子指针
struct BSTNode* parent; //4.双亲节点
}BSTNode;

//辅助节点
typedef struct BSTree {
struct BSTNode* root; //用来指向根节点
}BSTree;

3. 合法与非法BST示例

合法BST特征：全局有序，所有左子树节点小于根、所有右子树节点大于根。例如根为5，左子树所有节点为1、3、4，右子树所有节点为6、8、9，完全符合规则。

非法BST陷阱：很多初学者误以为只需对比父子节点，这是典型面试误区。例如根节点5，左孩子6，右孩子7，父子节点直接违背规则；更隐蔽的场景：根节点5，左孩子3，3的右孩子6，父子节点均合规，但6大于顶层根5，全局不满足BST规则，属于非法BST。

三、BST核心操作详解

BST核心操作包含查找、插入、遍历、删除，其中删除是面试重难点，场景复杂、易错点多，下文将分场景详细拆解。

核心思路

利用BST有序特性，从根节点开始二分查找：目标值小于当前节点值则遍历左子树，目标值大于当前节点值则遍历右子树，相等则查找成功，遍历至空节点则查找失败。支持递归、非递归两种实现。

递归代码实现

BSTNode* Search_BST_NoRecursion(BSTNode* root, ElemType val) {
if (root == NULL)
return NULL;

if (root->data > val)
Search_BST_NoRecursion(root->leftchild, val);
else if(root->data < val)
Search_BST_NoRecursion(root->rightchild, val);

return root;
}

非递归代码实现

BSTNode* Search_BST(BSTNode* root, ElemType val) {
assert(root != NULL);

BSTNode* tmp = root;
while (tmp != NULL && tmp->data != val) {
if (tmp->data > val) {
tmp = tmp->leftchild;
}
else {
tmp = tmp->rightchild;
}
}

return tmp;
}

复杂度分析

时间复杂度：O(h)，h为树的高度；空间复杂度：递归O(h)（栈空间），非递归O(1)。

2. 插入操作（Insert）

核心思路

插入逻辑与查找高度相似，核心是找到合法的空插入位置。从根节点遍历，按大小规则寻找空位，最终将新节点作为叶子节点插入，不改变原有树结构。BST默认不插入重复值。

图解逻辑

以树结构[5,3,7,2,4,6,8]为例：插入数值3，因树中已存在，跳过；插入数值1，从根5遍历→3→2，最终在2的左空位插入1，成为新叶子节点。

代码实现

//购买新节点
BSTNode* BuyNode(ElemType val) {
BSTNode* tmp = (BSTNode*)malloc(sizeof(BSTNode));
if (NULL == tmp)
exit(EXIT_FAILURE);
tmp->data = val;
tmp->leftchild = tmp->rightchild = tmp->parent = NULL;

return tmp;
}

//插入
bool Insert_BST(BSTree* pTree, ElemType val) {
//0.原来是一个空树
if (pTree->root == NULL) {
BSTNode* pnewNode = BuyNode(val);
pTree->root = pnewNode;
return true;
}

//1.申请两个节点分别指向当前节点和当前节点的父节点
BSTNode* p = pTree->root;
BSTNode* pp = NULL;

//2.进入while循环，循环条件是指针p指向节点存在，且值不等于要找的val
while (p != NULL && p->data != val) {
pp = p;
if (p->data > val)
p = p->leftchild;
else
p = p->rightchild;
}

//3.如果while循环退出，会出现两种情况：
//情况1：p遇到NULL，表示val值节点不存在，且插入在此时pp指向的节点下面
//情况2：p!=NULL且p的值等于val，表示val节点存在，此时无需再插入
if (p == NULL) {
if (pp->data > val){
BSTNode* pnewNode = BuyNode(val);
pp->leftchild = pnewNode;
pnewNode->parent = pp;
}
else{
BSTNode* pnewNode = BuyNode(val);
pp->rightchild = pnewNode;
pnewNode->parent = pp;
}
}

return true;
}

3. 遍历操作（Traversal）

BST遍历的核心考点是中序遍历，也是BST最核心的特性。

核心特性

BST 中序遍历（左→根→右，LNR）结果一定是严格升序数组，这是验证BST合法性、BST排序、求第K小元素的核心依据。

代码实现（中序遍历）

#include<stack>
using namespace std;
//2.打印（中序遍历得到中序序列） — 非递归
//单栈+变量tag
void showInOrder(BSTNode* root) {
assert(root != NULL);

stack<BSTNode*> st;
bool tag = true; //表示当前节点的左孩子区域是否已被处理，默认未处理
st.push(root);

while (!st.empty()) {
BSTNode* tmp = st.top();
while (tag && tmp->leftchild != NULL) {
st.push(tmp->leftchild);
tmp = tmp->leftchild;
}

tag = false;
printf("%d ", tmp->data);
st.pop();

if (tmp->rightchild != NULL) {
st.push(tmp->rightchild);
tag = true;
}
}

printf("\\n");
}

前序、后序遍历结果无序，面试仅需了解基本逻辑，无需重点掌握。

4. 删除操作（Delete）—— 面试重难点

BST删除是面试高频难点，需根据删除节点的子节点数量，分为三种核心场景，所有场景均需保证删除后仍为合法BST。

场景1：删除叶子节点（无左右子树）

逻辑最简单，直接删除当前节点，返回空即可，不影响整棵树结构。

bool Delete_BST_0(BSTree* pTree, ElemType val){
//0.原来是一个空树
if (pTree->root == NULL) {
return false;
}

//1.先通过查找函数判断val值节点是否存在
BSTNode* p = Search_BST(pTree->root, val);
if (NULL == p)
return true;

//2.如果节点存在，判断其是几分支节点（当前只删除零分支）
//只要存在几分支就退出
if (p->leftchild != NULL || p->rightchild != NULL)
return true;

//3.节点存在，修改其父节点指向它的指针域为NULL
BSTNode* father = p->parent;
if (father == NULL)
pTree->root = NULL;
else {
if (father->data > val)
father->leftchild = NULL;
else
father->rightchild = NULL;
}

//4.释放删除节点
free(p);
p = NULL;

return true;
}

场景2：删除单孩子节点（仅有左子树/右子树）

子承父业，直接用当前节点的唯一子节点替代自身位置，即可满足BST有序规则。

bool Delete_BST_01(BSTree* pTree, ElemType val) {
//0.原来是一个空树
if (pTree->root == NULL) {
return false;
}

//1.先通过查找函数判断val值节点是否存在
BSTNode* p = Search_BST(pTree->root, val);
if (NULL == p)
return true;

//2.如果节点存在，判断其是几分支节点（当前只删除0/1分支）
if (p->leftchild != NULL && p->rightchild != NULL)
return true;

//3.节点存在，修改其父节点指向它的指针域为NULL
BSTNode* father = p->parent;
//只要让当前指针的左指针进行判空，不为空就等于左指针，等于空就为右指针（右指针是否为空无所谓）
BSTNode* child = p->leftchild != NULL ? p->leftchild : p->rightchild;
if (father == NULL)
pTree->root = child;
else {
if (father->data > val)
father->leftchild = child;
else
father->rightchild = child;
}
return true;
}

场景3：删除双孩子节点（同时有左右子树）—— 最难

无法直接删除替换，需借助前驱/后继节点兜底：

  • 前驱节点：左子树中的最大值节点（左子树最右节点）；

  • 后继节点：右子树中的最小值节点（右子树最左节点）；

操作逻辑：将前驱/后继节点的值覆盖待删除节点，再递归删除原前驱/后继节点，完美保留BST有序性。

bool Delete_BST(BSTree* pTree, ElemType val) {
//0.原来是一个空树
if (pTree->root == NULL) {
return false;
}

//1.先通过查找函数判断val值节点是否存在
BSTNode* p = Search_BST(pTree->root, val);
if (NULL == p)
return true;

//2.如果节点存在，判断其是几分支节点（2分支转化为删除0/1分支）
if (p->leftchild != NULL && p->rightchild != NULL) {
//狸猫换太子，将删除当前节点转变为删除直接前驱或直接后继节点
//找当前待删除节点的直接前驱
BSTNode* cat = p->leftchild;
while (cat->rightchild != NULL)
cat = cat->rightchild;

//将狸猫节点的值赋值给待删除节点
p->data = cat->data;

//另待删除节点指向狸猫节点
p = cat;
}

//3.节点存在，修改其父节点指向它的指针域为NULL
BSTNode* father = p->parent;
BSTNode* child = p->leftchild != NULL ? p->leftchild : p->rightchild;

if (father == NULL)
pTree->root = child;
else {
if (father->data > val)
father->leftchild = child;
else
father->rightchild = child;
}

return true;
}

四、BST性能分析与树退化问题

1. 理想情况 vs 最坏情况

  • 理想平衡状态：节点分布均匀，树高h=logn，查找、插入、删除时间复杂度均为 O(log n)，性能最优；

  • 最坏退化状态：数据有序/近似有序插入（如依次插入1、2、3、4、5），BST会退化为单链链表，树高h=n，所有操作复杂度退化为 O(n)，彻底失去二分优势。

2. 退化核心原因

插入数据有序、单调递增/递减，导致树的左右子树高度差极大，结构失衡，是BST原生设计的最大缺陷。

3. 工程优化方向

为解决BST退化问题，工程中衍生出平衡二叉树，通过旋转操作维持树的平衡：

  • AVL树：严格平衡二叉树，左右子树高度差不超过1，平衡精度高，旋转操作频繁；

  • 红黑树：弱平衡二叉树，通过颜色标记和规则维持近似平衡，旋转次数少、性能稳定，是工业级首选。

日常开发中C++ STL的set/map、Java的TreeMap/TreeSet，底层均为红黑树，而非原生BST。

五、完整可运行BST代码（含测试用例）

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdint.h>
#include<assert.h>
#include"BST.h"

//1.搜索/查找 — 非递归
BSTNode* Search_BST(BSTNode* root, ElemType val) {
assert(root != NULL);

BSTNode* tmp = root;
while (tmp != NULL && tmp->data != val) {
if (tmp->data > val) {
tmp = tmp->leftchild;
}
else {
tmp = tmp->rightchild;
}
}

return tmp;
}

//1.搜索/查找 — 递归
BSTNode* Search_BST_NoRecursion(BSTNode* root, ElemType val) {
if (root == NULL)
return NULL;

if (root->data > val)
Search_BST_NoRecursion(root->leftchild, val);
else if(root->data < val)
Search_BST_NoRecursion(root->rightchild, val);

return root;
}

#include<stack>
using namespace std;
//2.打印（中序遍历得到中序序列） — 非递归
//单栈+变量tag
void showInOrder(BSTNode* root) {
assert(root != NULL);

stack<BSTNode*> st;
bool tag = true; //表示当前节点的左孩子区域是否已被处理，默认未处理
st.push(root);

while (!st.empty()) {
BSTNode* tmp = st.top();
while (tag && tmp->leftchild != NULL) {
st.push(tmp->leftchild);
tmp = tmp->leftchild;
}

tag = false;
printf("%d ", tmp->data);
st.pop();

if (tmp->rightchild != NULL) {
st.push(tmp->rightchild);
tag = true;
}
}

printf("\\n");
}

//4.购买新节点
BSTNode* BuyNode(ElemType val) {
BSTNode* tmp = (BSTNode*)malloc(sizeof(BSTNode));
if (NULL == tmp)
exit(EXIT_FAILURE);
tmp->data = val;
tmp->leftchild = tmp->rightchild = tmp->parent = NULL;

return tmp;
}

//3.插入
bool Insert_BST(BSTree* pTree, ElemType val) {
//0.原来是一个空树
if (pTree->root == NULL) {
BSTNode* pnewNode = BuyNode(val);
pTree->root = pnewNode;
return true;
}

//1.申请两个节点分别指向当前节点和当前节点的父节点
BSTNode* p = pTree->root;
BSTNode* pp = NULL;

//2.进入while循环，循环条件是指针p指向节点存在，且值不等于要找的val
while (p != NULL && p->data != val) {
pp = p;
if (p->data > val)
p = p->leftchild;
else
p = p->rightchild;
}

//3.如果while循环退出，会出现两种情况：
//情况1：p遇到NULL，表示val值节点不存在，且插入在此时pp指向的节点下面
//情况2：p!=NULL且p的值等于val，表示val节点存在，此时无需再插入
if (p == NULL) {
if (pp->data > val){
BSTNode* pnewNode = BuyNode(val);
pp->leftchild = pnewNode;
pnewNode->parent = pp;
}
else{
BSTNode* pnewNode = BuyNode(val);
pp->rightchild = pnewNode;
pnewNode->parent = pp;
}
}

return true;
}

//5.删除操作
bool Delete_BST_0(BSTree* pTree, ElemType val){
//0.原来是一个空树
if (pTree->root == NULL) {
return false;
}

//1.先通过查找函数判断val值节点是否存在
BSTNode* p = Search_BST(pTree->root, val);
if (NULL == p)
return true;

//2.如果节点存在，判断其是几分支节点（当前只删除零分支）
if (p->leftchild != NULL || p->rightchild != NULL)
return true;

//3.节点存在，修改其父节点指向它的指针域为NULL
BSTNode* father = p->parent;
if (father == NULL)
pTree->root = NULL;
else {
if (father->data > val)
father->leftchild = NULL;
else
father->rightchild = NULL;
}

//4.释放删除节点
free(p);
p = NULL;

return true;
}

bool Delete_BST_01(BSTree* pTree, ElemType val) {
//0.原来是一个空树
if (pTree->root == NULL) {
return false;
}

//1.先通过查找函数判断val值节点是否存在
BSTNode* p = Search_BST(pTree->root, val);
if (NULL == p)
return true;

//2.如果节点存在，判断其是几分支节点（当前只删除0/1分支）
if (p->leftchild != NULL && p->rightchild != NULL)
return true;

//3.节点存在，修改其父节点指向它的指针域为NULL
BSTNode* father = p->parent;
BSTNode* child = p->leftchild != NULL ? p->leftchild : p->rightchild;
if (father == NULL)
pTree->root = child;
else {
if (father->data > val)
father->leftchild = child;
else
father->rightchild = child;
}
return true;
}

bool Delete_BST(BSTree* pTree, ElemType val) {
//0.原来是一个空树
if (pTree->root == NULL) {
return false;
}

//1.先通过查找函数判断val值节点是否存在
BSTNode* p = Search_BST(pTree->root, val);
if (NULL == p)
return true;

//2.如果节点存在，判断其是几分支节点（2分支转化为删除0/1分支）
if (p->leftchild != NULL && p->rightchild != NULL) {
//找当前待删除节点的直接前驱
BSTNode* cat = p->leftchild;
while (cat->rightchild != NULL)
cat = cat->rightchild;

p->data = cat->data;

p = cat;
}

//3.节点存在，修改其父节点指向它的指针域为NULL
BSTNode* father = p->parent;
BSTNode* child = p->leftchild != NULL ? p->leftchild : p->rightchild;
if (father == NULL)
pTree->root = child;
else {
if (father->data > val)
father->leftchild = child;
else
father->rightchild = child;
}
return true;
}

int main()
{
BSTree head;
head.root = NULL;

Insert_BST(&head, 21);
Insert_BST(&head, 10);
Insert_BST(&head, 33);
Insert_BST(&head, 5);
Insert_BST(&head, 25);
Insert_BST(&head, 55);

showInOrder(head.root);

Delete_BST(&head, 5);
Delete_BST(&head, 33);
showInOrder(head.root);

return 0;
}

六、BST核心应用场景

BST不仅是面试考点，更是工程底层数据结构的核心基础，核心应用场景如下：

  • 动态查找表实现：字典、哈希表的雏形，支持动态增删改查，适配频繁更新的数据集；

  • 高效数据排序：无需排序算法，插入数据后通过中序遍历即可得到有序序列，实现动态排序；

  • 范围区间查询：快速查找区间[min, max]内的所有数据，适配统计、筛选场景；

  • 工程底层容器：STL set/map、TreeSet/TreeMap等有序容器的底层原型，优化后通过红黑树落地生产；

  • 数据库索引雏形：早期数据库有序索引的设计思想源自BST，后续迭代出B+树、B树等索引结构。

    • 七、面试高频练习题（自测进阶）

    学完原理与代码，可通过以下面试真题巩固考点，覆盖基础、进阶、变形场景：

  • 基础真题：验证一棵树是否为合法BST（避坑：不能仅对比父子节点，需判断全局区间）；

  • 进阶真题：求解BST中第K小的元素（利用中序升序特性）；

  • 变形真题：将BST转换为累加树（右根左遍历累加赋值）；

  • 设计真题：实现支持getRandomNode()的BST，等概率随机返回树中节点。

    • 八、全文总结

    1. 核心本质：BST是二分查找的树形实现，核心性质为左小右大、子树合规、中序有序，是有序动态查找的基础结构；

    2. 操作复杂度：理想平衡状态O(log n)，有序数据插入会退化为链表，复杂度O(n)；

    3. 核心优势：结构简单、支持动态增删、天然有序、适配范围查询；

    4. 原生缺陷：无自平衡能力，易退化，生产环境几乎不直接使用，均采用AVL树、红黑树等平衡变体替代。

    掌握BST是吃透高级树形结构的关键，面试中只要熟练掌握删除三场景、中序有序特性、退化问题，即可应对90%以上的BST面试考题。

    赞(0)
    未经允许不得转载：171主机测评 » 《一文通透二叉搜索树：从原理到实战，手撕BST》
    分享到： 更多 (0)
    标签：

    相关推荐

    评论 抢沙发

    取消

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址

    热门标签

    #人工智能(57916)#python(19718)#开发语言(16590)#java(15232)#运维(15163)#linux(14792)#大数据(14351)#服务器(12916)#算法(11622)#前端(10693)#网络(9220)#数据库(8762)#ai(8664)#c++(8061)#课程设计(6759)#学习(6650)#机器学习(6614)#区块链(5848)#OpenClaw(5378)#后端(5069)#spring boot(4959)#深度学习(4851)#c语言(4326)#毕业设计(4277)#数据结构(4153)#安全(3956)#docker(3896)#架构(3771)#javascript(3763)#大模型(3599)

    热门文章

    最新文章

    归档

    分类