replaced new type ('a,'b) tree by old type ('a*'b) tree. default tip
authornipkow
Wed Sep 25 17:22:57 2019 +0200 (3 weeks ago ago)
changeset 709443fb16bed5d6c
parent 70943 c5232e6fb10b
replaced new type ('a,'b) tree by old type ('a*'b) tree.
src/HOL/Data_Structures/AA_Map.thy
src/HOL/Data_Structures/AA_Set.thy
src/HOL/Data_Structures/AVL_Map.thy
src/HOL/Data_Structures/AVL_Set.thy
src/HOL/Data_Structures/Isin2.thy
src/HOL/Data_Structures/Leftist_Heap.thy
src/HOL/Data_Structures/Lookup2.thy
src/HOL/Data_Structures/RBT.thy
src/HOL/Data_Structures/RBT_Map.thy
src/HOL/Data_Structures/RBT_Set.thy
src/HOL/Data_Structures/Set2_Join.thy
src/HOL/Data_Structures/Set2_Join_RBT.thy
src/HOL/Data_Structures/Tree2.thy
src/HOL/Data_Structures/Trie_Map.thy
     1.1 --- a/src/HOL/Data_Structures/AA_Map.thy	Tue Sep 24 17:36:14 2019 +0200
     1.2 +++ b/src/HOL/Data_Structures/AA_Map.thy	Wed Sep 25 17:22:57 2019 +0200
     1.3 @@ -9,21 +9,21 @@
     1.4  begin
     1.5  
     1.6  fun update :: "'a::linorder \<Rightarrow> 'b \<Rightarrow> ('a*'b) aa_tree \<Rightarrow> ('a*'b) aa_tree" where
     1.7 -"update x y Leaf = Node Leaf (x,y) 1 Leaf" |
     1.8 -"update x y (Node t1 (a,b) lv t2) =
     1.9 +"update x y Leaf = Node Leaf ((x,y), 1) Leaf" |
    1.10 +"update x y (Node t1 ((a,b), lv) t2) =
    1.11    (case cmp x a of
    1.12 -     LT \<Rightarrow> split (skew (Node (update x y t1) (a,b) lv t2)) |
    1.13 -     GT \<Rightarrow> split (skew (Node t1 (a,b) lv (update x y t2))) |
    1.14 -     EQ \<Rightarrow> Node t1 (x,y) lv t2)"
    1.15 +     LT \<Rightarrow> split (skew (Node (update x y t1) ((a,b), lv) t2)) |
    1.16 +     GT \<Rightarrow> split (skew (Node t1 ((a,b), lv) (update x y t2))) |
    1.17 +     EQ \<Rightarrow> Node t1 ((x,y), lv) t2)"
    1.18  
    1.19  fun delete :: "'a::linorder \<Rightarrow> ('a*'b) aa_tree \<Rightarrow> ('a*'b) aa_tree" where
    1.20  "delete _ Leaf = Leaf" |
    1.21 -"delete x (Node l (a,b) lv r) =
    1.22 +"delete x (Node l ((a,b), lv) r) =
    1.23    (case cmp x a of
    1.24 -     LT \<Rightarrow> adjust (Node (delete x l) (a,b) lv r) |
    1.25 -     GT \<Rightarrow> adjust (Node l (a,b) lv (delete x r)) |
    1.26 +     LT \<Rightarrow> adjust (Node (delete x l) ((a,b), lv) r) |
    1.27 +     GT \<Rightarrow> adjust (Node l ((a,b), lv) (delete x r)) |
    1.28       EQ \<Rightarrow> (if l = Leaf then r
    1.29 -            else let (l',ab') = split_max l in adjust (Node l' ab' lv r)))"
    1.30 +            else let (l',ab') = split_max l in adjust (Node l' (ab', lv) r)))"
    1.31  
    1.32  
    1.33  subsection "Invariance"
    1.34 @@ -64,20 +64,20 @@
    1.35  qed simp
    1.36  
    1.37  lemma lvl_update_incr_iff: "(lvl(update a b t) = lvl t + 1) \<longleftrightarrow>
    1.38 -  (\<exists>l x r. update a b t = Node l x (lvl t + 1) r \<and> lvl l = lvl r)"
    1.39 +  (\<exists>l x r. update a b t = Node l (x,lvl t + 1) r \<and> lvl l = lvl r)"
    1.40  apply(cases t)
    1.41  apply(auto simp add: skew_case split_case split: if_splits)
    1.42  apply(auto split: tree.splits if_splits)
    1.43  done
    1.44  
    1.45  lemma invar_update: "invar t \<Longrightarrow> invar(update a b t)"
    1.46 -proof(induction t)
    1.47 +proof(induction t rule: tree2_induct)
    1.48    case N: (Node l xy n r)
    1.49    hence il: "invar l" and ir: "invar r" by auto
    1.50    note iil = N.IH(1)[OF il]
    1.51    note iir = N.IH(2)[OF ir]
    1.52    obtain x y where [simp]: "xy = (x,y)" by fastforce
    1.53 -  let ?t = "Node l xy n r"
    1.54 +  let ?t = "Node l (xy, n) r"
    1.55    have "a < x \<or> a = x \<or> x < a" by auto
    1.56    moreover
    1.57    have ?case if "a < x"
    1.58 @@ -87,16 +87,16 @@
    1.59        by (simp add: skew_invar split_invar del: invar.simps)
    1.60    next
    1.61      case (Incr)
    1.62 -    then obtain t1 w t2 where ial[simp]: "update a b l = Node t1 w n t2"
    1.63 +    then obtain t1 w t2 where ial[simp]: "update a b l = Node t1 (w, n) t2"
    1.64        using N.prems by (auto simp: lvl_Suc_iff)
    1.65      have l12: "lvl t1 = lvl t2"
    1.66        by (metis Incr(1) ial lvl_update_incr_iff tree.inject)
    1.67 -    have "update a b ?t = split(skew(Node (update a b l) xy n r))"
    1.68 +    have "update a b ?t = split(skew(Node (update a b l) (xy, n) r))"
    1.69        by(simp add: \<open>a<x\<close>)
    1.70 -    also have "skew(Node (update a b l) xy n r) = Node t1 w n (Node t2 xy n r)"
    1.71 +    also have "skew(Node (update a b l) (xy, n) r) = Node t1 (w, n) (Node t2 (xy, n) r)"
    1.72        by(simp)
    1.73      also have "invar(split \<dots>)"
    1.74 -    proof (cases r)
    1.75 +    proof (cases r rule: tree2_cases)
    1.76        case Leaf
    1.77        hence "l = Leaf" using N.prems by(auto simp: lvl_0_iff)
    1.78        thus ?thesis using Leaf ial by simp
    1.79 @@ -118,14 +118,14 @@
    1.80      thus ?case
    1.81      proof
    1.82        assume 0: "n = lvl r"
    1.83 -      have "update a b ?t = split(skew(Node l xy n (update a b r)))"
    1.84 +      have "update a b ?t = split(skew(Node l (xy, n) (update a b r)))"
    1.85          using \<open>a>x\<close> by(auto)
    1.86 -      also have "skew(Node l xy n (update a b r)) = Node l xy n (update a b r)"
    1.87 +      also have "skew(Node l (xy, n) (update a b r)) = Node l (xy, n) (update a b r)"
    1.88          using N.prems by(simp add: skew_case split: tree.split)
    1.89        also have "invar(split \<dots>)"
    1.90        proof -
    1.91          from lvl_update_sngl[OF ir sngl_if_invar[OF \<open>invar ?t\<close> 0], of a b]
    1.92 -        obtain t1 p t2 where iar: "update a b r = Node t1 p n t2"
    1.93 +        obtain t1 p t2 where iar: "update a b r = Node t1 (p, n) t2"
    1.94            using N.prems 0 by (auto simp: lvl_Suc_iff)
    1.95          from N.prems iar 0 iir
    1.96          show ?thesis by (auto simp: split_case split: tree.splits)
    1.97 @@ -156,13 +156,13 @@
    1.98  declare invar.simps(2)[simp del]
    1.99  
   1.100  theorem post_delete: "invar t \<Longrightarrow> post_del t (delete x t)"
   1.101 -proof (induction t)
   1.102 +proof (induction t  rule: tree2_induct)
   1.103    case (Node l ab lv r)
   1.104  
   1.105    obtain a b where [simp]: "ab = (a,b)" by fastforce
   1.106  
   1.107    let ?l' = "delete x l" and ?r' = "delete x r"
   1.108 -  let ?t = "Node l ab lv r" let ?t' = "delete x ?t"
   1.109 +  let ?t = "Node l (ab, lv) r" let ?t' = "delete x ?t"
   1.110  
   1.111    from Node.prems have inv_l: "invar l" and inv_r: "invar r" by (auto)
   1.112  
     2.1 --- a/src/HOL/Data_Structures/AA_Set.thy	Tue Sep 24 17:36:14 2019 +0200
     2.2 +++ b/src/HOL/Data_Structures/AA_Set.thy	Wed Sep 25 17:22:57 2019 +0200
     2.3 @@ -10,67 +10,67 @@
     2.4    Cmp
     2.5  begin
     2.6  
     2.7 -type_synonym 'a aa_tree = "('a,nat) tree"
     2.8 +type_synonym 'a aa_tree = "('a*nat) tree"
     2.9  
    2.10  definition empty :: "'a aa_tree" where
    2.11  "empty = Leaf"
    2.12  
    2.13  fun lvl :: "'a aa_tree \<Rightarrow> nat" where
    2.14  "lvl Leaf = 0" |
    2.15 -"lvl (Node _ _ lv _) = lv"
    2.16 +"lvl (Node _ (_, lv) _) = lv"
    2.17  
    2.18  fun invar :: "'a aa_tree \<Rightarrow> bool" where
    2.19  "invar Leaf = True" |
    2.20 -"invar (Node l a h r) =
    2.21 +"invar (Node l (a, h) r) =
    2.22   (invar l \<and> invar r \<and>
    2.23 -  h = lvl l + 1 \<and> (h = lvl r + 1 \<or> (\<exists>lr b rr. r = Node lr b h rr \<and> h = lvl rr + 1)))"
    2.24 +  h = lvl l + 1 \<and> (h = lvl r + 1 \<or> (\<exists>lr b rr. r = Node lr (b,h) rr \<and> h = lvl rr + 1)))"
    2.25  
    2.26  fun skew :: "'a aa_tree \<Rightarrow> 'a aa_tree" where
    2.27 -"skew (Node (Node t1 b lvb t2) a lva t3) =
    2.28 -  (if lva = lvb then Node t1 b lvb (Node t2 a lva t3) else Node (Node t1 b lvb t2) a lva t3)" |
    2.29 +"skew (Node (Node t1 (b, lvb) t2) (a, lva) t3) =
    2.30 +  (if lva = lvb then Node t1 (b, lvb) (Node t2 (a, lva) t3) else Node (Node t1 (b, lvb) t2) (a, lva) t3)" |
    2.31  "skew t = t"
    2.32  
    2.33  fun split :: "'a aa_tree \<Rightarrow> 'a aa_tree" where
    2.34 -"split (Node t1 a lva (Node t2 b lvb (Node t3 c lvc t4))) =
    2.35 +"split (Node t1 (a, lva) (Node t2 (b, lvb) (Node t3 (c, lvc) t4))) =
    2.36     (if lva = lvb \<and> lvb = lvc \<comment> \<open>\<open>lva = lvc\<close> suffices\<close>
    2.37 -    then Node (Node t1 a lva t2) b (lva+1) (Node t3 c lva t4)
    2.38 -    else Node t1 a lva (Node t2 b lvb (Node t3 c lvc t4)))" |
    2.39 +    then Node (Node t1 (a,lva) t2) (b,lva+1) (Node t3 (c, lva) t4)
    2.40 +    else Node t1 (a,lva) (Node t2 (b,lvb) (Node t3 (c,lvc) t4)))" |
    2.41  "split t = t"
    2.42  
    2.43  hide_const (open) insert
    2.44  
    2.45  fun insert :: "'a::linorder \<Rightarrow> 'a aa_tree \<Rightarrow> 'a aa_tree" where
    2.46 -"insert x Leaf = Node Leaf x 1 Leaf" |
    2.47 -"insert x (Node t1 a lv t2) =
    2.48 +"insert x Leaf = Node Leaf (x, 1) Leaf" |
    2.49 +"insert x (Node t1 (a,lv) t2) =
    2.50    (case cmp x a of
    2.51 -     LT \<Rightarrow> split (skew (Node (insert x t1) a lv t2)) |
    2.52 -     GT \<Rightarrow> split (skew (Node t1 a lv (insert x t2))) |
    2.53 -     EQ \<Rightarrow> Node t1 x lv t2)"
    2.54 +     LT \<Rightarrow> split (skew (Node (insert x t1) (a,lv) t2)) |
    2.55 +     GT \<Rightarrow> split (skew (Node t1 (a,lv) (insert x t2))) |
    2.56 +     EQ \<Rightarrow> Node t1 (x, lv) t2)"
    2.57  
    2.58  fun sngl :: "'a aa_tree \<Rightarrow> bool" where
    2.59  "sngl Leaf = False" |
    2.60 -"sngl (Node _ _ _ Leaf) = True" |
    2.61 -"sngl (Node _ _ lva (Node _ _ lvb _)) = (lva > lvb)"
    2.62 +"sngl (Node _ _ Leaf) = True" |
    2.63 +"sngl (Node _ (_, lva) (Node _ (_, lvb) _)) = (lva > lvb)"
    2.64  
    2.65  definition adjust :: "'a aa_tree \<Rightarrow> 'a aa_tree" where
    2.66  "adjust t =
    2.67   (case t of
    2.68 -  Node l x lv r \<Rightarrow>
    2.69 +  Node l (x,lv) r \<Rightarrow>
    2.70     (if lvl l >= lv-1 \<and> lvl r >= lv-1 then t else
    2.71 -    if lvl r < lv-1 \<and> sngl l then skew (Node l x (lv-1) r) else
    2.72 +    if lvl r < lv-1 \<and> sngl l then skew (Node l (x,lv-1) r) else
    2.73      if lvl r < lv-1
    2.74      then case l of
    2.75 -           Node t1 a lva (Node t2 b lvb t3)
    2.76 -             \<Rightarrow> Node (Node t1 a lva t2) b (lvb+1) (Node t3 x (lv-1) r) 
    2.77 +           Node t1 (a,lva) (Node t2 (b,lvb) t3)
    2.78 +             \<Rightarrow> Node (Node t1 (a,lva) t2) (b,lvb+1) (Node t3 (x,lv-1) r) 
    2.79      else
    2.80 -    if lvl r < lv then split (Node l x (lv-1) r)
    2.81 +    if lvl r < lv then split (Node l (x,lv-1) r)
    2.82      else
    2.83        case r of
    2.84 -        Node t1 b lvb t4 \<Rightarrow>
    2.85 +        Node t1 (b,lvb) t4 \<Rightarrow>
    2.86            (case t1 of
    2.87 -             Node t2 a lva t3
    2.88 -               \<Rightarrow> Node (Node l x (lv-1) t2) a (lva+1)
    2.89 -                    (split (Node t3 b (if sngl t1 then lva else lva+1) t4)))))"
    2.90 +             Node t2 (a,lva) t3
    2.91 +               \<Rightarrow> Node (Node l (x,lv-1) t2) (a,lva+1)
    2.92 +                    (split (Node t3 (b, if sngl t1 then lva else lva+1) t4)))))"
    2.93  
    2.94  text\<open>In the paper, the last case of \<^const>\<open>adjust\<close> is expressed with the help of an
    2.95  incorrect auxiliary function \texttt{nlvl}.
    2.96 @@ -81,20 +81,20 @@
    2.97  is not restored.\<close>
    2.98  
    2.99  fun split_max :: "'a aa_tree \<Rightarrow> 'a aa_tree * 'a" where
   2.100 -"split_max (Node l a lv Leaf) = (l,a)" |
   2.101 -"split_max (Node l a lv r) = (let (r',b) = split_max r in (adjust(Node l a lv r'), b))"
   2.102 +"split_max (Node l (a,lv) Leaf) = (l,a)" |
   2.103 +"split_max (Node l (a,lv) r) = (let (r',b) = split_max r in (adjust(Node l (a,lv) r'), b))"
   2.104  
   2.105  fun delete :: "'a::linorder \<Rightarrow> 'a aa_tree \<Rightarrow> 'a aa_tree" where
   2.106  "delete _ Leaf = Leaf" |
   2.107 -"delete x (Node l a lv r) =
   2.108 +"delete x (Node l (a,lv) r) =
   2.109    (case cmp x a of
   2.110 -     LT \<Rightarrow> adjust (Node (delete x l) a lv r) |
   2.111 -     GT \<Rightarrow> adjust (Node l a lv (delete x r)) |
   2.112 +     LT \<Rightarrow> adjust (Node (delete x l) (a,lv) r) |
   2.113 +     GT \<Rightarrow> adjust (Node l (a,lv) (delete x r)) |
   2.114       EQ \<Rightarrow> (if l = Leaf then r
   2.115 -            else let (l',b) = split_max l in adjust (Node l' b lv r)))"
   2.116 +            else let (l',b) = split_max l in adjust (Node l' (b,lv) r)))"
   2.117  
   2.118  fun pre_adjust where
   2.119 -"pre_adjust (Node l a lv r) = (invar l \<and> invar r \<and>
   2.120 +"pre_adjust (Node l (a,lv) r) = (invar l \<and> invar r \<and>
   2.121      ((lv = lvl l + 1 \<and> (lv = lvl r + 1 \<or> lv = lvl r + 2 \<or> lv = lvl r \<and> sngl r)) \<or>
   2.122       (lv = lvl l + 2 \<and> (lv = lvl r + 1 \<or> lv = lvl r \<and> sngl r))))"
   2.123  
   2.124 @@ -103,23 +103,23 @@
   2.125  subsection "Auxiliary Proofs"
   2.126  
   2.127  lemma split_case: "split t = (case t of
   2.128 -  Node t1 x lvx (Node t2 y lvy (Node t3 z lvz t4)) \<Rightarrow>
   2.129 +  Node t1 (x,lvx) (Node t2 (y,lvy) (Node t3 (z,lvz) t4)) \<Rightarrow>
   2.130     (if lvx = lvy \<and> lvy = lvz
   2.131 -    then Node (Node t1 x lvx t2) y (lvx+1) (Node t3 z lvx t4)
   2.132 +    then Node (Node t1 (x,lvx) t2) (y,lvx+1) (Node t3 (z,lvx) t4)
   2.133      else t)
   2.134    | t \<Rightarrow> t)"
   2.135  by(auto split: tree.split)
   2.136  
   2.137  lemma skew_case: "skew t = (case t of
   2.138 -  Node (Node t1 y lvy t2) x lvx t3 \<Rightarrow>
   2.139 -  (if lvx = lvy then Node t1 y lvx (Node t2 x lvx t3) else t)
   2.140 +  Node (Node t1 (y,lvy) t2) (x,lvx) t3 \<Rightarrow>
   2.141 +  (if lvx = lvy then Node t1 (y, lvx) (Node t2 (x,lvx) t3) else t)
   2.142   | t \<Rightarrow> t)"
   2.143  by(auto split: tree.split)
   2.144  
   2.145  lemma lvl_0_iff: "invar t \<Longrightarrow> lvl t = 0 \<longleftrightarrow> t = Leaf"
   2.146  by(cases t) auto
   2.147  
   2.148 -lemma lvl_Suc_iff: "lvl t = Suc n \<longleftrightarrow> (\<exists> l a r. t = Node l a (Suc n) r)"
   2.149 +lemma lvl_Suc_iff: "lvl t = Suc n \<longleftrightarrow> (\<exists> l a r. t = Node l (a,Suc n) r)"
   2.150  by(cases t) auto
   2.151  
   2.152  lemma lvl_skew: "lvl (skew t) = lvl t"
   2.153 @@ -128,16 +128,16 @@
   2.154  lemma lvl_split: "lvl (split t) = lvl t \<or> lvl (split t) = lvl t + 1 \<and> sngl (split t)"
   2.155  by(cases t rule: split.cases) auto
   2.156  
   2.157 -lemma invar_2Nodes:"invar (Node l x lv (Node rl rx rlv rr)) =
   2.158 -     (invar l \<and> invar \<langle>rl, rx, rlv, rr\<rangle> \<and> lv = Suc (lvl l) \<and>
   2.159 +lemma invar_2Nodes:"invar (Node l (x,lv) (Node rl (rx, rlv) rr)) =
   2.160 +     (invar l \<and> invar \<langle>rl, (rx, rlv), rr\<rangle> \<and> lv = Suc (lvl l) \<and>
   2.161       (lv = Suc rlv \<or> rlv = lv \<and> lv = Suc (lvl rr)))"
   2.162  by simp
   2.163  
   2.164  lemma invar_NodeLeaf[simp]:
   2.165 -  "invar (Node l x lv Leaf) = (invar l \<and> lv = Suc (lvl l) \<and> lv = Suc 0)"
   2.166 +  "invar (Node l (x,lv) Leaf) = (invar l \<and> lv = Suc (lvl l) \<and> lv = Suc 0)"
   2.167  by simp
   2.168  
   2.169 -lemma sngl_if_invar: "invar (Node l a n r) \<Longrightarrow> n = lvl r \<Longrightarrow> sngl r"
   2.170 +lemma sngl_if_invar: "invar (Node l (a, n) r) \<Longrightarrow> n = lvl r \<Longrightarrow> sngl r"
   2.171  by(cases r rule: sngl.cases) clarsimp+
   2.172  
   2.173  
   2.174 @@ -167,7 +167,8 @@
   2.175      thus ?thesis using 2 by (auto simp add: skew_case split_case split: tree.splits)
   2.176    next
   2.177      case GT
   2.178 -    thus ?thesis using 2 proof (cases t1)
   2.179 +    thus ?thesis using 2
   2.180 +    proof (cases t1 rule: tree2_cases)
   2.181        case Node
   2.182        thus ?thesis using 2 GT  
   2.183          apply (auto simp add: skew_case split_case split: tree.splits)
   2.184 @@ -183,32 +184,32 @@
   2.185  by(cases t rule: split.cases) clarsimp+
   2.186  
   2.187  lemma invar_NodeL:
   2.188 -  "\<lbrakk> invar(Node l x n r); invar l'; lvl l' = lvl l \<rbrakk> \<Longrightarrow> invar(Node l' x n r)"
   2.189 +  "\<lbrakk> invar(Node l (x, n) r); invar l'; lvl l' = lvl l \<rbrakk> \<Longrightarrow> invar(Node l' (x, n) r)"
   2.190  by(auto)
   2.191  
   2.192  lemma invar_NodeR:
   2.193 -  "\<lbrakk> invar(Node l x n r); n = lvl r + 1; invar r'; lvl r' = lvl r \<rbrakk> \<Longrightarrow> invar(Node l x n r')"
   2.194 +  "\<lbrakk> invar(Node l (x, n) r); n = lvl r + 1; invar r'; lvl r' = lvl r \<rbrakk> \<Longrightarrow> invar(Node l (x, n) r')"
   2.195  by(auto)
   2.196  
   2.197  lemma invar_NodeR2:
   2.198 -  "\<lbrakk> invar(Node l x n r); sngl r'; n = lvl r + 1; invar r'; lvl r' = n \<rbrakk> \<Longrightarrow> invar(Node l x n r')"
   2.199 +  "\<lbrakk> invar(Node l (x, n) r); sngl r'; n = lvl r + 1; invar r'; lvl r' = n \<rbrakk> \<Longrightarrow> invar(Node l (x, n) r')"
   2.200  by(cases r' rule: sngl.cases) clarsimp+
   2.201  
   2.202  
   2.203  lemma lvl_insert_incr_iff: "(lvl(insert a t) = lvl t + 1) \<longleftrightarrow>
   2.204 -  (\<exists>l x r. insert a t = Node l x (lvl t + 1) r \<and> lvl l = lvl r)"
   2.205 -apply(cases t)
   2.206 +  (\<exists>l x r. insert a t = Node l (x, lvl t + 1) r \<and> lvl l = lvl r)"
   2.207 +apply(cases t rule: tree2_cases)
   2.208  apply(auto simp add: skew_case split_case split: if_splits)
   2.209  apply(auto split: tree.splits if_splits)
   2.210  done
   2.211  
   2.212  lemma invar_insert: "invar t \<Longrightarrow> invar(insert a t)"
   2.213 -proof(induction t)
   2.214 +proof(induction t rule: tree2_induct)
   2.215    case N: (Node l x n r)
   2.216    hence il: "invar l" and ir: "invar r" by auto
   2.217    note iil = N.IH(1)[OF il]
   2.218    note iir = N.IH(2)[OF ir]
   2.219 -  let ?t = "Node l x n r"
   2.220 +  let ?t = "Node l (x, n) r"
   2.221    have "a < x \<or> a = x \<or> x < a" by auto
   2.222    moreover
   2.223    have ?case if "a < x"
   2.224 @@ -218,16 +219,16 @@
   2.225        by (simp add: skew_invar split_invar del: invar.simps)
   2.226    next
   2.227      case (Incr)
   2.228 -    then obtain t1 w t2 where ial[simp]: "insert a l = Node t1 w n t2"
   2.229 +    then obtain t1 w t2 where ial[simp]: "insert a l = Node t1 (w, n) t2"
   2.230        using N.prems by (auto simp: lvl_Suc_iff)
   2.231      have l12: "lvl t1 = lvl t2"
   2.232        by (metis Incr(1) ial lvl_insert_incr_iff tree.inject)
   2.233 -    have "insert a ?t = split(skew(Node (insert a l) x n r))"
   2.234 +    have "insert a ?t = split(skew(Node (insert a l) (x,n) r))"
   2.235        by(simp add: \<open>a<x\<close>)
   2.236 -    also have "skew(Node (insert a l) x n r) = Node t1 w n (Node t2 x n r)"
   2.237 +    also have "skew(Node (insert a l) (x,n) r) = Node t1 (w,n) (Node t2 (x,n) r)"
   2.238        by(simp)
   2.239      also have "invar(split \<dots>)"
   2.240 -    proof (cases r)
   2.241 +    proof (cases r rule: tree2_cases)
   2.242        case Leaf
   2.243        hence "l = Leaf" using N.prems by(auto simp: lvl_0_iff)
   2.244        thus ?thesis using Leaf ial by simp
   2.245 @@ -249,14 +250,14 @@
   2.246      thus ?case
   2.247      proof
   2.248        assume 0: "n = lvl r"
   2.249 -      have "insert a ?t = split(skew(Node l x n (insert a r)))"
   2.250 +      have "insert a ?t = split(skew(Node l (x, n) (insert a r)))"
   2.251          using \<open>a>x\<close> by(auto)
   2.252 -      also have "skew(Node l x n (insert a r)) = Node l x n (insert a r)"
   2.253 +      also have "skew(Node l (x,n) (insert a r)) = Node l (x,n) (insert a r)"
   2.254          using N.prems by(simp add: skew_case split: tree.split)
   2.255        also have "invar(split \<dots>)"
   2.256        proof -
   2.257          from lvl_insert_sngl[OF ir sngl_if_invar[OF \<open>invar ?t\<close> 0], of a]
   2.258 -        obtain t1 y t2 where iar: "insert a r = Node t1 y n t2"
   2.259 +        obtain t1 y t2 where iar: "insert a r = Node t1 (y,n) t2"
   2.260            using N.prems 0 by (auto simp: lvl_Suc_iff)
   2.261          from N.prems iar 0 iir
   2.262          show ?thesis by (auto simp: split_case split: tree.splits)
   2.263 @@ -285,21 +286,21 @@
   2.264  
   2.265  subsubsection "Proofs for delete"
   2.266  
   2.267 -lemma invarL: "ASSUMPTION(invar \<langle>l, a, lv, r\<rangle>) \<Longrightarrow> invar l"
   2.268 +lemma invarL: "ASSUMPTION(invar \<langle>l, (a, lv), r\<rangle>) \<Longrightarrow> invar l"
   2.269  by(simp add: ASSUMPTION_def)
   2.270  
   2.271 -lemma invarR: "ASSUMPTION(invar \<langle>lv, l, a, r\<rangle>) \<Longrightarrow> invar r"
   2.272 +lemma invarR: "ASSUMPTION(invar \<langle>l, (a,lv), r\<rangle>) \<Longrightarrow> invar r"
   2.273  by(simp add: ASSUMPTION_def)
   2.274  
   2.275  lemma sngl_NodeI:
   2.276 -  "sngl (Node l a lv r) \<Longrightarrow> sngl (Node l' a' lv r)"
   2.277 -by(cases r) (simp_all)
   2.278 +  "sngl (Node l (a,lv) r) \<Longrightarrow> sngl (Node l' (a', lv) r)"
   2.279 +by(cases r rule: tree2_cases) (simp_all)
   2.280  
   2.281  
   2.282  declare invarL[simp] invarR[simp]
   2.283  
   2.284  lemma pre_cases:
   2.285 -assumes "pre_adjust (Node l x lv r)"
   2.286 +assumes "pre_adjust (Node l (x,lv) r)"
   2.287  obtains
   2.288   (tSngl) "invar l \<and> invar r \<and>
   2.289      lv = Suc (lvl r) \<and> lvl l = lvl r" |
   2.290 @@ -317,38 +318,39 @@
   2.291  declare invar.simps(2)[simp del] invar_2Nodes[simp add]
   2.292  
   2.293  lemma invar_adjust:
   2.294 -  assumes pre: "pre_adjust (Node l a lv r)"
   2.295 -  shows  "invar(adjust (Node l a lv r))"
   2.296 +  assumes pre: "pre_adjust (Node l (a,lv) r)"
   2.297 +  shows  "invar(adjust (Node l (a,lv) r))"
   2.298  using pre proof (cases rule: pre_cases)
   2.299    case (tDouble) thus ?thesis unfolding adjust_def by (cases r) (auto simp: invar.simps(2)) 
   2.300  next 
   2.301    case (rDown)
   2.302 -  from rDown obtain llv ll la lr where l: "l = Node ll la llv lr" by (cases l) auto
   2.303 +  from rDown obtain llv ll la lr where l: "l = Node ll (la, llv) lr" by (cases l) auto
   2.304    from rDown show ?thesis unfolding adjust_def by (auto simp: l invar.simps(2) split: tree.splits)
   2.305  next
   2.306    case (lDown_tDouble)
   2.307 -  from lDown_tDouble obtain rlv rr ra rl where r: "r = Node rl ra rlv rr" by (cases r) auto
   2.308 +  from lDown_tDouble obtain rlv rr ra rl where r: "r = Node rl (ra, rlv) rr" by (cases r) auto
   2.309    from lDown_tDouble and r obtain rrlv rrr rra rrl where
   2.310 -    rr :"rr = Node rrr rra rrlv rrl" by (cases rr) auto
   2.311 +    rr :"rr = Node rrr (rra, rrlv) rrl" by (cases rr) auto
   2.312    from  lDown_tDouble show ?thesis unfolding adjust_def r rr
   2.313 -    apply (cases rl) apply (auto simp add: invar.simps(2) split!: if_split)
   2.314 +    apply (cases rl rule: tree2_cases) apply (auto simp add: invar.simps(2) split!: if_split)
   2.315      using lDown_tDouble by (auto simp: split_case lvl_0_iff  elim:lvl.elims split: tree.split)
   2.316  qed (auto simp: split_case invar.simps(2) adjust_def split: tree.splits)
   2.317  
   2.318  lemma lvl_adjust:
   2.319 -  assumes "pre_adjust (Node l a lv r)"
   2.320 -  shows "lv = lvl (adjust(Node l a lv r)) \<or> lv = lvl (adjust(Node l a lv r)) + 1"
   2.321 -using assms(1) proof(cases rule: pre_cases)
   2.322 +  assumes "pre_adjust (Node l (a,lv) r)"
   2.323 +  shows "lv = lvl (adjust(Node l (a,lv) r)) \<or> lv = lvl (adjust(Node l (a,lv) r)) + 1"
   2.324 +using assms(1)
   2.325 +proof(cases rule: pre_cases)
   2.326    case lDown_tSngl thus ?thesis
   2.327 -    using lvl_split[of "\<langle>l, a, lvl r, r\<rangle>"] by (auto simp: adjust_def)
   2.328 +    using lvl_split[of "\<langle>l, (a, lvl r), r\<rangle>"] by (auto simp: adjust_def)
   2.329  next
   2.330    case lDown_tDouble thus ?thesis
   2.331      by (auto simp: adjust_def invar.simps(2) split: tree.split)
   2.332  qed (auto simp: adjust_def split: tree.splits)
   2.333  
   2.334 -lemma sngl_adjust: assumes "pre_adjust (Node l a lv r)"
   2.335 -  "sngl \<langle>l, a, lv, r\<rangle>" "lv = lvl (adjust \<langle>l, a, lv, r\<rangle>)"
   2.336 -  shows "sngl (adjust \<langle>l, a, lv, r\<rangle>)" 
   2.337 +lemma sngl_adjust: assumes "pre_adjust (Node l (a,lv) r)"
   2.338 +  "sngl \<langle>l, (a, lv), r\<rangle>" "lv = lvl (adjust \<langle>l, (a, lv), r\<rangle>)"
   2.339 +  shows "sngl (adjust \<langle>l, (a, lv), r\<rangle>)" 
   2.340  using assms proof (cases rule: pre_cases)
   2.341    case rDown
   2.342    thus ?thesis using assms(2,3) unfolding adjust_def
   2.343 @@ -361,38 +363,38 @@
   2.344    (lvl t' = lvl t \<and> sngl t \<longrightarrow> sngl t')"
   2.345  
   2.346  lemma pre_adj_if_postR:
   2.347 -  "invar\<langle>lv, l, a, r\<rangle> \<Longrightarrow> post_del r r' \<Longrightarrow> pre_adjust \<langle>lv, l, a, r'\<rangle>"
   2.348 +  "invar\<langle>lv, (l, a), r\<rangle> \<Longrightarrow> post_del r r' \<Longrightarrow> pre_adjust \<langle>lv, (l, a), r'\<rangle>"
   2.349  by(cases "sngl r")
   2.350    (auto simp: pre_adjust.simps post_del_def invar.simps(2) elim: sngl.elims)
   2.351  
   2.352  lemma pre_adj_if_postL:
   2.353 -  "invar\<langle>l, a, lv, r\<rangle> \<Longrightarrow> post_del l l' \<Longrightarrow> pre_adjust \<langle>l', b, lv, r\<rangle>"
   2.354 +  "invar\<langle>l, (a, lv), r\<rangle> \<Longrightarrow> post_del l l' \<Longrightarrow> pre_adjust \<langle>l', (b, lv), r\<rangle>"
   2.355  by(cases "sngl r")
   2.356    (auto simp: pre_adjust.simps post_del_def invar.simps(2) elim: sngl.elims)
   2.357  
   2.358  lemma post_del_adjL:
   2.359 -  "\<lbrakk> invar\<langle>l, a, lv, r\<rangle>; pre_adjust \<langle>l', b, lv, r\<rangle> \<rbrakk>
   2.360 -  \<Longrightarrow> post_del \<langle>l, a, lv, r\<rangle> (adjust \<langle>l', b, lv, r\<rangle>)"
   2.361 +  "\<lbrakk> invar\<langle>l, (a, lv), r\<rangle>; pre_adjust \<langle>l', (b, lv), r\<rangle> \<rbrakk>
   2.362 +  \<Longrightarrow> post_del \<langle>l, (a, lv), r\<rangle> (adjust \<langle>l', (b, lv), r\<rangle>)"
   2.363  unfolding post_del_def
   2.364  by (metis invar_adjust lvl_adjust sngl_NodeI sngl_adjust lvl.simps(2))
   2.365  
   2.366  lemma post_del_adjR:
   2.367 -assumes "invar\<langle>lv, l, a, r\<rangle>" "pre_adjust \<langle>lv, l, a, r'\<rangle>" "post_del r r'"
   2.368 -shows "post_del \<langle>lv, l, a, r\<rangle> (adjust \<langle>lv, l, a, r'\<rangle>)"
   2.369 +assumes "invar\<langle>l, (a,lv), r\<rangle>" "pre_adjust \<langle>l, (a,lv), r'\<rangle>" "post_del r r'"
   2.370 +shows "post_del \<langle>l, (a,lv), r\<rangle> (adjust \<langle>l, (a,lv), r'\<rangle>)"
   2.371  proof(unfold post_del_def, safe del: disjCI)
   2.372 -  let ?t = "\<langle>lv, l, a, r\<rangle>"
   2.373 -  let ?t' = "adjust \<langle>lv, l, a, r'\<rangle>"
   2.374 +  let ?t = "\<langle>l, (a,lv), r\<rangle>"
   2.375 +  let ?t' = "adjust \<langle>l, (a,lv), r'\<rangle>"
   2.376    show "invar ?t'" by(rule invar_adjust[OF assms(2)])
   2.377    show "lvl ?t' = lvl ?t \<or> lvl ?t' + 1 = lvl ?t"
   2.378      using lvl_adjust[OF assms(2)] by auto
   2.379    show "sngl ?t'" if as: "lvl ?t' = lvl ?t" "sngl ?t"
   2.380    proof -
   2.381 -    have s: "sngl \<langle>lv, l, a, r'\<rangle>"
   2.382 -    proof(cases r')
   2.383 +    have s: "sngl \<langle>l, (a,lv), r'\<rangle>"
   2.384 +    proof(cases r' rule: tree2_cases)
   2.385        case Leaf thus ?thesis by simp
   2.386      next
   2.387        case Node thus ?thesis using as(2) assms(1,3)
   2.388 -      by (cases r) (auto simp: post_del_def)
   2.389 +      by (cases r rule: tree2_cases) (auto simp: post_del_def)
   2.390      qed
   2.391      show ?thesis using as(1) sngl_adjust[OF assms(2) s] by simp
   2.392    qed
   2.393 @@ -403,22 +405,22 @@
   2.394  theorem post_split_max:
   2.395   "\<lbrakk> invar t; (t', x) = split_max t; t \<noteq> Leaf \<rbrakk> \<Longrightarrow> post_del t t'"
   2.396  proof (induction t arbitrary: t' rule: split_max.induct)
   2.397 -  case (2 lv l a lvr rl ra rr)
   2.398 -  let ?r =  "\<langle>lvr, rl, ra, rr\<rangle>"
   2.399 -  let ?t = "\<langle>lv, l, a, ?r\<rangle>"
   2.400 +  case (2 l a lv rl bl rr)
   2.401 +  let ?r =  "\<langle>rl, bl, rr\<rangle>"
   2.402 +  let ?t = "\<langle>l, (a, lv), ?r\<rangle>"
   2.403    from "2.prems"(2) obtain r' where r': "(r', x) = split_max ?r"
   2.404 -    and [simp]: "t' = adjust \<langle>lv, l, a, r'\<rangle>" by auto
   2.405 +    and [simp]: "t' = adjust \<langle>l, (a, lv), r'\<rangle>" by auto
   2.406    from  "2.IH"[OF _ r'] \<open>invar ?t\<close> have post: "post_del ?r r'" by simp
   2.407    note preR = pre_adj_if_postR[OF \<open>invar ?t\<close> post]
   2.408    show ?case by (simp add: post_del_adjR[OF "2.prems"(1) preR post])
   2.409  qed (auto simp: post_del_def)
   2.410  
   2.411  theorem post_delete: "invar t \<Longrightarrow> post_del t (delete x t)"
   2.412 -proof (induction t)
   2.413 +proof (induction t rule: tree2_induct)
   2.414    case (Node l a lv r)
   2.415  
   2.416    let ?l' = "delete x l" and ?r' = "delete x r"
   2.417 -  let ?t = "Node l a lv r" let ?t' = "delete x ?t"
   2.418 +  let ?t = "Node l (a,lv) r" let ?t' = "delete x ?t"
   2.419  
   2.420    from Node.prems have inv_l: "invar l" and inv_r: "invar r" by (auto)
   2.421  
     3.1 --- a/src/HOL/Data_Structures/AVL_Map.thy	Tue Sep 24 17:36:14 2019 +0200
     3.2 +++ b/src/HOL/Data_Structures/AVL_Map.thy	Wed Sep 25 17:22:57 2019 +0200
     3.3 @@ -9,16 +9,16 @@
     3.4  begin
     3.5  
     3.6  fun update :: "'a::linorder \<Rightarrow> 'b \<Rightarrow> ('a*'b) avl_tree \<Rightarrow> ('a*'b) avl_tree" where
     3.7 -"update x y Leaf = Node Leaf (x,y) 1 Leaf" |
     3.8 -"update x y (Node l (a,b) h r) = (case cmp x a of
     3.9 -   EQ \<Rightarrow> Node l (x,y) h r |
    3.10 +"update x y Leaf = Node Leaf ((x,y), 1) Leaf" |
    3.11 +"update x y (Node l ((a,b), h) r) = (case cmp x a of
    3.12 +   EQ \<Rightarrow> Node l ((x,y), h) r |
    3.13     LT \<Rightarrow> balL (update x y l) (a,b) r |
    3.14     GT \<Rightarrow> balR l (a,b) (update x y r))"
    3.15  
    3.16  fun delete :: "'a::linorder \<Rightarrow> ('a*'b) avl_tree \<Rightarrow> ('a*'b) avl_tree" where
    3.17  "delete _ Leaf = Leaf" |
    3.18 -"delete x (Node l (a,b) h r) = (case cmp x a of
    3.19 -   EQ \<Rightarrow> del_root (Node l (a,b) h r) |
    3.20 +"delete x (Node l ((a,b), h) r) = (case cmp x a of
    3.21 +   EQ \<Rightarrow> del_root (Node l ((a,b), h) r) |
    3.22     LT \<Rightarrow> balR (delete x l) (a,b) r |
    3.23     GT \<Rightarrow> balL l (a,b) (delete x r))"
    3.24  
    3.25 @@ -114,7 +114,7 @@
    3.26    assumes "avl t" 
    3.27    shows "avl(delete x t)" and "height t = (height (delete x t)) \<or> height t = height (delete x t) + 1"
    3.28  using assms
    3.29 -proof (induct t)
    3.30 +proof (induct t rule: tree2_induct)
    3.31    case (Node l n h r)
    3.32    obtain a b where [simp]: "n = (a,b)" by fastforce
    3.33    case 1
    3.34 @@ -134,8 +134,8 @@
    3.35    show ?case
    3.36    proof(cases "x = a")
    3.37      case True
    3.38 -    with 1 have "height (Node l n h r) = height(del_root (Node l n h r))
    3.39 -      \<or> height (Node l n h r) = height(del_root (Node l n h r)) + 1"
    3.40 +    with 1 have "height (Node l (n, h) r) = height(del_root (Node l (n, h) r))
    3.41 +      \<or> height (Node l (n, h) r) = height(del_root (Node l (n, h) r)) + 1"
    3.42        by (subst height_del_root,simp_all)
    3.43      with True show ?thesis by simp
    3.44    next
     4.1 --- a/src/HOL/Data_Structures/AVL_Set.thy	Tue Sep 24 17:36:14 2019 +0200
     4.2 +++ b/src/HOL/Data_Structures/AVL_Set.thy	Wed Sep 25 17:22:57 2019 +0200
     4.3 @@ -12,7 +12,7 @@
     4.4    "HOL-Number_Theory.Fib"
     4.5  begin
     4.6  
     4.7 -type_synonym 'a avl_tree = "('a,nat) tree"
     4.8 +type_synonym 'a avl_tree = "('a*nat) tree"
     4.9  
    4.10  definition empty :: "'a avl_tree" where
    4.11  "empty = Leaf"
    4.12 @@ -21,25 +21,25 @@
    4.13  
    4.14  fun avl :: "'a avl_tree \<Rightarrow> bool" where
    4.15  "avl Leaf = True" |
    4.16 -"avl (Node l a h r) =
    4.17 +"avl (Node l (a,h) r) =
    4.18   ((height l = height r \<or> height l = height r + 1 \<or> height r = height l + 1) \<and> 
    4.19    h = max (height l) (height r) + 1 \<and> avl l \<and> avl r)"
    4.20  
    4.21  fun ht :: "'a avl_tree \<Rightarrow> nat" where
    4.22  "ht Leaf = 0" |
    4.23 -"ht (Node l a h r) = h"
    4.24 +"ht (Node l (a,h) r) = h"
    4.25  
    4.26  definition node :: "'a avl_tree \<Rightarrow> 'a \<Rightarrow> 'a avl_tree \<Rightarrow> 'a avl_tree" where
    4.27 -"node l a r = Node l a (max (ht l) (ht r) + 1) r"
    4.28 +"node l a r = Node l (a, max (ht l) (ht r) + 1) r"
    4.29  
    4.30  definition balL :: "'a avl_tree \<Rightarrow> 'a \<Rightarrow> 'a avl_tree \<Rightarrow> 'a avl_tree" where
    4.31  "balL l a r =
    4.32    (if ht l = ht r + 2 then
    4.33       case l of 
    4.34 -       Node bl b _ br \<Rightarrow>
    4.35 +       Node bl (b, _) br \<Rightarrow>
    4.36           if ht bl < ht br then
    4.37             case br of
    4.38 -             Node cl c _ cr \<Rightarrow> node (node bl b cl) c (node cr a r)
    4.39 +             Node cl (c, _) cr \<Rightarrow> node (node bl b cl) c (node cr a r)
    4.40           else node bl b (node br a r)
    4.41     else node l a r)"
    4.42  
    4.43 @@ -47,38 +47,38 @@
    4.44  "balR l a r =
    4.45     (if ht r = ht l + 2 then
    4.46        case r of
    4.47 -        Node bl b _ br \<Rightarrow>
    4.48 +        Node bl (b, _) br \<Rightarrow>
    4.49            if ht bl > ht br then
    4.50              case bl of
    4.51 -              Node cl c _ cr \<Rightarrow> node (node l a cl) c (node cr b br)
    4.52 +              Node cl (c, _) cr \<Rightarrow> node (node l a cl) c (node cr b br)
    4.53            else node (node l a bl) b br
    4.54    else node l a r)"
    4.55  
    4.56  fun insert :: "'a::linorder \<Rightarrow> 'a avl_tree \<Rightarrow> 'a avl_tree" where
    4.57 -"insert x Leaf = Node Leaf x 1 Leaf" |
    4.58 -"insert x (Node l a h r) = (case cmp x a of
    4.59 -   EQ \<Rightarrow> Node l a h r |
    4.60 +"insert x Leaf = Node Leaf (x, 1) Leaf" |
    4.61 +"insert x (Node l (a, h) r) = (case cmp x a of
    4.62 +   EQ \<Rightarrow> Node l (a, h) r |
    4.63     LT \<Rightarrow> balL (insert x l) a r |
    4.64     GT \<Rightarrow> balR l a (insert x r))"
    4.65  
    4.66  fun split_max :: "'a avl_tree \<Rightarrow> 'a avl_tree * 'a" where
    4.67 -"split_max (Node l a _ r) =
    4.68 +"split_max (Node l (a, _) r) =
    4.69    (if r = Leaf then (l,a) else let (r',a') = split_max r in (balL l a r', a'))"
    4.70  
    4.71  lemmas split_max_induct = split_max.induct[case_names Node Leaf]
    4.72  
    4.73  fun del_root :: "'a avl_tree \<Rightarrow> 'a avl_tree" where
    4.74 -"del_root (Node Leaf a h r) = r" |
    4.75 -"del_root (Node l a h Leaf) = l" |
    4.76 -"del_root (Node l a h r) = (let (l', a') = split_max l in balR l' a' r)"
    4.77 +"del_root (Node Leaf (a,h) r) = r" |
    4.78 +"del_root (Node l (a,h) Leaf) = l" |
    4.79 +"del_root (Node l (a,h) r) = (let (l', a') = split_max l in balR l' a' r)"
    4.80  
    4.81 -lemmas del_root_cases = del_root.cases[case_names Leaf_t Node_Leaf Node_Node]
    4.82 +lemmas del_root_cases = del_root.cases[split_format(complete), case_names Leaf_t Node_Leaf Node_Node]
    4.83  
    4.84  fun delete :: "'a::linorder \<Rightarrow> 'a avl_tree \<Rightarrow> 'a avl_tree" where
    4.85  "delete _ Leaf = Leaf" |
    4.86 -"delete x (Node l a h r) =
    4.87 +"delete x (Node l (a, h) r) =
    4.88    (case cmp x a of
    4.89 -     EQ \<Rightarrow> del_root (Node l a h r) |
    4.90 +     EQ \<Rightarrow> del_root (Node l (a, h) r) |
    4.91       LT \<Rightarrow> balR (delete x l) a r |
    4.92       GT \<Rightarrow> balL l a (delete x r))"
    4.93  
    4.94 @@ -113,8 +113,8 @@
    4.95    (auto simp: inorder_balL split: if_splits prod.splits tree.split)
    4.96  
    4.97  lemma inorder_del_root:
    4.98 -  "inorder (del_root (Node l a h r)) = inorder l @ inorder r"
    4.99 -by(cases "Node l a h r" rule: del_root.cases)
   4.100 +  "inorder (del_root (Node l ah r)) = inorder l @ inorder r"
   4.101 +by(cases "Node l ah r" rule: del_root.cases)
   4.102    (auto simp: inorder_balL inorder_balR inorder_split_maxD split: if_splits prod.splits)
   4.103  
   4.104  theorem inorder_delete:
   4.105 @@ -134,7 +134,7 @@
   4.106  declare Let_def [simp]
   4.107  
   4.108  lemma ht_height[simp]: "avl t \<Longrightarrow> ht t = height t"
   4.109 -by (cases t) simp_all
   4.110 +by (cases t rule: tree2_cases) simp_all
   4.111  
   4.112  lemma height_balL:
   4.113    "\<lbrakk> height l = height r + 2; avl l; avl r \<rbrakk> \<Longrightarrow>
   4.114 @@ -171,7 +171,7 @@
   4.115    assumes "avl l" "avl r" and "height l = height r \<or> height l = height r + 1
   4.116      \<or> height r = height l + 1 \<or> height l = height r + 2" 
   4.117    shows "avl(balL l a r)"
   4.118 -proof(cases l)
   4.119 +proof(cases l rule: tree2_cases)
   4.120    case Leaf
   4.121    with assms show ?thesis by (simp add: node_def balL_def)
   4.122  next
   4.123 @@ -191,7 +191,7 @@
   4.124    assumes "avl l" and "avl r" and "height l = height r \<or> height l = height r + 1
   4.125      \<or> height r = height l + 1 \<or> height r = height l + 2" 
   4.126    shows "avl(balR l a r)"
   4.127 -proof(cases r)
   4.128 +proof(cases r rule: tree2_cases)
   4.129    case Leaf
   4.130    with assms show ?thesis by (simp add: node_def balR_def)
   4.131  next
   4.132 @@ -216,7 +216,7 @@
   4.133    shows "avl(insert x t)"
   4.134          "(height (insert x t) = height t \<or> height (insert x t) = height t + 1)"
   4.135  using assms
   4.136 -proof (induction t)
   4.137 +proof (induction t rule: tree2_induct)
   4.138    case (Node l a h r)
   4.139    case 1
   4.140    show ?case
   4.141 @@ -304,8 +304,8 @@
   4.142  using assms
   4.143  proof (cases t rule:del_root_cases)
   4.144    case (Node_Node ll ln lh lr n h rl rn rh rr)
   4.145 -  let ?l = "Node ll ln lh lr"
   4.146 -  let ?r = "Node rl rn rh rr"
   4.147 +  let ?l = "Node ll (ln, lh) lr"
   4.148 +  let ?r = "Node rl (rn, rh) rr"
   4.149    let ?l' = "fst (split_max ?l)"
   4.150    from \<open>avl t\<close> and Node_Node have "avl ?r" by simp
   4.151    from \<open>avl t\<close> and Node_Node have "avl ?l" by simp
   4.152 @@ -324,8 +324,8 @@
   4.153  using assms
   4.154  proof (cases t rule: del_root_cases)
   4.155    case (Node_Node ll ln lh lr n h rl rn rh rr)
   4.156 -  let ?l = "Node ll ln lh lr"
   4.157 -  let ?r = "Node rl rn rh rr"
   4.158 +  let ?l = "Node ll (ln, lh) lr"
   4.159 +  let ?r = "Node rl (rn, rh) rr"
   4.160    let ?l' = "fst (split_max ?l)"
   4.161    let ?t' = "balR ?l' (snd(split_max ?l)) ?r"
   4.162    from \<open>avl t\<close> and Node_Node have "avl ?r" by simp
   4.163 @@ -356,7 +356,7 @@
   4.164    assumes "avl t" 
   4.165    shows "avl(delete x t)" and "height t = (height (delete x t)) \<or> height t = height (delete x t) + 1"
   4.166  using assms
   4.167 -proof (induct t)
   4.168 +proof (induct t rule: tree2_induct)
   4.169    case (Node l n h r)
   4.170    case 1
   4.171    show ?case
   4.172 @@ -375,8 +375,8 @@
   4.173    show ?case
   4.174    proof(cases "x = n")
   4.175      case True
   4.176 -    with 1 have "height (Node l n h r) = height(del_root (Node l n h r))
   4.177 -      \<or> height (Node l n h r) = height(del_root (Node l n h r)) + 1"
   4.178 +    with 1 have "height (Node l (n,h) r) = height(del_root (Node l (n,h) r))
   4.179 +      \<or> height (Node l (n,h) r) = height(del_root (Node l (n,h) r)) + 1"
   4.180        by (subst height_del_root,simp_all)
   4.181      with True show ?thesis by simp
   4.182    next
   4.183 @@ -449,7 +449,7 @@
   4.184  
   4.185  lemma height_invers: 
   4.186    "(height t = 0) = (t = Leaf)"
   4.187 -  "avl t \<Longrightarrow> (height t = Suc h) = (\<exists> l a r . t = Node l a (Suc h) r)"
   4.188 +  "avl t \<Longrightarrow> (height t = Suc h) = (\<exists> l a r . t = Node l (a,Suc h) r)"
   4.189  by (induction t) auto
   4.190  
   4.191  text \<open>Any AVL tree of height \<open>h\<close> has at least \<open>fib (h+2)\<close> leaves:\<close>
   4.192 @@ -462,7 +462,7 @@
   4.193  next
   4.194    case (3 h)
   4.195    from "3.prems" obtain l a r where
   4.196 -    [simp]: "t = Node l a (Suc(Suc h)) r" "avl l" "avl r"
   4.197 +    [simp]: "t = Node l (a,Suc(Suc h)) r" "avl l" "avl r"
   4.198      and C: "
   4.199        height r = Suc h \<and> height l = Suc h
   4.200      \<or> height r = Suc h \<and> height l = h
     5.1 --- a/src/HOL/Data_Structures/Isin2.thy	Tue Sep 24 17:36:14 2019 +0200
     5.2 +++ b/src/HOL/Data_Structures/Isin2.thy	Wed Sep 25 17:22:57 2019 +0200
     5.3 @@ -9,18 +9,18 @@
     5.4    Set_Specs
     5.5  begin
     5.6  
     5.7 -fun isin :: "('a::linorder,'b) tree \<Rightarrow> 'a \<Rightarrow> bool" where
     5.8 +fun isin :: "('a::linorder*'b) tree \<Rightarrow> 'a \<Rightarrow> bool" where
     5.9  "isin Leaf x = False" |
    5.10 -"isin (Node l a _ r) x =
    5.11 +"isin (Node l (a,_) r) x =
    5.12    (case cmp x a of
    5.13       LT \<Rightarrow> isin l x |
    5.14       EQ \<Rightarrow> True |
    5.15       GT \<Rightarrow> isin r x)"
    5.16  
    5.17  lemma isin_set_inorder: "sorted(inorder t) \<Longrightarrow> isin t x = (x \<in> set(inorder t))"
    5.18 -by (induction t) (auto simp: isin_simps)
    5.19 +by (induction t rule: tree2_induct) (auto simp: isin_simps)
    5.20  
    5.21  lemma isin_set_tree: "bst t \<Longrightarrow> isin t x \<longleftrightarrow> x \<in> set_tree t"
    5.22 -by(induction t) auto
    5.23 +by(induction t rule: tree2_induct) auto
    5.24  
    5.25  end
     6.1 --- a/src/HOL/Data_Structures/Leftist_Heap.thy	Tue Sep 24 17:36:14 2019 +0200
     6.2 +++ b/src/HOL/Data_Structures/Leftist_Heap.thy	Wed Sep 25 17:22:57 2019 +0200
     6.3 @@ -10,30 +10,30 @@
     6.4    Complex_Main
     6.5  begin
     6.6  
     6.7 -fun mset_tree :: "('a,'b) tree \<Rightarrow> 'a multiset" where
     6.8 +fun mset_tree :: "('a*'b) tree \<Rightarrow> 'a multiset" where
     6.9  "mset_tree Leaf = {#}" |
    6.10 -"mset_tree (Node l a _ r) = {#a#} + mset_tree l + mset_tree r"
    6.11 +"mset_tree (Node l (a, _) r) = {#a#} + mset_tree l + mset_tree r"
    6.12  
    6.13 -type_synonym 'a lheap = "('a,nat)tree"
    6.14 +type_synonym 'a lheap = "('a*nat)tree"
    6.15  
    6.16  fun rank :: "'a lheap \<Rightarrow> nat" where
    6.17  "rank Leaf = 0" |
    6.18 -"rank (Node _ _ _ r) = rank r + 1"
    6.19 +"rank (Node _ _ r) = rank r + 1"
    6.20  
    6.21  fun rk :: "'a lheap \<Rightarrow> nat" where
    6.22  "rk Leaf = 0" |
    6.23 -"rk (Node _ _ n _) = n"
    6.24 +"rk (Node _ (_, n) _) = n"
    6.25  
    6.26  text\<open>The invariants:\<close>
    6.27  
    6.28 -fun (in linorder) heap :: "('a,'b) tree \<Rightarrow> bool" where
    6.29 +fun (in linorder) heap :: "('a*'b) tree \<Rightarrow> bool" where
    6.30  "heap Leaf = True" |
    6.31 -"heap (Node l m _ r) =
    6.32 +"heap (Node l (m, _) r) =
    6.33    (heap l \<and> heap r \<and> (\<forall>x \<in> set_tree l \<union> set_tree r. m \<le> x))"
    6.34  
    6.35  fun ltree :: "'a lheap \<Rightarrow> bool" where
    6.36  "ltree Leaf = True" |
    6.37 -"ltree (Node l a n r) =
    6.38 +"ltree (Node l (a, n) r) =
    6.39   (n = rank r + 1 \<and> rank l \<ge> rank r \<and> ltree l & ltree r)"
    6.40  
    6.41  definition empty :: "'a lheap" where
    6.42 @@ -42,10 +42,10 @@
    6.43  definition node :: "'a lheap \<Rightarrow> 'a \<Rightarrow> 'a lheap \<Rightarrow> 'a lheap" where
    6.44  "node l a r =
    6.45   (let rl = rk l; rr = rk r
    6.46 -  in if rl \<ge> rr then Node l a (rr+1) r else Node r a (rl+1) l)"
    6.47 +  in if rl \<ge> rr then Node l (a,rr+1) r else Node r (a,rl+1) l)"
    6.48  
    6.49  fun get_min :: "'a lheap \<Rightarrow> 'a" where
    6.50 -"get_min(Node l a n r) = a"
    6.51 +"get_min(Node l (a, n) r) = a"
    6.52  
    6.53  text \<open>For function \<open>merge\<close>:\<close>
    6.54  unbundle pattern_aliases
    6.55 @@ -53,7 +53,7 @@
    6.56  fun merge :: "'a::ord lheap \<Rightarrow> 'a lheap \<Rightarrow> 'a lheap" where
    6.57  "merge Leaf t = t" |
    6.58  "merge t Leaf = t" |
    6.59 -"merge (Node l1 a1 n1 r1 =: t1) (Node l2 a2 n2 r2 =: t2) =
    6.60 +"merge (Node l1 (a1, n1) r1 =: t1) (Node l2 (a2, n2) r2 =: t2) =
    6.61     (if a1 \<le> a2 then node l1 a1 (merge r1 t2)
    6.62      else node l2 a2 (merge t1 r2))"
    6.63  
    6.64 @@ -63,18 +63,18 @@
    6.65  lemma merge_code: "merge t1 t2 = (case (t1,t2) of
    6.66    (Leaf, _) \<Rightarrow> t2 |
    6.67    (_, Leaf) \<Rightarrow> t1 |
    6.68 -  (Node l1 a1 n1 r1, Node l2 a2 n2 r2) \<Rightarrow>
    6.69 +  (Node l1 (a1, n1) r1, Node l2 (a2, n2) r2) \<Rightarrow>
    6.70      if a1 \<le> a2 then node l1 a1 (merge r1 t2) else node l2 a2 (merge t1 r2))"
    6.71  by(induction t1 t2 rule: merge.induct) (simp_all split: tree.split)
    6.72  
    6.73  hide_const (open) insert
    6.74  
    6.75  definition insert :: "'a::ord \<Rightarrow> 'a lheap \<Rightarrow> 'a lheap" where
    6.76 -"insert x t = merge (Node Leaf x 1 Leaf) t"
    6.77 +"insert x t = merge (Node Leaf (x,1) Leaf) t"
    6.78  
    6.79  fun del_min :: "'a::ord lheap \<Rightarrow> 'a lheap" where
    6.80  "del_min Leaf = Leaf" |
    6.81 -"del_min (Node l x n r) = merge l r"
    6.82 +"del_min (Node l _ r) = merge l r"
    6.83  
    6.84  
    6.85  subsection "Lemmas"
    6.86 @@ -177,17 +177,17 @@
    6.87  subsection "Complexity"
    6.88  
    6.89  lemma pow2_rank_size1: "ltree t \<Longrightarrow> 2 ^ rank t \<le> size1 t"
    6.90 -proof(induction t)
    6.91 +proof(induction t rule: tree2_induct)
    6.92    case Leaf show ?case by simp
    6.93  next
    6.94    case (Node l a n r)
    6.95    hence "rank r \<le> rank l" by simp
    6.96    hence *: "(2::nat) ^ rank r \<le> 2 ^ rank l" by simp
    6.97 -  have "(2::nat) ^ rank \<langle>l, a, n, r\<rangle> = 2 ^ rank r + 2 ^ rank r"
    6.98 +  have "(2::nat) ^ rank \<langle>l, (a, n), r\<rangle> = 2 ^ rank r + 2 ^ rank r"
    6.99      by(simp add: mult_2)
   6.100    also have "\<dots> \<le> size1 l + size1 r"
   6.101      using Node * by (simp del: power_increasing_iff)
   6.102 -  also have "\<dots> = size1 \<langle>l, a, n, r\<rangle>" by simp
   6.103 +  also have "\<dots> = size1 \<langle>l, (a, n), r\<rangle>" by simp
   6.104    finally show ?case .
   6.105  qed
   6.106  
   6.107 @@ -196,16 +196,16 @@
   6.108  fun t_merge :: "'a::ord lheap \<Rightarrow> 'a lheap \<Rightarrow> nat" where
   6.109  "t_merge Leaf t = 1" |
   6.110  "t_merge t Leaf = 1" |
   6.111 -"t_merge (Node l1 a1 n1 r1 =: t1) (Node l2 a2 n2 r2 =: t2) =
   6.112 +"t_merge (Node l1 (a1, n1) r1 =: t1) (Node l2 (a2, n2) r2 =: t2) =
   6.113    (if a1 \<le> a2 then 1 + t_merge r1 t2
   6.114     else 1 + t_merge t1 r2)"
   6.115  
   6.116  definition t_insert :: "'a::ord \<Rightarrow> 'a lheap \<Rightarrow> nat" where
   6.117 -"t_insert x t = t_merge (Node Leaf x 1 Leaf) t"
   6.118 +"t_insert x t = t_merge (Node Leaf (x, 1) Leaf) t"
   6.119  
   6.120  fun t_del_min :: "'a::ord lheap \<Rightarrow> nat" where
   6.121  "t_del_min Leaf = 1" |
   6.122 -"t_del_min (Node l a n r) = t_merge l r"
   6.123 +"t_del_min (Node l _ r) = t_merge l r"
   6.124  
   6.125  lemma t_merge_rank: "t_merge l r \<le> rank l + rank r + 1"
   6.126  proof(induction l r rule: merge.induct)
   6.127 @@ -219,7 +219,7 @@
   6.128  by linarith
   6.129  
   6.130  corollary t_insert_log: "ltree t \<Longrightarrow> t_insert x t \<le> log 2 (size1 t) + 2"
   6.131 -using t_merge_log[of "Node Leaf x 1 Leaf" t]
   6.132 +using t_merge_log[of "Node Leaf (x, 1) Leaf" t]
   6.133  by(simp add: t_insert_def split: tree.split)
   6.134  
   6.135  (* FIXME mv ? *)
   6.136 @@ -237,7 +237,7 @@
   6.137  
   6.138  corollary t_del_min_log: assumes "ltree t"
   6.139    shows "t_del_min t \<le> 2 * log 2 (size1 t) + 1"
   6.140 -proof(cases t)
   6.141 +proof(cases t rule: tree2_cases)
   6.142    case Leaf thus ?thesis using assms by simp
   6.143  next
   6.144    case [simp]: (Node t1 _ _ t2)
     7.1 --- a/src/HOL/Data_Structures/Lookup2.thy	Tue Sep 24 17:36:14 2019 +0200
     7.2 +++ b/src/HOL/Data_Structures/Lookup2.thy	Wed Sep 25 17:22:57 2019 +0200
     7.3 @@ -9,13 +9,13 @@
     7.4    Map_Specs
     7.5  begin
     7.6  
     7.7 -fun lookup :: "('a::linorder * 'b, 'c) tree \<Rightarrow> 'a \<Rightarrow> 'b option" where
     7.8 +fun lookup :: "(('a::linorder * 'b) * 'c) tree \<Rightarrow> 'a \<Rightarrow> 'b option" where
     7.9  "lookup Leaf x = None" |
    7.10 -"lookup (Node l (a,b) _ r) x =
    7.11 +"lookup (Node l ((a,b), _) r) x =
    7.12    (case cmp x a of LT \<Rightarrow> lookup l x | GT \<Rightarrow> lookup r x | EQ \<Rightarrow> Some b)"
    7.13  
    7.14  lemma lookup_map_of:
    7.15    "sorted1(inorder t) \<Longrightarrow> lookup t x = map_of (inorder t) x"
    7.16 -by(induction t) (auto simp: map_of_simps split: option.split)
    7.17 +by(induction t rule: tree2_induct) (auto simp: map_of_simps split: option.split)
    7.18  
    7.19  end
     8.1 --- a/src/HOL/Data_Structures/RBT.thy	Tue Sep 24 17:36:14 2019 +0200
     8.2 +++ b/src/HOL/Data_Structures/RBT.thy	Wed Sep 25 17:22:57 2019 +0200
     8.3 @@ -8,10 +8,10 @@
     8.4  
     8.5  datatype color = Red | Black
     8.6  
     8.7 -type_synonym 'a rbt = "('a,color)tree"
     8.8 +type_synonym 'a rbt = "('a*color)tree"
     8.9  
    8.10 -abbreviation R where "R l a r \<equiv> Node l a Red r"
    8.11 -abbreviation B where "B l a r \<equiv> Node l a Black r"
    8.12 +abbreviation R where "R l a r \<equiv> Node l (a, Red) r"
    8.13 +abbreviation B where "B l a r \<equiv> Node l (a, Black) r"
    8.14  
    8.15  fun baliL :: "'a rbt \<Rightarrow> 'a \<Rightarrow> 'a rbt \<Rightarrow> 'a rbt" where
    8.16  "baliL (R (R t1 a t2) b t3) c t4 = R (B t1 a t2) b (B t3 c t4)" |
    8.17 @@ -25,7 +25,7 @@
    8.18  
    8.19  fun paint :: "color \<Rightarrow> 'a rbt \<Rightarrow> 'a rbt" where
    8.20  "paint c Leaf = Leaf" |
    8.21 -"paint c (Node l a _ r) = Node l a c r"
    8.22 +"paint c (Node l (a,_) r) = Node l (a,c) r"
    8.23  
    8.24  fun baldL :: "'a rbt \<Rightarrow> 'a \<Rightarrow> 'a rbt \<Rightarrow> 'a rbt" where
    8.25  "baldL (R t1 a t2) b t3 = R (B t1 a t2) b t3" |
     9.1 --- a/src/HOL/Data_Structures/RBT_Map.thy	Tue Sep 24 17:36:14 2019 +0200
     9.2 +++ b/src/HOL/Data_Structures/RBT_Map.thy	Wed Sep 25 17:22:57 2019 +0200
     9.3 @@ -24,7 +24,7 @@
     9.4  
     9.5  fun del :: "'a::linorder \<Rightarrow> ('a*'b)rbt \<Rightarrow> ('a*'b)rbt" where
     9.6  "del x Leaf = Leaf" |
     9.7 -"del x (Node l (a,b) c r) = (case cmp x a of
     9.8 +"del x (Node l ((a,b), c) r) = (case cmp x a of
     9.9       LT \<Rightarrow> if l \<noteq> Leaf \<and> color l = Black
    9.10             then baldL (del x l) (a,b) r else R (del x l) (a,b) r |
    9.11       GT \<Rightarrow> if r \<noteq> Leaf\<and> color r = Black
    10.1 --- a/src/HOL/Data_Structures/RBT_Set.thy	Tue Sep 24 17:36:14 2019 +0200
    10.2 +++ b/src/HOL/Data_Structures/RBT_Set.thy	Wed Sep 25 17:22:57 2019 +0200
    10.3 @@ -31,11 +31,11 @@
    10.4  
    10.5  fun color :: "'a rbt \<Rightarrow> color" where
    10.6  "color Leaf = Black" |
    10.7 -"color (Node _ _ c _) = c"
    10.8 +"color (Node _ (_, c) _) = c"
    10.9  
   10.10  fun del :: "'a::linorder \<Rightarrow> 'a rbt \<Rightarrow> 'a rbt" where
   10.11  "del x Leaf = Leaf" |
   10.12 -"del x (Node l a _ r) =
   10.13 +"del x (Node l (a, _) r) =
   10.14    (case cmp x a of
   10.15       LT \<Rightarrow> if l \<noteq> Leaf \<and> color l = Black
   10.16             then baldL (del x l) a r else R (del x l) a r |
   10.17 @@ -100,11 +100,11 @@
   10.18  
   10.19  fun bheight :: "'a rbt \<Rightarrow> nat" where
   10.20  "bheight Leaf = 0" |
   10.21 -"bheight (Node l x c r) = (if c = Black then bheight l + 1 else bheight l)"
   10.22 +"bheight (Node l (x, c) r) = (if c = Black then bheight l + 1 else bheight l)"
   10.23  
   10.24  fun invc :: "'a rbt \<Rightarrow> bool" where
   10.25  "invc Leaf = True" |
   10.26 -"invc (Node l a c r) =
   10.27 +"invc (Node l (a,c) r) =
   10.28    (invc l \<and> invc r \<and> (c = Red \<longrightarrow> color l = Black \<and> color r = Black))"
   10.29  
   10.30  text \<open>Weaker version:\<close>
   10.31 @@ -113,10 +113,10 @@
   10.32  
   10.33  fun invh :: "'a rbt \<Rightarrow> bool" where
   10.34  "invh Leaf = True" |
   10.35 -"invh (Node l x c r) = (invh l \<and> invh r \<and> bheight l = bheight r)"
   10.36 +"invh (Node l (x, c) r) = (invh l \<and> invh r \<and> bheight l = bheight r)"
   10.37  
   10.38  lemma invc2I: "invc t \<Longrightarrow> invc2 t"
   10.39 -by (cases t) simp+
   10.40 +by (cases t rule: tree2_cases) simp+
   10.41  
   10.42  definition rbt :: "'a rbt \<Rightarrow> bool" where
   10.43  "rbt t = (invc t \<and> invh t \<and> color t = Black)"
   10.44 @@ -234,8 +234,8 @@
   10.45  by (induct l r rule: combine.induct)
   10.46     (auto simp: invc_baldL invc2I split: tree.splits color.splits)
   10.47  
   10.48 -lemma neq_LeafD: "t \<noteq> Leaf \<Longrightarrow> \<exists>c l x r. t = Node c l x r"
   10.49 -by(cases t) auto
   10.50 +lemma neq_LeafD: "t \<noteq> Leaf \<Longrightarrow> \<exists>l x c r. t = Node l (x,c) r"
   10.51 +by(cases t rule: tree2_cases) auto
   10.52  
   10.53  lemma del_invc_invh: "invh t \<Longrightarrow> invc t \<Longrightarrow> invh (del x t) \<and>
   10.54     (color t = Red \<and> bheight (del x t) = bheight t \<and> invc (del x t) \<or>
    11.1 --- a/src/HOL/Data_Structures/Set2_Join.thy	Tue Sep 24 17:36:14 2019 +0200
    11.2 +++ b/src/HOL/Data_Structures/Set2_Join.thy	Wed Sep 25 17:22:57 2019 +0200
    11.3 @@ -20,26 +20,26 @@
    11.4  and recursion operators on it.\<close>
    11.5  
    11.6  locale Set2_Join =
    11.7 -fixes join :: "('a::linorder,'b) tree \<Rightarrow> 'a \<Rightarrow> ('a,'b) tree \<Rightarrow> ('a,'b) tree"
    11.8 -fixes inv :: "('a,'b) tree \<Rightarrow> bool"
    11.9 +fixes join :: "('a::linorder*'b) tree \<Rightarrow> 'a \<Rightarrow> ('a*'b) tree \<Rightarrow> ('a*'b) tree"
   11.10 +fixes inv :: "('a*'b) tree \<Rightarrow> bool"
   11.11  assumes set_join: "set_tree (join l a r) = set_tree l \<union> {a} \<union> set_tree r"
   11.12 -assumes bst_join: "bst (Node l a b r) \<Longrightarrow> bst (join l a r)"
   11.13 +assumes bst_join: "bst (Node l (a, b) r) \<Longrightarrow> bst (join l a r)"
   11.14  assumes inv_Leaf: "inv \<langle>\<rangle>"
   11.15  assumes inv_join: "\<lbrakk> inv l; inv r \<rbrakk> \<Longrightarrow> inv (join l a r)"
   11.16 -assumes inv_Node: "\<lbrakk> inv (Node l a b r) \<rbrakk> \<Longrightarrow> inv l \<and> inv r"
   11.17 +assumes inv_Node: "\<lbrakk> inv (Node l (a,b) r) \<rbrakk> \<Longrightarrow> inv l \<and> inv r"
   11.18  begin
   11.19  
   11.20  declare set_join [simp]
   11.21  
   11.22  subsection "\<open>split_min\<close>"
   11.23  
   11.24 -fun split_min :: "('a,'b) tree \<Rightarrow> 'a \<times> ('a,'b) tree" where
   11.25 -"split_min (Node l a _ r) =
   11.26 +fun split_min :: "('a*'b) tree \<Rightarrow> 'a \<times> ('a*'b) tree" where
   11.27 +"split_min (Node l (a, _) r) =
   11.28    (if l = Leaf then (a,r) else let (m,l') = split_min l in (m, join l' a r))"
   11.29  
   11.30  lemma split_min_set:
   11.31    "\<lbrakk> split_min t = (m,t');  t \<noteq> Leaf \<rbrakk> \<Longrightarrow> m \<in> set_tree t \<and> set_tree t = {m} \<union> set_tree t'"
   11.32 -proof(induction t arbitrary: t')
   11.33 +proof(induction t arbitrary: t' rule: tree2_induct)
   11.34    case Node thus ?case by(auto split: prod.splits if_splits dest: inv_Node)
   11.35  next
   11.36    case Leaf thus ?case by simp
   11.37 @@ -47,7 +47,7 @@
   11.38  
   11.39  lemma split_min_bst:
   11.40    "\<lbrakk> split_min t = (m,t');  bst t;  t \<noteq> Leaf \<rbrakk> \<Longrightarrow>  bst t' \<and> (\<forall>x \<in> set_tree t'. m < x)"
   11.41 -proof(induction t arbitrary: t')
   11.42 +proof(induction t arbitrary: t' rule: tree2_induct)
   11.43    case Node thus ?case by(fastforce simp: split_min_set bst_join split: prod.splits if_splits)
   11.44  next
   11.45    case Leaf thus ?case by simp
   11.46 @@ -55,7 +55,7 @@
   11.47  
   11.48  lemma split_min_inv:
   11.49    "\<lbrakk> split_min t = (m,t');  inv t;  t \<noteq> Leaf \<rbrakk> \<Longrightarrow>  inv t'"
   11.50 -proof(induction t arbitrary: t')
   11.51 +proof(induction t arbitrary: t' rule: tree2_induct)
   11.52    case Node thus ?case by(auto simp: inv_join split: prod.splits if_splits dest: inv_Node)
   11.53  next
   11.54    case Leaf thus ?case by simp
   11.55 @@ -64,7 +64,7 @@
   11.56  
   11.57  subsection "\<open>join2\<close>"
   11.58  
   11.59 -definition join2 :: "('a,'b) tree \<Rightarrow> ('a,'b) tree \<Rightarrow> ('a,'b) tree" where
   11.60 +definition join2 :: "('a*'b) tree \<Rightarrow> ('a*'b) tree \<Rightarrow> ('a*'b) tree" where
   11.61  "join2 l r = (if r = Leaf then l else let (m,r') = split_min r in join l m r')"
   11.62  
   11.63  lemma set_join2[simp]: "set_tree (join2 l r) = set_tree l \<union> set_tree r"
   11.64 @@ -80,9 +80,9 @@
   11.65  
   11.66  subsection "\<open>split\<close>"
   11.67  
   11.68 -fun split :: "('a,'b)tree \<Rightarrow> 'a \<Rightarrow> ('a,'b)tree \<times> bool \<times> ('a,'b)tree" where
   11.69 +fun split :: "('a*'b)tree \<Rightarrow> 'a \<Rightarrow> ('a*'b)tree \<times> bool \<times> ('a*'b)tree" where
   11.70  "split Leaf k = (Leaf, False, Leaf)" |
   11.71 -"split (Node l a _ r) x =
   11.72 +"split (Node l (a, _) r) x =
   11.73    (case cmp x a of
   11.74       LT \<Rightarrow> let (l1,b,l2) = split l x in (l1, b, join l2 a r) |
   11.75       GT \<Rightarrow> let (r1,b,r2) = split r x in (join l a r1, b, r2) |
   11.76 @@ -91,14 +91,14 @@
   11.77  lemma split: "split t x = (l,xin,r) \<Longrightarrow> bst t \<Longrightarrow>
   11.78    set_tree l = {a \<in> set_tree t. a < x} \<and> set_tree r = {a \<in> set_tree t. x < a}
   11.79    \<and> (xin = (x \<in> set_tree t)) \<and> bst l \<and> bst r"
   11.80 -proof(induction t arbitrary: l xin r)
   11.81 +proof(induction t arbitrary: l xin r rule: tree2_induct)
   11.82    case Leaf thus ?case by simp
   11.83  next
   11.84    case Node thus ?case by(force split!: prod.splits if_splits intro!: bst_join)
   11.85  qed
   11.86  
   11.87  lemma split_inv: "split t x = (l,xin,r) \<Longrightarrow> inv t \<Longrightarrow> inv l \<and> inv r"
   11.88 -proof(induction t arbitrary: l xin r)
   11.89 +proof(induction t arbitrary: l xin r rule: tree2_induct)
   11.90    case Leaf thus ?case by simp
   11.91  next
   11.92    case Node
   11.93 @@ -110,7 +110,7 @@
   11.94  
   11.95  subsection "\<open>insert\<close>"
   11.96  
   11.97 -definition insert :: "'a \<Rightarrow> ('a,'b) tree \<Rightarrow> ('a,'b) tree" where
   11.98 +definition insert :: "'a \<Rightarrow> ('a*'b) tree \<Rightarrow> ('a*'b) tree" where
   11.99  "insert x t = (let (l,_,r) = split t x in join l x r)"
  11.100  
  11.101  lemma set_tree_insert: "bst t \<Longrightarrow> set_tree (insert x t) = {x} \<union> set_tree t"
  11.102 @@ -125,7 +125,7 @@
  11.103  
  11.104  subsection "\<open>delete\<close>"
  11.105  
  11.106 -definition delete :: "'a \<Rightarrow> ('a,'b) tree \<Rightarrow> ('a,'b) tree" where
  11.107 +definition delete :: "'a \<Rightarrow> ('a*'b) tree \<Rightarrow> ('a*'b) tree" where
  11.108  "delete x t = (let (l,_,r) = split t x in join2 l r)"
  11.109  
  11.110  lemma set_tree_delete: "bst t \<Longrightarrow> set_tree (delete x t) = set_tree t - {x}"
  11.111 @@ -140,11 +140,11 @@
  11.112  
  11.113  subsection "\<open>union\<close>"
  11.114  
  11.115 -fun union :: "('a,'b)tree \<Rightarrow> ('a,'b)tree \<Rightarrow> ('a,'b)tree" where
  11.116 +fun union :: "('a*'b)tree \<Rightarrow> ('a*'b)tree \<Rightarrow> ('a*'b)tree" where
  11.117  "union t1 t2 =
  11.118    (if t1 = Leaf then t2 else
  11.119     if t2 = Leaf then t1 else
  11.120 -   case t1 of Node l1 a _ r1 \<Rightarrow>
  11.121 +   case t1 of Node l1 (a, _) r1 \<Rightarrow>
  11.122     let (l2,_ ,r2) = split t2 a;
  11.123         l' = union l1 l2; r' = union r1 r2
  11.124     in join l' a r')"
  11.125 @@ -176,11 +176,11 @@
  11.126  
  11.127  subsection "\<open>inter\<close>"
  11.128  
  11.129 -fun inter :: "('a,'b)tree \<Rightarrow> ('a,'b)tree \<Rightarrow> ('a,'b)tree" where
  11.130 +fun inter :: "('a*'b)tree \<Rightarrow> ('a*'b)tree \<Rightarrow> ('a*'b)tree" where
  11.131  "inter t1 t2 =
  11.132    (if t1 = Leaf then Leaf else
  11.133     if t2 = Leaf then Leaf else
  11.134 -   case t1 of Node l1 a _ r1 \<Rightarrow>
  11.135 +   case t1 of Node l1 (a, _) r1 \<Rightarrow>
  11.136     let (l2,ain,r2) = split t2 a;
  11.137         l' = inter l1 l2; r' = inter r1 r2
  11.138     in if ain then join l' a r' else join2 l' r')"
  11.139 @@ -192,7 +192,7 @@
  11.140  proof(induction t1 t2 rule: inter.induct)
  11.141    case (1 t1 t2)
  11.142    show ?case
  11.143 -  proof (cases t1)
  11.144 +  proof (cases t1 rule: tree2_cases)
  11.145      case Leaf thus ?thesis by (simp add: inter.simps)
  11.146    next
  11.147      case [simp]: (Node l1 a _ r1)
  11.148 @@ -209,9 +209,9 @@
  11.149             **: "?L2 \<inter> ?R2 = {}" "a \<notin> ?L2 \<union> ?R2" "?L1 \<inter> ?R2 = {}" "?L2 \<inter> ?R1 = {}"
  11.150          using split[OF sp] \<open>bst t1\<close> \<open>bst t2\<close> by (force, force, force, force, force)
  11.151        have IHl: "set_tree (inter l1 l2) = set_tree l1 \<inter> set_tree l2"
  11.152 -        using "1.IH"(1)[OF _ False _ sp[symmetric]] "1.prems"(1,2) split[OF sp] by simp
  11.153 +        using "1.IH"(1)[OF _ False _ _ sp[symmetric]] "1.prems"(1,2) split[OF sp] by simp
  11.154        have IHr: "set_tree (inter r1 r2) = set_tree r1 \<inter> set_tree r2"
  11.155 -        using "1.IH"(2)[OF _ False _ sp[symmetric]] "1.prems"(1,2) split[OF sp] by simp
  11.156 +        using "1.IH"(2)[OF _ False _ _ sp[symmetric]] "1.prems"(1,2) split[OF sp] by simp
  11.157        have "set_tree t1 \<inter> set_tree t2 = (?L1 \<union> ?R1 \<union> {a}) \<inter> (?L2 \<union> ?R2 \<union> ?K)"
  11.158          by(simp add: t2)
  11.159        also have "\<dots> = (?L1 \<inter> ?L2) \<union> (?R1 \<inter> ?R2) \<union> ?K"
  11.160 @@ -241,11 +241,11 @@
  11.161  
  11.162  subsection "\<open>diff\<close>"
  11.163  
  11.164 -fun diff :: "('a,'b)tree \<Rightarrow> ('a,'b)tree \<Rightarrow> ('a,'b)tree" where
  11.165 +fun diff :: "('a*'b)tree \<Rightarrow> ('a*'b)tree \<Rightarrow> ('a*'b)tree" where
  11.166  "diff t1 t2 =
  11.167    (if t1 = Leaf then Leaf else
  11.168     if t2 = Leaf then t1 else
  11.169 -   case t2 of Node l2 a _ r2 \<Rightarrow>
  11.170 +   case t2 of Node l2 (a, _) r2 \<Rightarrow>
  11.171     let (l1,_,r1) = split t1 a;
  11.172         l' = diff l1 l2; r' = diff r1 r2
  11.173     in join2 l' r')"
  11.174 @@ -257,7 +257,7 @@
  11.175  proof(induction t1 t2 rule: diff.induct)
  11.176    case (1 t1 t2)
  11.177    show ?case
  11.178 -  proof (cases t2)
  11.179 +  proof (cases t2 rule: tree2_cases)
  11.180      case Leaf thus ?thesis by (simp add: diff.simps)
  11.181    next
  11.182      case [simp]: (Node l2 a _ r2)
  11.183 @@ -273,9 +273,9 @@
  11.184             **: "a \<notin> ?L1 \<union> ?R1" "?L1 \<inter> ?R2 = {}" "?L2 \<inter> ?R1 = {}"
  11.185          using split[OF sp] \<open>bst t1\<close> \<open>bst t2\<close> by (force, force, force, force)
  11.186        have IHl: "set_tree (diff l1 l2) = set_tree l1 - set_tree l2"
  11.187 -        using "1.IH"(1)[OF False _ _ sp[symmetric]] "1.prems"(1,2) split[OF sp] by simp
  11.188 +        using "1.IH"(1)[OF False _ _ _ sp[symmetric]] "1.prems"(1,2) split[OF sp] by simp
  11.189        have IHr: "set_tree (diff r1 r2) = set_tree r1 - set_tree r2"
  11.190 -        using "1.IH"(2)[OF False _ _ sp[symmetric]] "1.prems"(1,2) split[OF sp] by simp
  11.191 +        using "1.IH"(2)[OF False _ _ _ sp[symmetric]] "1.prems"(1,2) split[OF sp] by simp
  11.192        have "set_tree t1 - set_tree t2 = (?L1 \<union> ?R1) - (?L2 \<union> ?R2  \<union> {a})"
  11.193          by(simp add: t1)
  11.194        also have "\<dots> = (?L1 - ?L2) \<union> (?R1 - ?R2)"
  11.195 @@ -340,7 +340,7 @@
  11.196  end
  11.197  
  11.198  interpretation unbal: Set2_Join
  11.199 -where join = "\<lambda>l x r. Node l x () r" and inv = "\<lambda>t. True"
  11.200 +where join = "\<lambda>l x r. Node l (x, ()) r" and inv = "\<lambda>t. True"
  11.201  proof (standard, goal_cases)
  11.202    case 1 show ?case by simp
  11.203  next
    12.1 --- a/src/HOL/Data_Structures/Set2_Join_RBT.thy	Tue Sep 24 17:36:14 2019 +0200
    12.2 +++ b/src/HOL/Data_Structures/Set2_Join_RBT.thy	Wed Sep 25 17:22:57 2019 +0200
    12.3 @@ -179,7 +179,7 @@
    12.4  by(cases "(l,a,r)" rule: baliR.cases) (auto simp: ball_Un)
    12.5  
    12.6  lemma bst_joinL:
    12.7 -  "\<lbrakk>bst (Node l a n r); bheight l \<le> bheight r\<rbrakk>
    12.8 +  "\<lbrakk>bst (Node l (a, n) r); bheight l \<le> bheight r\<rbrakk>
    12.9    \<Longrightarrow> bst (joinL l a r)"
   12.10  proof(induction l a r rule: joinL.induct)
   12.11    case (1 l a r)
   12.12 @@ -202,7 +202,7 @@
   12.13  by(cases t) auto
   12.14  
   12.15  lemma bst_join:
   12.16 -  "bst (Node l a n r) \<Longrightarrow> bst (join l a r)"
   12.17 +  "bst (Node l (a, n) r) \<Longrightarrow> bst (join l a r)"
   12.18  by(auto simp: bst_paint bst_joinL bst_joinR join_def)
   12.19  
   12.20  lemma inv_join: "\<lbrakk> invc l; invh l; invc r; invh r \<rbrakk> \<Longrightarrow> invc(join l x r) \<and> invh(join l x r)"
    13.1 --- a/src/HOL/Data_Structures/Tree2.thy	Tue Sep 24 17:36:14 2019 +0200
    13.2 +++ b/src/HOL/Data_Structures/Tree2.thy	Wed Sep 25 17:22:57 2019 +0200
    13.3 @@ -1,40 +1,29 @@
    13.4  theory Tree2
    13.5 -imports Main
    13.6 +imports "HOL-Library.Tree"
    13.7  begin
    13.8  
    13.9 -datatype ('a,'b) tree =
   13.10 -  Leaf ("\<langle>\<rangle>") |
   13.11 -  Node "('a,'b)tree" 'a 'b "('a,'b) tree" ("(1\<langle>_,/ _,/ _,/ _\<rangle>)")
   13.12 -
   13.13 -fun inorder :: "('a,'b)tree \<Rightarrow> 'a list" where
   13.14 -"inorder Leaf = []" |
   13.15 -"inorder (Node l a _ r) = inorder l @ a # inorder r"
   13.16 +text \<open>This theory provides the basic infrastructure for the type @{typ \<open>('a * 'b) tree\<close>}
   13.17 +of augmented trees where @{typ 'a} is the key and @{typ 'b} some additional information.\<close>
   13.18  
   13.19 -fun height :: "('a,'b) tree \<Rightarrow> nat" where
   13.20 -"height Leaf = 0" |
   13.21 -"height (Node l a _ r) = max (height l) (height r) + 1"
   13.22 +text \<open>IMPORTANT: Inductions and cases analyses on augmented trees need to use the following
   13.23 +two rules explicitly. They generate nodes of the form @{term "Node l (a,b) r"}
   13.24 +rather than @{term "Node l a r"} for trees of type @{typ "'a tree"}.\<close>
   13.25  
   13.26 -fun set_tree :: "('a,'b) tree \<Rightarrow> 'a set" where
   13.27 -"set_tree Leaf = {}" |
   13.28 -"set_tree (Node l a _ r) = Set.insert a (set_tree l \<union> set_tree r)"
   13.29 +lemmas tree2_induct = tree.induct[where 'a = "'a * 'b", split_format(complete)]
   13.30 +
   13.31 +lemmas tree2_cases = tree.exhaust[where 'a = "'a * 'b", split_format(complete)]
   13.32  
   13.33 -fun bst :: "('a::linorder,'b) tree \<Rightarrow> bool" where
   13.34 -"bst Leaf = True" |
   13.35 -"bst (Node l a _ r) = (bst l \<and> bst r \<and> (\<forall>x \<in> set_tree l. x < a) \<and> (\<forall>x \<in> set_tree r. a < x))"
   13.36 -
   13.37 -fun size1 :: "('a,'b) tree \<Rightarrow> nat" where
   13.38 -"size1 \<langle>\<rangle> = 1" |
   13.39 -"size1 \<langle>l, _, _, r\<rangle> = size1 l + size1 r"
   13.40 +fun inorder :: "('a*'b)tree \<Rightarrow> 'a list" where
   13.41 +"inorder Leaf = []" |
   13.42 +"inorder (Node l (a,_) r) = inorder l @ a # inorder r"
   13.43  
   13.44 -fun complete :: "('a,'b) tree \<Rightarrow> bool" where
   13.45 -"complete Leaf = True" |
   13.46 -"complete (Node l _ _ r) = (complete l \<and> complete r \<and> height l = height r)"
   13.47 +fun set_tree :: "('a*'b) tree \<Rightarrow> 'a set" where
   13.48 +"set_tree Leaf = {}" |
   13.49 +"set_tree (Node l (a,_) r) = Set.insert a (set_tree l \<union> set_tree r)"
   13.50  
   13.51 -lemma size1_size: "size1 t = size t + 1"
   13.52 -by (induction t) simp_all
   13.53 -
   13.54 -lemma size1_ge0[simp]: "0 < size1 t"
   13.55 -by (simp add: size1_size)
   13.56 +fun bst :: "('a::linorder*'b) tree \<Rightarrow> bool" where
   13.57 +"bst Leaf = True" |
   13.58 +"bst (Node l (a, _) r) = (bst l \<and> bst r \<and> (\<forall>x \<in> set_tree l. x < a) \<and> (\<forall>x \<in> set_tree r. a < x))"
   13.59  
   13.60  lemma finite_set_tree[simp]: "finite(set_tree t)"
   13.61  by(induction t) auto
    14.1 --- a/src/HOL/Data_Structures/Trie_Map.thy	Tue Sep 24 17:36:14 2019 +0200
    14.2 +++ b/src/HOL/Data_Structures/Trie_Map.thy	Wed Sep 25 17:22:57 2019 +0200
    14.3 @@ -21,10 +21,10 @@
    14.4  
    14.5  However, the development below works verbatim for any map implementation, eg \<open>Tree_Map\<close>,
    14.6  and not just \<open>RBT_Map\<close>, except for the termination lemma \<open>lookup_size\<close>.\<close>
    14.7 -
    14.8 +term size_tree
    14.9  lemma lookup_size[termination_simp]:
   14.10    fixes t :: "('a::linorder * 'a trie_map) rbt"
   14.11 -  shows "lookup t a = Some b \<Longrightarrow> size b < Suc (size_tree (\<lambda>ab. Suc (size (snd ab))) (\<lambda>x. 0) t)"
   14.12 +  shows "lookup t a = Some b \<Longrightarrow> size b < Suc (size_tree (\<lambda>ab. Suc(Suc (size (snd(fst ab))))) t)"
   14.13  apply(induction t a rule: lookup.induct)
   14.14  apply(auto split: if_splits)
   14.15  done