equal
deleted
inserted
replaced
354 |
354 |
355 subsection \<open>@{const ipl}\<close> |
355 subsection \<open>@{const ipl}\<close> |
356 |
356 |
357 text \<open>The internal path length of a tree:\<close> |
357 text \<open>The internal path length of a tree:\<close> |
358 |
358 |
359 lemma ipl_if_complete: "complete t |
359 lemma ipl_if_complete_int: |
360 \<Longrightarrow> ipl t = (let h = height t in 2 + h*2^h - 2^(h+1))" |
360 "complete t \<Longrightarrow> int(ipl t) = (int(height t) - 2) * 2^(height t) + 2" |
361 proof(induction t) |
361 apply(induction t) |
362 case (Node l x r) |
362 apply simp |
363 have *: "2^(n+1) \<le> 2 + n*2^n" for n :: nat |
363 apply simp |
364 by(induction n) auto |
364 apply (simp add: algebra_simps size_if_complete of_nat_diff) |
365 have **: "(0::nat) < 2^n" for n :: nat by simp |
365 done |
366 let ?h = "height r" |
|
367 show ?case using Node *[of ?h] **[of ?h] by (simp add: size_if_complete Let_def) |
|
368 qed simp |
|
369 |
366 |
370 |
367 |
371 subsection "List of entries" |
368 subsection "List of entries" |
372 |
369 |
373 lemma set_inorder[simp]: "set (inorder t) = set_tree t" |
370 lemma set_inorder[simp]: "set (inorder t) = set_tree t" |