印刷继任者和前身在BST [英] Printing Successor and Predecessor in a BST

问题描述

我的问题如下：

我有一个带有键的二进制搜索树： a1< a2< ...< an ，问题是使用O（n）中的递归算法打印树中的所有（a_i，a_i + 1）对（其中i = {1,2,3，...}）时间没有任何全局变量，并使用O（1）额外的空间。一个例子：
让键是：1,2，...，5
将被打印的对：（1,2）（2,3）（3,4）（4,5） ）

所以你不能在树中排序遍历，并找到每个节点的后继/前导。因为这将需要O（nh）时间，并且如果树是平衡的，则对于整个树将是O（nlgn）。

解决方案

虽然你是正确的，找到一个有序的后继者或前辈可能需要O（h）时间，事实证明如果您从BST开始的最小值，并重复找到其后继者，则完成的工作总数将最终出现到O（n），而不管树的形状。

$ b $直觉这是为了思考在迭代执行后续查找时遍历树中每个边的次数。具体来说，您将访问树中的每个边缘两次：一旦您下载到子树中，并且一旦您走出了它访问了该子树中的每个节点。由于n节点树具有O（n）边，所以需要花费时间O（n）才能完成。

如果您对此持怀疑态度，请尝试编写一个简单的程序来验证它。我记得当我第一次听到这个结果，直到我写了一个程序来确认它，才不相信这个结果。 ： - ）

在伪代码中，逻辑如下所示：

1. 通过从根开始并重复跟随左子指针，找到树中最低的值，直到没有这样的指针存在。


2. 在所有节点被访问之前，记住当前节点并找到它的后继如下：
   
   
   
   1. 如果当前节点有一个正确的孩子：
      
      
      
      1. 向右。
      
      
      2. 向左走，直到没有留下的孩子。
      
      
      3. 输出您开始的节点，然后输出该节点。
         2：否则：
      
      
      4. 走到父节点，直到发现您开始的节点是其父级的左边小孩。
      
      
      
      5. 否则，输出您记住的节点，然后输出当前节点。
      
      

   
   

希望这有帮助！ / p>

My problem is as follows:

I have a binary search tree with keys: a1<a2<...<an, the problem is to print all the (a_i, a_i+1) pairs in the tree (where i={1,2,3,...}) using a recursive algorithm in O(n) time without any global variable and using O(1) extra space. An example: Let the keys be: 1,2, ..., 5 Pairs that will be printed: (1,2) (2,3) (3, 4) (4, 5)

So you can't do inorder traversal in the tree and find the successor/predecessor for each node. Because that would take O(nh) time and if the tree is balanced, it will be O(nlgn) for the whole tree.

解决方案

Although you are right that finding an in-order successor or predecessor might take O(h) time, it turns out that if you start at the smallest value in a BST and repeatedly find its successor, the total amount of work done ends up coming out to O(n) regardless of the shape of the tree.

On intuition for this is to think about how many times you traverse each edge in the tree when iteratively doing successor lookups. Specifically, you will visit every edge in the tree exactly twice: once when you descend into the subtree, and once when you walk up out of it having visited every node in that subtree. Since an n-node tree has O(n) edges, this takes time O(n) to complete.

If you're skeptical about this, try writing a simple program to verify it. I remember not believing this result when I first heard it until I wrote a program to confirm it. :-)

In pseudocode, the logic would look like this:

1. Find the lowest value in the tree by starting at the root and repeatedly following the left child pointer until no such pointer exists.
2. Until all nodes are visited, remember the current node and find its successor as follows:
   1. If the current node has a right child:
      1. Go right.
      2. Go left until there are no left children left.
      3. Output the node you started at, then this node. 2: Otherwise:
      4. Walk up to the parent node until you find that the node you started at was a left child of its parent.
      5. If you hit the root and never found that you traversed from a left child upward, you are done.
      6. Otherwise, output the node you remembers, then the current node.

Hope this helps!

这篇关于印刷继任者和前身在BST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！