数据结构-二叉搜索树 详解

数据结构-二叉搜索树 详解 😊 | Powered By HeartFireY | Binary Search Tree 一、二叉搜索树 简介

二叉搜索树(BST, Binary Search Tree)是一种基于二叉树的树形数据结构，定义(满足的性质)如下

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

不难发现，二叉搜索树是采用递归进行定义的。

我们可以通过例子来具体了解二叉搜索树的结构，如图所示是一颗二叉搜索树：

二叉搜索树的基本操作所花费的时间与树的高度成正比。对于一个有 n n n个节点的二叉搜索树：

• 最优时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)，此时左右平衡
• 最差时间复杂度为 O ( n ) O(n) O(n)，此时二叉搜索树退化为链

二、二叉搜索树-基本操作

我们采用数组表示法来储存一棵搜索树：

int val[x];		//节点x所储存的值
int cnt[x];		//节点x所储存的值出现的次数
int siz[x];		//节点x的子树大小
int lc[x];		//节点x的左孩子
int rc[x];		//节点x的右孩子

为了说明方便，我们定义 h h h表示二叉树的高度。

1.插入操作

二叉搜索树的建树逻辑是比较简单的，假设我们需要向以 r o o t root root为根节点的二叉搜索树中插入一个值为 v v v的新节点。

定义该操作为 i n s e r t ( r o o t , v ) insert(root, v) insert(root,v)，则步骤总结如下：

1. 判断 r o o t root root是否为空树，如果为空树则建立根节点直接存放数据；
2. 如果 r o o t root root的权值等于 v v v，则该节点对应出现的次数自增 1 1 1次；
3. 如果 r o o t root root的权值大于 v v v，则递归向 r o o t root root的左子树中插入 v v v；
4. 如果 r o o t root root的权值小于 v v v，则递归向 r o o t root root的右子树中插入 v v v。

根据步骤，我们可以写出插入操作的代码：

void insert(int &root, int v){
    if(!root){
        val[root = ++sum] = v, cnt[root] = siz[root] = 1;
        lc[root] = rc[root] = 0;
        return;
    }
    siz[root]++;
    if(val[root] == v){
        cnt[root]++;
        return;
    }
    if(val[root] > v) insert(lc[root], v);
    if(val[root]  1){
            cnt[root]--;
            return;
        }
        if(lc[root] && rc[root]) root = delmin(rc[root]);
        else root = lc[root] + rc[root];
        return;
    }
    if(val[root] > v) del(lc[root], v);
    if(val[root]