src/HOL/ex/AVL.ML
changeset 12486 0ed8bdd883e0
parent 8797 b55e2354d71e
child 13187 e5434b822a96
equal deleted inserted replaced
12485:3df60299a6d0 12486:0ed8bdd883e0
   127  by (Asm_simp_tac 1);
   127  by (Asm_simp_tac 1);
   128 by (case_tac "x<nat" 1);
   128 by (case_tac "x<nat" 1);
   129  by (case_tac "height (insert x tree1) = Suc (Suc (height tree2))" 1);
   129  by (case_tac "height (insert x tree1) = Suc (Suc (height tree2))" 1);
   130   by (forw_inst_tac [("n","nat")]  height_l_bal 1);  
   130   by (forw_inst_tac [("n","nat")]  height_l_bal 1);  
   131   by (asm_full_simp_tac (simpset() addsimps [max_def]) 1);
   131   by (asm_full_simp_tac (simpset() addsimps [max_def]) 1);
   132   by(fast_tac (claset() addss simpset()) 1);
   132   by (fast_tac (claset() addss simpset()) 1);
   133  by (asm_full_simp_tac (simpset() addsimps [max_def]) 1);
   133  by (asm_full_simp_tac (simpset() addsimps [max_def]) 1);
   134  by(fast_tac (claset() addss simpset()) 1);
   134  by (fast_tac (claset() addss simpset()) 1);
   135 by (case_tac "height (insert x tree2) = Suc (Suc (height tree1))" 1);
   135 by (case_tac "height (insert x tree2) = Suc (Suc (height tree1))" 1);
   136  by (forw_inst_tac [("n","nat")]  height_r_bal 1); 
   136  by (forw_inst_tac [("n","nat")]  height_r_bal 1); 
   137  by (asm_full_simp_tac (simpset() addsimps [max_def]) 1);
   137  by (asm_full_simp_tac (simpset() addsimps [max_def]) 1);
   138  by(fast_tac (claset() addss simpset()) 1);
   138  by (fast_tac (claset() addss simpset()) 1);
   139 by (asm_full_simp_tac (simpset() addsimps [max_def]) 1);
   139 by (asm_full_simp_tac (simpset() addsimps [max_def]) 1);
   140 by(fast_tac (claset() addss simpset()) 1);
   140 by (fast_tac (claset() addss simpset()) 1);
   141 qed_spec_mp "height_insert";
   141 qed_spec_mp "height_insert";
   142 
   142 
   143 
   143 
   144 Goal
   144 Goal
   145 "!!x. [| height (insert x l) ~= Suc(Suc(height r)); isbal (insert x l); isbal (MKT n l r) |] \
   145 "!!x. [| height (insert x l) ~= Suc(Suc(height r)); isbal (insert x l); isbal (MKT n l r) |] \
   172    by (fast_tac (claset() addIs [isbal_lr_rot] addss (simpset() 
   172    by (fast_tac (claset() addIs [isbal_lr_rot] addss (simpset() 
   173 	addsimps [l_bal_def])) 1);  
   173 	addsimps [l_bal_def])) 1);  
   174   by (fast_tac (claset() addIs [isbal_r_rot] addss (simpset() 
   174   by (fast_tac (claset() addIs [isbal_r_rot] addss (simpset() 
   175 	addsimps [l_bal_def])) 1);  
   175 	addsimps [l_bal_def])) 1);  
   176  by (Clarify_tac 1);
   176  by (Clarify_tac 1);
   177  by (forward_tac [isbal_insert_left] 1);
   177  by (ftac isbal_insert_left 1);
   178    by (Asm_full_simp_tac 1); 
   178    by (Asm_full_simp_tac 1); 
   179   ba 1;
   179   by (assume_tac 1);
   180  by (Asm_full_simp_tac 1); 
   180  by (Asm_full_simp_tac 1); 
   181 by (case_tac "height (insert x tree2) = Suc (Suc (height tree1))" 1);
   181 by (case_tac "height (insert x tree2) = Suc (Suc (height tree1))" 1);
   182  by (case_tac "bal (insert x tree2) = Left" 1);
   182  by (case_tac "bal (insert x tree2) = Left" 1);
   183   by (fast_tac (claset() addIs [isbal_rl_rot] addss (simpset() 
   183   by (fast_tac (claset() addIs [isbal_rl_rot] addss (simpset() 
   184 	addsimps [r_bal_def])) 1);  
   184 	addsimps [r_bal_def])) 1);  
   185  by (fast_tac (claset() addIs [isbal_l_rot] addss (simpset() 
   185  by (fast_tac (claset() addIs [isbal_l_rot] addss (simpset() 
   186 	addsimps [r_bal_def])) 1);  
   186 	addsimps [r_bal_def])) 1);  
   187 by (Clarify_tac 1);
   187 by (Clarify_tac 1);
   188 by (forward_tac [isbal_insert_right] 1);
   188 by (ftac isbal_insert_right 1);
   189    by (Asm_full_simp_tac 1); 
   189    by (Asm_full_simp_tac 1); 
   190   ba 1;
   190   by (assume_tac 1);
   191  by (Asm_full_simp_tac 1); 
   191  by (Asm_full_simp_tac 1); 
   192 qed_spec_mp "isbal_insert";
   192 qed_spec_mp "isbal_insert";
   193 
   193 
   194 
   194 
   195 (******************************    isin    **********************************)
   195 (******************************    isin    **********************************)
   241 
   241 
   242 Goal
   242 Goal
   243 "isin y (insert x t) = (y=x | isin y t)";
   243 "isin y (insert x t) = (y=x | isin y t)";
   244 by (induct_tac "t" 1);
   244 by (induct_tac "t" 1);
   245  by (Asm_simp_tac 1);
   245  by (Asm_simp_tac 1);
   246 by(asm_simp_tac (simpset() addsimps [l_bal_def,isin_lr_rot,isin_r_rot,
   246 by (asm_simp_tac (simpset() addsimps [l_bal_def,isin_lr_rot,isin_r_rot,
   247 	r_bal_def,isin_rl_rot,isin_l_rot]) 1);
   247 	r_bal_def,isin_rl_rot,isin_l_rot]) 1);
   248 by(Blast_tac 1);
   248 by (Blast_tac 1);
   249 qed "isin_insert";
   249 qed "isin_insert";
   250 
   250 
   251 
   251 
   252 (******************************    isord    **********************************)
   252 (******************************    isord    **********************************)
   253 
   253 
   259 by (case_tac "l" 1); 
   259 by (case_tac "l" 1); 
   260  by (Asm_simp_tac 1);
   260  by (Asm_simp_tac 1);
   261 by (case_tac "tree2" 1);
   261 by (case_tac "tree2" 1);
   262  by (Asm_simp_tac 1);
   262  by (Asm_simp_tac 1);
   263 by (Asm_simp_tac 1);
   263 by (Asm_simp_tac 1);
   264 by(blast_tac (claset() addIs [less_trans])1);
   264 by (blast_tac (claset() addIs [less_trans])1);
   265 qed_spec_mp "isord_lr_rot";
   265 qed_spec_mp "isord_lr_rot";
   266 
   266 
   267 
   267 
   268 Goalw [bal_def]
   268 Goalw [bal_def]
   269 "height l = Suc(Suc(height r)) --> bal l ~= Right --> isord (MKT n l r) \
   269 "height l = Suc(Suc(height r)) --> bal l ~= Right --> isord (MKT n l r) \
   280 by (case_tac "r" 1); 
   280 by (case_tac "r" 1); 
   281  by (Asm_simp_tac 1);
   281  by (Asm_simp_tac 1);
   282 by (case_tac "tree1" 1);
   282 by (case_tac "tree1" 1);
   283  by (asm_simp_tac (simpset() addsimps [le_def]) 1);
   283  by (asm_simp_tac (simpset() addsimps [le_def]) 1);
   284 by (Asm_simp_tac 1);
   284 by (Asm_simp_tac 1);
   285 by(blast_tac (claset() addIs [less_trans])1);
   285 by (blast_tac (claset() addIs [less_trans])1);
   286 qed_spec_mp "isord_rl_rot";
   286 qed_spec_mp "isord_rl_rot";
   287 
   287 
   288 
   288 
   289 Goalw [bal_def]
   289 Goalw [bal_def]
   290 "height r = Suc(Suc(height l)) --> bal r ~= Left --> isord (MKT n l r)  \
   290 "height r = Suc(Suc(height l)) --> bal r ~= Left --> isord (MKT n l r)  \
   291 \ --> isord (l_rot (n, l, r))";
   291 \ --> isord (l_rot (n, l, r))";
   292 by (case_tac "r" 1); 
   292 by (case_tac "r" 1); 
   293  by (Asm_simp_tac 1);
   293  by (Asm_simp_tac 1);
   294 by (Asm_simp_tac 1);
   294 by (Asm_simp_tac 1);
   295 by(blast_tac (claset() addIs [less_trans])1);
   295 by (blast_tac (claset() addIs [less_trans])1);
   296 qed_spec_mp "isord_l_rot";
   296 qed_spec_mp "isord_l_rot";
   297 
   297 
   298 (* insert operation presreves isord property *)
   298 (* insert operation presreves isord property *)
   299 
   299 
   300 Goal
   300 Goal