1回答
动态规划-最优断点
、、、、
我了解到，利用动态规划，矩阵链乘法问题可以用n^3次求解，而对于最优二叉树问题，我们也可以得到n^3次，但是我们可以将它优化到n^2，为什么呢？这是因为在矩阵乘法问题中，链M(i，n)的最优断点可能大于链M(i+1，n)的最优断点。有人能帮我理解这一点吗？为什么在矩阵乘法问题上是这样，而在最优二叉树问题中却不是这样呢？
谢谢
浏览 1提问于2016-03-23得票数 0
回答已采纳
1回答
是否有可能通过贪婪算法而不是动态规划(如Huffman算法)来构造最优二叉树(OBST)？如果是这样的话，为什么在建造OBST时首选DP？
浏览 3提问于2013-04-04得票数 0
我正在努力掌握大O符号。它看起来很抽象。我选择了最常见的数据结构--数组、哈希表、链表(单链表和双链表)和二叉树，并猜测了最常见的操作--插入和搜索--的大O符号。这是一个惯性视图的准备工作。我只需要学习基础知识，而不是阅读一整本关于算法的教科书，尽管这将是理想的。下表是否有效？
Data Structure Big O Search Big O Insert
Array O(1) O(n)
Hash O(1) O(1)
Single Linked List
浏览 1提问于2011-10-15得票数 6
回答已采纳
1回答
给定n个实数正数A1，A2....An构建一个二叉树T，如：
每一个数字都是一片叶子。
T的重量将尽可能小。树的重量等于每片叶子乘以其高度的总和。
这个问题是在测试算法和数据结构时给我的。简单地说，我的回答是构建一棵二叉树，这样每一片叶子都是A1到一个。T的权重为logn*之和。
我没有得到这个答案的分数。被授予满分的答案是按频率对数字进行排序，并构建一棵霍夫曼树。
我的问题是为什么我的答案被忽略了？
如果A1到a都是非常小的数字，例如从0到1，那么每片叶子的高度将成为计算树的重量的主要因素。
帮助会很感激的。
浏览 3提问于2014-02-09得票数 0
回答已采纳
3回答
我正在研究对字符流进行位编码的霍夫曼编码，我读到最优码将由一个完整的二叉树表示，其中每个不同的字符由一个叶子表示，所有内部节点恰好包含两个子节点。
我想知道为什么完整的二叉树是这里的最佳选择？换句话说，完全二叉树在这里的优势是什么？
浏览 2提问于2012-09-17得票数 2
2回答
在huffman编码算法中，有一个引理说：
对应于最优二进制前缀代码的二叉树是满的。
但我搞不懂为什么。你怎么能证明这个引理？
浏览 0提问于2014-05-16得票数 3
回答已采纳
1回答
阅读RFC 1951，似乎有效的动态Huffman树不一定是一个完整的二叉树-例如，由位长(2，2，2)指定的树有一个节点，只有一个子节点：
____
/ \
0 1
/ \ /
0 1 0
当试图在一次分配中为完整树分配足够的内存时，这会引起问题，因为任意二叉树中的节点数不一定有任何上限。
放气标准中的约束是否意味着动态Huffman树大小的上限？
浏览 1提问于2020-08-03得票数 0
回答已采纳
是否存在平衡的二叉树，而不是平衡的二叉树？如果是这样的话，在这样的树中搜索节点的时间复杂度是多少？
我的理解是：
二叉树:任何节点都有两个最大的叶节点。在二叉树中搜索，使用DFS或BFS是O|V+E|。
二进制搜索树: BST是由有序节点组成的树。使用DFS在二进制搜索树中进行搜索
平衡树(假设高度平衡)：在根以下的最高层数保持在最小。平衡对搜索的时间复杂度有影响吗？
所以，从本质上说，我可以创建一个高度平衡但没有排序的二叉树。这棵树的搜索时间是O|V+E|还是更好？
浏览 4提问于2015-07-28得票数 1
回答已采纳
1回答
我正在为一个作业做二进制搜索树和AVL树。
当我试图向二进制搜索树中添加1,000,000个元素时，我遇到了问题，但是我可以将键->值对添加到AVLTree中。(AVLTree没有问题)
如果我平衡二进制搜索树，那么与AVLTree没有什么区别？？(如果我平衡二进制搜索树，它会变成一个AVLTree?)
在插入15,000个元素后，从二进制搜索树中获得错误:线程"main“java.lang.StackOverflowError中的异常
项目定义：
使用这些测试和为朴素二叉树创建的代码，比较了AVL树和朴素二叉树在搜索、插入和删除时间以及长序列树平衡方面的性能。您应该使用树中最多
浏览 1提问于2014-01-15得票数 1
回答已采纳
1回答
我了解了二叉树，以及它如何使搜索更有效率。我知道数据库支持二叉树搜索，有些库可以用javascript和python等语言进行这种类型的搜索。我的问题是，是否有一种常见的情况，您必须在前端或后端实现二叉树搜索(您设置了像树和节点这样的类)？给定您可以获得或插入数据的RESTful API，您的javascript或后端语言是否需要二叉树实现？
浏览 1提问于2017-05-17得票数 0
回答已采纳
我很好奇，是否有可能以这样的方式构造一个二进制搜索树，即它的n个元素有最小的高度，但它不是AVL树。
换句话说，根据定义，每个最小高度的二叉树也是一棵AVL树吗？
浏览 1提问于2021-10-11得票数 0
回答已采纳
7回答
为什么我们要专门研究二叉树？正如在一般的m-way搜索树中一样，在DataStructure教科书中没有给予二叉树那么重要。
二叉树的使用是否超过了m-way树？
浏览 1提问于2009-12-05得票数 21
回答已采纳
1回答
如果我有一个平衡的二叉树，并且我想在其中搜索一个项，那么大的--哦，时间复杂度会是O(n)吗？在二叉树中搜索某一项，无论它是否平衡，都会从O(n)中改变大的我知道，如果我们有一个平衡的BST，那么搜索一个项就等于BST的高度，所以O(log )，但是普通的二叉树呢？
浏览 1提问于2017-03-30得票数 0
回答已采纳
3回答
当我搜索上面的问题时，我得到了一个答案Yes。
完整二叉树的定义如下：
一棵完整的二叉树(有时是适当的二叉树或2棵树)是一棵树，其中除叶子以外的每个节点都有两个子节点。
但问题是，当我每次构造B-树时，这个属性可能并不满足。
例如：
在B-第2顺序树中插入10,17,45
我们得到的结构是
10
17
45
这不是一个完整的二叉树。
那么为什么说B-树的第2阶是一个完整的二叉树呢？
浏览 3提问于2016-04-10得票数 2
回答已采纳
1回答
在给定一组密钥和所选密钥的相关概率的情况下，有许多查找的算法。以这种方式生成的二进制搜索树将具有查找这些元素的最低期望时间。但是，对于其他度量，这种二进位搜索树可能不是最优的。例如，如果试图查找不包含在树中的键，查找时间可能非常长，因为为了优化某些元素的查找，树可能是不平衡的。
我目前感兴趣的是如何从一组键构建二进制搜索树，目标是尽可能减少查找具有特定价值的后继所需的时间。也就是说，我希望树的构造方式是，给定一些随机密钥k，我可以尽可能有效地找到k的继承者。我碰巧提前知道了一个给定的随机密钥落入任意两个密钥之间的概率，这两个密钥都是由任意两个密钥构成的。
有人知道这个问题的算法吗？还是我错了，
浏览 2提问于2011-12-28得票数 0
回答已采纳
我有一个链表/二叉树方法库，当标准容器不合适时使用--例如，当有不同类型的节点时，或者当我需要从二叉树转换到列表和返回时。它包括红黑树处理。
其中一种方法在O(n)时间内将双链接列表转换为一个完全平衡的简单二叉树(假定预先知道项目的数量)。这种算法被称为“折叠”--它是一种二叉树再平衡算法的下半部分，该算法曾在多布斯博士上发表过。台阶基本上是..。
给定树的大小，决定左右子树的大小。
左子树的递归
从列表中弹出一个节点作为根
右子树的递归
将子树链接到根
我也有一个类似的方法来创建一个红黑树。原理相同，但递归保持节点的高度-高度零节点创建红色，所有其他都是黑色的。起
浏览 3提问于2009-11-04得票数 3
回答已采纳
2回答
今天，在课堂上，我的教授说有一种平衡的二叉树，我以前从未听说过。我想知道有没有没有轮换的平衡二叉树？根据我的理解，平衡二进制搜索树是AVL树。除此之外，我不认为有可能建立一个“平衡二进制搜索树”。但是，如果有这样的数据结构，我如何从一系列随机数构建一个“平衡二进制搜索树”呢？
谢谢,
浏览 0提问于2010-08-26得票数 2
回答已采纳
3回答
我知道如何从一般的树转换成二叉树，
a a
/ | \ /
b c d -> b
\
c
\
d
我刚刚被问到如何从一般的树转换成二叉树。我的想法是，问我的人要么不是指二叉搜索树(我问他，他说他指的是)，要么是他误解了课堂笔记中的某些东西。无论如何，有没有人听说过这样做？从通用树到二叉搜索树？我给他的答案是首先转换成二叉树，然后对其进行排序，得到二
浏览 0提问于2013-04-18得票数 0
回答已采纳
1回答
我无法理解和想到一种情况，即在不平衡的二叉树中的搜索操作可能比在平衡的二叉树中的搜索操作更有效。如果二叉树是高度倾斜的，那么它可能以链表的形式出现，此时运行时的复杂度将是O(n)。有可能发生这种情况吗？我的教授坚持说有一些，但我根本想不出有什么。
浏览 1提问于2022-05-07得票数 0
回答已采纳
1回答
范围树构造
、、、
让我们看一下下面的图片
这就是所谓的范围树。我不明白一件事，它看起来像一个二叉搜索树，所以如果我们插入元素，我们可以使用与插入二叉搜索树相同的过程。那么有什么不同呢？
我读过一篇教程，我猜它是kd树的变体，查询搜索树(如几何点搜索等)，但如何构建它？像二叉树或者它需要额外的参数吗？也许就像这样
struct range
{
int lowerbound;
int upperbound,
int element;
};
在插入过程中，我们必须检查
if(element>lowerbound && element <upperbound)
then ins
浏览 0提问于2012-09-09得票数 2
回答已采纳
1回答
我正在做一个关于二叉树的家庭作业，我遇到了一个我不太理解的问题。问题是，密度如何影响搜索二叉树所需的时间。我了解二进制搜索树和大O表示法，但我们以前从未处理过密度。
浏览 1提问于2012-06-19得票数 0
回答已采纳
1回答
假设我有一棵平衡的二叉树。我想在树上找一把钥匙。然而，如果在二叉树中不存在k，它应该给出离k最近的下一个最大数。
例如，假设在树中有这些数字1,5,6,8,10作为键。如果我搜索'7‘，它应该返回8，如果我搜索2，它应该返回5等等。
要执行这样的搜索，必须对二叉树进行哪些修改？我也想要一个O(log )的解。
浏览 0提问于2017-03-17得票数 1
回答已采纳
2回答
我一直在使用一种数据结构，最初的开发人员称之为heap，它用于实现优先级队列。
虽然有很多关于二叉树的文章，但(min/max)堆似乎定义得不太好(细节因实现而异)。
我注意到一些不一定适用于二叉树结构的特性。
相同的元素可以多次出现在队列中，而不会造成执行或实现上的复杂性。
搜索(虽然可能并且比彻底搜索更快)，但效率不高(因为每个节点的子元素不需要平衡)。
由于搜索效率不高，而且可能存在重复搜索，因此删除可能需要存储对node的引用，而不是使用key查找节点(这是二叉树的常见做法)。
，与二叉树相比。
(与二叉树相比，最好的情况更好，最差的情况更糟)
对于符合这些特征
浏览 4提问于2017-10-31得票数 1
回答已采纳
2回答
为什么二叉树比已排序的值数组更可取？
在任何一种情况下，找到给定的键值(通过遍历二叉树，或者通过在排序的数组上执行二进制搜索)都需要O(log )的时间复杂度。
浏览 1提问于2015-03-10得票数 1
4回答
是否有可能构造一个二叉搜索树，仅给出它的前序遍历？
我知道只有在中序遍历和预序遍历都给定的情况下，才能构建二叉树。但我的问题是关于二叉搜索树的。
例如:给定: 5,3,1,4,7,8
Construct :
5
3 7
1 4 8
浏览 0提问于2012-09-26得票数 5
回答已采纳
给定两棵二叉搜索树，有没有一种算法可以将它们组合成一棵具有线性时间复杂度的二叉搜索树？
我考虑过将第二棵树的元素逐个放入第一棵树中，但未能在线性时间复杂度内实现。
浏览 3提问于2019-09-24得票数 0
5回答
在二叉树中插入元素
、、、
试着在网络上进行大量的探索，但是可以得到任何帮助，就像在二叉树中添加一个节点一样。
问题:请求向二叉树添加节点的算法和代码片段。(或指向我更正URL )
假设:根据我的理解，二叉树和二进制搜索树是不同的？如果我错了，请纠正我。
(要求:如果您正在编写代码片段，请使用适当的变量名，这有助于理解)
二叉树
5 7 3 x1 x2 x3
5
7 3
x1 x2 x3
二进制搜索树5 7 3 2 4 6
5
3
浏览 3提问于2013-04-30得票数 10
2回答
二进制搜索的最佳运行时间是O(log(n))，如果二叉树是平衡的。最坏的情况是，如果二叉树是如此不平衡，它基本上代表一个链接列表。在这种情况下，二进制搜索的运行时间是O(n)。
但是，如果树只是稍微不平衡呢，就像这棵树的情况一样：
如果我没有弄错的话，最好的情况仍然是O(log )。但最坏的情况是什么？
浏览 4提问于2017-04-01得票数 1
我有一个任务要构建二叉树，具体如下：
构建理想的平衡树。从指定的树到二叉树查找节点数量。
所以..。奇怪的是:无论我在哪里读到二叉树，它们都不包含有重复值的节点，但在第二个任务中，我必须找到大量的节点，这些节点的数学运算要输入值……如果我按规则建树，不是只有0或1吗？
或者，也许，我建造的第一棵树必须是无序的，并且允许有重复的树？如果我重建树为二叉树搜索树，我只需要删除重复和排序节点的左-无右-多规则？
浏览 4提问于2012-05-22得票数 0
回答已采纳
2回答
我有一个关于最优二叉树的作业，在做的时候出现了一些问题。我发现很多在线链接都很有用(仅仅是通过谷歌搜索)，但我想知道.
为什么必须首先对密钥进行排序？
如果我得到一个较低的成本(对于一个最优的BST)，当键没有排序时，这是否意味着我的代码中一定有错误？
最佳的BST必须是完全的/完美的吗？(使用维基百科的完整和完美的定义)
完美二叉树是一棵完整的二叉树，其中所有的叶子都在相同的深度或水平上。
一个完整的二叉树是一个二叉树，其中的每一层，除了可能的最后一层，都被完全填满，所有的节点都尽可能地留在最左边。2
对于最后一个问题，我假设一棵最优的树必须是完整的/完美的，但是一些applets在线让我
浏览 7提问于2011-09-30得票数 2
回答已采纳
1回答
我有一个问题，我有点困惑。它实际上是关于如何使用广度优先搜索(使用队列)遍历一般树(而不是二叉树)。我能找到的都是二叉树。事前谢谢你
浏览 0提问于2013-07-03得票数 0
我正在尝试解决这个问题：“给出一个二叉树，检查他的预排序访问，并用相同的预排序访问建立一个二进制搜索树。证明它总是可能的，如果不可能，请给出一个例子。”有什么帮助吗？我需要编写伪代码，并给出时间复杂度，但我对为每一棵可能的二叉树构建具有相同预序访问的二进制搜索树有很多疑问。
浏览 27提问于2019-01-13得票数 2
1回答
我知道，在二进制搜索树中，元素是根据不等式的属性插入的，即：
if(n->val > val) insert(n->left, val); // root node greater then val insert to left
else if(n->val < val) insert(n->right, val); // root node less then val insert to left
// I am ignoring the case when n->val == val here
我想知道应该根据什么基础将节点插入到纯
浏览 3提问于2016-07-23得票数 1
回答已采纳
1回答
下面是的摘录
如果给定的二叉树是二进位搜索树，我们可以通过存储预顺序或后置遍历来存储它。对于二进位搜索树，只有先序或后序遍历才足以存储结构信息。
问题
不可能使用顺序遍历来序列化和反序列化二叉树吗？如果是的话，为什么？
二叉树和BST序列化有什么区别？上述声明对这种区别并不清楚。
浏览 2提问于2020-05-17得票数 0
2回答
在什么情况下，使用二叉搜索树搜索术语需要与术语词汇表(例如M)的大小成线性的时间复杂度？如何保证log M的最坏时间复杂度？
浏览 0提问于2016-09-30得票数 0
1回答
基于继承的AVL树实现
、、、
我被要求实现一个AVL树，我做到了--现在它适用于所有我能想到的压力测试。现在我发现我们被建议实现它，不是从二叉树继承的二叉树继承的。我希望它是正确的-我将很高兴得到一个不变量(必须出现的字段)应该出现在每个不变量(二叉树，搜索和AVL)的建议。谢谢!以下是我的实现：
浏览 0提问于2016-11-28得票数 0
回答已采纳
1回答
我对如何在二叉搜索树中排列节点的顺序感到有点困惑。在左边的二叉树中，会有比根节点更大的子树节点吗？
例如，下面是一个二进制搜索树吗？
2
/ \
1 4
/ \
3
上面让我困惑的是，1 (3)的右子树是否可以大于原始根节点(2)。
浏览 0提问于2012-10-01得票数 1
回答已采纳
在什么情况下使用平衡的二叉树而不是哈希表来实现字典ADT？
我的假设是，使用二进制搜索树总是更好，因为它的自然排序。
但是，对于二叉树，哈希表的搜索时间可以与O(1)、V.S.O(Logn)一样好。
所以我不确定割礼会是什么。
浏览 5提问于2011-04-15得票数 1
1回答
我在看LeetCode问题
给定二叉树，确定它是否是高度平衡的.
对于这个问题，高度平衡二叉树被定义为：
一种二叉树，每个节点的左右子树的高度相差不超过1。
我有这样的意见：
[2,1,3,0,null,null,4,null,null,null,5]
对于这个输入，预期的输出是false。为什么这不是一个高度平衡的二进位搜索树？我确实找到了什么是高度平衡的定义，但也许我不清楚如何看待这棵树，以确定它是否是高度平衡的。
浏览 1提问于2021-09-02得票数 1
3回答
关于树的基本运算的困惑
、、、
如何在二叉树中插入密钥(而不是a BST)？
我的意思是二叉树没有像BST这样的节点的某些属性，所以似乎键的插入可以在树中的任何位置。
然而，通过将键放置在任何位置，二叉树可能会将其退化为一个“列表”，从而失去它的O(logN)属性。
我见过使用合并方案创建二叉树(例如，应用程序是一个Huffman Tree)，但似乎没有遇到二叉树的插入方法。
我认为这个问题扩展到了多路树，因为二叉树是多路树(两个子节点)的一个具体例子，对吗？
我做错了吗？是否有一种向二叉树添加新键的特定方法，或者二叉树的应用程序是如此具体，以至于合并操作就足够了，并且不需要插入方法？也许我已经完全错过了BT的用法应用或概念
浏览 7提问于2012-05-27得票数 1
1回答
我试图实现二叉树(不是二叉树搜索树)。它将主要是一个由insert/delete/search和clear过程组成的类模板。节点中保存的数据可以是任何数据。如下所示：
template<class T>
class BinaryTree
{
public:
BinaryTree(int size);
~BinaryTree();
virtual bool insert(T data);
virtual bool remove(T data);
virtual void clear();
virtual bool search(T da
浏览 1提问于2016-11-02得票数 1
2回答
标签与未标记的二叉树？
、、、、
这个链接谈到了一些“标记的”二叉树。那么，是否也有所谓的“未标签”二叉树呢？对两者做一个简明的解释会很好。
我为什么要找这个？
我试着回答这个问题：
给出了n个不同元素的集合和n个节点的未标记二叉树。我们可以用多少种方式将树填充到给定的集合中，从而使它成为二进制搜索树？
现在，我知道给定n个节点的二叉树的数目是第n个，但现在我感到困惑:这个公式适用于上述两种类型中的哪一种？
PS:对引号中的问题提供一些帮助也会很好:)
浏览 3提问于2015-04-16得票数 1
5回答
树型数据结构
、、
我试着理解什么是排序树，二叉树，avl和...我仍然不确定，排序后的树是如何排序的？在排序的树中搜索和在未排序的树中搜索之间的复杂度(Big-Oh)是多少？希望你能帮助我。
浏览 0提问于2009-05-31得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
腾讯会议
实时音视频活动推荐
腾讯云开发者
