首页 > 其他分享 >二叉搜索树(BST)

二叉搜索树(BST)

时间:2023-12-15 14:46:29浏览次数:36  
标签:Node return val BST 二叉 int 搜索 键值 root

\(INF\)表示无效值的常量,\(Node\)表示二叉搜索树的结点,\(key、count、left、right\)分别表示节点的键值、数量、左孩子、右孩子,\(size\)表示以该节点为根的子树大小,\(root\)表示树的根节点。

\(private\)中的函数解析见注释。

\(public\)中:\(empty\):判断树是否为空,时间复杂度:\(O(1)\)。

以下操作时间复杂度相同,均为期望\(O(logn)\),最坏\(O(n)\)。

\(Max\):求树中最大键值。 \(Min\):求树中最小键值。 \(insert(val)\):向树中插入键值为\(val\)的节点。

\(count(val)\):求键值为\(val\)的节点数量。 \(erase(val, cnt)\):删除\(cnt\)个键值为\(val\)的节点。

\(rank(val)\):求键值\(val\)的排名。(排名定义为比当前键值小的键值的个数加一) \(kth(val)\):求第\(k\)小的键值。

\(prev(val)\):求键值\(val\)的前驱。(前驱定义为小于\(val\),且最大的键值)

\(next(val)\):求键值\(val\)的后继。(后继定义为大于\(val\),且最小的键值)

class BinarySearchTree
{
private:
    int INF = 0x3f3f3f3f;
    struct Node 
    {
        int key, size = 1, count = 1;
        Node *left = nullptr, *right = nullptr;
        Node(int key) : key(key) {}
    };

    Node *root = nullptr;

    Node *FindMinNode(Node *root) // 在以root为根的子树中查找最小节点
    {
        if (!root) return root;
        while (root->left) root = root->left;
        return root;
    }

    Node *FindMaxNode(Node *root) // 在以root为根的子树中查找最大节点
    {
        if (!root) return root;
        while (root->right) root = root->right;
        return root;
    }

    int FindMin(Node *root) // 在以root为根的子树中查找最小键值
    {
        root = FindMinNode(root);
        return (root ? root->key : INF);
    }

    int FindMax(Node *root) // 在以root为根的子树中查找最大键值
    {
        root = FindMaxNode(root);
        return (root ? root->key : INF);
    }

    int count(Node *root, int val) // 在以root为根的子树中查找键值为val的数量
    {
        if (!root) return 0;
        if (root->key == val) return root->count;
        else if (val < root->key) return count(root->left, val);
        else return count(root->right, val);
    }

    Node *insert(Node *root, int val) // 在以root为根的子树中插入键值为val的节点
    {
        if (!root) return new Node(val);
        root->size++;
        if (val < root->key) root->left = insert(root->left, val);
        else if (val > root->key) root->right = insert(root->right, val);
        else root->count++;
        return root;
    }

    Node *erase(Node *root, int val, int cnt) // 在以root为根的子树中删除cnt个键值为val的节点
    {
        if (!root) return root;
        root->size -= cnt;
        if (val < root->key) root->left = erase(root->left, val, cnt);
        else if (val > root->key) root->right = erase(root->right, val, cnt);
        else 
        {
            if (root->count > cnt) root->count -= cnt;
            else 
            {
                if (!root->left)
                {
                    Node *temp = root->right;
                    delete root;
                    return temp;
                } 
                else if (!root->right) 
                {
                    Node *temp = root->left;
                    delete root;
                    return temp;
                } 
                else 
                {
                    Node *successor = FindMinNode(root->right);
                    root->key = successor->key;
                    root->count = successor->count;
                    root->right = erase(root->right, successor->key, successor->count);
                }
            }
        }
        return root;
    }

    int rank(Node *root, int val) // 计算键值为val的排名
    {
        if (!root) return 1;
        if (val == root->key) return (root->left ? root->left->size : 0) + 1;
        if (val < root->key) return rank(root->left, val);
        return rank(root->right, val) + root->count + (root->left ? root->left->size : 0);
    }

    int kth(Node *root, int k) // 计算排名为k的键值
    {
        if (!root) return INF;
        int leftSize = (root->left ? root->left->size : 0);
        if (leftSize >= k) return kth(root->left, k);
        if (leftSize + root->count >= k) return root->key;
        return kth(root->right, k - leftSize - root->count);
    }
public:
    bool empty(){return !root;}
    int Max(){return (root ? FindMax(root) : INF);}
    int Min(){return (root ? FindMin(root) : INF);}
    void insert(int val){root = insert(root, val);}
    int count(int val){return count(root, val);}
    void erase(int val, int cnt = 1){cnt = min(cnt, count(val)); if (cnt) root = erase(root, val, cnt);}
    int rank(int val){return rank(root, val);}
    int kth(int k){return kth(root, k);}
    int prev(int val){return kth(rank(val) - 1);}
    int next(int val){return kth(rank(val + 1));}
} BST;

