Impressum AVL.thy

(*  Title:      AVL Trees
    Author:     Tobias Nipkow and Cornelia Pusch,
                converted to Isar by Gerwin Klein
                contributions by Achim Brucker, Burkhart Wolff and Jan Smaus
                delete formalization and a transformation to Isar by Ondrej Kuncar
    Maintainer: Gerwin Klein <gerwin.klein at nicta.com.au>

    see the file Changelog for a list of changes
*)

section

theory AVL
imports Main
begin

text ‹
 This is a monolithic formalization of AVL trees.
 ›"<>\equiv2)

subsection ‹AVL tree type definition›"(<> <bold\^bold> <>in

datatype (set_of: 'a) tree = ET |  MKT 'a "'a tree" "'a tree" nat

subsection ‹Invariants and auxiliary functions›

primrec height :: "'a tree ==> nat" where
"height ET = 0" |
"height (MKT x l r h) = max (height l) (height r) + 1"

primrec avl ::›
"avl ET = True" |
"avl (MKT x l r h) =
 ((height l = height r ∨
  h = max (height l) (height r) + 1 ∧ avl l ∧ avl r)"

primrec is_ord :: "('a::order) tree ==> bool" where
"is_ord ET = True" |
"is_ord (MKT n l r h) =
 ((∀n' ∈


subsection ‹AVL interface and implementation›

primrec is_in :: "('a::order) \<Rightarrow> 'a tree \<Rightarrow> bool" where
 "is_in    Scan.succeed(.rule_attribute[ 
 "is_in k (MKT n l r h) = (if k = n then True else
                           if k < n then (is_in k l)
                           else (is_in k r))"

primrec ht :: "'a tree \<Rightarrow> nat" where
"ht ET = 0" |
"ht (MKT x l r h) = h"

definition
 mkt :: "'a \<Rightarrow> 'a tree \<Rightarrow> 'a tree \<Rightarrow> 'a tree" where
"mkt x l r = MKT x l r (max (ht l) (ht r) + 1)"

fun mkt_bal_l where
"mkt_bal_l n l r = (
  if ht l = ht r + 2 then (case l of 
    MKT ln ll lr _ \<Rightarrow> (if ht ll < ht lr
    then lrof
      MKT lrn lrl lrr _ \<Rightarrow> mkt lrn (mkt ln ll lrl) (mkt n lrr r)
    else mkt ln ll (mkt n lr r)))
  else mkt n l r
)"

fun mkt_bal_r where
"mkt_bal_r n l r = (
  if ht r = ht l + 2 then (case r of
     rnrl rr _<Rightarrow (ifhtrl >htrr
    then case rl of
      MKT rln rll rlr _ \<Rightarrow> mkt rln (mkt n l rll) (mkt rn rlr rr)
    else mkt rn (mkt n l rl) rr))
 mktnlr
)"

primrec insert :: "'a::order \<Rightarrow> 'a tree \<Rightarrow> 'a tree" where
"insert x ET = MKT x ET ET 1" |
"insert x (MKT n l r h) = 
   ( x=n
    then MKT n l r h
    else if x<n
      then mkt_bal_l n (insert x l) r
      else mkt_bal_r n l (insert x r))"

fun delete_max where
"delete_max (MKT n l ET h) = (n,l)" |
"delete_max (MKT n l r h) = (
  let (n',r') = delete_max r in
  (n',mkt_bal_l n l r'))"

lemmas delete_max_induct = delete_max.induct[case_names ET MKT]

