--- a/src/HOL/Data_Structures/Tree23_Map.thy Sat Oct 24 13:42:31 2015 +0200
+++ b/src/HOL/Data_Structures/Tree23_Map.thy Sun Oct 25 16:52:13 2015 +0100
@@ -1,6 +1,6 @@
(* Author: Tobias Nipkow *)
-section \<open>2-3 Tree Implementation of Maps\<close>
+section \<open>A 2-3 Tree Implementation of Maps\<close>
theory Tree23_Map
imports
@@ -70,49 +70,39 @@
"delete k t = tree\<^sub>d(del k t)"
-subsection "Proofs for Lookup"
+subsection \<open>Functional Correctness\<close>
lemma lookup: "sorted1(inorder t) \<Longrightarrow> lookup t x = map_of (inorder t) x"
by (induction t) (auto simp: map_of_simps split: option.split)
-subsection "Proofs for Update"
-
-text {* Balanced trees *}
-
-text{* First a standard proof that @{const upd} preserves @{const bal}. *}
-
-lemma bal_upd: "bal t \<Longrightarrow> bal (tree\<^sub>i(upd a b t)) \<and> height(upd a b t) = height t"
-by (induct t) (auto split: up\<^sub>i.split)
-
-text{* Now an alternative proof (by Brian Huffman) that runs faster because
-two properties (balance and height) are combined in one predicate. *}
-
-lemma full\<^sub>i_ins: "full n t \<Longrightarrow> full\<^sub>i n (upd a b t)"
-by (induct rule: full.induct, auto split: up\<^sub>i.split)
-
-text {* The @{const update} operation preserves balance. *}
-
-lemma bal_update: "bal t \<Longrightarrow> bal (update a b t)"
-unfolding bal_iff_full update_def
-apply (erule exE)
-apply (drule full\<^sub>i_ins [of _ _ a b])
-apply (cases "upd a b t")
-apply (auto intro: full.intros)
-done
-
-text {* Functional correctness of @{const "update"}. *}
-
lemma inorder_upd:
"sorted1(inorder t) \<Longrightarrow> inorder(tree\<^sub>i(upd a b t)) = upd_list a b (inorder t)"
by(induction t) (auto simp: upd_list_simps split: up\<^sub>i.splits)
-lemma inorder_update:
+corollary inorder_update:
"sorted1(inorder t) \<Longrightarrow> inorder(update a b t) = upd_list a b (inorder t)"
by(simp add: update_def inorder_upd)
-subsection "Proofs for Deletion"
+lemma inorder_del: "\<lbrakk> bal t ; sorted1(inorder t) \<rbrakk> \<Longrightarrow>
+ inorder(tree\<^sub>d (del x t)) = del_list x (inorder t)"
+by(induction t rule: del.induct)
+ (auto simp: del_list_simps inorder_nodes del_minD split: prod.splits)
+
+corollary inorder_delete: "\<lbrakk> bal t ; sorted1(inorder t) \<rbrakk> \<Longrightarrow>
+ inorder(delete x t) = del_list x (inorder t)"
+by(simp add: delete_def inorder_del)
+
+
+subsection \<open>Balancedness\<close>
+
+lemma bal_upd: "bal t \<Longrightarrow> bal (tree\<^sub>i(upd a b t)) \<and> height(upd a b t) = height t"
+by (induct t) (auto split: up\<^sub>i.split)(* 30 secs in 2015 *)
+
+corollary bal_update: "bal t \<Longrightarrow> bal (update a b t)"
+by (simp add: update_def bal_upd)
+
lemma height_del: "bal t \<Longrightarrow> height(del x t) = height t"
by(induction x t rule: del.induct)
@@ -125,15 +115,6 @@
corollary bal_delete: "bal t \<Longrightarrow> bal(delete x t)"
by(simp add: delete_def bal_tree\<^sub>d_del)
-lemma inorder_del: "\<lbrakk> bal t ; sorted1(inorder t) \<rbrakk> \<Longrightarrow>
- inorder(tree\<^sub>d (del x t)) = del_list x (inorder t)"
-by(induction t rule: del.induct)
- (auto simp: del_list_simps inorder_nodes del_minD split: prod.splits)
-
-lemma inorder_delete: "\<lbrakk> bal t ; sorted1(inorder t) \<rbrakk> \<Longrightarrow>
- inorder(delete x t) = del_list x (inorder t)"
-by(simp add: delete_def inorder_del)
-
subsection \<open>Overall Correctness\<close>
--- a/src/HOL/Data_Structures/Tree23_Set.thy Sat Oct 24 13:42:31 2015 +0200
+++ b/src/HOL/Data_Structures/Tree23_Set.thy Sun Oct 25 16:52:13 2015 +0100
@@ -1,6 +1,6 @@
(* Author: Tobias Nipkow *)
-section \<open>2-3 Tree Implementation of Sets\<close>
+section \<open>A 2-3 Tree Implementation of Sets\<close>
theory Tree23_Set
imports
@@ -111,8 +111,6 @@
"delete k t = tree\<^sub>d(del k t)"
-declare prod.splits [split]
-
subsection "Functional Correctness"
@@ -165,12 +163,12 @@
"del_min t = (x,t') \<Longrightarrow> bal t \<Longrightarrow> height t > 0 \<Longrightarrow>
x # inorder(tree\<^sub>d t') = inorder t"
by(induction t arbitrary: t' rule: del_min.induct)
- (auto simp: inorder_nodes)
+ (auto simp: inorder_nodes split: prod.splits)
lemma inorder_del: "\<lbrakk> bal t ; sorted(inorder t) \<rbrakk> \<Longrightarrow>
inorder(tree\<^sub>d (del x t)) = del_list x (inorder t)"
by(induction t rule: del.induct)
- (auto simp: del_list_simps inorder_nodes del_minD)
+ (auto simp: del_list_simps inorder_nodes del_minD split: prod.splits)
lemma inorder_delete: "\<lbrakk> bal t ; sorted(inorder t) \<rbrakk> \<Longrightarrow>
inorder(delete x t) = del_list x (inorder t)"
@@ -196,7 +194,7 @@
end
lemma bal_ins: "bal t \<Longrightarrow> bal (tree\<^sub>i(ins a t)) \<and> height(ins a t) = height t"
-by (induct t) (auto split: up\<^sub>i.split)
+by (induct t) (auto split: up\<^sub>i.split) (* 25 secs in 2015 *)
text{* Now an alternative proof (by Brian Huffman) that runs faster because
two properties (balance and height) are combined in one predicate. *}
@@ -336,16 +334,17 @@
lemma height_del: "bal t \<Longrightarrow> height(del x t) = height t"
by(induction x t rule: del.induct)
- (auto simp add: heights max_def height_del_min)
+ (auto simp: heights max_def height_del_min split: prod.splits)
lemma bal_del_min:
"\<lbrakk> del_min t = (x, t'); bal t; height t > 0 \<rbrakk> \<Longrightarrow> bal (tree\<^sub>d t')"
by(induct t arbitrary: x t' rule: del_min.induct)
- (auto simp: heights height_del_min bals)
+ (auto simp: heights height_del_min bals split: prod.splits)
lemma bal_tree\<^sub>d_del: "bal t \<Longrightarrow> bal(tree\<^sub>d(del x t))"
by(induction x t rule: del.induct)
- (auto simp: bals bal_del_min height_del height_del_min)
+ (auto simp: bals bal_del_min height_del height_del_min split: prod.splits)
+
corollary bal_delete: "bal t \<Longrightarrow> bal(delete x t)"
by(simp add: delete_def bal_tree\<^sub>d_del)