src/HOL/Data_Structures/Tree_Set.thy
changeset 61231 cc6969542f8d
parent 61229 0b9c45c4af29
child 61428 5e1938107371
equal deleted inserted replaced
61230:e367b93f78e5 61231:cc6969542f8d
    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"