section "AVL Tree Implementation of Sets"
theory AVL_Set
imports
Cmp
Isin2
"HOL-Number_Theory.Fib"
begin
type_synonym 'a avl_tree = "('a,nat) tree"
definition empty :: "'a avl_tree" where
"empty = Leaf"
text ‹Invariant:›
fun avl :: "'a avl_tree ⇒ bool" where
"avl Leaf = True" |
"avl (Node l a h r) =
((height l = height r ∨ height l = height r + 1 ∨ height r = height l + 1) ∧
h = max (height l) (height r) + 1 ∧ avl l ∧ avl r)"
fun ht :: "'a avl_tree ⇒ nat" where
"ht Leaf = 0" |
"ht (Node l a h r) = h"
definition node :: "'a avl_tree ⇒ 'a ⇒ 'a avl_tree ⇒ 'a avl_tree" where
"node l a r = Node l a (max (ht l) (ht r) + 1) r"
definition balL :: "'a avl_tree ⇒ 'a ⇒ 'a avl_tree ⇒ 'a avl_tree" where
"balL l a r =
(if ht l = ht r + 2 then
case l of
Node bl b _ br ⇒
if ht bl < ht br then
case br of
Node cl c _ cr ⇒ node (node bl b cl) c (node cr a r)
else node bl b (node br a r)
else node l a r)"
definition balR :: "'a avl_tree ⇒ 'a ⇒ 'a avl_tree ⇒ 'a avl_tree" where
"balR l a r =
(if ht r = ht l + 2 then
case r of
Node bl b _ br ⇒
if ht bl > ht br then
case bl of
Node cl c _ cr ⇒ node (node l a cl) c (node cr b br)
else node (node l a bl) b br
else node l a r)"
fun insert :: "'a::linorder ⇒ 'a avl_tree ⇒ 'a avl_tree" where
"insert x Leaf = Node Leaf x 1 Leaf" |
"insert x (Node l a h r) = (case cmp x a of
EQ ⇒ Node l a h r |
LT ⇒ balL (insert x l) a r |
GT ⇒ balR l a (insert x r))"
fun split_max :: "'a avl_tree ⇒ 'a avl_tree * 'a" where
"split_max (Node l a _ r) =
(if r = Leaf then (l,a) else let (r',a') = split_max r in (balL l a r', a'))"
lemmas split_max_induct = split_max.induct[case_names Node Leaf]
fun del_root :: "'a avl_tree ⇒ 'a avl_tree" where
"del_root (Node Leaf a h r) = r" |
"del_root (Node l a h Leaf) = l" |
"del_root (Node l a h r) = (let (l', a') = split_max l in balR l' a' r)"
lemmas del_root_cases = del_root.cases[case_names Leaf_t Node_Leaf Node_Node]
fun delete :: "'a::linorder ⇒ 'a avl_tree ⇒ 'a avl_tree" where
"delete _ Leaf = Leaf" |
"delete x (Node l a h r) =
(case cmp x a of
EQ ⇒ del_root (Node l a h r) |
LT ⇒ balR (delete x l) a r |
GT ⇒ balL l a (delete x r))"
subsection ‹Functional Correctness Proofs›
text‹Very different from the AFP/AVL proofs›
subsubsection "Proofs for insert"
lemma inorder_balL:
"inorder (balL l a r) = inorder l @ a # inorder r"
by (auto simp: node_def balL_def split:tree.splits)
lemma inorder_balR:
"inorder (balR l a r) = inorder l @ a # inorder r"
by (auto simp: node_def balR_def split:tree.splits)
theorem inorder_insert:
"sorted(inorder t) ⟹ inorder(insert x t) = ins_list x (inorder t)"
by (induct t)
(auto simp: ins_list_simps inorder_balL inorder_balR)
subsubsection "Proofs for delete"
lemma inorder_split_maxD:
"⟦ split_max t = (t',a); t ≠ Leaf ⟧ ⟹
inorder t' @ [a] = inorder t"
by(induction t arbitrary: t' rule: split_max.induct)
(auto simp: inorder_balL split: if_splits prod.splits tree.split)
lemma inorder_del_root:
"inorder (del_root (Node l a h r)) = inorder l @ inorder r"
by(cases "Node l a h r" rule: del_root.cases)
(auto simp: inorder_balL inorder_balR inorder_split_maxD split: if_splits prod.splits)
theorem inorder_delete:
"sorted(inorder t) ⟹ inorder (delete x t) = del_list x (inorder t)"
by(induction t)
(auto simp: del_list_simps inorder_balL inorder_balR
inorder_del_root inorder_split_maxD split: prod.splits)
subsection ‹AVL invariants›
text‹Essentially the AFP/AVL proofs›
subsubsection ‹Insertion maintains AVL balance›
declare Let_def [simp]
lemma [simp]: "avl t ⟹ ht t = height t"
by (induct t) simp_all
lemma height_balL:
"⟦ height l = height r + 2; avl l; avl r ⟧ ⟹
height (balL l a r) = height r + 2 ∨
height (balL l a r) = height r + 3"
by (cases l) (auto simp:node_def balL_def split:tree.split)
lemma height_balR:
"⟦ height r = height l + 2; avl l; avl r ⟧ ⟹
height (balR l a r) = height l + 2 ∨
height (balR l a r) = height l + 3"
by (cases r) (auto simp add:node_def balR_def split:tree.split)
lemma [simp]: "height(node l a r) = max (height l) (height r) + 1"
by (simp add: node_def)
lemma avl_node:
"⟦ avl l; avl r;
height l = height r ∨ height l = height r + 1 ∨ height r = height l + 1
⟧ ⟹ avl(node l a r)"
by (auto simp add:max_def node_def)
lemma height_balL2:
"⟦ avl l; avl r; height l ≠ height r + 2 ⟧ ⟹
height (balL l a r) = (1 + max (height l) (height r))"
by (cases l, cases r) (simp_all add: balL_def)
lemma height_balR2:
"⟦ avl l; avl r; height r ≠ height l + 2 ⟧ ⟹
height (balR l a r) = (1 + max (height l) (height r))"
by (cases l, cases r) (simp_all add: balR_def)
lemma avl_balL:
assumes "avl l" "avl r" and "height l = height r ∨ height l = height r + 1
∨ height r = height l + 1 ∨ height l = height r + 2"
shows "avl(balL l a r)"
proof(cases l)
case Leaf
with assms show ?thesis by (simp add: node_def balL_def)
next
case Node
with assms show ?thesis
proof(cases "height l = height r + 2")
case True
from True Node assms show ?thesis
by (auto simp: balL_def intro!: avl_node split: tree.split) arith+
next
case False
with assms show ?thesis by (simp add: avl_node balL_def)
qed
qed
lemma avl_balR:
assumes "avl l" and "avl r" and "height l = height r ∨ height l = height r + 1
∨ height r = height l + 1 ∨ height r = height l + 2"
shows "avl(balR l a r)"
proof(cases r)
case Leaf
with assms show ?thesis by (simp add: node_def balR_def)
next
case Node
with assms show ?thesis
proof(cases "height r = height l + 2")
case True
from True Node assms show ?thesis
by (auto simp: balR_def intro!: avl_node split: tree.split) arith+
next
case False
with assms show ?thesis by (simp add: balR_def avl_node)
qed
qed
text‹Insertion maintains the AVL property:›
theorem avl_insert:
assumes "avl t"
shows "avl(insert x t)"
"(height (insert x t) = height t ∨ height (insert x t) = height t + 1)"
using assms
proof (induction t)
case (Node l a h r)
case 1
show ?case
proof(cases "x = a")
case True with Node 1 show ?thesis by simp
next
case False
show ?thesis
proof(cases "x<a")
case True with Node 1 show ?thesis by (auto simp add:avl_balL)
next
case False with Node 1 ‹x≠a› show ?thesis by (auto simp add:avl_balR)
qed
qed
case 2
show ?case
proof(cases "x = a")
case True with Node 1 show ?thesis by simp
next
case False
show ?thesis
proof(cases "x<a")
case True
show ?thesis
proof(cases "height (insert x l) = height r + 2")
case False with Node 2 ‹x < a› show ?thesis by (auto simp: height_balL2)
next
case True
hence "(height (balL (insert x l) a r) = height r + 2) ∨
(height (balL (insert x l) a r) = height r + 3)" (is "?A ∨ ?B")
using Node 2 by (intro height_balL) simp_all
thus ?thesis
proof
assume ?A with 2 ‹x < a› show ?thesis by (auto)
next
assume ?B with True 1 Node(2) ‹x < a› show ?thesis by (simp) arith
qed
qed
next
case False
show ?thesis
proof(cases "height (insert x r) = height l + 2")
case False with Node 2 ‹¬x < a› show ?thesis by (auto simp: height_balR2)
next
case True
hence "(height (balR l a (insert x r)) = height l + 2) ∨
(height (balR l a (insert x r)) = height l + 3)" (is "?A ∨ ?B")
using Node 2 by (intro height_balR) simp_all
thus ?thesis
proof
assume ?A with 2 ‹¬x < a› show ?thesis by (auto)
next
assume ?B with True 1 Node(4) ‹¬x < a› show ?thesis by (simp) arith
qed
qed
qed
qed
qed simp_all
subsubsection ‹Deletion maintains AVL balance›
lemma avl_split_max:
assumes "avl x" and "x ≠ Leaf"
shows "avl (fst (split_max x))" "height x = height(fst (split_max x)) ∨
height x = height(fst (split_max x)) + 1"
using assms
proof (induct x rule: split_max_induct)
case (Node l a h r)
case 1
thus ?case using Node
by (auto simp: height_balL height_balL2 avl_balL split:prod.split)
next
case (Node l a h r)
case 2
let ?r' = "fst (split_max r)"
from ‹avl x› Node 2 have "avl l" and "avl r" by simp_all
thus ?case using Node 2 height_balL[of l ?r' a] height_balL2[of l ?r' a]
apply (auto split:prod.splits simp del:avl.simps) by arith+
qed auto
lemma avl_del_root:
assumes "avl t" and "t ≠ Leaf"
shows "avl(del_root t)"
using assms
proof (cases t rule:del_root_cases)
case (Node_Node ll ln lh lr n h rl rn rh rr)
let ?l = "Node ll ln lh lr"
let ?r = "Node rl rn rh rr"
let ?l' = "fst (split_max ?l)"
from ‹avl t› and Node_Node have "avl ?r" by simp
from ‹avl t› and Node_Node have "avl ?l" by simp
hence "avl(?l')" "height ?l = height(?l') ∨
height ?l = height(?l') + 1" by (rule avl_split_max,simp)+
with ‹avl t› Node_Node have "height ?l' = height ?r ∨ height ?l' = height ?r + 1
∨ height ?r = height ?l' + 1 ∨ height ?r = height ?l' + 2" by fastforce
with ‹avl ?l'› ‹avl ?r› have "avl(balR ?l' (snd(split_max ?l)) ?r)"
by (rule avl_balR)
with Node_Node show ?thesis by (auto split:prod.splits)
qed simp_all
lemma height_del_root:
assumes "avl t" and "t ≠ Leaf"
shows "height t = height(del_root t) ∨ height t = height(del_root t) + 1"
using assms
proof (cases t rule: del_root_cases)
case (Node_Node ll ln lh lr n h rl rn rh rr)
let ?l = "Node ll ln lh lr"
let ?r = "Node rl rn rh rr"
let ?l' = "fst (split_max ?l)"
let ?t' = "balR ?l' (snd(split_max ?l)) ?r"
from ‹avl t› and Node_Node have "avl ?r" by simp
from ‹avl t› and Node_Node have "avl ?l" by simp
hence "avl(?l')" by (rule avl_split_max,simp)
have l'_height: "height ?l = height ?l' ∨ height ?l = height ?l' + 1" using ‹avl ?l› by (intro avl_split_max) auto
have t_height: "height t = 1 + max (height ?l) (height ?r)" using ‹avl t› Node_Node by simp
have "height t = height ?t' ∨ height t = height ?t' + 1" using ‹avl t› Node_Node
proof(cases "height ?r = height ?l' + 2")
case False
show ?thesis using l'_height t_height False
by (subst height_balR2[OF ‹avl ?l'› ‹avl ?r› False])+ arith
next
case True
show ?thesis
proof(cases rule: disjE[OF height_balR[OF True ‹avl ?l'› ‹avl ?r›, of "snd (split_max ?l)"]])
case 1 thus ?thesis using l'_height t_height True by arith
next
case 2 thus ?thesis using l'_height t_height True by arith
qed
qed
thus ?thesis using Node_Node by (auto split:prod.splits)
qed simp_all
text‹Deletion maintains the AVL property:›
theorem avl_delete:
assumes "avl t"
shows "avl(delete x t)" and "height t = (height (delete x t)) ∨ height t = height (delete x t) + 1"
using assms
proof (induct t)
case (Node l n h r)
case 1
show ?case
proof(cases "x = n")
case True with Node 1 show ?thesis by (auto simp:avl_del_root)
next
case False
show ?thesis
proof(cases "x<n")
case True with Node 1 show ?thesis by (auto simp add:avl_balR)
next
case False with Node 1 ‹x≠n› show ?thesis by (auto simp add:avl_balL)
qed
qed
case 2
show ?case
proof(cases "x = n")
case True
with 1 have "height (Node l n h r) = height(del_root (Node l n h r))
∨ height (Node l n h r) = height(del_root (Node l n h r)) + 1"
by (subst height_del_root,simp_all)
with True show ?thesis by simp
next
case False
show ?thesis
proof(cases "x<n")
case True
show ?thesis
proof(cases "height r = height (delete x l) + 2")
case False with Node 1 ‹x < n› show ?thesis by(auto simp: balR_def)
next
case True
hence "(height (balR (delete x l) n r) = height (delete x l) + 2) ∨
height (balR (delete x l) n r) = height (delete x l) + 3" (is "?A ∨ ?B")
using Node 2 by (intro height_balR) auto
thus ?thesis
proof
assume ?A with ‹x < n› Node 2 show ?thesis by(auto simp: balR_def)
next
assume ?B with ‹x < n› Node 2 show ?thesis by(auto simp: balR_def)
qed
qed
next
case False
show ?thesis
proof(cases "height l = height (delete x r) + 2")
case False with Node 1 ‹¬x < n› ‹x ≠ n› show ?thesis by(auto simp: balL_def)
next
case True
hence "(height (balL l n (delete x r)) = height (delete x r) + 2) ∨
height (balL l n (delete x r)) = height (delete x r) + 3" (is "?A ∨ ?B")
using Node 2 by (intro height_balL) auto
thus ?thesis
proof
assume ?A with ‹¬x < n› ‹x ≠ n› Node 2 show ?thesis by(auto simp: balL_def)
next
assume ?B with ‹¬x < n› ‹x ≠ n› Node 2 show ?thesis by(auto simp: balL_def)
qed
qed
qed
qed
qed simp_all
subsection "Overall correctness"
interpretation S: Set_by_Ordered
where empty = empty and isin = isin and insert = insert and delete = delete
and inorder = inorder and inv = avl
proof (standard, goal_cases)
case 1 show ?case by (simp add: empty_def)
next
case 2 thus ?case by(simp add: isin_set_inorder)
next
case 3 thus ?case by(simp add: inorder_insert)
next
case 4 thus ?case by(simp add: inorder_delete)
next
case 5 thus ?case by (simp add: empty_def)
next
case 6 thus ?case by (simp add: avl_insert(1))
next
case 7 thus ?case by (simp add: avl_delete(1))
qed
subsection ‹Height-Size Relation›
text ‹Based on theorems by Daniel St\"uwe, Manuel Eberl and Peter Lammich.›
lemma height_invers:
"(height t = 0) = (t = Leaf)"
"avl t ⟹ (height t = Suc h) = (∃ l a r . t = Node l a (Suc h) r)"
by (induction t) auto
text ‹Any AVL tree of height ‹h› has at least ‹fib (h+2)› leaves:›
lemma avl_fib_bound: "avl t ⟹ height t = h ⟹ fib (h+2) ≤ size1 t"
proof (induction h arbitrary: t rule: fib.induct)
case 1 thus ?case by (simp add: height_invers)
next
case 2 thus ?case by (cases t) (auto simp: height_invers)
next
case (3 h)
from "3.prems" obtain l a r where
[simp]: "t = Node l a (Suc(Suc h)) r" "avl l" "avl r"
and C: "
height r = Suc h ∧ height l = Suc h
∨ height r = Suc h ∧ height l = h
∨ height r = h ∧ height l = Suc h" (is "?C1 ∨ ?C2 ∨ ?C3")
by (cases t) (simp, fastforce)
{
assume ?C1
with "3.IH"(1)
have "fib (h + 3) ≤ size1 l" "fib (h + 3) ≤ size1 r"
by (simp_all add: eval_nat_numeral)
hence ?case by (auto simp: eval_nat_numeral)
} moreover {
assume ?C2
hence ?case using "3.IH"(1)[of r] "3.IH"(2)[of l] by auto
} moreover {
assume ?C3
hence ?case using "3.IH"(1)[of l] "3.IH"(2)[of r] by auto
} ultimately show ?case using C by blast
qed
lemma fib_alt_induct [consumes 1, case_names 1 2 rec]:
assumes "n > 0" "P 1" "P 2" "⋀n. n > 0 ⟹ P n ⟹ P (Suc n) ⟹ P (Suc (Suc n))"
shows "P n"
using assms(1)
proof (induction n rule: fib.induct)
case (3 n)
thus ?case using assms by (cases n) (auto simp: eval_nat_numeral)
qed (insert assms, auto)
text ‹An exponential lower bound for \<^const>‹fib›:›
lemma fib_lowerbound:
defines "φ ≡ (1 + sqrt 5) / 2"
defines "c ≡ 1 / φ ^ 2"
assumes "n > 0"
shows "real (fib n) ≥ c * φ ^ n"
proof -
have "φ > 1" by (simp add: φ_def)
hence "c > 0" by (simp add: c_def)
from ‹n > 0› show ?thesis
proof (induction n rule: fib_alt_induct)
case (rec n)
have "c * φ ^ Suc (Suc n) = φ ^ 2 * (c * φ ^ n)"
by (simp add: field_simps power2_eq_square)
also have "… ≤ (φ + 1) * (c * φ ^ n)"
by (rule mult_right_mono) (insert ‹c > 0›, simp_all add: φ_def power2_eq_square field_simps)
also have "… = c * φ ^ Suc n + c * φ ^ n"
by (simp add: field_simps)
also have "… ≤ real (fib (Suc n)) + real (fib n)"
by (intro add_mono rec.IH)
finally show ?case by simp
qed (insert ‹φ > 1›, simp_all add: c_def power2_eq_square eval_nat_numeral)
qed
text ‹The size of an AVL tree is (at least) exponential in its height:›
lemma avl_size_lowerbound:
defines "φ ≡ (1 + sqrt 5) / 2"
assumes "avl t"
shows "φ ^ (height t) ≤ size1 t"
proof -
have "φ > 0" by(simp add: φ_def add_pos_nonneg)
hence "φ ^ height t = (1 / φ ^ 2) * φ ^ (height t + 2)"
by(simp add: field_simps power2_eq_square)
also have "… ≤ fib (height t + 2)"
using fib_lowerbound[of "height t + 2"] by(simp add: φ_def)
also have "… ≤ size1 t"
using avl_fib_bound[of t "height t"] assms by simp
finally show ?thesis .
qed
text ‹The height of an AVL tree is most \<^term>‹(1/log 2 φ)› ‹≈ 1.44› times worse
than \<^term>‹log 2 (size1 t)›:›
lemma avl_height_upperbound:
defines "φ ≡ (1 + sqrt 5) / 2"
assumes "avl t"
shows "height t ≤ (1/log 2 φ) * log 2 (size1 t)"
proof -
have "φ > 0" "φ > 1" by(auto simp: φ_def pos_add_strict)
hence "height t = log φ (φ ^ height t)" by(simp add: log_nat_power)
also have "… ≤ log φ (size1 t)"
using avl_size_lowerbound[OF assms(2), folded φ_def] ‹1 < φ› by simp
also have "… = (1/log 2 φ) * log 2 (size1 t)"
by(simp add: log_base_change[of 2 φ])
finally show ?thesis .
qed
end