BST和Splay树中1…n个键的插入操作的复杂度是多少？
BST（Binary Search Tree）和Splay树是两种常见的二叉搜索树数据结构。在这两种树中，1…n个键的插入操作的复杂度分别如下：
- BST（二叉搜索树）的插入操作复杂度：
- 平均情况下，BST的插入操作的时间复杂度为O(log n)。这是因为BST的插入操作是根据键的大小进行比较，并根据比较结果选择左子树或右子树进行插入，每次插入都将搜索范围减半，因此平均情况下的时间复杂度为对数级别。
- 最坏情况下，BST的插入操作的时间复杂度为O(n)。当BST退化为链表形式时，每次插入都需要遍历整个链表，因此最坏情况下的时间复杂度为线性级别。
- Splay树的插入操作复杂度：
- 平均情况下，Splay树的插入操作的时间复杂度为O(log n)。Splay树通过旋转操作将最近访问的节点移动到根节点，从而提高了后续操作的效率。插入操作会导致被插入的节点成为新的根节点，因此平均情况下的时间复杂度为对数级别。
- 最坏情况下，Splay树的插入操作的时间复杂度为O(n)。当Splay树退化为链表形式时，每次插入都需要遍历整个链表，并进行多次旋转操作，因此最坏情况下的时间复杂度为线性级别。
总结：BST和Splay树中1…n个键的插入操作的复杂度分别为O(log n)和O(n)。需要注意的是，这里的复杂度分析是基于平均情况和最坏情况的，具体的时间复杂度可能会受到树的平衡性、插入顺序等因素的影响。
相关·内容
2回答
基于值的二叉树复杂度
、、、、
我用C语言创建了一个二进制搜索树，当我测试我的树时，插入和搜索操作需要不同的时间来执行。例如，我有两个场景，从1到10000插入随机值，从1到10000插入排序值。当我将1到10000的随机值插入到我的BST中时，它比将排序值从1插入到我的BST所花费的时间要少。
同样，在我的BST中执行搜索操作时，在那些随机值中搜索所花费的时间较少，但在BST中搜索排序值时所需时间太长。现在，问题是时间的复杂性，谁能解释一下，这是如何处理的？这四种情况的时间复杂度是多少？
注意：插入和搜索这些排序的值几乎要花费相同的时间，仍然需要更长的时间！
浏览 2提问于2018-12-05得票数 0
回答已采纳
我很好奇你们是否知道这个问题的答案。
我们知道，平均插入BST成本是O(log n)，而最坏的情况下，AVL/Splay的平均成本是O(log n)。
由于我们正在插入n时间(基本上是在构建一棵树)，我们将收到最终成本为n*logn。
我们怎么能证明我们不能比这更低呢？这是很容易观察，但有点难以证明。
也许我们可以使用递归方程，并以某种方式限制它们？
提前谢谢。
浏览 2提问于2021-01-07得票数 0
回答已采纳
1回答
因为splay树用于缓存，所以我想知道当我想要高效缓存时，Splay树比HashTable有什么优势？
什么时候我应该更喜欢splay树而不是哈希表？
我猜这是一个比BST更专业的案例，请不要链接到BST vs Hashtable答案。
浏览 0提问于2017-11-28得票数 4
splay树中的每个字典操作都使用splay操作将一个节点带到树根。这种splay操作的摊还效率通常用潜在的方法进行分析，并在许多在线源(包括wikipedia)页面中进行描述。然后，摊销操作的摊销时间报告为O(m n)。
但是，我找不到对完整字典操作的实际分析，例如插入、删除、.这些操作中的每一个，除了一个splay操作之外，还通过树向下搜索以找到要插入或删除的节点的正确位置。只有在找到该节点之后，才能启动splay操作。
人们倾向于发表如下声明：
“在我们的分析中，我们注意到执行搜索、插入或删除的时间与相关的播放时间成正比”，古德里奇书第456页题为“C++中的数据结构和算法”。
浏览 4提问于2020-08-13得票数 2
我不能回答一个问题，你能帮我吗？
For i=1 to i=n/2, if A[i]<=A[2i] and A[i]<=A[2i+1] A is called as a "bst"
在一个有n个元素的bst中寻找kth最小元素的时间复杂度是多少？
浏览 0提问于2015-06-14得票数 3
考虑使用二进制搜索树对n个元素的列表进行排序的以下算法：
initialise t to be an empty binary search tree
for each element x in the list,
add x to t
while t is not empty,
remove and print the smallest element of t
如果使用以下方式实现树，则此算法的最坏时间复杂度是多少：
a)一个普通的二叉搜索树？
b) AVL树？
我的解决方案:我认为的解决方案，对于AVL树: O(Log N)，对于BST，它将是O(N)
浏览 5提问于2014-12-22得票数 0
回答已采纳
2回答
我有一个函数，它使用BST对数组进行排序。首先，我使用for循环和函数插入(在树中插入数据保持顺序)创建树，然后按顺序访问树，并以排序模式在新的临时存档中复制每个节点。这是我的代码：
double btree_sort(SPerson Archive[], unsigned int ne, double *btree_creating_time)
{
int i = 0;
TBinaryTree BinaryTree = NULL;
cont = 0;
LARGE_INTEGER freq;
LARGE_INTEGER t0, tF, tDiff;
QueryPerformance
浏览 3提问于2016-02-16得票数 1
回答已采纳
1回答
此问题与相关
我正在尝试实现一个泛型函数，它在给定一定范围的连续整数值[m...n] where n>=m的情况下生成所有结构上等价的BST。例如，我们可以有(n,m) = (1,9)和(n,m) = (5,13)，其中两者的大小都是9。这两个范围在结构方面将生成相同的BST，只是值不同。在这种情况下，我们将1换成5，2换成6，...，9换成13，反之亦然。
所以我想设计一些函数，为一些输入n-m+1生成结构上等价的树，存储这些结构上等价的n,m，然后能够插入任何BST，并让它给我所有的结构等价，节点值在n...m范围内。我不想为将来相同范围大小的输入重新生成BST。
Leetcode问
浏览 0提问于2019-04-07得票数 0
给定一个整数数组，将每个数字ai替换为其右侧的下一个更高的数字(根据值)，其值更接近
例如
输入->3 7 5
输出-> 5 7 5
输入->3 6 2 6 4 7 1
输出->4 7 4 7 7 7 1
这个问题是在一次采访中提出的。
如果从右开始，在BST中插入每个元素，然后在BST中找到更接近的值，但这种方法在最坏的情况下也是O(n^2)。
有没有针对这一点的优化方法？
浏览 2提问于2014-01-05得票数 0
1回答
展开树:最坏情况序列
、、、
我想尝试在Splay树上执行最坏情况的序列。
但是，在展开树上最坏的序列是什么？有没有什么方法可以很容易地计算出插入到树中的关键字？
有谁能帮我吗？
浏览 1提问于2015-04-01得票数 1
1回答
我正在学习AVL树。AVL树是通过旋转来平衡自身的二进制搜索树。因为它们是平衡的，所以查询时间是O(log )。但是添加条目的顺序对于避免每次插入的最坏情况O(log )旋转也很重要。
它的渐近运行时间是多少：
(a)在AVL树中添加n个具有连续键的条目(插入所有条目的时间，而不是每个条目)
b)搜索不在树中的关键字。
我所理解的是这个高度是O(log )，所以插入到AVL树中的最坏情况是O(log )。搜索AVL树完全不同于BST，因此也需要与树的高度成比例的时间，使得O(log )。
这是正确的吗？
浏览 0提问于2020-10-14得票数 0
1回答
我在中读了一篇关于如何使用平衡BST实现字典的文章，并发现了这一行：
如果将密钥存储在二叉树中，则良好平衡的BST将需要与M* log N成正比的时间，其中M是最大字符串长度，N是树中的键数。
我不明白这怎么会是O(M*logn)，考虑到平衡的BST总是保持O(logn)的最大高度，这不是(logn)吗？
浏览 2提问于2022-01-31得票数 0
回答已采纳
1回答
基于逻辑，我自己实现了二叉树插入方法。那么，在插入和搜索(使用您自己的搜索方法，如inorder，preorder，postorder)时，是否有人可以验证代码是否工作正常？ 并且还可以找到代码的时间复杂度。 public void insert(int data) {
Node node = new Node(data);
if (root == null) {
root = node;
size++;
} else {
Node n = root;
if (data > n.data) {
浏览 11提问于2020-09-22得票数 1
回答已采纳
2回答
堆可以在O(n logn)时间内从列表中构造，因为将元素插入堆需要O(logn)时间，并且有n个元素。
类似地，可以从O(n logn)时间的列表中构造二进制搜索树，因为将一个元素插入到BST需要平均的日志时间，并且有n个元素。
从min到max遍历堆需要O(n logn)时间(因为我们必须弹出n个元素，而且每个pop都需要O(logn)接收器操作)。从最小到最大遍历BST需要O(n)时间(字面上只是顺序遍历)。
因此，在我看来，构建这两个结构需要相同的时间，但是BST迭代速度更快。那么，为什么我们使用“Heap排序”而不是"BSTsort“呢？
编辑:谢谢Tobias和lrlreon
浏览 1提问于2017-12-25得票数 10
回答已采纳
1回答
我已经用Java实现了splay树(插入、搜索、删除操作)。现在我想检查算法的复杂度是否为O(logn)。有没有办法通过改变输入值(节点数)并检查以秒为单位的运行时间来检查这一点？比如说，通过输入像1000,100000这样的输入值并检查运行时，还有没有其他方法？
浏览 1提问于2016-11-11得票数 1
在大学里，我必须实现一个n元树，并插入一个节点作为另一个节点的子节点，复杂度是O (n)，因为我必须遍历它并寻找插入它的父亲，而且由于它没有被组织起来(像BST)，我没有办法减少搜索。我的问题是:是否有可能在n元树中实现比O (n)更短的时间来插入、删除、获取父级和类似的操作？
浏览 1提问于2018-02-20得票数 0
3回答
链表
对于实际操作，链表的插入时间复杂度为O(1)，但需要O(n)时间遍历到正确的位置。大多数在线资源将链接列表的平均插入时间列为O(1)：
https://stackoverflow.com/a/17410009/10426919
https://www.bigocheatsheet.com/
https://www.geeksforgeeks.org/time-complexities-of-different-data-structures/
BST
二进制搜索树的插入需要遍历节点，所需时间为O(log )。
问题
Am I mistaken to believe that insert
浏览 2提问于2021-10-13得票数 4
回答已采纳
我正在用JavaScript进行这个实现，这是我被要求解决的。我想得到一些代码审查。
/**
* Binary Search Tree
*
* TreeNode class
*
* Create a TreeNode class
* The TreeNode class should contain the following properties:
*
*
*
* BinarySearchTree class.
*
* Create a BinarySearchTree class
*
浏览 0提问于2018-08-13得票数 1
2回答
我正在从事一个关于算法和数据结构类的项目。
如果我有一个二进制搜索树，其中每个节点都包含：
typedef struct Node {
char* name;
List* list;
struct Node *right;
struct Node *left;
} Node;
我想在这个列表中搜索一个确定的值，这个搜索的时间复杂度是多少？我知道列表中搜索的时间复杂度是O(n)，但我也想说明树中搜索的时间复杂性。列表没有排序，BST是按字母顺序排列的。
浏览 4提问于2017-03-18得票数 0
回答已采纳
我觉得这是必须存在的，但我就是想不出来。有没有一种数据结构可以保存已排序的值列表并快速搜索(可能是log(N)时间，就像数组一样)，并且还支持在log(N)或常量时间中插入和删除元素？
浏览 0提问于2013-07-15得票数 1
回答已采纳
3回答
这是我不太明白的。当我阅读堆上的文献时，它总是说堆的最大优点是可以立即获得顶部(如果是最大的堆)元素。但是，您不能使用BST并存储指向同一个节点(最右下角)的指针，并使用插入/删除更新指针吗？
如果我没有弄错的话，用我描述的BST实现
================================================
| Insert | Remove Max
================================================
Special BST | O(log(n)) | O(
浏览 6提问于2022-05-15得票数 2
回答已采纳
我们给出了具有n个节点的BST，这些节点是整数。以排序的顺序打印所有整数的复杂度是多少？有人能帮上忙吗？
浏览 15提问于2019-11-18得票数 0
回答已采纳
哪种数据结构最适合查询，如插入、删除和获取所有值小于给定数字的元素。BST还是优先级队列？或任何其他数据结构。
浏览 14提问于2020-05-26得票数 0
回答已采纳
2回答
给定浮点数的BST和整数的BST。我只是想知道，不同的基于BST的数据类型之间是否存在插入、删除等时间复杂度的差异？
浏览 5提问于2013-10-28得票数 1
回答已采纳
给定一个BST的序遍历，我必须构造BST。我能否简单地通过创建一个空BST，然后从第一个元素开始，以最后一个元素结尾的顺序遍历中的元素插入空BST来构造BST呢？
例如，考虑以下BST：
10
/ \
5 40
/ \ \
1 7 50
它的前置遍历是：
10 5 1 7 40 50
通过创建一个空的BST，然后从第一个元素开始逐个插入预顺序遍历的元素，就可以得到如下解释的确切的BST：
(empty tree)
插入前置遍历的第一个元素: 10
10
插入前置遍历的第二个元素:5
10
/
5
同样，
浏览 0提问于2019-06-08得票数 0
回答已采纳
1回答
展开树删除
、、
我在构思从splay树中删除的过程时遇到了麻烦。给定这个初始的树，我想删除节点78。 ? 根据我的课程中的信息(来自Goodrich，Tamassia和Goldwasser)，BST中被删除的节点应该被从节点执行顺序遍历到达的下一个节点替换，该节点应该是91。然后，此节点应展开到树的顶部。然而，情况并非如此，如这里的可视化工具所示。https://www.cs.usfca.edu/~galles/visualization/SplayTree.html ?
浏览 18提问于2021-11-08得票数 1
回答已采纳
2回答
AVL树与展式树的区别
、、、、
我正在研究各种树木，偶然发现了AVL树和弹奏树。我想知道
AVL树和splay树有什么区别？
我们是在什么基础上挑选这些女士的？
这些树的正面和反面是什么？
这些树在大O表示法方面的表现是什么？
浏览 5提问于2011-09-19得票数 53
回答已采纳
我知道，如果平衡的话，BST的高度是O(log(n))，意思是搜索是O(log(n))，但是将不平衡的树变成平衡的树会增加插入/删除的运行时间，因为在每次插入/删除之后必须重新平衡它。
是否有另一种方法来修改BST，以便在O(log(n))时间内找到Kth最小项，而不影响其他函数的运行时？
浏览 0提问于2013-10-10得票数 2
回答已采纳
3回答
我必须选择哪种操作在AVL树上比BST有更好的最坏情况时间复杂度。我已经确定每个操作的时间复杂度是相同的，这取决于树.
AVL树最糟糕的时间复杂度是..。
Insert - O(log(n))
Remove - O(log(n))
Search - O(log(n))
BST最坏的时间复杂度是..。
Insert - O(height)
Remove - O(height)
Search - O(height)
那么，O(log(n))比O(高度)更复杂吗？
浏览 2提问于2017-12-05得票数 1
回答已采纳
我们正在编写一个项目，其中我们使用链表在BST中添加和减去数字。但是，我们可以添加数字，但不能删除它们。有没有人可以看看我们的删除功能，看看出了什么问题？
// 2016 Spring Data Structure BST Sample Code at MIU (For the project #2)
// You may add/modify the classes but should maintain the basic structure of the classes.
import java.util.*;
import java.util.*;
class Node {
浏览 0提问于2017-05-31得票数 0
1回答
当被要求在给定预订单遍历的情况下创建一个BST时，给出的答案如下：
这需要大量的代码。
我的问题是，为什么我不能直接插入到一个空树中来给我正确的答案呢？有没有简单的插入会导致错误答案的例子？例如，在该链接中给出的示例中，我们使用{10，5，1，7，40，50}作为预订单遍历。但是，仅仅按照预序列表的顺序使用常规的BST insert方法6次，就不会给出相应的树吗？我能得到一个反例和/或解释为什么我是错误的吗？我一直没能想出一个反例。
浏览 2提问于2013-07-14得票数 0
回答已采纳
1回答
BST和RBT插入更糟的情况
、、、、
RBT和BST的插入复杂度为O(logn)。我用Java语言实现了这两种方法，给了它们很多数字，并以秒为单位测量了时间，分析我绘制的performance.The数字似乎表明它是O(n)。有没有人能想到这一点并评论一下为什么会这样？
浏览 6提问于2018-05-13得票数 0
我所说的通用树是指具有多个子节点的不平衡树(不像二叉树那样，每个分支只能有两个子节点)。删除节点、插入节点、查找节点的大O复杂度是多少
浏览 15提问于2017-07-26得票数 1
3回答
对于BST中的每个节点，从该节点到叶子的最长路径长度是多少？(最坏的情况)我认为在最坏的情况下，我们有一条从节点到叶子的线性路径。如果树中有n个节点，则运行时间为O(n*n)。是这样的吗？
浏览 1提问于2016-03-31得票数 0
5回答
树型数据结构
、、
我试着理解什么是排序树，二叉树，avl和...我仍然不确定，排序后的树是如何排序的？在排序的树中搜索和在未排序的树中搜索之间的复杂度(Big-Oh)是多少？希望你能帮助我。
浏览 0提问于2009-05-31得票数 0
回答已采纳
1回答
我在Haskell中实现了一个二进制搜索树
data BST = Nil | Node (BST) Int (BST) deriving Show
emptyTree :: BST
emptyTree = Nil
isEmptyTree :: BST -> Bool
isEmptyTree Nil = True
isEmptyTree _ = False
leftChild :: BST -> BST
leftChild Nil = Nil
leftChild (Node l k r) = l
rightChild :: BST -> BST
rightChild N
浏览 2提问于2017-09-27得票数 1
回答已采纳
2回答
排序依据:二进制搜索树
、、、
我对最坏情况时间和平均情况时间复杂性感到有点困惑。我的困惑来源是
我的目标是按升序缩短数据:我选择BST来完成我的sorting.Here任务，我正在做的打印数据的工作是按升序进行的。
1) Construct a binary search tree for given input.
Time complexity: Avg Case O(log n)
Worst Case O(H) {H is height of tree, here we can Assume Height is equal to number of n
浏览 1提问于2012-05-22得票数 1
回答已采纳
链表需要O(n)来搜索，而BST则需要O(log n)。那么，为什么使用链接列表来处理冲突呢？我能想到的唯一原因是因为插入链接列表是O(1)，而插入BST是O(log )。
浏览 5提问于2015-01-01得票数 3
回答已采纳
1回答
顺序后继法打印BST的时间复杂度
、、、、
我有一个在二进制搜索树(BST)中查找下一个顺序后继的方法。"inorderSuccessor“方法将BST的任何节点作为输入并输出下一个顺序后继节点。方法和树类定义如下：
class BSTInorderSuccessor{
public static Node inorderSuccessor(Node node) {
if (node.right != null) {
return minValue(node.right);
}
Node parent = node.parent;
while (parent != null &am
浏览 3提问于2017-06-13得票数 2
回答已采纳
1回答
我想知道：
使用递归将n个节点插入空高度平衡搜索树的最坏情况是什么时间复杂度？
我知道在平衡BST中插入一个节点的最坏情况是O(logn)。但是，当我将节点插入到空的平衡BST中时，是否存在相同的情况，我对此感到困惑。
浏览 3提问于2022-07-08得票数 -2
回答已采纳
1回答
我有这个代码关于二进制搜索树，我想计算效率的插入，删除和查找最大值和最小值在BST
我把它做成这样的插件
public static void main(String args[]) {
BinarySearchTree bst = new BinarySearchTree();
Random random = new Random(System.currentTimeMillis());
int[] randoms = new int[1000];
Random randGen = new Random();
long start = System.
浏览 0提问于2011-12-27得票数 0
回答已采纳
因此，我在研究AVL树时遇到了从树中删除特定节点的问题。这是通过删除一个类似于BST的节点，然后平衡高度差因子来完成的。但是如果我们有一个包含插入元素顺序的数组，并且我们有一个要删除的节点。我删除了数组中该节点的匹配项，然后从头开始构造AVL。这是一种删除的好方法吗？
浏览 2提问于2019-08-17得票数 0
1回答
用于排序的改进的二叉树？
、、、
我必须对一个数组进行排序。除了已经存在的排序类型之外，我想知道像这样的算法是否可以工作，以及它的复杂性可能是什么。
我有一个要排序的数组。我创建了一个二进制搜索树。
因此，如果我将数组的所有元素插入到BST中，然后在按顺序遍历树时将它们逐个分配回数组，我将获得排序结果。(尽管由于树节点的存在而消耗了更多的空间复杂度。非就地排序。)
int i=0;
void sort_by_inorder(node *n)
{
if(n==NULL)
{
return;
}
sort_by_inorder(n->leftchild);
array
浏览 0提问于2012-07-13得票数 1
回答已采纳
排序算法可以描述如下：
1.从数组数据创建二进制搜索树.
(对于多次发生，当前节点的增量发生变量)
2.无序地遍历BST。。
(无序遍历将返回数组中元素的排序顺序)。
3.按顺序遍历每个节点，用当前节点值覆盖当前索引处的数组元素(索引从0开始)。
下面是一个相同的Java实现：
节点类的结构
class Node {
Node left;
int data;
int occurence;
Node right;
}
无序函数(返回类型为int，只用于在每次调用时获得正确的索引，它们没有其他用途)
public int inorder(Node root,int[
浏览 3提问于2017-07-25得票数 0
回答已采纳
我正在尝试构建一个基于数组的BST。我的问题是，一旦我有了一个新值(BST值)，并希望将其插入到我的TreeNode中，并在插入后返回此TreeNode的级别。有没有一种(快速)方法可以知道它的级别/深度信息？此外，有没有一种方法可以在不实际构建BST的情况下知道其级别。例如，我有一个数组3,1,2，我想插入4，有没有一种方法可以知道4的深度/级别是多少，而不需要实际构建BST并搜索4来获得深度？谢谢。(如果您不介意，最好使用python代码。给您带来不便，我深表歉意。)
浏览 15提问于2020-01-18得票数 0
1回答
我已经学习了Treap和Splay树，并且用它们解决了一些问题。
理论上，它们的复杂度平均为O(log n)，但在最坏情况下，Treap的复杂度为O(n)，而Splay树的复杂度为摊销O(log n)。
在哪种情况下，最坏的情况发生在Treap中(因为它的优先级是随机选择的)，Treap真的比Splay树慢吗？我已经用Splay树和Treap在SPOJ上解决了一些任务，使用Treap的解决方案比使用Splay树的解决方案要快一些(大约是0.2s)。那么，哪一个更快，我应该主要使用哪一个，什么时候呢？
浏览 2提问于2018-01-06得票数 2
回答已采纳
以下是一个问题：
考虑以下排序算法: I.按给定顺序将给定的输入A1、A2、.a插入到二进制搜索树T中，从空树开始；2.对T进行无序遍历，以不递减的顺序输出元素。(a)算法最坏的时间是什么？(b)采用该算法的最佳时间是多少？
我的答案是：
我在t(n) = 2(n/2) + n中创建了一个BST，因为我们必须遍历每个单独的元素，然后我在t(n) = 2(n/2) + n中打印出BST的顺序，因为我们必须再次遍历每个元素。然后，我将时间复杂性加在一起，以t(n) = 4(n/2)+2n结尾。
根据硕士的方法，这符合案例1。使它θ(n^2)。如果是θ(n^2)，这将同时回答问题的a和b。我看不出怎
浏览 1提问于2018-09-30得票数 1
回答已采纳
如果我有10个元素，并且从一个空树开始，那么以大O表示法将10个元素插入Red Black的复杂度是多少？
它是否会大于O(log 10)，因为每次插入一个元素时，它都必须为该元素搜索合适的位置，并在祖先节点和子节点之间执行一系列旋转。因此，如果我有N个元素，并将N次插入Red Black Tree，这不是O(Black)吗？
谢谢你的帮助。
浏览 3提问于2009-11-15得票数 2
2回答
例如，BST类使用树结构：
public class BST<Key extends Comparable<Key>,Value> {
private Node root;
public class Node {
private int n;
private Node left;
private Node right;
private Key key;
private Value val;
}
public void put()
浏览 1提问于2015-09-22得票数 0
3回答
层次顺序遍历的时间复杂度
、、、、
二叉树层次顺序遍历的时间复杂度是多少？是O(n)还是O(log )？
void levelorder(Node *n)
{ queue < Node * >q;
q.enqueue(n);
while(!q.empty())
{
Node * node = q.front();
DoSmthwith node;
q.dequeue();
if(node->left != NULL)
q.enqueue(node->left
浏览 1提问于2012-12-29得票数 7
回答已采纳
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频
腾讯云开发者
