0
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ What have you tried? Have you tried proving the base case? Have you written out the inductive hypothesis? Have you tried seeing what you need to prove? Have you reviewed standard textbooks on proof by induction? There are lots and lots of resources on the subject; there would not be a lot of value in asking us to repeat all that to you. I expect you to make a serious effort on your own before asking, and to show us in the question what you tried. Please show us what you've tried in the question; otherwise we cannot be expected to help you. $\endgroup$ – D.W.♦ Oct 5 '14 at 2:52
  • $\begingroup$ @D.W. Yes, I have read Discrete Math textbooks on proof by induction all of which deal with number based proofs. And ones featuring trees are also of numerical nature like tree height, depth, and path lengths. Perhaps it is my lack of understanding, but I see this problem as a "graphical" question which is essentially my issue. I do not see how I can define a base case for this proof. Maybe a smallest of hints can help me get started. $\endgroup$ – oneCoderToRuleThemAll Oct 5 '14 at 3:15
  • $\begingroup$ Are you looking for help understanding how to do proof by induction with trees? A typical approach would be to try proof by induction on the number of nodes in the tree -- which makes it a numerical question, not a graphical question. $\endgroup$ – D.W.♦ Oct 5 '14 at 4:47
  • $\begingroup$ Another common quantity is to perform induction over the height of the trees, or go for structural induction. Here, you'll need to figure out how refer to the accessing process for $n-1$ nodes when talking about the same process for $n$ nodes. $\endgroup$ – Raphael♦ Oct 5 '14 at 8:45
  • $\begingroup$ @Raphael Can you give me an example ? I am still struggling with this proof. The book where I took this from claims that this proof is "very easy" and omits any elaboration. $\endgroup$ – oneCoderToRuleThemAll Oct 5 '14 at 15:28

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.