src/HOL/Data_Structures/AVL_Set.thy
author nipkow
Wed Jun 13 15:24:20 2018 +0200 (10 months ago)
changeset 68440 6826718f732d
parent 68431 b294e095f64c
child 69597 ff784d5a5bfb
permissions -rw-r--r--
qualify interpretations to avoid clashes
nipkow@61232
     1
(*
nipkow@63411
     2
Author:     Tobias Nipkow, Daniel Stüwe
nipkow@63411
     3
Largely derived from AFP entry AVL.
nipkow@61232
     4
*)
nipkow@61232
     5
nipkow@61232
     6
section "AVL Tree Implementation of Sets"
nipkow@61232
     7
nipkow@61232
     8
theory AVL_Set
nipkow@63411
     9
imports
nipkow@67964
    10
  Cmp
nipkow@67964
    11
  Isin2
wenzelm@66453
    12
  "HOL-Number_Theory.Fib"
nipkow@61232
    13
begin
nipkow@61232
    14
nipkow@61232
    15
type_synonym 'a avl_tree = "('a,nat) tree"
nipkow@61232
    16
nipkow@68431
    17
definition empty :: "'a avl_tree" where
nipkow@68431
    18
"empty = Leaf"
nipkow@68431
    19
wenzelm@67406
    20
text \<open>Invariant:\<close>
nipkow@61232
    21
nipkow@61232
    22
fun avl :: "'a avl_tree \<Rightarrow> bool" where
nipkow@61232
    23
"avl Leaf = True" |
nipkow@68413
    24
"avl (Node l a h r) =
nipkow@61232
    25
 ((height l = height r \<or> height l = height r + 1 \<or> height r = height l + 1) \<and> 
nipkow@61232
    26
  h = max (height l) (height r) + 1 \<and> avl l \<and> avl r)"
nipkow@61232
    27
nipkow@61232
    28
fun ht :: "'a avl_tree \<Rightarrow> nat" where
nipkow@61232
    29
"ht Leaf = 0" |
nipkow@68413
    30
"ht (Node l a h r) = h"
nipkow@61232
    31
nipkow@61232
    32
definition node :: "'a avl_tree \<Rightarrow> 'a \<Rightarrow> 'a avl_tree \<Rightarrow> 'a avl_tree" where
nipkow@68413
    33
"node l a r = Node l a (max (ht l) (ht r) + 1) r"
nipkow@61232
    34
nipkow@61581
    35
definition balL :: "'a avl_tree \<Rightarrow> 'a \<Rightarrow> 'a avl_tree \<Rightarrow> 'a avl_tree" where
nipkow@61678
    36
"balL l a r =
nipkow@61678
    37
  (if ht l = ht r + 2 then
nipkow@61678
    38
     case l of 
nipkow@68413
    39
       Node bl b _ br \<Rightarrow>
nipkow@61678
    40
         if ht bl < ht br then
nipkow@61678
    41
           case br of
nipkow@68413
    42
             Node cl c _ cr \<Rightarrow> node (node bl b cl) c (node cr a r)
nipkow@61678
    43
         else node bl b (node br a r)
nipkow@61678
    44
   else node l a r)"
nipkow@61232
    45
nipkow@61581
    46
definition balR :: "'a avl_tree \<Rightarrow> 'a \<Rightarrow> 'a avl_tree \<Rightarrow> 'a avl_tree" where
nipkow@61678
    47
"balR l a r =
nipkow@61678
    48
   (if ht r = ht l + 2 then
nipkow@61678
    49
      case r of
nipkow@68413
    50
        Node bl b _ br \<Rightarrow>
nipkow@61678
    51
          if ht bl > ht br then
nipkow@61678
    52
            case bl of
nipkow@68413
    53
              Node cl c _ cr \<Rightarrow> node (node l a cl) c (node cr b br)
nipkow@61678
    54
          else node (node l a bl) b br
nipkow@61232
    55
  else node l a r)"
nipkow@61232
    56
nipkow@63411
    57
fun insert :: "'a::linorder \<Rightarrow> 'a avl_tree \<Rightarrow> 'a avl_tree" where
nipkow@68413
    58
"insert x Leaf = Node Leaf x 1 Leaf" |
nipkow@68413
    59
"insert x (Node l a h r) = (case cmp x a of
nipkow@68413
    60
   EQ \<Rightarrow> Node l a h r |
nipkow@61581
    61
   LT \<Rightarrow> balL (insert x l) a r |
nipkow@61581
    62
   GT \<Rightarrow> balR l a (insert x r))"
nipkow@61232
    63
nipkow@68023
    64
fun split_max :: "'a avl_tree \<Rightarrow> 'a avl_tree * 'a" where
nipkow@68413
    65
"split_max (Node l a _ r) =
nipkow@68023
    66
  (if r = Leaf then (l,a) else let (r',a') = split_max r in (balL l a r', a'))"
nipkow@61232
    67
