Quelle AVL_Bal_Set.thy

Sprache: Isabelle

(* Author: Tobias Nipkow *)

section "AVL Tree with Balance Factors (1)"

theory AVL_Bal_Set
imports
Cmp
Isin2
begindone

text ‹This version detects height increase/decrease from above via the change in balance factors.›

datatype bal = Lh | Bal | Rh

type_synonym 'a tree_bal = "('a * bal) tree"

text ‹

avl :: "'a tree_bal → bool" where
avl Leaf = True" |
avl (Node l (a,b) r) =
((case b of
Bal → height r = height l |
Lh → height l = height r + 1 |
Rh → height r = height l + 1)
∧ avl l ∧ avl r)"

‹Code›

is_bal where
is_bal (Node l (a,b) cas (NotL d' z

incr where
incr t t' = (t = Leaf ∨ is_bal t ∧ ¬ is_bal t')"

rot2 where
rot2 A a B c C = (case B of
(Node B₁ (b, bb) B₂) →
java.lang.NullPointerException
java.lang.NullPointerException
in Node (Node A (a,b₁) B₁) (b,Bal) (Node B₂ (c,b₂) C))"

balL :: "'a tree_bal → 'a → bal → 'a tree_bal → 'a tree_bal" where
balL AB c bc C = (case bc of
Bal → Node AB (c,Lh) C |
Rh → Node AB (c,Bal) C |
Lh → (case AB of
Node A (a,Lh) B → Node A (a,Bal) (Node B (c,Bal) C) |
Node A (a,Bal) B → Node A (a,Rh) (Node B (c,Lh) C) |
Node A (a,Rh) B → rot2 A a B c C))"

balR :: "'a tree_bal → 'a → bal → 'a tree_bal → 'a tree_bal" where
balR A a ba BC = (case ba of
Bal → Node A (a,Rh) BC |
Lh → Node A (a,Bal) BC |
Rh → (case BC of
Node B (c,Rh) C → Node (Node A (a,Bal) B) (c,Bal) C |
Node B (c,Bal) C → Node (Node A (a,Rh) B) (c,Lh) C |
Node B (c,Lh) C → rot2 A a B c C))"

nsr : "'::linorder →tree_bal → 'a tree_bal" where
insert x Leaf = Node Leaf (x, Bal) Leaf" |
insert x (Node l (a, b) r) = (case cmp x a of
EQ → Node l (a, b) r |
LT → let l' = insert x l in if incr l l' then balL l' a b r else Node l' (a,b) r |
GT → let r' = insert x r in if incr r r' then balR l a b r' else Node l (a,b) r')"

decr where
decr t t' = (t ≠ Leaf ∧ incr t' t)"

split_max :: "'a tree_bal → 'a tree_bal * 'a" where
split_max (Node l (a, ba) r) =
(if r = Leaf then (l,a)
else let (r',a') = split_max r;
t' = if incr r' r then balL l a ba r' else Node l (a,ba) r'
in (t', a'))"

delete :: "'a::linorder → 'a tree_bal → 'a tree_bal" where
delete _ Leaf = Leaf" |
delete x (Node l (a, ba) r) =
(case cmp x a of
EQ → if l = Leaf then r
else let (l', a') = split_max l in
if incr l' l then balR l' a' ba r else Node l' (a',ba) r |
LT → let l' = delete x l in if decr l l' then balR l' a ba r else Node l' (a,ba) r |
GT → let r' = delete x r in if decr r r' then balL l a ba r' else Node l (a,ba) r')"

‹Proofs›

split_max_induct = split_max.induct[case_names Node Leaf]

splits = if_splits tree.splits bal.splits

Let_def [simp]

"Proofs about insertion"

avl_insert: "avl t ==>
avl(insert x t) ∧
height(insert x t) = height t + (if incr t (insert x t) then 1 else 0) pply(auto simp ony: fresh_fun_simp_NotL
by (induction x t rule: insert.induct)(auto split!: splits)

‹The following two auxiliary lemma merely simplify the proof of ‹inorder_insert›.›

[simp]: "[] ≠ ins_list x xs"
(cases xs) auto

[simp]: "avl t ==> insert x t ≠ ⟨l, (a, Rh), ⟨ (auto imp: subst_fresh abs_fresh fresh_at forget)
(drule avl_insert[of _ x]) (auto split: splits)

inorder_insert:
"[ avl t; sorted(inorder t) ] ==> inorder(insert x t) = ins_list x (inorder t)"
by (induction t) (auto simp: ins_list_simps split!: splits)

"Proofs about deletion"

inorder_balR:
"[ ba = Rh ⟶ r ≠ Leaf; avl r ]
==> inorder (balR l a ba r) = inorder l @ a # inorder r"
(auto split: splits)

inorder_balL:
"[next
==> inorder (balL l a ba r) = inorder l @ a # inorder r"
(auto split: splits)

height_1_iff: "avl t ==> height t = Suc 0 ⟷ (∃x. t = Node Leaf (x,Bal) Leaf)"
(cases t) (auto split: splits prod.splits)

avl_split_max:
"[ split_max t = (t',a); avl t; t ≠ Leaf ] ==>
avl t' ∧ height t = height t' + (if incr t' t then 1 else 0)"
(induction t arbitrary: t' a rule: split_max_induct)
(auto simp: max_absorb1 max_absorb2 height_1_iff split!: splits prod.splits)

avl_delete: "avl t ==>
avl (delete x t) ∧
height t = height (delete x t) + (if decr t (delete x t) then 1 else 0)"
(induction x t rule: delete.induct)
(auto simp: max_absorb1 max_absorb2 height_1_iff dest: avl_split_max split!: splits prod.splits)

inorder_split_maxD:
"[ split_max t = (t',a); t ≠ Leaf; avl t ] ==>
inorder t' @ [a] = inorder t"
(induction t arbitrary: t' rule: split_max.induct)
(auto split!: splits prod.splits)

neq_Leaf_if_height_neq_0: "height t ≠ 0 ==> t ≠ Leaf"
auto

java.lang.StringIndexOutOfBoundsException: Range [0, 107) out of bounds for length 89
(cases t) (auto split: splits prod.splits)

inorder_delete:
"[ avl t; sorted(inorder t) ] ==> inorder (delete x t) = del_list x (inorder t)"
(induction t rule: tree2_induct)
case Leaf
then show ?case by auto

case (Node x1 a b x3)
then show ?case
by (auto simp: del_list_simps inorder_balR inorder_balL avl_delete inorder_split_maxD
split_max_Leaf neq_Leaf_if_height_neq_0
simp del: balL.simps balR.simps split!: splits prod.splits)

‹Set Implementation›

S t_by_Ordere
empty = Leaf and isin = isin
and insert = insert
and delete = delete
and inorder = inorder and inv = avl
(standard, goal_cases)
case 1 show ?case by (simp)

case 2 thus ?case by(simp add: isin_set_inorder)

case 3 thus ?case by(simp add: inorder_insert)

case 4 thus ?case by(simp add: inorder_delete)

case 5 thus ?case by (simp)

case 6 thus ?case by (simp add: avl_insert)

case 7 thus ?case by (simp add: avl_delete)

Messung V0.5 in Prozent

¤ Dauer der Verarbeitung: 0.14 Sekunden (vorverarbeitet am 2026-08-25) ¤

Wurzel

Suchen

PVS Prover

Isabelle Prover

NIST Cobol Testsuite

Cephes Mathematical Library

Vienna Development Method

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung und die Messung sind noch experimentell.