walkccc / CLRS

📚 Solutions to Introduction to Algorithms Third Edition
https://walkccc.me/CLRS
MIT License
4.72k stars 1.26k forks source link

Problem 13-2.a: about Fibonacci numbers #273

Open run27017 opened 4 years ago

run27017 commented 4 years ago

For this problem, I get some wonders:

part a

In answer a, it says the Fibonacci numbers recurrence is:

T(h)=T(h−1)+T(h−2)+1

But in my mind, the Fibonacci numbers recurrence seems to be:

T(h)=T(h−1)+T(h−2)

part b

For BALANCE operation of b, it seems wrong. For most tutorial of AVL tree, it is divided into four cases: LL, LR, RL, RR. All of them rotates most two times. However, the answer gives a recursion and it cannot see ending conditions legibly because we cannot claim the height minus 1 after left-rotate.

There are also other odds:

  1. the while condition, which will rotate nodes until UNBAL <= 1
  2. why executing balance recursion after left rotating not right one