在具有O(1)辅助空间的二叉树上进行迭代
迭代访问二叉树时使用O(1)辅助空间的问题是一个很有意思的问题。文章中提到了几种可能的解决方法。
首先,可以使用破坏性的方式来做,即在遍历的过程中断开每个叶子节点的链接。这种方法可能在某些情况下是适用的,比如当你之后不再需要使用这个树的时候。
其次,可以在销毁第一棵树的同时构建另一棵二叉树。需要进行一些内存的手动管理,以确保峰值内存不超过原始树的大小加上一些常数。但这种方法可能会有很大的计算开销。
编辑者补充说,有一种方法可以实现这个问题!可以使用节点本身来指示回到树的上层。当访问一个节点时,将它的左子节点指针指向它的父节点,将它的右子节点指针指向你上一次在路径上向右转的位置(即此时父节点的右子节点指针所指向的位置),并将它的真实子节点存储在现在多余的父节点的右子节点指针或者在遍历状态中下一个访问的子节点的左子节点指针中。需要保持一些指向当前节点及其周围节点的指针,但没有"非本地"的指针。当你回到树的上层时,将过程反转即可。
希望我能够清楚地解释这个方法;这只是一个大致的草图。你可能需要在某个地方查找(我确信这在《计算机程序设计艺术》中的某个地方有提到)。
另外,还有其他的一些评论者也提到了一些解决方法,比如在每个元素中添加一个指向上层的指针。这种方法更简单、更直观,并且已经被广泛认可和理解。
"Iterating over a Binary Tree with O(1) Auxiliary Space"这个问题的出现的原因以及解决方法,整理成一篇文章如下:
在这篇文章中,介绍了一种在二叉树上进行迭代的方法,其辅助空间复杂度为O(1)。这个方法由Joseph M. Morris提出,发表于1979年的Inf. Proc. Letters中。根据的观察,该方法的时间复杂度为O(NlogN)。
方法的实现如下所示:
static void VisitInO1Memory (Node root, ActionpreorderVisitor) { Node parent = root ; Node right = null ; Node curr ; while (parent != null) { curr = parent.left ; if (curr != null) { // search for thread while (curr != right && curr.right != null) curr = curr.right ; if (curr != right) { // insert thread assert curr.right == null ; curr.right = parent ; preorderVisitor (parent) ; parent = parent.left ; continue ; } else // remove thread, left subtree of P already traversed // this restores the node to original state curr.right = null ; } else preorderVisitor (parent) ; right = parent ; parent = parent.right ; } } class Node { public Node left ; public Node right ; }
有人提出了一个问题,认为这个方法会破坏二叉树的结构。解释说,实际上,这个方法只是暂时地添加了一些特定叶子节点的反向引用。
另一个人指出,这个方法的时间复杂度实际上是O(n)。这是因为每个节点只被访问了固定次数。内部的while循环只会在向右走的路径上执行,并且只有在curr是该路径上最左边节点的父节点时才会执行。这个情况只会在进入子树时发生一次,以及离开子树时发生一次。所以,这些路径的长度加起来等于整棵树的大小,即O(size of the whole tree)。
还有一个问题是关于assert语句的作用以及如何将代码改成C++。对此,提供了一个链接,链接中详细讨论了这个算法的实现。
最后,有人指出了链接已经失效的问题。
通过整理以上内容,我们了解到了"Iterating over a Binary Tree with O(1) Auxiliary Space"这个问题的出现原因和解决方法。这个方法通过暂时添加反向引用来实现二叉树的迭代,同时保持了二叉树的结构。这个方法的时间复杂度为O(n),空间复杂度为O(1)。
迭代二叉树的解决方法是在每个子节点中保存对父节点的链接。当遇到一个子节点时,先访问其左子树,然后返回时检查自己是否是父节点的左子节点。如果是,再访问右子树。否则,一直向上移动,直到成为左子节点或者到达树的根节点。
这个算法中使用的栈的大小保持不变,因此不会消耗额外的内存。当然,正如Mehrdad所指出的,链接父节点可以被认为是O(n)的空间复杂度,但这更多是树的属性,而不是算法的属性。
如果不关心遍历树的顺序,可以为节点分配一个整数映射,其中根节点是1,根节点的子节点是2和3,它们的子节点是4、5、6、7等。然后通过递增一个计数器并通过其数值访问节点,循环遍历树的每一行。可以跟踪最大可能的子元素,并在计数器超过它时停止循环。从时间上来说,这是一个极其低效的算法,但我认为它的空间复杂度是O(1)。
这是C语言中使用这个算法的示例。请注意,除了创建树的malloc之外,没有malloc,而且没有递归函数,这意味着栈占用恒定的空间。
对于无法使用额外空间来访问节点的问题,可以通过每个数字的位来确定应该走哪个方向。例如,你如何访问节点#7而不使用额外空间?要递归查找这样的节点将占用空间,如果将所有节点存储在另一个数据结构中,也将占用额外空间。
实际上,只需要减去1并除以2即可确定3是7的父节点。同样,只需减去1并再次除以2即可确定1是3的父节点。因此,你只需要一个循环来计算从当前节点到所需节点的路径中的下一步。
对于树的每个层级,如何访问每个元素?实际上,只需检查在尝试访问之前子节点是否存在,因此它适用于任何二叉树。
然而,必须注意到,这种方法仅适用于完全二叉树,并且从纯理论的角度来看,仍然需要O(高度)位空间来存储所在位置。
即使你返回根节点,你也不知道孙子节点的子节点数目,所以这种方法不起作用。每次访问一个节点时,都是从根节点开始遍历。在此遍历过程中,在尝试访问子节点之前,检查子节点是否存在。
如果二叉树是非常不平衡的(只有左节点的链表,因此有N个层级),那么需要O(N)位来存储编号。
要访问第N个层级的每个元素,可以在循环中访问编号为2^(N-1)到2^N-1的节点。
以上是迭代二叉树的方法及其解决问题的原因。