二叉搜索树

定义

又称二叉排序树，用于维护动态有序序列，满足以下性质：

1. 每个节点的值 > 左子树中所有节点的值
2. 每个节点的值 < 右子树中所有节点的值

推论：中序遍历二叉搜索树得到的序列是递增的

存储结构

竞赛常用——数组模拟链式法

struct Node{
    int val;
    int left;
    int right;
    Node(int v, int l=0, int r=0): 
      val(v), left(l), right(r){}
};
vector<Node> tree;

查找

实现方式

查找一个值$k$，从根节点开始比较，有几种情况：

• 当前节点值 == $k$，找到目标节点
• 当前节点值 > $k$，继续在左子树查找
• 当前节点值 < $k$，继续在右子树查找
• 到达空节点，说明树中不存在值$k$

时间复杂度

• 最坏情况：$O(n)$，当树退化成链表时
• 平均情况：$O(\log n)$，当树保持平衡时

代码

递归实现

int search(int root, int tar){
    // 根为空，没找到
    if(!root) return 0;
    // 找到目标值，返回根节点下标
    if(tar == tree[root].val) return root;
    // 目标值小于根节点值，在左子树继续查找
    if(tar < tree[root].val) return search(tree[root].left, tar);
    // 目标值大于根节点值，在右子树继续查找
    return search(tree[root].right, tar);
}

迭代实现

推荐，减少占用栈空间，且无需回溯

int search(int root, int tar){
    // root不为空，继续查找
    while(root){
        // 找到目标值，返回根节点下标
        if(tar == tree[root].val) return root;
        // 目标值小于根节点值，在左子树继续查找
        if(tar < tree[root].val) root = tree[root].left;
        // 目标值大于根节点值，在右子树继续查找
        else root = tree[root].right;
    }
    return 0; // 没找到
}

插入

实现方式

插入一个值$k$，从根节点开始比较，有几种情况：

• 当前节点值 == $k$，树中已存在值$k$，不插入
• 当前节点值 > $k$，在左子树中插入
• 当前节点值 < $k$，在右子树中插入
• 到达空节点，插入新节点

时间复杂度

• 最坏情况：$O(n)$，当树退化成链表时
• 平均情况：$O(\log n)$，当树保持平衡时

代码

与查找类似，只不过到达空节点插入新节点

// root传引用，因为root为空时需要修改它的值
void insert(int &root, int tar){
    if(!root){
        // 到达空节点，插入新节点
        tree.emplace_back(tar);
        // 修改根节点的指针指向新节点
        root = tree.size() - 1;
        return;
    }
  	// 已存在，不插入
  	if(tar == tree[root].val) return;
  	// 目标值小于根节点值，在左子树插入
  	if(tar < tree[root].val) insert(tree[root].left, tar);
  	// 目标值大于根节点值，在右子树插入
  	else insert(tree[root].right, tar);
}

构建

从一个数组或列表构建二叉搜索树，通常有两种方法

逐个插入

• 依次将数组中的元素插入到二叉搜索树中
• 平均时间复杂度为$O(n \log n)$
• 有序数组退化成链表，时间复杂度$O(n^2)$

递归构建

• 将数组排序后
• 选择中间元素为根节点，递归构建左右子树
• 时间复杂度为$O(n)$
• 排序额外开销$O(n \log n)$

代码

逐个插入

推荐，简单易实现

int create(vector<int> &a){
    // 根节点初始化为空
    int root = 0;
    // 依次插入数组中的元素
    for(int x : a) insert(root, x);
	// 返回根节点下标
	return root;
}

递归构建

适合构建平衡树，或处理有序数组

// 先排序，保证中间元素是树的根节点
sort(a.begin(), a.end());
// 递归构建二叉搜索树，返回根节点下标
int create(vector<int> &a, int l, int r){
	// 没有元素了，返回空节点
	if(l > r) return 0;
	// 选择中间元素作为根节点
	int mid = l + (r - l) / 2;
	// 插入根节点
	tree.emplace_back(a[mid]);
	int root = tree.size() - 1;
	// 递归构建左子树
	tree[root].left = create(a, l, mid - 1);
	// 递归构建右子树
	tree[root].right = create(a, mid + 1, r);
	// 返回根节点下标
	return root;
}

删除

实现方式

删除一个值$k$，从根节点开始比较，有几种情况：

• 当前节点值 == $k$，找到目标节点，进行删除
• 当前节点值 > $k$，继续在左子树删除
• 当前节点值 < $k$，继续在右子树删除
• 到达空节点，说明树中不存在值$k$

删除节点的情况

• 目标节点为叶子节点，直接删除
• 目标节点有一个子节点，用子节点替代目标节点
• 目标节点有两个子节点
  • 找到右子树的最小节点（或左子树的最大节点）
  • 替代目标节点
  • 删除该最小节点（或最大节点）

时间复杂度

• 最坏情况：$O(n)$，当树退化成链表时
• 平均情况：$O(\log n)$，当树保持平衡时】

代码

// root传引用，可能需要修改父节点的指针
void Delete(int &root, int tar){
    // 根为空，没找到
    if(!root) return;
    // 目标值小于根节点值，目标在左子树
    if(tar < tree[root].val) Delete(tree[root].left, tar);
    // 目标值大于根节点值，目标在右子树
    else if(tar > tree[root].val) Delete(tree[root].right, tar);
    // 找到目标节点，进行删除
    else{
        auto [v, l, r] = tree[root]; //简化代码
        // 目标节点为叶子节点，直接删除
        if(!l && !r) root = 0;
        // 目标节点有一个子节点，用子节点替代目标节点
        else if(!l) root = r;
        else if(!r) root = l;
        // 目标节点有两个子节点
        else{
            // 找到右子树的最小节点（后继）
            // 也可以找左子树的最大节点（前驱）
            int minNode = r;
            // 找到右子树的最小节点
            while(tree[minNode].left) minNode = tree[minNode].left;
            // 复制后继值到目标节点
            tree[root].val = tree[minNode].val;
            // 删除后继节点
            // 注意：传参传右子树的根节点，不能直接传minNode
            Delete(tree[root].right, tree[minNode].val);
        }
    }
}

判断

中序递增法

检查中序序列是否递增。

时间复杂度

$O(n)$，需要遍历所有节点

代码

// prev传引用因为会在递归中修改，可以用全局变量、静态变量或作为返回值
bool isBST(int root, int &prev = INT_MIN){
    // 空树是二叉搜索树
    if(!root) return true; 
    // 递归检查左子树（顺便更新prev）
    // 左子树不是搜索树此树也不是，如果是则继续检查
    if(!isBST(tree[root].left, prev)) return false;
    // 当前节点值必须大于上一个访问的节点值
    if(tree[root].val <= prev) return false;
    // 更新上一个访问的节点值为当前节点值
    prev = tree[root].val; 
    // 递归检查右子树
    if(!isBST(tree[root].right, prev)) return false;
    return true;
}

区间约束法

检查每个节点值是否在合法范围内

左子树节点值 < 当前节点值 < 右子树节点值

时间复杂度

$O(n)$，需要遍历所有节点

代码

// 初始调用时为(INT_MIN, INT_MAX)
bool isBST(int root, int low, int high){
    // 空树是二叉搜索树
    if(!root) return true;
    // 当前节点值必须在开区间(low, high)范围内
    auto [v, l, r] = tree[root];
    if(v <= low || v >= high) return false;
    // 递归检查左右子树
    return isBST(l, low, v) && isBST(r, v, high);
}