I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is:

Prove by induction that if all nodes in a splay tree is accessed in sequential order, the resulting tree consists of a chain of left children.

When I take a set a set of numbers like 5,1,3,6,2,4 and put them into a Splay tree, and then access them all sequentially (1,2,3,4,5,6), it is very easy to see that the question statement is indeed true (This is a great visualizer) . I just can't find a way to write it in a proof by induction. Any help would be greatly appreciated as I am a struggling beginner.

  • $\begingroup$ You did not add the link to the visualizer. $\endgroup$ – sayantankhan Oct 5 '14 at 3:32
  • $\begingroup$ @Bolt64 updated. $\endgroup$ – Gdgames Gamers Oct 5 '14 at 3:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.