Geek Answers Handbook

How can I prove this operation on binary search trees?

I want you to give me a hint to prove this exercise from Cormen’s book: “Prove that no matter that the node starts with a binary search tree of height h, consecutive TREE-SUCCESSOR calls take O (k + h) time.

+5
source share
2 answers
  • Let it xbe the starting node and zbe the end of the node after ksuccessive calls to TREE-SUCCESSOR.
  • Let be pa simple path between xand zinclusive.
  • Let yis the common ancestor xand zwho visits p.
  • Length pno more than 2hthat O(h).
  • Let outputare the elements whose values ​​are between x.keyand z.keyinclusive.
  • The size outputis equal O(k).
  • When making ksequential calls to TREE-SUCCESSOR, the nodes located in pare visited, and except for the nodes x, yand zif the visited tree is node in p, then all its elements are in output.
  • Thus, the working time O(h+k).
+6
source

Hint: work out a small example, observe the result, try to extrapolate the reason.

, .

node, k Tree-Succcesor - . ( ) ? (: (x)). , (?).

: O(2h+k).

+3

More articles:


All Articles