我刚开始阅读Okasaki的《纯函数数据结构》(Purely Functional Data Structures),但是我使用的是Haskell而不是Standard ML。然而,我遇到了一个早期练习(2.5),让我有点困惑如何在Haskell中完成: 将现有元素插入二叉搜索树会复制整...
根据维基百科,一棵树的高度是从根节点到最深的节点的路径长度。一棵仅有一个节点(根节点)的(有根)树高度为零(或一)。我不明白 - 是零还是一(或两者都是)?
我在Coursera算法课程中遇到了这个问题,意识到我不知道如何解决。但是,我对此有一些想法。脑海中浮现出的第一件事是使用优化的位集(如Java的BitSet)来获取映射节点的key -> color。所以,我们只需要为整个树分配一个位集,并将其用作颜色信息源。如果树中没有重复元素,那么...
我正在使用PHP(CodeIgniter)和MySQL为网站实现MLM树。我需要在数据库中实现二叉树。需要考虑以下几点: 1. 对于每个节点,左子树中孩子/节点数量和右子树中孩子/节点数量的最小值称为一对。对于每一对,一个节点获得1分-应存储在数据库中(节点代表用户)。 2. 当创建新节点...
我最近意识到,尽管我在生活中经常使用二叉搜索树(BST),但我从未考虑过除中序遍历以外的其他遍历方式(虽然我知道如何轻松地调整程序以使用前序或后序遍历)。 在意识到这一点后,我拿出了一些旧的数据结构教科书,寻找前序遍历和后序遍历有用性背后的原因-不过他们没有说太多。 有哪些实际场景下需要使用先...
我有一个具有重复值的二叉搜索树(BST),我正在尝试查找重复的值。现在显然我可以编写一个愚蠢的算法来遍历整个树,这很容易。 然而,我想写一个更有效率的算法。以下是我迄今为止所做/思考过的内容: 假设以下树结构: 10 / \ 5 15 /\ ...
请帮忙识别这个B-堆中的模式: 在普通的二叉堆中,我们总是使用以下条件: 左子节点 = 2*i, 右子节点 = 2*i+1 父节点 = i/2 但是这些条件仅适用于前两层,并且我无法识别剩余的模式。请帮我。
是否有可能在不使用栈、队列等辅助空间的情况下(即O(1)辅助空间)遍历二叉树?这一点是否已经被证明是不可能的呢?如果可能,应该如何实现? 编辑:我得到的关于如果存在指向父节点的指针就可以实现此操作的回复很有趣,我不知道这是可能的,但是从某种角度来看,这可能需要O(n)的辅助空间。此外,在我的...
我正在阅读Steve Yegge关于单例模式的文章,他在其中提到他的老师告诉他AVL树是邪恶的。这只是因为红黑树是更好的解决方案吗?