nipkow@68023
    68
lemmas split_max_induct = split_max.induct[case_names Node Leaf]
nipkow@61232
    69
nipkow@61647
    70
fun del_root :: "'a avl_tree \<Rightarrow> 'a avl_tree" where
nipkow@68413
    71
"del_root (Node Leaf a h r) = r" |
nipkow@68413
    72
"del_root (Node l a h Leaf) = l" |
nipkow@68413
    73
"del_root (Node l a h r) = (let (l', a') = split_max l in balR l' a' r)"
nipkow@61232
    74
nipkow@61647
    75
lemmas del_root_cases = del_root.cases[case_names Leaf_t Node_Leaf Node_Node]
nipkow@61232
    76
nipkow@63411
    77
fun delete :: "'a::linorder \<Rightarrow> 'a avl_tree \<Rightarrow> 'a avl_tree" where
nipkow@61232
    78
"delete _ Leaf = Leaf" |
nipkow@68413
    79
"delete x (Node l a h r) =
nipkow@61678
    80
  (case cmp x a of
nipkow@68413
    81
     EQ \<Rightarrow> del_root (Node l a h r) |
nipkow@61678
    82
     LT \<Rightarrow> balR (delete x l) a r |
nipkow@61678
    83
     GT \<Rightarrow> balL l a (delete x r))"
nipkow@61232
    84
nipkow@61232
    85
wenzelm@67406
    86
subsection \<open>Functional Correctness Proofs\<close>
nipkow@61232
    87
wenzelm@67406
    88
text\<open>Very different from the AFP/AVL proofs\<close>
nipkow@61232
    89
nipkow@61232
    90
nipkow@61232
    91
subsubsection "Proofs for insert"
nipkow@61232
    92
nipkow@61581
    93
lemma inorder_balL:
nipkow@61581
    94
  "inorder (balL l a r) = inorder l @ a # inorder r"
nipkow@61581
    95
by (auto simp: node_def balL_def split:tree.splits)
nipkow@61232
    96
nipkow@61581
    97
lemma inorder_balR:
nipkow@61581
    98
  "inorder (balR l a r) = inorder l @ a # inorder r"
nipkow@61581
    99
by (auto simp: node_def balR_def split:tree.splits)
nipkow@61232
   100
nipkow@61232
   101
theorem inorder_insert:
nipkow@61232
   102
  "sorted(inorder t) \<Longrightarrow> inorder(insert x t) = ins_list x (inorder t)"
nipkow@61232
   103
by (induct t) 
nipkow@61581
   104
   (auto simp: ins_list_simps inorder_balL inorder_balR)
nipkow@61232
   105
nipkow@61232
   106
nipkow@61232
   107
subsubsection "Proofs for delete"
nipkow@61232
   108
nipkow@68023
   109
lemma inorder_split_maxD:
nipkow@68023
   110
  "\<lbrakk> split_max t = (t',a); t \<noteq> Leaf \<rbrakk> \<Longrightarrow>
nipkow@61232
   111
   inorder t' @ [a] = inorder t"
nipkow@68023
   112
