给定高度的二叉搜索树（BST）h，需要O(k+h)时间来应用BST InOrder Successor 算法 https://stackoverflow.com/a/5471990/5459839 k连续多次，从任何节点开始，将每个下一个调用应用到上一个调用返回的节点上。
伪代码：
get_kth_successor(node):
for times = 1 to k:
node = successor(node)
return node
如何证明这个时间复杂度呢？
特别是，我试图在之间建立一种关系k以及访问的节点数，但在这里找不到任何模式。
请了解以下有关后继遍历的事实：
您可以遍历分支不超过两次：向下和向上。
分支的每次两次访问都对应于找到至少一个后继者：当您通过分支向上回溯时，您将比第一次通过同一分支时向下访问至少一个后继者。
您将遍历的分支数量只有一次不能超过2h。当您从树的左下角的叶子开始并且必须一直向上到根（后继），然后再次向下到底部叶子以找到根的后继时，就会发生这种最坏的情况。但是，如果此后您需要更多后继者，则必须再次访问其中一些分支（回溯），然后才能第一次遍历其他分支。所以你遍历的分支总数只有一次不能增加超过2h.
所以，要找到k你最多会穿越的继任者k分支两次（向下和向上，参见第 2 点）并且2h分支一次（第 3 点），最坏情况下的分支遍历计数为2k+2h这是O(h+k).
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
