【笔记/模板】二叉搜索树与平衡树

ThySecret · 2025-02-20 07:46:11 · 算法·理论

同步发表于 Thy's Blog。

二叉搜索树

Definition

二叉搜索树（\text{Binary Search Tree}）是一种形状如二叉树的数据结构，用于快速查找和增加删除操作，它有如下几个特殊性质：

1. 空树是二叉搜索树。
2. 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。
3. 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。
4. 二叉搜索树的左右子树均为二叉搜索树。

对于一个二叉搜索树，进行操作所花费的平均时间和这个二叉树的高度成正比。对于一个有 n 个结点的二叉搜索树中，这些操作的最优时间复杂度为 O(\log n)，最坏为 O(n)​。

Define

对于一个二叉搜索树的每一个节点，都要存储以下几样东西：

1. 左子树节点和右子树节点：l 和 r
2. 这一个节点上存储的权值：val
3. 表示这个节点权值出现次数的计数器：cnt
4. 代表这个树上的大小（即子树和自己大小之和）：size

struct BST
{
    int l, r;       // 左右子树节点
    int val;        // 这一个节点上存储的权值
    int cnt, size;  // 节点权值出现次数的计数器和这个树的大小
}tr[N];

与此同时，由于操作中需要不断插入新的数，因此还需要两个变量分别储存树的下标和当前的下标，我们用 root 和 idx 表示：

int root, idx;        // root表示这个树的根的下标，idx记录着当前的下标

Newnode

创建一个新的节点就是将这个节点全部初始化，同时返回原来的下标值：

int new_node(int k)                    // 创建新节点
{
    tr[idx].val = k;                // 将权值修改
    tr[idx].size = tr[idx].cnt = 1; // 默认的子树的大小以及出现的次数肯定为1
    return idx;                     // 返回用过的下标（以后会用）
}

Pushup

像线段树一样，二叉搜索树同样也有需要维护的信息：每个子树的本身大小，有二叉树的性质可得出：

void pushup(int u)    // 上传信息
{
    tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + tr[u].cnt;
}

Init

为了防止有时候询问的二叉搜索树为空，我们可以先在树中加入两个哨兵：\text{-INF} 和 \text{INF}，在不断的插入中，他们会始终在树的左右两端，从而有效防止查询越界。

void build()
{
    new_node(-INF), new_node(INF);  // 添加两个哨兵以防止越界RE
    root = 1, tr[1].r = 2;          // 让根节点为1，右子树节点为2
    pushup(root);                   // 上传更新节点大小
}

Insert

根据二叉搜索树的性质可得，对于每个节点 u 以及要插入的权值 k，可以分为四种情况：