by(induction t arbitrary: t' rule: split_max.induct)
nipkow@61647
   113
  (auto simp: inorder_balL split: if_splits prod.splits tree.split)
nipkow@61232
   114
nipkow@61647
   115
lemma inorder_del_root:
nipkow@68413
   116
  "inorder (del_root (Node l a h r)) = inorder l @ inorder r"
nipkow@68413
   117
by(cases "Node l a h r" rule: del_root.cases)
nipkow@68023
   118
  (auto simp: inorder_balL inorder_balR inorder_split_maxD split: if_splits prod.splits)
nipkow@61232
   119
nipkow@61232
   120
theorem inorder_delete:
nipkow@61232
   121
  "sorted(inorder t) \<Longrightarrow> inorder (delete x t) = del_list x (inorder t)"
nipkow@61232
   122
by(induction t)
nipkow@61581
   123
  (auto simp: del_list_simps inorder_balL inorder_balR
nipkow@68023
   124
    inorder_del_root inorder_split_maxD split: prod.splits)
nipkow@61232
   125
nipkow@61232
   126
wenzelm@67406
   127
subsection \<open>AVL invariants\<close>
nipkow@61232
   128
wenzelm@67406
   129
text\<open>Essentially the AFP/AVL proofs\<close>
nipkow@61232
   130
nipkow@61232
   131
wenzelm@67406
   132
subsubsection \<open>Insertion maintains AVL balance\<close>
nipkow@61232
   133
nipkow@61232
   134
declare Let_def [simp]
nipkow@61232
   135
nipkow@61232
   136
lemma [simp]: "avl t \<Longrightarrow> ht t = height t"
nipkow@61232
   137
by (induct t) simp_all
nipkow@61232
   138
nipkow@61581
   139
lemma height_balL:
nipkow@61232
   140
  "\<lbrakk> height l = height r + 2; avl l; avl r \<rbrakk> \<Longrightarrow>
nipkow@61581
   141
   height (balL l a r) = height r + 2 \<or>
nipkow@61581
   142
   height (balL l a r) = height r + 3"
nipkow@61581
   143
by (cases l) (auto simp:node_def balL_def split:tree.split)
nipkow@61232
   144
       
nipkow@61581
   145
lemma height_balR:
nipkow@61232
   146
  "\<lbrakk> height r = height l + 2; avl l; avl r \<rbrakk> \<Longrightarrow>
nipkow@61581
   147
   height (balR l a r) = height l + 2 \<or>
nipkow@61581
   148
   height (balR l a r) = height l + 3"
nipkow@61581
   149
by (cases r) (auto simp add:node_def balR_def split:tree.split)
nipkow@61232
   150
nipkow@61232
   151
lemma [simp]: "height(node l a r) = max (height l) (height r) + 1"
nipkow@61232
   152
by (simp add: node_def)
nipkow@61232
   153
nipkow@61232
   154
lemma avl_node:
nipkow@61232
   155
  "\<lbrakk> avl l; avl r;
nipkow@61232
   156
     height l = height r \<or> height l = height r + 1 \<or> height r = height l + 1
nipkow@61232
   157
   \<rbrakk> \<Longrightarrow> avl(node l a r)"
nipkow@61232
   158
by (auto simp add:max_def node_def)
nipkow@61232
   159
nipkow@61581
   160
lemma height_balL2:
nipkow@61232
   161
  "\<lbrakk> avl l; avl r; height l \<noteq> height r + 2 \<rbrakk> \<Longrightarrow>
nipkow@61581
   162
   height (balL l a r) = (1 + max (height l) (height r))"
nipkow@61581
   163
by (cases l, cases r) (simp_all add: balL_def)
nipkow@61232
   164
nipkow@61581
   165
lemma height_balR2:
nipkow@61232
   166
  "\<lbrakk> avl l;  avl r;  height r \<noteq> height l + 2 \<rbrakk> \<Longrightarrow>
nipkow@61581
   167
   height (balR l a r) = (1 + max (height l) (height r))"
nipkow@61581
   168
by (cases l, cases r) (simp_all add: balR_def)
nipkow@61232
   169
nipkow@61581
   170
lemma avl_balL: 
nipkow@61232
   171
  assumes "avl l" "avl r" and "height l = height r \<or> height l = height r + 1
nipkow@61232
   172
    \<or> height r = height l + 1 \<or> height l = height r + 2" 
nipkow@61581
   173
  shows "avl(balL l a r)"
nipkow@61232
   174
proof(cases l)
nipkow@61232
   175
  case Leaf
nipkow@61581
   176
  with assms show ?thesis by (simp add: node_def balL_def)
nipkow@61232
   177
next
nipkow@68413
   178
  case Node
nipkow@61232
   179
  with assms show ?thesis
nipkow@61232
   180
  proof(cases "height l = height r + 2")
nipkow@61232
   181
    case True
nipkow@61232
   182
    from True Node assms show ?thesis
nipkow@61581
   183
      by (auto simp: balL_def intro!: avl_node split: tree.split) arith+
nipkow@61232
   184
  next
nipkow@61232
   185
    case False
nipkow@61581
   186
    with assms show ?thesis by (simp add: avl_node balL_def)
nipkow@61232
   187
  qed
nipkow@61232
   188
qed
nipkow@61232
   189
nipkow@61581
   190
lemma avl_balR: 
nipkow@61232
   191
  assumes "avl l" and "avl r" and "height l = height r \<or> height l = height r + 1
nipkow@61232
   192
    \<or> height r = height l + 1 \<or> height r = height l + 2" 
nipkow@61581
   193
  shows "avl(balR l a r)"
nipkow@61232
   194
proof(cases r)
nipkow@61232
   195
  case Leaf
nipkow@61581
   196
  with assms show ?thesis by (simp add: node_def balR_def)
nipkow@61232
   197
next
nipkow@68413
   198
  case Node
nipkow@61232
   199
  with assms show ?thesis
nipkow@61232
   200
  proof(cases "height r = height l + 2")
nipkow@61232
   201
    case True
nipkow@61232
   202
      from True Node assms show ?thesis
nipkow@61581
   203
        by (auto simp: balR_def intro!: avl_node split: tree.split) arith+
nipkow@61232
   204
  next
nipkow@61232
   205
    case False
nipkow@61581
   206
    with assms show ?thesis by (simp add: balR_def avl_node)
nipkow@61232
   207
  qed
nipkow@61232
   208
qed
nipkow@61232
   209
nipkow@61232
   210
(* It appears that these two properties need to be proved simultaneously: *)
nipkow@61232
   211
wenzelm@67406
   212
text\<open>Insertion maintains the AVL property:\<close>
nipkow@61232
   213
nipkow@68422
   214
theorem avl_insert:
nipkow@61232
   215
  assumes "avl t"
nipkow@61232
   216
  shows "avl(insert x t)"
nipkow@61232
   217
        "(height (insert x t) = height t \<or> height (insert x t) = height t + 1)"
nipkow@61232
   218
using assms
nipkow@61232
   219
proof (induction t)
nipkow@68413
   220
  case (Node l a h r)
nipkow@61232
   221
  case 1
nipkow@68422
   222
  show ?case
nipkow@61232
   223
  proof(cases "x = a")
nipkow@68422
   224
    case True with Node 1 show ?thesis by simp
nipkow@61232
   225
  next
nipkow@61232
   226
    case False
nipkow@68422
   227
    show ?thesis 
nipkow@61232
   228
    proof(cases "x<a")
nipkow@68422
   229
      case True with Node 1 show ?thesis by (auto simp add:avl_balL)
nipkow@61232
   230
    next
nipkow@68422
   231
      case False with Node 1 \<open>x\<noteq>a\<close> show ?thesis by (auto simp add:avl_balR)
nipkow@61232
   232
    qed
nipkow@61232
   233
  qed
nipkow@61232
   234
  case 2
nipkow@68422
   235
  show ?case
nipkow@61232
   236
  proof(cases "x = a")
nipkow@68422
   237
    case True with Node 1 show ?thesis by simp
nipkow@61232
   238
  next
nipkow@61232
   239
    case False
nipkow@68422
   240
    show ?thesis 
nipkow@68422
   241
    proof(cases "x<a")
nipkow@61232
   242
      case True
nipkow@68422
   243
      show ?thesis
nipkow@61232
   244
      proof(cases "height (insert x l) = height r + 2")
wenzelm@67406
   245
        case False with Node 2 \<open>x < a\<close> show ?thesis by (auto simp: height_balL2)
nipkow@61232
   246
      next
nipkow@61232
   247
        case True 
nipkow@61581
   248
        hence "(height (balL (insert x l) a r) = height r + 2) \<or>
nipkow@61581
   249
          (height (balL (insert x l) a r) = height r + 3)" (is "?A \<or> ?B")
nipkow@61581
   250
          using Node 2 by (intro height_balL) simp_all
nipkow@61232
   251
        thus ?thesis
nipkow@61232
   252
        proof
nipkow@68422
   253
          assume ?A with 2 \<open>x < a\<close> show ?thesis by (auto)
nipkow@61232
   254
        next
nipkow@68422
   255
          assume ?B with True 1 Node(2) \<open>x < a\<close> show ?thesis by (simp) arith
nipkow@61232
   256
        qed
nipkow@61232
   257
      qed
nipkow@61232
   258
    next
nipkow@61232
   259
      case False
nipkow@68422
   260
      show ?thesis 
nipkow@61232
   261
      proof(cases "height (insert x r) = height l + 2")
nipkow@68422
   262
        case False with Node 2 \<open>\<not>x < a\<close> show ?thesis by (auto simp: height_balR2)
nipkow@61232
   263
      next
nipkow@61232
   264
        case True 
nipkow@61581
   265
        hence "(height (balR l a (insert x r)) = height l + 2) \<or>
nipkow@61581
   266
          (height (balR l a (insert x r)) = height l + 3)"  (is "?A \<or> ?B")
nipkow@61581
   267
          using Node 2 by (intro height_balR) simp_all
nipkow@61232
   268
        thus ?thesis 
nipkow@61232
   269
        proof
nipkow@68422
   270
          assume ?A with 2 \<open>\<not>x < a\<close> show ?thesis by (auto)
nipkow@61232
   271
        next
nipkow@68422
   272
          assume ?B with True 1 Node(4) \<open>\<not>x < a\<close> show ?thesis by (simp) arith
nipkow@61232
   273
        qed
nipkow@61232
   274
      qed
nipkow@61232
   275
    qed
nipkow@61232
   276
  qed
nipkow@61232
   277
qed simp_all
nipkow@61232
   278
nipkow@61232
   279
wenzelm@67406
   280
subsubsection \<open>Deletion maintains AVL balance\<close>
nipkow@61232
   281
nipkow@68023
   282
lemma avl_split_max:
nipkow@61232
   283
  assumes "avl x" and "x \<noteq> Leaf"
nipkow@68023
   284
  shows "avl (fst (split_max x))" "height x = height(fst (split_max x)) \<or>
nipkow@68023
   285
         height x = height(fst (split_max x)) + 1"
nipkow@61232
   286
using assms
nipkow@68023
   287
proof (induct x rule: split_max_induct)
nipkow@68413
   288
  case (Node l a h r)
nipkow@61232
   289
  case 1
nipkow@61647
   290
  thus ?case using Node
nipkow@68422
   291
    by (auto simp: height_balL height_balL2 avl_balL split:prod.split)
nipkow@61232
   292
next
nipkow@68413
   293
  case (Node l a h r)
nipkow@61232
   294
  case 2
nipkow@68023
   295
  let ?r' = "fst (split_max r)"
wenzelm@67406
   296
  from \<open>avl x\<close> Node 2 have "avl l" and "avl r" by simp_all
nipkow@61581
   297
  thus ?case using Node 2 height_balL[of l ?r' a] height_balL2[of l ?r' a]
nipkow@61232
   298
    apply (auto split:prod.splits simp del:avl.simps) by arith+
nipkow@61232
   299
qed auto
nipkow@61232
   300
nipkow@61647
   301
lemma avl_del_root:
nipkow@61232
   302
  assumes "avl t" and "t \<noteq> Leaf"
nipkow@61647
   303
  shows "avl(del_root t)" 
nipkow@61232
   304
using assms
nipkow@61647
   305
proof (cases t rule:del_root_cases)
nipkow@68413
   306
  case (Node_Node ll ln lh lr n h rl rn rh rr)
nipkow@68413
   307
  let ?l = "Node ll ln lh lr"
nipkow@68413
   308
  let ?r = "Node rl rn rh rr"
nipkow@68023
   309
  let ?l' = "fst (split_max ?l)"
wenzelm@67406
   310
  from \<open>avl t\<close> and Node_Node have "avl ?r" by simp
wenzelm@67406
   311
  from \<open>avl t\<close> and Node_Node have "avl ?l" by simp
nipkow@61232
   312
  hence "avl(?l')" "height ?l = height(?l') \<or>
nipkow@68023
   313
         height ?l = height(?l') + 1" by (rule avl_split_max,simp)+
wenzelm@67406
   314
  with \<open>avl t\<close> Node_Node have "height ?l' = height ?r \<or> height ?l' = height ?r + 1
nipkow@61232
   315
            \<or> height ?r = height ?l' + 1 \<or> height ?r = height ?l' + 2" by fastforce
nipkow@68023
   316
  with \<open>avl ?l'\<close> \<open>avl ?r\<close> have "avl(balR ?l' (snd(split_max ?l)) ?r)"
nipkow@61581
   317
    by (rule avl_balR)
nipkow@61232
   318
  with Node_Node show ?thesis by (auto split:prod.splits)
nipkow@61232
   319
qed simp_all
nipkow@61232
   320
nipkow@61647
   321
lemma height_del_root:
nipkow@61232
   322
  assumes "avl t" and "t \<noteq> Leaf" 
nipkow@61647
   323
  shows "height t = height(del_root t) \<or> height t = height(del_root t) + 1"
nipkow@61232
   324
using assms
nipkow@61647
   325
proof (cases t rule: del_root_cases)
nipkow@68413
   326
  case (Node_Node ll ln lh lr n h rl rn rh rr)
nipkow@68413
   327
  let ?l = "Node ll ln lh lr"
nipkow@68413
   328
  let ?r = "Node rl rn rh rr"
nipkow@68023
   329
  let ?l' = "fst (split_max ?l)"
nipkow@68023
   330
  let ?t' = "balR ?l' (snd(split_max ?l)) ?r"
wenzelm@67406
   331
  from \<open>avl t\<close> and Node_Node have "avl ?r" by simp
wenzelm@67406
   332
  from \<open>avl t\<close> and Node_Node have "avl ?l" by simp
nipkow@68023
   333
  hence "avl(?l')"  by (rule avl_split_max,simp)
nipkow@68023
   334
  have l'_height: "height ?l = height ?l' \<or> height ?l = height ?l' + 1" using \<open>avl ?l\<close> by (intro avl_split_max) auto
wenzelm@67406
   335
  have t_height: "height t = 1 + max (height ?l) (height ?r)" using \<open>avl t\<close> Node_Node by simp
wenzelm@67406
   336
  have "height t = height ?t' \<or> height t = height ?t' + 1" using  \<open>avl t\<close> Node_Node
nipkow@61232
   337
  proof(cases "height ?r = height ?l' + 2")
nipkow@61232
   338
    case False
nipkow@68422
   339
    show ?thesis using l'_height t_height False
nipkow@68422
   340
      by (subst height_balR2[OF \<open>avl ?l'\<close> \<open>avl ?r\<close> False])+ arith
nipkow@61232
   341
  next
nipkow@61232
   342
    case True
nipkow@61232
   343
    show ?thesis
nipkow@68023
   344
    proof(cases rule: disjE[OF height_balR[OF True \<open>avl ?l'\<close> \<open>avl ?r\<close>, of "snd (split_max ?l)"]])
nipkow@68422
   345
      case 1 thus ?thesis using l'_height t_height True by arith
nipkow@61232
   346
    next
nipkow@68422
   347
      case 2 thus ?thesis using l'_height t_height True by arith
nipkow@61232
   348
    qed
nipkow@61232
   349
  qed
nipkow@61232
   350
  thus ?thesis using Node_Node by (auto split:prod.splits)
nipkow@61232
   351
qed simp_all
nipkow@61232
   352
wenzelm@67406
   353
text\<open>Deletion maintains the AVL property:\<close>
nipkow@61232
   354
nipkow@68422
   355
theorem avl_delete:
nipkow@61232
   356
  assumes "avl t" 
nipkow@61232
   357
  shows "avl(delete x t)" and "height t = (height (delete x t)) \<or> height t = height (delete x t) + 1"
nipkow@61232
   358
using assms
nipkow@61232
   359
proof (induct t)
nipkow@68413
   360
  case (Node l n h r)
nipkow@61232
   361
  case 1
nipkow@68422
   362
  show ?case
nipkow@61232
   363
  proof(cases "x = n")
nipkow@68422
   364
    case True with Node 1 show ?thesis by (auto simp:avl_del_root)
nipkow@61232
   365
  next
nipkow@61232
   366
    case False
nipkow@68422
   367
    show ?thesis 
nipkow@61232
   368
    proof(cases "x<n")
nipkow@68422
   369
      case True with Node 1 show ?thesis by (auto simp add:avl_balR)
nipkow@61232
   370
    next
nipkow@68422
   371
      case False with Node 1 \<open>x\<noteq>n\<close> show ?thesis by (auto simp add:avl_balL)
nipkow@61232
   372
    qed
nipkow@61232
   373
  qed
nipkow@61232
   374
  case 2
nipkow@68422
   375
  show ?case
nipkow@61232
   376
  proof(cases "x = n")
nipkow@61232
   377
    case True
nipkow@68413
   378
    with 1 have "height (Node l n h r) = height(del_root (Node l n h r))
nipkow@68413
   379
      \<or> height (Node l n h r) = height(del_root (Node l n h r)) + 1"
nipkow@61647
   380
      by (subst height_del_root,simp_all)
nipkow@61232
   381
    with True show ?thesis by simp
nipkow@61232
   382
  next
nipkow@61232
   383
    case False
nipkow@68422
   384
    show ?thesis 
nipkow@68422
   385
    proof(cases "x<n")
nipkow@61232
   386
      case True
nipkow@61232
   387
      show ?thesis
nipkow@61232
   388
      proof(cases "height r = height (delete x l) + 2")
wenzelm@67406
   389
        case False with Node 1 \<open>x < n\<close> show ?thesis by(auto simp: balR_def)
nipkow@61232
   390
      next
nipkow@61232
   391
        case True 
nipkow@61581
   392
        hence "(height (balR (delete x l) n r) = height (delete x l) + 2) \<or>
nipkow@61581
   393
          height (balR (delete x l) n r) = height (delete x l) + 3" (is "?A \<or> ?B")
nipkow@61581
   394
          using Node 2 by (intro height_balR) auto
nipkow@61232
   395
        thus ?thesis 
nipkow@61232
   396
        proof
nipkow@68422
   397
          assume ?A with \<open>x < n\<close> Node 2 show ?thesis by(auto simp: balR_def)
nipkow@61232
   398
        next
nipkow@68422
   399
          assume ?B with \<open>x < n\<close> Node 2 show ?thesis by(auto simp: balR_def)
nipkow@61232
   400
        qed
nipkow@61232
   401
      qed
nipkow@61232
   402
    next
nipkow@61232
   403
      case False
nipkow@61232
   404
      show ?thesis
nipkow@61232
   405
      proof(cases "height l = height (delete x r) + 2")
wenzelm@67406
   406
        case False with Node 1 \<open>\<not>x < n\<close> \<open>x \<noteq> n\<close> show ?thesis by(auto simp: balL_def)
nipkow@61232
   407
      next
nipkow@61232
   408
        case True 
nipkow@61581
   409
        hence "(height (balL l n (delete x r)) = height (delete x r) + 2) \<or>
nipkow@61581
   410
          height (balL l n (delete x r)) = height (delete x r) + 3" (is "?A \<or> ?B")
nipkow@61581
   411
          using Node 2 by (intro height_balL) auto
nipkow@61232
   412
        thus ?thesis 
nipkow@61232
   413
        proof
nipkow@68422
   414
          assume ?A with \<open>\<not>x < n\<close> \<open>x \<noteq> n\<close> Node 2 show ?thesis by(auto simp: balL_def)
nipkow@61232
   415
        next
nipkow@68422
   416
          assume ?B with \<open>\<not>x < n\<close> \<open>x \<noteq> n\<close> Node 2 show ?thesis by(auto simp: balL_def)
nipkow@61232
   417
        qed
nipkow@61232
   418
      qed
nipkow@61232
   419
    qed
nipkow@61232
   420
  qed
nipkow@61232
   421
qed simp_all
nipkow@61232
   422
nipkow@63411
   423
nipkow@68422
   424
subsection "Overall correctness"
nipkow@68422
   425
nipkow@68440
   426
interpretation S: Set_by_Ordered
nipkow@68431
   427
where empty = empty and isin = isin and insert = insert and delete = delete
nipkow@68422
   428
and inorder = inorder and inv = avl
nipkow@68422
   429
proof (standard, goal_cases)
nipkow@68431
   430
  case 1 show ?case by (simp add: empty_def)
nipkow@68422
   431
next
nipkow@68422
   432
  case 2 thus ?case by(simp add: isin_set_inorder)
nipkow@68422
   433
next
nipkow@68422
   434
  case 3 thus ?case by(simp add: inorder_insert)
nipkow@68422
   435
next
nipkow@68422
   436
  case 4 thus ?case by(simp add: inorder_delete)
nipkow@68422
   437
next
nipkow@68431
   438
  case 5 thus ?case by (simp add: empty_def)
nipkow@68422
   439
next
nipkow@68422
   440
  case 6 thus ?case by (simp add: avl_insert(1))
nipkow@68422
   441
next
nipkow@68422
   442
  case 7 thus ?case by (simp add: avl_delete(1))
nipkow@68422
   443
qed
nipkow@68422
   444
nipkow@68422
   445
nipkow@63411
   446
subsection \<open>Height-Size Relation\<close>
nipkow@63411
   447
nipkow@68342
   448
text \<open>Based on theorems by Daniel St\"uwe, Manuel Eberl and Peter Lammich.\<close>
nipkow@63411
   449
nipkow@68313
   450
lemma height_invers: 
nipkow@63411
   451
  "(height t = 0) = (t = Leaf)"
nipkow@68413
   452
  "avl t \<Longrightarrow> (height t = Suc h) = (\<exists> l a r . t = Node l a (Suc h) r)"
nipkow@63411
   453
by (induction t) auto
nipkow@63411
   454
nipkow@68313
   455
text \<open>Any AVL tree of height \<open>h\<close> has at least \<open>fib (h+2)\<close> leaves:\<close>
nipkow@63411
   456
nipkow@68313
   457
lemma avl_fib_bound: "avl t \<Longrightarrow> height t = h \<Longrightarrow> fib (h+2) \<le> size1 t"
nipkow@68313
   458
proof (induction h arbitrary: t rule: fib.induct)
nipkow@68313
   459
  case 1 thus ?case by (simp add: height_invers)
nipkow@63411
   460
next
nipkow@68313
   461
  case 2 thus ?case by (cases t) (auto simp: height_invers)
nipkow@63411
   462
next
nipkow@68313
   463
  case (3 h)
nipkow@68313
   464
  from "3.prems" obtain l a r where
nipkow@68413
   465
    [simp]: "t = Node l a (Suc(Suc h)) r" "avl l" "avl r"
nipkow@68313
   466
    and C: "
nipkow@68313
   467
      height r = Suc h \<and> height l = Suc h
nipkow@68313
   468
    \<or> height r = Suc h \<and> height l = h
nipkow@68313
   469
    \<or> height r = h \<and> height l = Suc h" (is "?C1 \<or> ?C2 \<or> ?C3")
nipkow@68313
   470
    by (cases t) (simp, fastforce)
nipkow@68313
   471
  {
nipkow@68313
   472
    assume ?C1
nipkow@68313
   473
    with "3.IH"(1)
nipkow@68313
   474
    have "fib (h + 3) \<le> size1 l" "fib (h + 3) \<le> size1 r"
nipkow@68313
   475
      by (simp_all add: eval_nat_numeral)
nipkow@68313
   476
    hence ?case by (auto simp: eval_nat_numeral)
nipkow@68313
   477
  } moreover {
nipkow@68313
   478
    assume ?C2
nipkow@68313
   479
    hence ?case using "3.IH"(1)[of r] "3.IH"(2)[of l] by auto
nipkow@68313
   480
  } moreover {
nipkow@68313
   481
    assume ?C3
nipkow@68313
   482
    hence ?case using "3.IH"(1)[of l] "3.IH"(2)[of r] by auto
nipkow@68313
   483
  } ultimately show ?case using C by blast
nipkow@68313
   484
qed
nipkow@68313
   485
nipkow@68313
   486
lemma fib_alt_induct [consumes 1, case_names 1 2 rec]:
nipkow@68313
   487
  assumes "n > 0" "P 1" "P 2" "\<And>n. n > 0 \<Longrightarrow> P n \<Longrightarrow> P (Suc n) \<Longrightarrow> P (Suc (Suc n))"
nipkow@68313
   488
  shows   "P n"
nipkow@68313
   489
  using assms(1)
nipkow@68313
   490
proof (induction n rule: fib.induct)
nipkow@68313
   491
  case (3 n)
nipkow@68313
   492
  thus ?case using assms by (cases n) (auto simp: eval_nat_numeral)
nipkow@68313
   493
qed (insert assms, auto)
nipkow@68313
   494
nipkow@68313
   495
text \<open>An exponential lower bound for @{const fib}:\<close>
nipkow@63411
   496
nipkow@68313
   497
lemma fib_lowerbound:
nipkow@68313
   498
  defines "\<phi> \<equiv> (1 + sqrt 5) / 2"
nipkow@68313
   499
  defines "c \<equiv> 1 / \<phi> ^ 2"
nipkow@68313
   500
  assumes "n > 0"
nipkow@68313
   501
  shows   "real (fib n) \<ge> c * \<phi> ^ n"
nipkow@68313
   502
proof -
nipkow@68313
   503
  have "\<phi> > 1" by (simp add: \<phi>_def)
nipkow@68313
   504
  hence "c > 0" by (simp add: c_def)
nipkow@68313
   505
  from \<open>n > 0\<close> show ?thesis
nipkow@68313
   506
  proof (induction n rule: fib_alt_induct)
nipkow@68313
   507
    case (rec n)
nipkow@68313
   508
    have "c * \<phi> ^ Suc (Suc n) = \<phi> ^ 2 * (c * \<phi> ^ n)"
nipkow@68313
   509
      by (simp add: field_simps power2_eq_square)
nipkow@68313
   510
    also have "\<dots> \<le> (\<phi> + 1) * (c * \<phi> ^ n)"
nipkow@68313
   511
      by (rule mult_right_mono) (insert \<open>c > 0\<close>, simp_all add: \<phi>_def power2_eq_square field_simps)
nipkow@68313
   512
    also have "\<dots> = c * \<phi> ^ Suc n + c * \<phi> ^ n"
nipkow@68313
   513
      by (simp add: field_simps)
nipkow@68313
   514
    also have "\<dots> \<le> real (fib (Suc n)) + real (fib n)"
nipkow@68313
   515
      by (intro add_mono rec.IH)
nipkow@68313
   516
    finally show ?case by simp
nipkow@68313
   517
  qed (insert \<open>\<phi> > 1\<close>, simp_all add: c_def power2_eq_square eval_nat_numeral)
nipkow@68313
   518
qed
nipkow@68313
   519
nipkow@68313
   520
text \<open>The size of an AVL tree is (at least) exponential in its height:\<close>
nipkow@68313
   521
nipkow@68342
   522
lemma avl_size_lowerbound:
nipkow@68313
   523
  defines "\<phi> \<equiv> (1 + sqrt 5) / 2"
nipkow@68313
   524
  assumes "avl t"
nipkow@68342
   525
  shows   "\<phi> ^ (height t) \<le> size1 t"
nipkow@68313
   526
proof -
nipkow@68313
   527
  have "\<phi> > 0" by(simp add: \<phi>_def add_pos_nonneg)
nipkow@68313
   528
  hence "\<phi> ^ height t = (1 / \<phi> ^ 2) * \<phi> ^ (height t + 2)"
nipkow@68313
   529
    by(simp add: field_simps power2_eq_square)
nipkow@68342
   530
  also have "\<dots> \<le> fib (height t + 2)"
nipkow@68313
   531
    using fib_lowerbound[of "height t + 2"] by(simp add: \<phi>_def)
nipkow@68342
   532
  also have "\<dots> \<le> size1 t"
nipkow@68313
   533
    using avl_fib_bound[of t "height t"] assms by simp
nipkow@68313
   534
  finally show ?thesis .
nipkow@68313
   535
qed
nipkow@63411
   536
nipkow@68342
   537
text \<open>The height of an AVL tree is most @{term "(1/log 2 \<phi>)"} \<open>\<approx> 1.44\<close> times worse
nipkow@68342
   538
than @{term "log 2 (size1 t)"}:\<close>
nipkow@68342
   539
nipkow@68342
   540
lemma  avl_height_upperbound:
nipkow@68342
   541
  defines "\<phi> \<equiv> (1 + sqrt 5) / 2"
nipkow@68342
   542
  assumes "avl t"
nipkow@68342
   543
  shows   "height t \<le> (1/log 2 \<phi>) * log 2 (size1 t)"
nipkow@68342
   544
proof -
nipkow@68342
   545
  have "\<phi> > 0" "\<phi> > 1" by(auto simp: \<phi>_def pos_add_strict)
nipkow@68342
   546
  hence "height t = log \<phi> (\<phi> ^ height t)" by(simp add: log_nat_power)
nipkow@68342
   547
  also have "\<dots> \<le> log \<phi> (size1 t)"
nipkow@68342
   548
    using avl_size_lowerbound[OF assms(2), folded \<phi>_def] \<open>1 < \<phi>\<close>  by simp
nipkow@68342
   549
  also have "\<dots> = (1/log 2 \<phi>) * log 2 (size1 t)"
nipkow@68342
   550
    by(simp add: log_base_change[of 2 \<phi>])
nipkow@68342
   551
  finally show ?thesis .
nipkow@68342
   552
qed
nipkow@68342
   553
nipkow@61232
   554
end