Binary Search Tree | 二叉查找树

参考书：胡凡、曾磊《算法笔记》

二叉查找树BST

• 又称为排序二叉树、二叉搜索树、二叉排序树
• BST 是数据域有序的二叉树。

递归定义

• 一棵空树
• 由根结点、左子树、右子树组成，其中左子树、右子树都是二叉查找树，且左子树上所有结点的数据域均小于等于根结点的数据域，右子树上所有结点的数据域均大于根结点的数据域。

性质

BST的中序遍历结果是有序的。

BST的基本操作

查找

区别于普通二叉树的查找（递归遍历左右子树），BST的查找是每次选择一棵子树查找，是从树根到查找结点的一条路径。
最坏复杂度 O（h），h是二叉查找树的高度。
void search(Node* root, int x)

• 当前root为空，查找失败
• x == root->data，查找成功
• x < root->data，search(root->lchild, int x)
• x > root->data，search(root->rchild, int x)

插入

先查找， 查找成功，结点已存在，不用插入；查找失败，root == NULL，在此处插入
复杂度O（h），h是二叉查找树的高度。
⚠️可能改变树的结构，故要传引用！！！
void insert(Node* &root, int x)

建BST

Node* CreateBST(int data[], int nn)
一组相同的数字，仅仅插入顺序不同，生成的二叉树结构也可能不同。

删除

void delete(Node* &root, int x)
⚠️ 传引用
要保证删除操作后仍然是二叉查找树。
复杂度O（h），h是二叉查找树的高度。

1. root == NULL，不存在权值为x的结点
2. root->data == x

• 是叶子结点，直接删除，root = NULL
• 有左孩子，在左子树中找pre（不断往右），用pre的权值覆盖root，然后删除pre
• 有右孩子，在右子树中找后继next（不断往左），用next的权值覆盖root，然后删除next

3. root->data > x，在左子树中递归
4. root->data < x，在右子树中递归

重要概念

前驱 — BST中比结点权值小的最大结点
后继 — BST中比结点权值大的最小结点

图源：巴特曼@cnblogs
总是优先删除前驱/后继，容易使树的左右子树高度极度不平衡，甚至使BST退化为一条链。

Solution：

1. 交替删除前驱、后继
2. 记录子树高度，从较高子树删除结点

例题

1043 Is It a Binary Search Tree (25 分)
给定二叉树的插入序列s，问序列s是否是该二叉树或该二叉树左右子树对调后二叉树的先序遍历序列。若是，输出对应的后序遍历序列。
⚠️允许插入key相同的结点（右子树结点key >= 根结点的key）
⚠️插入时，必须有root->lchild = NULL, root->rchild = NULL;

#include <cstdio>
#include <vector>

using namespace std;
struct Node {
    int key;
    Node *lchild, *rchild;
};
int nn, cnt1 = 0, cnt2 = 0;
vector<int> seq;

void insertNode(Node *&root, int x) {
    if (root == NULL) {
        root = new Node;
        root->key = x;
        root->lchild = NULL, root->rchild = NULL;
    } else {
        if (x < root->key) {
            insertNode(root->lchild, x);
        } else insertNode(root->rchild, x);
    }
}

void pre_order(Node *root) {
    if (root->key == seq[cnt1]) cnt1++;
    else return;
    if (root->lchild) pre_order(root->lchild);
    if (root->rchild) pre_order(root->rchild);
}

void mirror_pre_order(Node *root) {
    if (root->key == seq[cnt2]) cnt2++;
    else return;
    if (root->rchild) mirror_pre_order(root->rchild);
    if (root->lchild) mirror_pre_order(root->lchild);
}

void post_order(Node *root) {
    if (root == NULL) return;
    if (root->lchild) post_order(root->lchild);
    if (root->rchild) post_order(root->rchild);
    printf("%d", root->key);
    cnt1--;
    if (cnt1 > 0) printf(" ");
}

void mirror_post_order(Node *root) {
    if (root == NULL) return;
    if (root->rchild) mirror_post_order(root->rchild);
    if (root->lchild) mirror_post_order(root->lchild);
    printf("%d", root->key);
    cnt2--;
    if (cnt2 > 0) printf(" ");
}

int main() {
    Node *root = NULL;
    scanf("%d", &nn);
    int temp;
    for (int i = 0; i < nn; ++i) {
        scanf("%d", &temp);
        seq.emplace_back(temp);
        insertNode(root, temp);
    }
    pre_order(root);
    if (cnt1 == nn) {
        puts("YES");
        post_order(root);
    } else {
        mirror_pre_order(root);
        if (cnt2 == nn) {
            puts("YES");
            mirror_post_order(root);
        } else puts("NO");
    }
    return 0;
}