src/HOL/Data_Structures/AVL_Set.thy
changeset 69597 ff784d5a5bfb
parent 68440 6826718f732d
child 70350 571ae57313a4
equal deleted inserted replaced
69596:c8a2755bf220 69597:ff784d5a5bfb
   490 proof (induction n rule: fib.induct)
   490 proof (induction n rule: fib.induct)
   491   case (3 n)
   491   case (3 n)
   492   thus ?case using assms by (cases n) (auto simp: eval_nat_numeral)
   492   thus ?case using assms by (cases n) (auto simp: eval_nat_numeral)
   493 qed (insert assms, auto)
   493 qed (insert assms, auto)
   494 
   494 
   495 text \<open>An exponential lower bound for @{const fib}:\<close>
   495 text \<open>An exponential lower bound for \<^const>\<open>fib\<close>:\<close>
   496 
   496 
   497 lemma fib_lowerbound:
   497 lemma fib_lowerbound:
   498   defines "\<phi> \<equiv> (1 + sqrt 5) / 2"
   498   defines "\<phi> \<equiv> (1 + sqrt 5) / 2"
   499   defines "c \<equiv> 1 / \<phi> ^ 2"
   499   defines "c \<equiv> 1 / \<phi> ^ 2"
   500   assumes "n > 0"
   500   assumes "n > 0"
   532   also have "\<dots> \<le> size1 t"
   532   also have "\<dots> \<le> size1 t"
   533     using avl_fib_bound[of t "height t"] assms by simp
   533     using avl_fib_bound[of t "height t"] assms by simp
   534   finally show ?thesis .
   534   finally show ?thesis .
   535 qed
   535 qed
   536 
   536 
   537 text \<open>The height of an AVL tree is most @{term "(1/log 2 \<phi>)"} \<open>\<approx> 1.44\<close> times worse
   537 text \<open>The height of an AVL tree is most \<^term>\<open>(1/log 2 \<phi>)\<close> \<open>\<approx> 1.44\<close> times worse
   538 than @{term "log 2 (size1 t)"}:\<close>
   538 than \<^term>\<open>log 2 (size1 t)\<close>:\<close>
   539 
   539 
   540 lemma  avl_height_upperbound:
   540 lemma  avl_height_upperbound:
   541   defines "\<phi> \<equiv> (1 + sqrt 5) / 2"
   541   defines "\<phi> \<equiv> (1 + sqrt 5) / 2"
   542   assumes "avl t"
   542   assumes "avl t"
   543   shows   "height t \<le> (1/log 2 \<phi>) * log 2 (size1 t)"
   543   shows   "height t \<le> (1/log 2 \<phi>) * log 2 (size1 t)"