首页
学习
活动
专区
圈层
工具
发布

【C++】二叉搜索树(搜索二叉树)

本篇聊聊二叉搜索树,二叉树基本知识的详细讲解在【数据结构】二叉树 。...1.二叉树搜索的概念及性能 1.1 概念 ⼆叉搜索树⼜称⼆叉排序树,它有可能是⼀棵空树,或者是具有以下性质的⼆叉树: 若它的左⼦树不为空,则左⼦树上所有结点的值都⼩于或等于根结点的值 若它的右⼦树不为空...最优情况下:⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树),其⾼度为: 最坏情况下:⼆叉搜索树退化为单⽀树(或者类似单⽀),其⾼度近似为节点个数: 所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为: 那么这样的效率显然是...在BSTree.h里先建立一下二叉搜索树的节点的结构,放一些需要用到的头文件。...2.2 插入数据 二叉搜索树的插⼊逻辑如下: 树为空,则直接新增结点,赋值给root指针。

82610
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    二叉树——700.二叉搜索树中的搜索

    1 题目描述 给定二叉搜索树(BST)的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 null 。...problems/search-in-a-binary-search-tree 2 题目示例 3 题目提示 数中节点数在 [1, 5000] 范围内 1 <= Node.val <= 10^7 root 是二叉搜索树...1 <= val <= 10^7 4 思路 方法一:递归 二叉搜索树满足如下性质: 左子树所有节点的元素值均小于根的元素值; 右子树所有节点的元素值均大于根的元素值。...复杂度分析 时间复杂度:O(N),其中N是二叉搜索树的节点数。最坏情况下二叉搜索树是—条链,且要找的元素比链末尾的元素值还要小(大),这种情况下我们需要递归N次 空间复杂度:O(N)。...复杂度分析 时间复杂度:O(N),其中N是二叉搜索树的节点数。最坏情况下二叉搜索树是—条链,且要找的元素比链末尾的元素值还要小(大),这种情况下我们需要迭代Ⅳ次 空间复杂度:O(1)。

    84920

    二叉搜索树

    二叉查找树满足以下性质:(假设二叉查找树中每个节点元素都是不同的,它也可以为空) 非空左子树的所有键值小于其根节点的键值; 非空右子树的所有键值大于其根节点的键值; 左,右两棵子树都是二叉搜索树 二叉搜索树本质上还是一棵二叉树...对二叉搜索树的遍历和创建操作与普通二叉树一致。但是二叉搜索树的特点使得对它的查找,插入,删除变得有些不同。 二叉搜索树的平均深度是O(logn)的,一般不会造成爆栈的。...二叉搜索树则可以支持插入和删除操作,它使得查找的范围可以动态变化,称之为动态查找。...如果按照查找操作是如何进行的来分类,那么二叉搜索树和二分查找都是基于比较实现的;另外一种实现查找的方式是基于映射实现的,即:散列表,或者称之为哈希表。...BST 二叉搜索树操作集的C++实现代码: #include "searchtree.h" //递归版本实现的查找函数,二叉树的平均深度是O(log n),可以递归的 Position Find(ElementType

    99620

    二叉搜索树

    二叉搜索树的查找 2. 二叉搜索树的插入 3. 二叉搜索树的删除 4....拷贝构造函数以及重载运算符=的实现 5.析构函数 二叉搜索树的完整代码: 三、二叉搜索树的KV用法 ---- 一、概念 二叉搜索树又称二叉排序树,它或者是一棵空树 , 或者是具有以下性质的二叉树:...二叉搜索树的查找 从根开始比较,查找,比根大则往右边走查找,比根小则往左边走查找。...二叉搜索树的插入 树为空,则直接新增节点,赋值给root指针 树不空,按二叉搜索树性质查找插入位置,插入新节点(一颗二叉搜索树不能存在同样的数据) 代码实现: bool Insert(const K...二叉搜索树的删除 首先查找元素是否在二叉搜索树中,如果不存在,则返回, 否则要删除的结点可能分下面四种情 况: 要删除的结点无孩子结点或者要删除的结点只有右孩子结点:删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点

    1K40

    二叉搜索树

    一、二叉搜索树的概念 ⼆叉搜索树⼜称⼆叉排序树,它可以是⼀棵空树,或者是具有以下性质的⼆叉树: 若它的左⼦树不为空,则左⼦树上所有结点的值都⼩于等于根结点的值 若它的右⼦树不为空,则右⼦树上所有结点的值都...⼤于等于根结点的值 它的左右⼦树也分别为⼆叉搜索树 如下: ⼆叉搜索树中可以⽀持插⼊相等的值,也可以不⽀持插⼊相等的值,具体看使⽤场景定义。...二、二叉搜索树性能 最优情况下,⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树),其⾼度为:O(logN)  最差情况下,⼆叉搜索树退化为单⽀树(类似链表),其⾼度为:O(N)  所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为...:O(N)          如果要追求较高的查找、插入和删除效率,通常会选择使用平衡二叉搜索树(如AVL树、红黑树等),这些树通过特定的旋转操作来保持树的平衡,从而确保操作的时间复杂度保持在O(log...三、二叉搜索树的增删查 1.插入 1.树为空树:直接新增节点赋值给root 2.树不为空:按⼆叉搜索树性质,插⼊值⽐当前结点⼤往右⾛,插⼊值⽐当前结点⼩往左⾛,找到空位置,插⼊新结点。 3.

    62910

    二叉搜索树

    二叉搜索树 1.1 二叉搜索树的概念 二叉搜索树是在普通的二叉树上进阶的,所以咱们今天的内容也可以说是,数据结构二叉树的进阶。...二叉搜索树可谓是起到了承上启下的作用,向前承接了数据结构的二叉树,向后对于map和set的模拟实现也起到了启示作用。 那什么是二叉搜索树呢?...我们对于具有以下特征的二叉树为二叉搜索树: 若左子树不为空,则左子树所有节点的值比根节点的值小 若右子树不为空,则右子树所有节点的值比根节点的值大 左右子树都是二叉搜索树 1.2 二叉搜索树的常用操作以及实现...1.2.1 二叉搜索树的查找操作 查找操作要求我们从跟开始找,如果要找的值小于根节点的值,则走左子树,反之走右子树。...二叉搜索树的性能分析 对于比较完美的搜索树,比如下图左边这种情况: 这种时间复杂度是O(logN)的。 而对于右边的这种极端情况,时间复杂度是O(N)的。

    55210

    二叉搜索树

    前言 二叉搜索树的定义: 若左子树不为空,则左子树上所有节点的值都小于根节点的值; 若右子树不为空,则右子树上所有节点的值都大于根节点的值。 树中不会有重复的元素。...二叉搜索树最左侧结点一定是最小的,最右侧一定是最大的; 对二叉搜索树进行中序遍历,一定能够得到一个有序序列。...null){ tmp1 = tmp; tmp = tmp.left; } return tmp1; } 最优情况下:二叉搜索树为完全二叉树...,其平均比较次数为:log2 (n) 最坏情况下:二叉搜索树退化为单支树,其平均比较次数为:n/2 四、完整代码 public class BinarySearchTree { static...tmp1 = tmp; tmp = tmp.left; } return tmp1; } } ---- 结语 代码链接在这里哦~ 二叉搜索树

    60030

    二叉搜索树

    在计算机术语中,二叉搜索树又叫二叉查找树、二叉排序树。...二叉搜索树(Binary Search Tree)的定义: 它或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值...; 它的左、右子树也分别为二叉搜索树。...好吧,不管我解释的清不清楚,下面来看一张图就知道了: ? 一个典型的二叉搜索树。对照定义看看就很清楚了,那么,问题来了,怎么构造二叉搜索树呢?...其实核心思想也是对节点的值进行寻找,如果找到了就删除这个节点并且连接对应节点,那么怎么确定这个“对应节点”呢?我们要注意定义中说明的:一个二叉搜索树的左右子树也是二叉搜索树(如果存在)。

    1.4K20

    二叉搜索树

    一、操作: 判断元素是否存在:递归的在左右子树中查找 查找最小元素:在左子树中递归或者循环 查找最大元素:在右子树中递归或循环 插入:递归的插入,大于则插入在节点的右子树,小于则左子树,等于则是重复节点不作处理...删除:递归删除( 或者说递归查找需要删除的元素 ),找到该元素后,如果元素有两个子节点那么久找到这个元素的右子树的最小元素代替要删除的元素,然后再删除那个右子树上的最小元素。...如果只有一个子节点直接让要被删除的节点赋值上他的子节点。...else if (result < 0) { root.rChild = remove(ele, root.rChild); } //这个地方就是递归的结束条件...也就是当我们找到了要删除的节点,这时候要分情况如果两个子节点都不空我们需要把右子树的最小值的替换到当前节点然后删除右子树最小节点 //当有一个或者0个节点的时候我们只需要把左边或者右边挂上去就行

    98650

    二叉搜索树

    二叉搜索树概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值...它的左右子树也分别为二叉搜索树 二叉搜索树实现 结构框架 template struct BSTreeNode { BSTreeNode *left; BSTreeNode...,指向cur的左 如果,cur为父亲的右,那么让父亲的右,指向cur的右 情况3、左右孩子都不为空 找右树的最小节点,也就是右树的最左 找左树的最大节点 ,也就是左树的最右 情况1 情况2 非递归代码...parent->right = cur->left; } } delete cur; } else { //左右孩子都不为空 //先找当前节点右树的最小节点...= cur->right; while (min->left) { parent = min; min = min->left; } //找到了右树的最左节点

    65920

    二叉树搜索树

    二叉搜索树 什么是二叉搜索树? 二叉搜索树首先是个二叉树,这个二叉树有这么一个特点,左子树的所有节点都比根节点小,右子树的所有节点都比根节点大。...并且左右子树也都满足这个条件 二叉搜索树又叫二叉排序树,因为它的中序遍历是有序的。...二叉搜索树的实现——K模型 K模型只存k值 二叉搜索树的每一个节点都有一个值,以及两个指针,指向左节点的指针,指向右节点的指针。...有很多要注意的地方,因为删除之后要保证该树依然是搜索二叉树。...,用来修改值 插入还是和k模型差不多 删除没有改变,还是按键K进行删除 源码在本博客代码链接 二叉搜索树的性能分析 对于它的查找的时间复杂度O(h),h为数的高度,当该二叉树是个单支树的话,复杂度为

    57320

    【C++二叉搜索树】树语静谧:探寻二叉搜索树的内在秩序

    1.二叉搜索树的概念 二叉搜索树又称二叉排序树,它或者是一棵空树,或者是具有以下性质的二叉树: 若它的左子树不为空,则左子树上所有结点的值都小于等于根结点的值 若它的右子树不为空,则右子树上所有结点的值都大于等于根结点的值...2.底层结构要求是数组,头部或者中间插入删除数据效率很低 排序的话那么就是按照中序遍历的话,那么整个排序出来的数组就是升序的,所以搜索二叉树的功能之一是排序 2.二叉树搜索的性能分析 最优情况下,二叉搜索树为完全二叉树...(或者接近完全二叉树),其高度为:log2N 最差情况下,二叉搜索树退化为单支树(或者类似单支),其高度为:N 所以综合而言二叉搜索树增删查改时间复杂度为:0(N) 那么这样的效率显然是无法满足我们需求的...,我们后续课程需要继续讲解二叉搜索树的变形,平衡二叉搜索树AVL树和红黑树,才能适用于我们在内存中存储和搜索数据。...下面两个都是二叉搜索树 二叉树效率不错的前提是左右节点比较均衡接近完全二叉树 3.二叉搜索树的插入 插入的具体过程如下: 1.树为空,则直接新增结点,赋值给root指针 2.树不空,按二叉搜索树性质,插入值比当前结点大往右走

    54110

    LeetCode96|二叉搜索树中的搜索

    1,问题简述 给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。...2,示例 例如, 给定二叉搜索树: 4 / \ 2 7 / \ 1 3 和值: 2 你应该返回如下子树: 2.../ \ 1 3 在上述示例中,如果要找的值是 5,但因为没有节点值为 5,我们应该返回 NULL。...3,题解思路 递归方法+二叉树的有序性 4,题解程序 public class SearchBSTTest { public static void main(String[] args) {...6,总结 这道题还是比较容易理解的,理解二叉树的特点和数据的有序性是非常有必要的,二叉树的遍历方式,二叉树的节点特点都是我们需要掌握的

    79940
    领券