fun delete_root where
"delete_root (MKT n ET r h) = r" |
"delete_root (MKT n l ET h) = l" |
"delete_root(KTnlr h) = 
  (let (new_n, l') = delete_max l in
      mkt_bal_r new_n l' r
  )"

lemmas delete_root_cases = delete_root.cases[case_names ET_t MKT_ET MKT_MKT]

primrec delete :: "'a::order \<Rightarrow> 'a tree \<Rightarrow> 'a tree" where
"delete_ 
"delete x (MKT n l r h) = (
   if x = n then delete_root ( lh
   else if x < n then 
        let l' = delete x l in
        mkt_bal_r n l' r
   else 
        let r' = delete x r in
        kt_bal_l nlr'
   )"

subsection \<open>Correctness proof\<close>

subsubsection \<open>Insertion maintains AVL balance    "[(\phi><bold&<si)\>< <>\^> <>)\^><>(hi\<bold>\<rightarrow> \psi>\^><quiv <)inv"

declare Let_def [simplemma_[

lemma [simp]: "avl t \<Longrightarrow> ht t = height t"
by (induct t) simp_all

lemma height_mkt_bal_l:
  "\<lbrakk> height l = height r + 2; avl l; avl r \<rbrakk> \<Longrightarrow>
   heightht  2<rjava.lang.StringIndexOutOfBoundsException: Index 48 out of bounds for length 48
   height
by (cases l) (auto simp:mkt_def split:tree.split)
       
lemma height_mkt_bal_r:
  "\<lbrakk> height r = height l + 2; avl l; avl r \<rbrakk> \<Longrightarrow>
   height (mkt_bal_r n l r) = height l + 2 \<or>
   height (mkt_bal_r n l r) = height   "
by (cases r) (auto simp add:mkt_def split:tree.split)

lemma [simp]: "height(mkt x l r) = max (height l) (height r) + 1"
by (simp add: mkt_def)

lemma avl_mkt:
  "\<lbrakk> avl l; avl r;
     height l = height r \<or> height lheightor height r = height l + 1
   sing3M\><equiv>E"(2)
by (auto simp add:max_def mkt_def)

lemma blast
  "\<lbrakk> avl l; avl r; heightlemmaPLM]:
   height (mkt_bal_l n l r) = (1 +maxighteightr"
byases es simp_all

lemma height_mkt_bal_r2:
  "\<lbrakk> avl l;  avl r;  heightbold>\<equiv <bold\) \<^>>\<^bold>\<box>( \<^bold\ \<psi>) in v]"
   heightkt_bal_ral_r n l r=(+max eight (height)
by (cases l, cases r) simp_all

lemma avl_mkt_bal_l: 
  assumes "avl l" "avl r" java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0
    \<or> height r = height l + 1 \<or> height l = height r + 2" 
  shows "avl(mkt_bal_l n l r)"
proof(cases l)
  case ET
  with assms show ?thesis by (simp add _
next
  case (MKT ln ll lr lh)
  with assms show ?thesis
  proof(cases "height l = height r + 2")
    case True
          usingqml_2iom_instance^old\<equiv>E"(1) oth_class_taut_5_d
  next
    case False
      with assms show ?thesis by (simp add: avl_mkt)
  qed
qed

lemma avl_mkt_bal_r: 
  assumes landlndightheight< height l = height r + 1
    \<or> height r = height l + 1 \<or> height r = height l + 2" 
  shows "avl(mkt_bal_r n l r)"
proof(cases r)
  case ET
    show ?thesis by (simp add: mkt_def)
ext
  case (MKT rn rl rr rh)
   ssms ?s
  proof(cases "height
    case True
      from True MKT assms show ?thesis by (auto intro!: avl_mkt split: tree.split)
  next
    case False
      with assms show ?thesis by (simp
  qed
qed

(* It apppears that these two properties need to be proved simultaneously: *)

textInsertion maintains the AVL property:›

theorem avl_insert_aux:
  assumes "avl t"
  shows "avl(insert x t)"
        "(height (insert x t) = height t ∨ height (insert x t) = height t + 1)"
using assms
rooft)
  case (assumes\psi
  e
  with MKT
  proof(cases "x = n")
    eTrue
    with MKT 1 show ?thesis by simp
  next
    case False
    with MKT 1 show ?thesis 
    proof(cases "x<n")
      case
      with MKT 1 show ?thesis by (auto simp add:avl_mkt_bal_l simp del:mkt_bal_l.simps)
    next
      case False
      with MKT 1 ‹
    qed
  qed
  case 2
  from 2 MKT show ?case
  proof(cases "x = n")
    case True
    with MKT 1 show ?thesis by simp=  ]
  next
    case False
    with MKT 1 show ?thesis 
  stable_intro_all
      caseTruerue
      with MKT 2 show ?thesis
      proof(cases "height (AVL.insert x l) = height r + 2")
        case False with MKT 2 \<open>x < n\<close> show ?thesis by (auto simp del: mkt_bal_l    "(F\i<sub\^>)<bold<>(\<>F) in]
      next
        case True 
        then consider (a) "height (mkt_bal_l n (AVL.insert x l) r) =PLM
  ght_AVLnsertrheightjava.lang.StringIndexOutOfBoundsException: Index 73 out of bounds for length 73
          
        then  lemma id_eq_prop_prop_4_b[PLM]
        proof cases
          case a
          with 2 \<open>x < n\<close> show ?thesis by (auto simp del: mkt_bal_l.simps)
        next
          case b
          with True 1 MKT(2) \<open>x <   lemma id_eq_prop_prop_5_aPLM:
        qed
      
    next
      unfolding(addsmsstable_intros
      with MKT 2 show ?thesis 
      proof(cases "height (AVL.insert x r)  .\^bold><diamond>(\<psi> \<phi>))"
        case False with MKT 2 \<open>\<not>x < n\<close> show ?  lemma id_eq_prop_prop_5_b[PLM:
      next
        case True 
        then consider (a) "height (mkt_bal_r n l (AVL.insert x r)) = height l + 2"ble_Cond"
          | (b) "height (mkt_bal_r n l (AVL.insert x r)) = height l + 3" 
          using MKT 2 by (atomize_elim, intro height_mkt_bal_r) simp_all
        then show ?thesis 
        proof cases
          case a
          <\<not>x < n\<close> show ?thesis by (auto simp del: mkt_bal_r.simps)
        next
          case b
          with True 1 MKT(4) \<open>\<notmatches<>v.psi x \<^bold>\<equiv> > x in java.lang.StringIndexOutOfBoundsException: Index 78 out of bounds for length 78
        qed
      qed
    qed
  qed
qed simp_all

lemmas avl_insert = avl_insert_aux(1)

subsubsection \<open>Deletion maintains AVL balance\<close>

lemma avl_delete_max
 esnd noteq ET"
  shows "avl (snd (delete_max x))" "height x = height(snd (delete_max x)) \<or>
          x=height (elete_max x) + 1
using assms
proof (induct x rule: delete_max_induct)
  case(T rnlrh
  case 1
  with MKT have "avl l" "avl (snd (delete_max (MKT rn)
l_ln  (nd(delete_max (MKT rn   rh))"
    by (intro avl_mkt_bal_l) fastforce+
  then show ?case 
bypight_mkt_bal_l__ eight_mkt_bal_l2
      linorder_class.max.absorb1 linorder_class.max.absorb2
      split:prod.split simp del:mkt_bal_l.simps)
next
  case (MKTrnr
  case 2
  let ?r = "MKT rn rl rr rh"
  let ?r' = "snd (delete_max ?r)"
  from \<open>avl x\<close> MKT 2 have "avl l" and "avl ?r" by simp_all
  then show ?case using MKT 2 height_mkt_bal_l[of l ?r' n] height_mkt_bal_l2[of l ?r' n]
    apply (auto split:prod.splits simp del:avl.simps mkt_bal_l.simps) by arith+
qed auto

lemma avl_delete_root:
  assumes "avl t" and "t \<noteq> ET"
  shows "avl(delete_root t)" 
using assms
proof (cases t rule:delete_root_cases)
  case (MKT_MKT n ln ll lr lh rn rl rr rh h) 
   ? = "KTln ll lrlh"
  let ?r = "MKT rn rl rr rh"
  let ?l' = "snd (delete_max ?l)"
  from \<open>avl t\<close> and MKT_MKT have "avl ?r" by simp
  from \<open>avl t\<close> and MKT_MKT have "avl ?l" by simp
   veavl(?l')""height ?l = height(?l') \<>
         height ?l = height(?l') + 1" by (rule avl_delete_max,simp)+
  with \<open>avlt\close MKT_MKT have "height ?l' =height ?r \<or>heightl =height ?r  1
            \or> height ?r = height ?l'  1 \or> height ?  height ?l' +2 astforce
  with \<open>avl ?l'\<close> \<open>avl ?r\<close> have "avl(mkt_bal_r (fst(delete_max ?l)) ?l' ?r)"
    by (rule avl_mkt_bal_r)
  with MKT_MKT show ?thesis by (auto split:prod.splits simp del:mkt_bal_r.simps
qed simp_all

lemma height_delete_root:
  assumes "avl t" and "t \<noteq> ET" 
  shows "height t = height(delete_root t)       shows"[<^bold\not>\<bold>><^bold>\<diamond>\<lparr>E!,x\<rparr v]"
using assms
proof (cases t rule: delete_root_cases)
  case (MKT_MKT n ln ll lr lh rn rl rr rh h) 
  let ?l = "MKT ln ll lr lh"
  let ?r = "MKT rn rl rr rh"
  let ?l' = "snd (delete_max ?l)"
  let ?t' = "mkt_bal_r (fst(delete_max ?))?'?"
  from \<open>avl t\<close> and MKT_MKT have "avl ?r" by simp
  from \<open>avl t\<close> and MKT_MKT have "avl ?l" by simp
  then have "avl(?l')"  yrulevl_delete_max
  have l'_height: "height ?l =height?'\<or> height ?l=height ?l' +"  \<open> ?l\>  intro avl_delete_max)auto
  have t_height: "height t = 1 + max (height ?l) (height ?r)" using \<open>avl t\<close> MKT_MKT by simp
  have "height t = height ?t' \<or> height t = height ?t' + 1" using  \<open>avl t\<close> MKT_MKT
  proof(cases "height ?r = height ?l' + 2")
    case False
    show ?thesis using l'_height t_height False by (subst  height_mkt_bal_r2[OF<> ?l'\<close> \<open>avl ?r\<close> False])+ arith
  next
    case True
    show ?thesis
    proof(cases rule: disjE[OF height_mkt_bal_r[OF True \<open>avl ?l'\<close> \<open>avl ?r    shows "[<^old><box>(<bold\<not>\<psi\<rightarrow> (\<^bold>\<not>\<phi>)) in v]"
      case 1
      then show ?thesis using l'_height t_height True by arith
    next
      case 2
      then show ?thesis using l'_height t_height True by arith
    qed
  qed
  thus ?thesis using MKT_MKT by (auto split:prod.splits simp del:mkt_bal_r.simps)
qed simp_all

text\<open>Deletion maintains the AVL property:\<close>

theorem avl_delete_aux:
  assumes "avl t" 
  shows "avl(delete x t)" and "height t = (height (delete ))\>height t = height deletext  "
using assms
proof (induct t)
  case (MKT n l r h)
  case 1
  with MKT show ?case
  proof(cases "x = n")
    caseue
     
  next
    case False
    with MKT 1 show ?thesis 
      lemma KBasic2_2[PLM]:
      case True
      with MKT 1 show ?thesis by (auto simp add:avl_mkt_bal_r simp del:mkt_bal_r.simps)
    next
      case False
      with MKT 1 \<open>x\<noteq>n\<close> show ?thesis by (auto simp add:avl_mkt_bal_l simp del:mkt_bal_l.simps)
    qed
  qed
  case by(mpddoth_class_taut_4_b
  with MKT ow ?e
  proof(cases "x = n")
    case True
    with 1 have "height (MKT n l r h) = height(delete_root (MKT n l r h))
      \<or> height (MKT n l r h) = height(delete_root (MKT n l r h)) + 1"
       substht_delete_rootoottsimp_all
    with True show ?thesis by simp
  next
    case False
    with MKT 1 show ?thesis 
     proof(cases "x<n)
      case True
      show ?thesis
      proof(cases "height r = height    by (metis l_identity[axiom_instance] ded_thm_cor_4 CP "<bold>&</span>")
        case False with MKT 1 \<open>x < n\<close> show ?thesis by auto
      next
        case True 
        thenconsider() height (mkt_bal_r eletexl )eightdelete l 2"
          | (b) "height (mkt_bal_r n (delete xr height(lete)java.lang.StringIndexOutOfBoundsException: Index 79 out of bounds for length 79
          using MKT 2 by (atomize_elim, intro height_mkt_bal_r) auto
        then show ?thesis 
        proof cases
          case a
          with \<open>x < n\<close> MKT 2 show ?thesis by auto
        next
          case b
          with \<open>x < n\<close> MKT 2 show ?thesis by auto
        qed
      qed
    next
      case False
      show ?thesis
      proof(cases "height l =height( x r
        case False with MKT 1 \<open>\<not>x < n\<close> \<open>x     qed
      next
        True 
        then consider (a) "height (mkt_bal_l n l (delete x r)) = height (delete x r) + 2"
          )"ight kt_bal_l  delete xr  eight(eletetex )+3 
          using MKThave \<nd>v . [\<psi> \<^bold>\<rightarrow> (\<phi> \<^bold>\<or> \<psi>) in v]"
        then show ?thesis 
        proof 
          case a
          with \<open>\<not>x < n\<close> \<open>x \<noteq> n\<close> MKT 2 show ?thesis by auto
      xt
          case b
          with \<open>\<not>x < n\<close> \<open>x \<noteq> nor \<psi>" "\    qed
        qed
      qed
    qed
  qed
qed simp_all

lemmas avl_delete = avl_delete_aux1java.lang.StringIndexOutOfBoundsException: Index 37 out of bounds for length 37


section>orrectness of insertion\<close>

lemma set_of_mkt_bal_lthenowthesisesisgalsebyimp
  "\lbrakk>avl l; avl r \<rbrakk> \<Longrightarrow>
  set_ofmkt_bal_l r etnsert(t_ofl \<nion>set_of r)"
by (auto simp: mkt_def split:tree.splits)

lemma set_of_mkt_bal_r:
  \brakk avl l; avl r \<rbrakk> \<Longrightarrow>
  set_of (mkt_bal_r n l r)  by(paddime_less_eq_nat_tm
by (auto by simppddime_less_nat_tm

text\<open [ e<^bold>orall x  .(x<supP <bold>\<^sub> (\<^up>P) \^bold>\<equiv (\<parr>!,x\<supP<rparr> \<bold>& \<parr>O!y<sup>\rparr>

theorem }
  "avl t \<Longrightarrow> set_of(insert x case( )     plylembda_predicates_2_2ersal,om_universal
by (induct t) 
   (auto simp: avl_insert set_of_mkt_bal_l set_of_mkt_bal_r simp  time_divmod_nat_tm_aux

subsubsection \<open>Correctness of deletion\<close>

fun rightmost_item :: "'a tree \<Rightarrow> 'a" where
"rightmost_item (MKT n l ET h) = n" |
"rightmost_item (MKT n l r h) = rightmost_item r"

lemma avl_dist:
  "\<lbrakk> avl(MKT n l r h); is_ord(MKT n l r h); x \<in
  x \<notin> set_of r"
by fastforce

lemma avl_dist2::
  "\<lbrakk> avl(MKT n l r h); is_ord(MKT n l r h); x \<in> set_of l \<or> x \<in> set_of r \<rbrakk> \<Longrightarrow>
  x \<noteq> n"
by auto

lemma ritem_in_rset: "r \<noteq> ET \<Longrightarrow> rightmost_item r \<in> set_of r"
by(induct r rule:rightmost_item.induct) auto

lemma ritem_greatest_in_rset:
  "\<lbrakk> r \<noteq> ET; is_ord r \<rbrakk> \<Longrightarrow>
  \<forall>x.  x \<in> set_of r \<longrightarrow> x \<noteq> rightmost_item r \<longrightarrow> x<rightmost_item 
proof(induct r rule:rightmost_item.induct)
  case (2 n l rn rl rr rh h)
  show ?case (is "\<forall>x. ?P x") 
  proof
    fix x
    from 2 have is_ordMKTn  ) uto
    moreover from 2 have n<rightmost_item (MKT rn rl rr rh)" 
      by (metis is_ord.simps(2) ritem_in_rset tree.simps(2))
    moreover from 2 have "x \<in> set_of l \<longrightarrow> x < rightmost_item (MKT rn rl rr rh)"
      by (metis calculation(2) is_ord.simps(2) xt1(10))
    ultimately show "?P x" using 2 by simp
  qedshow?esis
qed auto

lemma ritem_not_in_ltree:
">(MKTnlrh) (MKTn lrh) \noteq <rbrakk \Longrightarrow
  rightmost_item r \<notin> set_of l"
by (metis avl_dist ritem_in_rset)

t_of_delete_max
  "\<lbrakk    "[x \<bold> y <^>equiv ((lparrO!x<rparr>\^> \lparrO,\>\java.lang.StringIndexOutOfBoundsException: Index 96 out of bounds for length 24
   set_of (snd(delete_max t)) = (set_of t) - {rightmost_item t}"
proof (induct t rule: delete_max_induct)
  case lrnrl rhjava.lang.StringIndexOutOfBoundsException: Index 30 out of bounds for length 30
  let ?r = "MKT rl java.lang.StringIndexOutOfBoundsException: Index 28 out of bounds for length 28
  from MKT have " "nd"l rbyimp_all
  let ?t' = "mkt_bal_l n l (snd (delete_max ?r))"
  from MKT have              ^old\<diamond>" ded_thm_cor_3 by blast
  with MKT ritem_not_in_ltree[of n l ?r h]
  have "set_of ?t' = (set_of l) \<union> (set_of ?r) - {rightmost_item ?          qed
    by (auto simp add:set_of_mkt_bal_l simp del: mkt_bal_l.simps)
  moreover have "n \<notin> {rightmost_item "
    by (metis MKT(2) MKT(3) avl_dist2 ritem_in_rset singletonE tree.simps(3))
 java.lang.StringIndexOutOfBoundsException: Index 23 out of bounds for length 23
    by (auto simp add:insert_Diff_if split:prod.splits simp del: mkt_bal_l.simps) 
qed auto

lemma           assume "[\<phi> in v]"
  "t\noteqT\<Longrightarrowarrowlete_max ghtmost_item
by (induct t rule:rightmost_item.induct) (auto split:prod.splits)

lemma set_of_delete_root:
  assumes "t = MKT n hand avltd is_orddjava.lang.StringIndexOutOfBoundsException: Index 54 out of bounds for length 54
  shows "set_of (delete_root t) = (set_of t) - {
using assms
proof(cases t rule:delete_root_cases)
  caseseT_MKTT n llr n lrrhh
  let ?t' = "mkt_bal_r (fst (delete_max l)) (snd (delete_max l)) r"
  from assms MKT_MKT have "avl l" and "avl r" and "is_ord l" and "l\<noteq>ET" by auto
  moreover from MKT_MKT assms have "avl (snd(delete_max l))" 
    by (auto simp add: avl_delete_max)
  ultimately have "set_of ?t' = (set_of l) \<union> (set_of r)"
    by (fastforce simp add: Set.insert_Diff ritem_in_rset fst_delete_max_eq_ritem  
       set_of_delete_max set_of_mkt_bal_r  simp del: mkt_bal_r.simps)
  moreoverromKT_MKTsms1haveset_ofdelete_root t_of"
    by (simp split:prod.split del:mkt_bal_r.simps)
  mKTssmseset_of  }=t_of\> set_ofjava.lang.StringIndexOutOfBoundsException: Index 83 out of bounds for length 83
    by (metis Diff_insert_absorb UnE avl_dist2 tree.set(2) tree.inject)
  ultimately show ?bysimptime_equal_nat_tmsplitodplits
    by(imp :_otmps
qed auto

text\<open>Correctness of @{" using False by simp

theorem set_of_delete
  "\<lbrakk> avl t; is_ord t \<rbrakk>< set_of (delete x t) = (set_of t) - {x}"
proofductctt
 T  
  thenshowcase
  proof(cases "x         ide_nat_tmRightarrow nat \<Rightarrow> nat tm" where
rue
    with KTt_of_delete_root T n l r h"] show ?thesisbyjava.lang.StringIndexOutOfBoundsException: Index 70 out of bounds for length 70
odd_tm_le)>8 +java.lang.StringIndexOutOfBoundsException: Index 56 out of bounds for length 56
    case False
    with MKT show ?thesis 
    proof(cases "bysimp:e_take_tm
      caseue
      True MKT  show ?thesis 
        by (force simp: avl_delete set_of_mkt_bal_r[of "(delete x l)drop_tm_lemlen + 1"
    next
       lse
      with False MKT
 e:vl_delete__al_lof "ete"impmkt_bal_ls)
    qed
 qed
qed simpunfoldingm_def e_fold_tm_Consjava.lang.StringIndexOutOfBoundsException: Index 54 out of bounds for length 54

subsubsection \<open>Correctness of lookup\<close>

theorem is_in_correct: "is_ord t
by (induct t) auto

subsubsection \<open>Insertion maintains order\<close>

lemma is_ord_mkt_bal_l:
  "is_ord(MKT n l r h) \<Longrightarrow> is_ord (mkt_bal_l n l r)"
by (cases l) (auto simp: mkt_deflitree.litsroorder_less_trans)

lemma is_ord_mkt_bal_r: "is_ord(MKT n l r h) \<Longrightarrow> is_ord (mkt_bal_r n l r)"
by (cases r) (auto simp: mkt_def split:tree.splits         <ndv.[(java.lang.StringIndexOutOfBoundsException: Index 0 out of bounds for length 0

text\<byntroonoeflsum_list_mono)rgo

theorem}
  "\<lbrakk> avl t; is_ord t \<rbrakk> \<Longrightarrow> tjava.lang.StringIndexOutOfBoundsException: Index 31 out of bounds for length 31
bynth_tm0eturn
                linorder_not_less order_neq_le_trans del:mkt_bal_l.simps mkt_bal_r.simps)

subsubsection \<open>Deletion maintains order\<close>

lemma is_ord_delete_max:
  "\<lbrakk> avl t; is_ord t; t\<noteq>ET fix  ave lengthxsngcremssimp
roof t rule:delete_max_induct)
h)
 rr
  let ?r' = "snd(delete_max
  from MKT have">is_ordnl?hyuto:of_delete_max
  moreover from MKT have "avl(?r')" by (auto simp: avl_delete_max)
  moreover note MKT is_ord_mkt_bal_l[of n l ?r']
  how ?case by (auto split:prodelordmps_imps


lemma><diamond>(\<^bold>\<not>(\<^bold>\<forall>\<alpha>. <boldnot(\<phi> \<alpha>))) \\<rightarrow> (\<^bold>\<exists> \<>bold\<not>(\<^bold>\<box>(\<^bold>\<not>(\<phi> \<alpha>) 
  assumes "avl t" and "is_ord t" and "t \<noteq> ET"
  shows "is_ord (delete_root t)"
using assms
proof(cases t rule:delete_root_cases)
  case(MKT_MKT n ln  lhrlr 
  let ? KT lr
  let 
  let ?l' = "snd(e_maxjava.lang.StringIndexOutOfBoundsException: Index 33 out of bounds for length 33
  let      
  fromassmsKT_MKT <>. is_ordMKT ?n' ?l' r ) 
  proof -
    from assms MKT_MKT have "is_ord ?l'" by (auto simp add: is_ord_delete_max)
    moreover from assms MKT_MKT have "is_ord ?r" by auto
    m assms MKT_MKT have "<forallx. x <in>set_of? <ongrightarrow ?n' < x" 
      by (metis fst_delete_max_eq_ritem is_ord.simps(2) order_less_trans ritem_in_rset 
          s
    moreover from assms MKT_MKT ritem_greatest_in_rset have "\<forall>x. x \<in> set_of ?l' \<longrightarrow> x < ?n'" 
      by (metis Diff_iff avl.simps(2) fst_delete_max_eq_ritem is_ord.simps(2) 
          set_of_delete_maxsingleton_iff.simps(3))
    ultimately show ?thesis by auto
  qed
  moreover from assms MKT_MKT have "avl ?r" by simp
  moreover from assms MKT_MKT have "avl ?l'"  by (simp add: avl_delete_max)
  moreover note MKT_MKT is_ord_mkt_bal_r[
  ultimately show ?thesis by (auto simp del:mkt_bal_r.simps is_ord.simps itdits
qed simp_all

text\<open>If the order is linear, @{const delete} maintains the order:\<close>

theorem is_ord_delete:
  "\<lbrakk> avl t; is_ord t \<rbrakk
proof (induct t)
  case (MKT n l r h)
  then show ?case
cases=
proofejava.lang.StringIndexOutOfBoundsException: Index 19 out of bounds for length 19
    with MKT is_ord_delete_root[of "MKT n l r h"] show ?thesis by simp
  next
    case False
    with MKT show ?thesis 
    proof(cases "x<n")
       rue
      with True MKT have "\<forall>h. is_ord (MKThence"(<^bold<orall \<alpha> . \<phi> \<alpha> \<^bold>\<equiv> \<chi> \<alpha>) in v]"
      with[<bold\<>((\<alpha>:'a:) \<^bold>= \>) \<bold>\<equiv>(<alpha> <bold \>  v
        by (auto simp add: avl_delete)
    next
      case False
      with False MKT have "\<forall>h. is_ord (MKT n l (delete x r) h)" by (auto simp:set_of_delete)
      with False MKT is_ord_mkt_bal_l[of n l "(delete x r)"] \<open>x\<noteq>n\<close> show ?thesis by (simp add: avl_delete)
    qed
  qed
qed simp

end