最近我一直在编码了一堆不同的二叉搜索树实现(AVL,扇,树堆),并很好奇,如果有一个特别"好"的方式来写一个迭代器遍历这些结构.我现在使用的解决方案是让BST中的每个节点都存储指向树中下一个和前一个元素的指针,这会将迭代减少到标准的链表迭代.但是,我对这个答案并不满意.它通过两个指针(下一个和前一个)增加每个节点的空间使用量,在某种意义上它只是作弊.
我知道的构建,通过使用堆栈跟踪前沿节点的探索以后用0-1(H)的辅助存储空间(其中,h为树的高度),二叉搜索树迭代器的方式,但我由于内存的使用,我们拒绝对此进行编码.我希望有一些方法来构建一个只使用常量空间的迭代器.
我的问题是 - 有没有办法在具有以下属性的二叉搜索树上设计迭代器？
next()和hasNext()查询在O(1)时间内运行.为了更方便,它的罚款,如果你认为迭代(即没有插入,删除或旋转)在树形结构不改变形状,但如果有,确实可以处理这样的解决方案将是真的很酷.
所以我自学了AVL树,我理解它背后的基本思想,但我只是想确保我实际实现它的直觉是有效的:
我会用左旋转检查它 -
所以,以下情况很简单:
8
/ \
7 10
/
6
/
3
当我们添加3时,树重新平衡为:
8
/ \
6 10
/ \
3 7
但轮换是基于3的增加还是根据7的子树的不平衡？它甚至是基于植根于8的树的不平衡吗？
在我看来,以下示例是事情变得有点毛茸茸的地方:
9
/ \
7 10
/ \
6 8
/
3
因此,在这种情况下,当添加3时,7处的子树很好,因此子树不需要旋转.然而,9处的树是不平衡的,加上3,所以我们将旋转基于9.我们得到:
7
/ \
6 9
/ / \
3 8 10
因此,在编写我的代码时,我很快就会编写以下代码,从小子树开始,使用更大的子树来完成这个工作？
伪代码:
function balanceTree(Node n){
if (n is not null){
balanceTree(n.rightchild);
balanceTree(n.leftchild);
}
if (abs(balanceFactor(n))>1){
rotateAsNeeded(n);// rotate based on balance factor
}
}
提前致谢!
algorithm rotation avl-tree binary-search-tree data-structures
我今天去接受采访,要求我序列化一棵二叉树.我实现了一种基于数组的方法,其中节点i的子节点(在水平顺序遍历中编号)处于左子节点的2*i索引和右子节点的2*i + 1.面试官似乎或多或少都很高兴,但我想知道序列化究竟意味着什么？它是否专门用于展平树以写入磁盘,或者序列化树还包括将树转换为链表,比方说.另外,我们如何将树扁平化为(双重)链表,然后重构它？您可以从链表重新创建树的确切结构吗？
我需要在当地时间上午9:00向世界各地的用户发送电子邮件.服务器在英国.我能做的是在每个用户和服务器的时间之间设置一个时间差,如果DST不存在,这将完美地起作用.
这是一个例子来说明它:
当服务器在特定星期日凌晨2:00从GMT转到GMT +1(BST)时,这意味着John现在具有-6H的时差.
这种情况下我仍然可以通过更新所有用户的服务器的本地时间之外处理,但一旦我前进/后退的所有其他用户的时候,我还需要一种方法来检测时(时间和日期)的用户生活英国境外将(或不会)将当地时间改为可能的夏令时.
我需要一个PHP方法来了解/检测世界其他地方何时进入/退出夏令时.
std::lower_bound()如果我将一对红黑树迭代器(set::iterator或map::iterator)传递给它,我总是假设以对数时间运行.std::lower_bound()在这种情况下,至少在libstdc ++实现中,我必须自己两次燃烧以注意在O(n)时间运行.据我所知,该标准没有红黑树迭代器的概念; std::lower_bound()将它们视为双向迭代器,advance并将它们视为线性时间.我仍然没有看到任何理由为什么实现无法为红黑树迭代器创建特定于实现的迭代器标记, 并且lower_bound()如果传入的迭代器恰好是红黑树迭代器则调用专用.
是否有任何技术原因std::lower_bound()不专门用于红黑树迭代器？
更新:是的,我知道查找成员函数,但它不是重点.(在模板化代码中,我可能无法访问容器或仅在容器的一部分上工作.)
赏金到期后:我发现Mehrdad和Yakk的答案最有说服力.我也无法决定; 我正在给予Mehrdad赏金并接受Yakk的回答.
我目前正在研究二叉搜索树,我想知道如果你尝试插入一个与根相同的元素,你会怎么做？它去哪儿了？
二分搜索和二叉搜索树有什么区别？
它们是一样的吗？阅读互联网似乎第二个仅适用于树(最多2个子节点),二分搜索不遵循此规则.我没理得.
如何合并两个保持BST属性的二叉搜索树？
如果我们决定从树上取每个元素,并将其插入到另一个中,这种方法的复杂性将是O(n1 * log(n2))其中n1的(比如树的节点数量T1),这是我们分裂,并且n2是节点的数量另一棵树(比如说T2).在此操作之后,只有一个BST具有n1 + n2节点.
我的问题是:我们能比O更好(n1*log(n2))吗？
给定BST中的节点,如何找到下一个更高的密钥？
如果二叉搜索树的预订遍历是6,2,1,4,3,7,10,9,11,那么如何获得后序遍历？