equal
deleted
inserted
replaced
41 by (induction t) (auto simp: elems_simps2) |
41 by (induction t) (auto simp: elems_simps2) |
42 |
42 |
43 |
43 |
44 lemma inorder_insert: |
44 lemma inorder_insert: |
45 "sorted(inorder t) \<Longrightarrow> inorder(insert x t) = ins_list x (inorder t)" |
45 "sorted(inorder t) \<Longrightarrow> inorder(insert x t) = ins_list x (inorder t)" |
46 by(induction t) (auto simp: ins_simps) |
46 by(induction t) (auto simp: ins_list_simps) |
47 |
47 |
48 |
48 |
49 lemma del_minD: |
49 lemma del_minD: |
50 "del_min t = (x,t') \<Longrightarrow> t \<noteq> Leaf \<Longrightarrow> sorted(inorder t) \<Longrightarrow> |
50 "del_min t = (x,t') \<Longrightarrow> t \<noteq> Leaf \<Longrightarrow> sorted(inorder t) \<Longrightarrow> |
51 x # inorder t' = inorder t" |
51 x # inorder t' = inorder t" |
52 by(induction t arbitrary: t' rule: del_min.induct) |
52 by(induction t arbitrary: t' rule: del_min.induct) |
53 (auto simp: sorted_lems split: prod.splits) |
53 (auto simp: sorted_lems split: prod.splits) |
54 |
54 |
55 lemma inorder_delete: |
55 lemma inorder_delete: |
56 "sorted(inorder t) \<Longrightarrow> inorder(delete x t) = del_list x (inorder t)" |
56 "sorted(inorder t) \<Longrightarrow> inorder(delete x t) = del_list x (inorder t)" |
57 by(induction t) (auto simp: del_simps del_minD split: prod.splits) |
57 by(induction t) (auto simp: del_list_simps del_minD split: prod.splits) |
58 |
58 |
59 |
59 |
60 interpretation Set_by_Ordered |
60 interpretation Set_by_Ordered |
61 where empty = Leaf and isin = isin and insert = insert and delete = delete |
61 where empty = Leaf and isin = isin and insert = insert and delete = delete |
62 and inorder = inorder and wf = "\<lambda>_. True" |
62 and inorder = inorder and wf = "\<lambda>_. True" |