标签:Node,return,val,BST,二叉,int,搜索,键值,root
From: https://www.cnblogs.com/xiojoy/p/17903320.html

相关文章

  • 搜索引擎优化方式•SEO搜索引擎优化原理
    搜索引擎优化方式•SEO搜索引擎优化原理搜索引擎优化的根本,是指利用搜索引擎工作的基本原理,采用互联网数据分析的结果,用关键词选取与投放、网络平台的选取与投放、网站结构的调整来进行优化,是优化者结合搜索引擎工作原理与互联网消费者的行为数据分析,提高企业排名的优化方式。......
  • Flutter 自带的搜索组件
    效果如下官方需要重写四个关键方法classsearchBarDelegateextendsSearchDelegate<String>{/*这个方法返回一个控件列表,显示为搜索框右边的图标按钮,这里设置为一个清除按钮,并且在搜索内容为空的时候显示建议搜索内容,使用的是showSuggestions(context)方法:*/@overrid......
  • Acwing秋季每日一题补题---搜索字符串
    搜索字符串题目链接思路:字符串哈希+滑动窗口当然因为符合题意的子串会重复,所以我们要考虑去重的问题代码:#include<bits/stdc++.h>usingnamespacestd;#defineintunsignedlonglongconstintN=2e5+10;constintP=131;chara[N],b[N];//字符串intcnt[26];//统......
  • 655. 输出二叉树(中)
    目录题目题解题目给你一棵二叉树的根节点root,请你构造一个下标从0开始、大小为mxn的字符串矩阵res,用以表示树的格式化布局。构造此格式化布局矩阵需要遵循以下规则:树的高度为height,矩阵的行数m应该等于height+1。矩阵的列数n应该等于2的(height+1)次......
  • 【GUI软件】小红书搜索结果批量采集,支持多个关键词同时抓取!
    目录一、背景介绍1.1爬取目标1.2演示视频1.3软件说明二、代码讲解2.1爬虫采集模块2.2软件界面模块2.3日志模块三、获取源码及软件一、背景介绍1.1爬取目标您好!我是@马哥python说,一名10年程序猿。我用python开发了一个爬虫采集软件,可自动按关键词抓取小红书笔记数据。......
  • 第六节:二叉树详解
    一.        二.        三.         !作       者:Yaopengfei(姚鹏飞)博客地址:http://www.cnblogs.com/yaopengfei/声     明1:如有错误,欢迎讨论,请勿谩骂^_^。声     明2:原创博客请在转载......
  • 543. 二叉树的直径
    1.题目介绍给你一棵二叉树的根节点,返回该树的直径。二叉树的直径是指树中任意两个节点之间最长路径的长度。这条路径可能经过也可能不经过根节点\(root\)。两节点之间路径的长度由它们之间边数表示。示例1:输入:root=[1,2,3,4,5]输出:3解释:3,取路径[4,2,1,3]......
  • 101. 对称二叉树
    1.题目介绍给你一个二叉树的根节点\(root\),检查它是否轴对称。示例1:输入:root=[1,2,2,3,4,4,3]输出:true示例2:输入:root=[1,2,2,null,3,null,3]输出:false提示:树中节点数目在范围\([1,1000]\)内\(-100<=Node.val<=100\)进阶:你可以运用递归和迭代两种......
  • 226. 翻转二叉树
    1.题目介绍给你一棵二叉树的根节点\(root\),翻转这棵二叉树,并返回其根节点。示例1:输入:root=[4,2,7,1,3,6,9]输出:[4,7,2,9,6,3,1]示例2:输入:root=[2,1,3]输出:[2,3,1]示例3:输入:root=[]输出:[]提示:树中节点数目范围在\([0,100]\)内\(-100<=Node.val......
  • C++堆——heap与二叉树和python
    数据结构栈-->stack队列-->queue树-->tree堆-->heap散列-->hash图-->graph图结构一般包括顶点和边邻接矩阵DAG,DirectedAcyclicGraph即「有向无环图」树树(Tree)是一种非线性的数据结构,由n个节点组成,其中每个节点都有零个或多个子节点。......