我已经能够BST通过几个来源找到几个自平衡的细节,但是我没有找到任何好的描述,详细描述哪个最适合在不同的情况下使用(或者如果它真的无关紧要).
我想要一个BST最适合存储超过一千万个节点的东西.节点的插入顺序基本上是随机的,我永远不需要删除节点,因此插入时间是唯一需要优化的东西.
我打算用它来存储益智游戏中先前访问过的游戏状态,以便我可以快速检查是否已经遇到过以前的配置.
我已经实现了一个二叉搜索树,我想在其插入函数中添加更多功能,使其成为一个自平衡树.我在C#编码.
任何人都可以建议我很好的教程或链接吗？我做了一些搜索并找到了一些链接,但它们都没有足够的描述性.
谢谢.
考虑我有一个数组[3,18,15,25,26],可以从中形成多少个可能的二叉搜索树？
我对树很新,我正在尝试创建一种"叶子迭代器".我认为它应该将没有.left和.right值的所有节点放在堆栈上,但我不确定它是怎么做的,甚至是不对的.我已经尝试过搜索它,但是我遇到的每个例子都是从最左边的叶子开始,然后继续p = node.parent,我避免链接到节点的父节点.
我不明白我怎么能重复从根开始并经过葡萄藤而不会一遍又一遍地访问相同的葡萄藤.
编辑
我看到人们建议使用递归方法来解决这个问题,我现在同意了.但是我一直试图找到迭代器级方法来解决这个问题,但是我仍然想知道这是否可能,以及如何做到这一点!
试图通过网络进行大量探索,但可以得到任何帮助,Everywhere就像在Binary Search树中添加一个节点一样.
问题:请求用于将节点添加到二叉树的算法和代码片段.(或指向我更正网址)
假设:根据我的理解,二叉树和二叉搜索树是不同的？如果我错了,请纠正我.
(请求:如果您正在编写代码片段,请使用适当的变量名称,这有助于理解)
例如:二叉树
5 7 3 x1 x2 x3
5
7 3
x1 x2 x3
二进制搜索树5 7 3 2 4 6
5
3 7
2 4 6
insert(int key, struct node **root)
{
if( NULL == *root )`
{
*root = (struct node*) malloc( sizeof( struct node ) );`
(*root)->data = key;
(*root)->left = NULL;
(*root)->right = NULL;
}
else if(key < (*root)->data)
{
insert( key, &(*root)->left );
}
else if(key …这是"算法导论"第3版的练习15.5-4,这是关于Knuth对最优二叉搜索树的DP方法的改进.
最优二叉搜索树的DP算法是:
OPTIMAL_BST(p, q, n)
let e[1..n+1, 0..n], w[1..n+1, 0..n], and root[1..n, 1..n] be new tables
for i = 1 to n+1
e[i, i - 1] = q[i - 1];
w[i, i - 1] = q[i - 1];
for l = 1 to n
for i = 1 to n - l + 1
j = i + l - 1
e[i, j] = INFINITY
w[i, j] = w[i, j - 1] + p[j] + q[j]
for r = i …我对c ++编程比较陌生,想知道是否有人可以帮我澄清一些问题.
http://www.cplusplus.com/reference/set/set/
http://www.cplusplus.com/reference/map/map/
我一直在阅读如何实现STL二进制搜索树,并且我一直注意到std :: set和std :: map经常被提到作为完成这样一个任务的方法.然而,这两者究竟有什么区别？对我来说,两者看起来几乎完全相同,我不确定是否有一些我没有注意到的东西,使一个人比另一个更好的特定任务.使用std :: set over std :: map来实现从数组或向量中获取值的STL二叉搜索树(例如速度)是否有任何优势？
如果有人能帮我理解这个概念,我会非常感激!
问题是找出BinarySearchTree的每两个节点之间的距离之和,假设每个父子对由单位距离分开.每次插入后都要计算.
例如:
->first node is inserted..
(root)
total sum=0;
->left and right node are inserted
(root)
/ \
(left) (right)
total sum = distance(root,left)+distance(root,right)+distance(left,right);
= 1 + 1 + 2
= 4
and so on.....
我提出的解决方案:
蛮力.脚步:
O(n).O(nC2)_times_O(log(n))=O(n2log(n))使用最低公共祖先方法计算它们之间的距离并将它们相加.整体复杂性:-O(n2log(n)).
O(nlog(n)).脚步:-
O(n).O(nlog(n)).剩下的节点.整体复杂性:-O(nlog(n)).
现在的问题是"是否存在任何解决方案O(n)？
java algorithm dynamic-programming time-complexity binary-search-tree
我正在阅读这个答案
并遇到这一段
好吧，实际上四叉树并不是我最喜欢的用于此目的的数据结构。我倾向于更喜欢网格层次结构，例如世界的粗网格，区域的更细的网格，以及子区域的更细的网格（3 个固定级别的密集网格，不涉及树），具有行-基于优化，因此其中没有实体的行将被释放并变成空指针，同样完全空的区域或子区域变成空值。虽然这个在一个线程中运行的四叉树的简单实现可以在我的 i7 上以 60+ FPS 处理 100k 代理，但我已经实现了可以处理几百万个代理在旧硬件（i3）上每帧相互反弹的网格。此外，我一直很喜欢网格如何使预测它们需要多少内存变得非常容易，因为它们不细分单元格。
这种类型的网格看起来很直观，听起来有点像“N 阶”网格，其中每个父节点有 N 个子节点，而不是 4 个子节点。N^3 可以比 4^3 走得更远，这允许更好的精度和潜在的（我猜）更少的分支（因为要分支的节点少得多）。
我有点困惑，因为我会直觉地使用一个或可能是 3 个 std::map< operator()来减少它的内存占用，但我不确定它会这么快，因为查询 AABB 意味着堆叠几次访问都是 O(log n)。
他所说的那些基于行的优化到底是什么？这种类型的网格搜索常见吗？
我对 az 阶曲线有一些了解，而且我对四叉树并不完全满意。