AVL tree: Difference between revisions
Add Emacs Lisp
(Add Emacs Lisp) |
|||
| (34 intermediate revisions by 11 users not shown) | |||
Line 2:
{{wikipedia|AVL tree}}
[[Category:Data Structures]]
<br>
Line 12 ⟶ 11:
;Task:
Implement an AVL tree in the language of choice, and provide at least basic operations.
<br><br>
;Related task
[[Red_black_tree_sort]]
<br><br>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program avltree64.s */
Line 877 ⟶ 879:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|Ada}}==
{{trans|C++}}
<
with Ada.Text_IO, Ada.Finalization, Ada.Unchecked_Deallocation;
Line 1,122 ⟶ 1,124:
Ada.Text_IO.New_Line;
end Main;
</syntaxhighlight>
{{Output}}
<pre>
Line 1,129 ⟶ 1,131:
=={{header|Agda}}==
This implementation uses the type system to enforce the height invariants, though not the BST invariants
<
module Avl where
Line 1,233 ⟶ 1,235:
... | Same T' = avl T'
... | Bigger T' = avl T'
</syntaxhighlight>
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program avltree2.s */
Line 2,001 ⟶ 2,003:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
{{Output}}
<pre>
Line 2,047 ⟶ 2,049:
Ele: 007ED095 G: 00000000 D: 00000000 val 10 h 1 pere 007ED081
</pre>
=={{header|ATS}}==
=== Persistent, non-linear trees ===
{{trans|Scheme}}
See also [[#Fortran|Fortran]].
The following implementation does not have many proofs. I hope it is a good example of how you can do ATS programming without many proofs, and thus have an easier time than programming the same thing in C.
It would be an interesting exercise to write a C interface to the the following, for given key and value types. Unlike with many languages, no large runtime library would be needed.
Insertion, deletion, and search are implemented, of course. Conversion to and from (linked) lists is provided. So also there are functions to create ‘generator’ closures, which traverse the tree one node at a time. (ATS does not have call-with-current-continuation, so the generators are implemented quite differently from how I implemented similar generators in Scheme.)
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
#define ATS_DYNLOADFLAG 0
#include "share/atspre_staload.hats"
(*------------------------------------------------------------------*)
(*
Persistent AVL trees.
References:
* Niklaus Wirth, 1976. Algorithms + Data Structures =
Programs. Prentice-Hall, Englewood Cliffs, New Jersey.
* Niklaus Wirth, 2004. Algorithms and Data Structures. Updated
by Fyodor Tkachov, 2014.
(Note: Wirth’s implementations, which are in Pascal and Oberon, are
for non-persistent trees.)
*)
(*------------------------------------------------------------------*)
(*
For now, a very simple interface, without much provided in the way
of proofs.
You could put all this interface stuff into a .sats file. (You would
have to remove the word ‘extern’ from the definitions.)
You might also make avl_t abstract, and put these details in the
.dats file; you would use ‘assume’ to identify the abstract type
with an implemented type. That approach would require some name
changes, and also would make pattern matching on the trees
impossible outside their implementation. Having users do pattern
matching on the AVL trees probably is a terrible idea, anyway.
*)
datatype bal_t =
| bal_minus1
| bal_zero
| bal_plus1
datatype avl_t (key_t : t@ype+,
data_t : t@ype+,
size : int) =
| avl_t_nil (key_t, data_t, 0)
| {size_L, size_R : nat}
avl_t_cons (key_t, data_t, size_L + size_R + 1) of
(key_t, data_t, bal_t,
avl_t (key_t, data_t, size_L),
avl_t (key_t, data_t, size_R))
typedef avl_t (key_t : t@ype+,
data_t : t@ype+) =
[size : int] avl_t (key_t, data_t, size)
extern prfun
lemma_avl_t_param :
{key_t, data_t : t@ype}
{size : int}
avl_t (key_t, data_t, size) -<prf> [0 <= size] void
(* Implement this template, for whichever type of key you are
using. It should return a negative number if u < v, zero if
u = v, or a positive number if u > v. *)
extern fun {key_t : t@ype}
avl_t$compare (u : key_t, v : key_t) :<> int
(* Is the AVL tree empty? *)
extern fun
avl_t_is_empty
{key_t : t@ype}
{data_t : t@ype}
{size : int}
(avl : avl_t (key_t, data_t, size)) :<>
[b : bool | b == (size == 0)]
bool b
(* Does the AVL tree contain at least one association? *)
extern fun
avl_t_isnot_empty
{key_t : t@ype}
{data_t : t@ype}
{size : int}
(avl : avl_t (key_t, data_t, size)) :<>
[b : bool | b == (size <> 0)]
bool b
(* How many associations are stored in the AVL tree? (Currently we
have no way to do an avl_t_size that preserves the ‘size’ static
value. This is the best we can do.) *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_size {size : int}
(avl : avl_t (key_t, data_t, size)) :<>
[sz : int | (size == 0 && sz == 0) || (0 < size && 0 < sz)]
size_t sz
(* Does the AVL tree contain the given key? *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_has_key
{size : int}
(avl : avl_t (key_t, data_t, size),
key : key_t) :<>
bool
(* Search for a key. If the key is found, return the data value
associated with it. Otherwise return the value of ‘dflt’. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_search_dflt
{size : int}
(avl : avl_t (key_t, data_t, size),
key : key_t,
dflt : data_t) :<>
data_t
(* Search for a key. If the key is found, return
‘Some(data)’. Otherwise return ‘None()’. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_search_opt
{size : int}
(avl : avl_t (key_t, data_t, size),
key : key_t) :<>
Option (data_t)
(* Search for a key. If the key is found, set ‘found’ to true, and set
‘data’. Otherwise set ‘found’ to false. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_search_ref
{size : int}
(avl : avl_t (key_t, data_t, size),
key : key_t,
data : &data_t? >> opt (data_t, found),
found : &bool? >> bool found) :<!wrt>
#[found : bool]
void
(* Overload avl_t_search; these functions are easy for the compiler to
distinguish. *)
overload avl_t_search with avl_t_search_dflt
overload avl_t_search with avl_t_search_opt
overload avl_t_search with avl_t_search_ref
(* If a key is not present in the AVL tree, insert the key-data
association; return the new AVL tree. If the key *is* present in
the AVL tree, then *replace* the key-data association; return the
new AVL tree. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_insert
{size : int}
(avl : avl_t (key_t, data_t, size),
key : key_t,
data : data_t) :<>
[sz : pos]
avl_t (key_t, data_t, sz)
(* If a key is not present in the AVL tree, insert the key-data
association; return the new AVL tree and ‘true’. If the key *is*
present in the AVL tree, then *replace* the key-data association;
return the new AVL tree and ‘false’. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_insert_or_replace
{size : int}
(avl : avl_t (key_t, data_t, size),
key : key_t,
data : data_t) :<>
[sz : pos]
(avl_t (key_t, data_t, sz), bool)
(* If a key is present in the AVL tree, delete the key-data
association; otherwise return the tree as it came. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_delete
{size : int}
(avl : avl_t (key_t, data_t, size),
key : key_t) :<>
[sz : nat]
avl_t (key_t, data_t, sz)
(* If a key is present in the AVL tree, delete the key-data
association; otherwise return the tree as it came. Also, return a
bool to indicate whether or not the key was found; ‘true’ if found,
‘false’ if not. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_delete_if_found
{size : int}
(avl : avl_t (key_t, data_t, size),
key : key_t) :<>
[sz : nat]
(avl_t (key_t, data_t, sz), bool)
(* Return a sorted list of the association pairs in an AVL
tree. (Currently we have no way to do an avl_t_pairs that preserves
the ‘size’ static value. This is the best we can do.) *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_pairs {size : int}
(avl : avl_t (key_t, data_t, size)) :<>
[sz : int | (size == 0 && sz == 0) || (0 < size && 0 < sz)]
list ((key_t, data_t), sz)
(* Return a sorted list of the keys in an AVL tree. (Currently we have
no way to do an avl_t_keys that preserves the ‘size’ static
value. This is the best we can do.) *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_keys {size : int}
(avl : avl_t (key_t, data_t, size)) :<>
[sz : int | (size == 0 && sz == 0) || (0 < size && 0 < sz)]
list (key_t, sz)
(* Return a list of the data values in an AVL tree, sorted in the
order of their keys. (Currently we have no way to do an avl_t_data
that preserves the ‘size’ static value. This is the best we can
do.) *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_data {size : int}
(avl : avl_t (key_t, data_t, size)) :<>
[sz : int | (size == 0 && sz == 0) || (0 < size && 0 < sz)]
list (data_t, sz)
(* list2avl_t does the reverse of what avl_t_pairs does (although
they are not inverses of each other).
Currently we have no way to do a list2avl_t that preserves the
‘size’ static value. This is the best we can do. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
list2avl_t {size : int}
(lst : list ((key_t, data_t), size)) :<>
[sz : int | (size == 0 && sz == 0) || (0 < size && 0 < sz)]
avl_t (key_t, data_t, sz)
(* Make a closure that returns association pairs in either forwards or
reverse order. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_make_pairs_generator
{size : int}
(avl : avl_t (key_t, data_t, size),
direction : int) :
() -<cloref1> Option @(key_t, data_t)
(* Make a closure that returns keys in either forwards or reverse
order. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_make_keys_generator
{size : int}
(avl : avl_t (key_t, data_t, size),
direction : int) :
() -<cloref1> Option key_t
(* Make a closure that returns data values in forwards or reverse
order of their keys. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_make_data_generator
{size : int}
(avl : avl_t (key_t, data_t, size),
direction : int) :
() -<cloref1> Option data_t
(* Raise an assertion if the AVL condition is not met. This template
is for testing the code. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_check_avl_condition
{size : int}
(avl : avl_t (key_t, data_t, size)) :
void
(* Print an AVL tree to standard output, in some useful and perhaps
even pretty format. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_pretty_print
{size : int}
(avl : avl_t (key_t, data_t, size)) :
void
(* Implement this template for whichever types of keys and data you
wish to pretty print. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
avl_t_pretty_print$key_and_data
(key : key_t,
data : data_t) :
void
(*------------------------------------------------------------------*)
(*
What follows is the implementation. It would go into a .dats
file. Note, however, that the .dats file would have to be staloaded!
(Preferably anonymously.) This is because the implementation
contains template functions.
Notice there are several assertions with ‘$effmask_ntm’ (as opposed
to proofs) that the routines are terminating. One hopes to remedy
that problem (with proofs).
Also there are some ‘$effmask_wrt’, but these effect masks are safe,
because the writing is to our own stack variables.
*)
#define NIL avl_t_nil ()
#define CONS avl_t_cons
#define LNIL list_nil ()
#define :: list_cons
#define F false
#define T true
typedef fixbal_t = bool
primplement
lemma_avl_t_param avl =
case+ avl of
| NIL => ()
| CONS _ => ()
fn {}
minus_neg_bal (bal : bal_t) :<> bal_t =
case+ bal of
| bal_minus1 () => bal_plus1
| _ => bal_zero ()
fn {}
minus_pos_bal (bal : bal_t) :<> bal_t =
case+ bal of
| bal_plus1 () => bal_minus1
| _ => bal_zero ()
fn {}
bal2int (bal : bal_t) :<> int =
case+ bal of
| bal_minus1 () => ~1
| bal_zero () => 0
| bal_plus1 () => 1
implement
avl_t_is_empty avl =
case+ avl of
| NIL => T
| CONS _ => F
implement
avl_t_isnot_empty avl =
~avl_t_is_empty avl
implement {key_t} {data_t}
avl_t_size {siz} avl =
let
fun
traverse {size : int}
(p : avl_t (key_t, data_t, size)) :<!ntm>
[sz : int | (size == 0 && sz == 0) ||
(0 < size && 0 < sz)]
size_t sz =
case+ p of
| NIL => i2sz 0
| CONS (_, _, _, left, right) =>
let
val [sz_L : int] sz_L = traverse left
val [sz_R : int] sz_R = traverse right
prval _ = prop_verify {0 <= sz_L} ()
prval _ = prop_verify {0 <= sz_R} ()
in
succ (sz_L + sz_R)
end
val [sz : int] sz = $effmask_ntm (traverse {siz} avl)
prval _ = prop_verify {(siz == 0 && sz == 0) ||
(0 < siz && 0 < sz)} ()
in
sz
end
implement {key_t} {data_t}
avl_t_has_key (avl, key) =
let
fun
search {size : int}
(p : avl_t (key_t, data_t, size)) :<!ntm>
bool =
case+ p of
| NIL => F
| CONS (k, _, _, left, right) =>
begin
case+ avl_t$compare<key_t> (key, k) of
| cmp when cmp < 0 => search left
| cmp when cmp > 0 => search right
| _ => T
end
in
$effmask_ntm search avl
end
implement {key_t} {data_t}
avl_t_search_dflt (avl, key, dflt) =
let
var data : data_t?
var found : bool?
val _ = $effmask_wrt avl_t_search_ref (avl, key, data, found)
in
if found then
let
prval _ = opt_unsome data
in
data
end
else
let
prval _ = opt_unnone data
in
dflt
end
end
implement {key_t} {data_t}
avl_t_search_opt (avl, key) =
let
var data : data_t?
var found : bool?
val _ = $effmask_wrt avl_t_search_ref (avl, key, data, found)
in
if found then
let
prval _ = opt_unsome data
in
Some {data_t} data
end
else
let
prval _ = opt_unnone data
in
None {data_t} ()
end
end
implement {key_t} {data_t}
avl_t_search_ref (avl, key, data, found) =
let
fun
search (p : avl_t (key_t, data_t),
data : &data_t? >> opt (data_t, found),
found : &bool? >> bool found) :<!wrt,!ntm>
#[found : bool] void =
case+ p of
| NIL =>
{
prval _ = opt_none {data_t} data
val _ = found := F
}
| CONS (k, d, _, left, right) =>
begin
case+ avl_t$compare<key_t> (key, k) of
| cmp when cmp < 0 => search (left, data, found)
| cmp when cmp > 0 => search (right, data, found)
| _ =>
{
val _ = data := d
prval _ = opt_some {data_t} data
val _ = found := T
}
end
in
$effmask_ntm search (avl, data, found)
end
implement {key_t} {data_t}
avl_t_insert (avl, key, data) =
let
val (avl, _) =
avl_t_insert_or_replace<key_t><data_t> (avl, key, data)
in
avl
end
implement {key_t} {data_t}
avl_t_insert_or_replace (avl, key, data) =
let
fun
search {size : nat}
(p : avl_t (key_t, data_t, size),
fixbal : fixbal_t,
found : bool) :<!ntm>
[sz : pos]
(avl_t (key_t, data_t, sz), fixbal_t, bool) =
case+ p of
| NIL =>
(* The key was not found. Insert a new node. The tree will
need rebalancing. *)
(CONS (key, data, bal_zero, NIL, NIL), T, F)
| CONS (k, d, bal, left, right) =>
case+ avl_t$compare<key_t> (key, k) of
| cmp when cmp < 0 =>
let
val (p1, fixbal, found) = search (left, fixbal, found)
in
(* If fixbal is T, then a node has been inserted
on the left, and rebalancing may be necessary. *)
case+ (fixbal, bal) of
| (F, _) =>
(* No rebalancing is necessary. *)
(CONS (k, d, bal, p1, right), F, found)
| (T, bal_plus1 ()) =>
(* No rebalancing is necessary. *)
(CONS (k, d, bal_zero (), p1, right), F, found)
| (T, bal_zero ()) =>
(* Rebalancing might still be necessary. *)
(CONS (k, d, bal_minus1 (), p1, right), fixbal, found)
| (T, bal_minus1 ()) =>
(* Rebalancing is necessary. *)
let
val+ CONS (k1, d1, bal1, left1, right1) = p1
in
case+ bal1 of
| bal_minus1 () =>
(* A single LL rotation. *)
let
val q = CONS (k, d, bal_zero (), right1, right)
val q1 = CONS (k1, d1, bal_zero (), left1, q)
in
(q1, F, found)
end
| _ =>
(* A double LR rotation. *)
let
val p2 = right1
val- CONS (k2, d2, bal2, left2, right2) = p2
val q = CONS (k, d, minus_neg_bal bal2,
right2, right)
val q1 = CONS (k1, d1, minus_pos_bal bal2,
left1, left2)
val q2 = CONS (k2, d2, bal_zero (), q1, q)
in
(q2, F, found)
end
end
end
| cmp when cmp > 0 =>
let
val (p1, fixbal, found) = search (right, fixbal, found)
in
(* If fixbal is T, then a node has been inserted
on the right, and rebalancing may be necessary. *)
case+ (fixbal, bal) of
| (F, _) =>
(* No rebalancing is necessary. *)
(CONS (k, d, bal, left, p1), F, found)
| (T, bal_minus1 ()) =>
(* No rebalancing is necessary. *)
(CONS (k, d, bal_zero (), left, p1), F, found)
| (T, bal_zero ()) =>
(* Rebalancing might still be necessary. *)
(CONS (k, d, bal_plus1 (), left, p1), fixbal, found)
| (T, bal_plus1 ()) =>
(* Rebalancing is necessary. *)
let
val+ CONS (k1, d1, bal1, left1, right1) = p1
in
case+ bal1 of
| bal_plus1 () =>
(* A single RR rotation. *)
let
val q = CONS (k, d, bal_zero (), left, left1)
val q1 = CONS (k1, d1, bal_zero (), q, right1)
in
(q1, F, found)
end
| _ =>
(* A double RL rotation. *)
let
val p2 = left1
val- CONS (k2, d2, bal2, left2, right2) = p2
val q = CONS (k, d, minus_pos_bal bal2,
left, left2)
val q1 = CONS (k1, d1, minus_neg_bal bal2,
right2, right1)
val q2 = CONS (k2, d2, bal_zero (), q, q1)
in
(q2, F, found)
end
end
end
| _ =>
(* The key was found; p is an existing node. Replace
it. The tree needs no rebalancing. *)
(CONS (key, data, bal, left, right), F, T)
in
if avl_t_is_empty avl then
(* Start a new tree. *)
(CONS (key, data, bal_zero, NIL, NIL), F)
else
let
prval _ = lemma_avl_t_param avl
val (avl, _, found) = $effmask_ntm search (avl, F, F)
in
(avl, found)
end
end
fn {key_t : t@ype}
{data_t : t@ype}
balance_for_shrunken_left
{size : pos}
(p : avl_t (key_t, data_t, size)) :<>
(* Returns a new avl_t, and a ‘fixbal’ flag. *)
[sz : pos]
(avl_t (key_t, data_t, sz), fixbal_t) =
let
val+ CONS (k, d, bal, left, right) = p
in
case+ bal of
| bal_minus1 () => (CONS (k, d, bal_zero, left, right), T)
| bal_zero () => (CONS (k, d, bal_plus1, left, right), F)
| bal_plus1 () =>
(* Rebalance. *)
let
val p1 = right
val- CONS (k1, d1, bal1, left1, right1) = p1
in
case+ bal1 of
| bal_zero () =>
(* A single RR rotation. *)
let
val q = CONS (k, d, bal_plus1, left, left1)
val q1 = CONS (k1, d1, bal_minus1, q, right1)
in
(q1, F)
end
| bal_plus1 () =>
(* A single RR rotation. *)
let
val q = CONS (k, d, bal_zero, left, left1)
val q1 = CONS (k1, d1, bal_zero, q, right1)
in
(q1, T)
end
| bal_minus1 () =>
(* A double RL rotation. *)
let
val p2 = left1
val- CONS (k2, d2, bal2, left2, right2) = p2
val q = CONS (k, d, minus_pos_bal bal2, left, left2)
val q1 = CONS (k1, d1, minus_neg_bal bal2, right2, right1)
val q2 = CONS (k2, d2, bal_zero, q, q1)
in
(q2, T)
end
end
end
fn {key_t : t@ype}
{data_t : t@ype}
balance_for_shrunken_right
{size : pos}
(p : avl_t (key_t, data_t, size)) :<>
(* Returns a new avl_t, and a ‘fixbal’ flag. *)
[sz : pos]
(avl_t (key_t, data_t, sz), fixbal_t) =
let
val+ CONS (k, d, bal, left, right) = p
in
case+ bal of
| bal_plus1 () => (CONS (k, d, bal_zero, left, right), T)
| bal_zero () => (CONS (k, d, bal_minus1, left, right), F)
| bal_minus1 () =>
(* Rebalance. *)
let
val p1 = left
val- CONS (k1, d1, bal1, left1, right1) = p1
in
case+ bal1 of
| bal_zero () =>
(* A single LL rotation. *)
let
val q = CONS (k, d, bal_minus1, right1, right)
val q1 = CONS (k1, d1, bal_plus1, left1, q)
in
(q1, F)
end
| bal_minus1 () =>
(* A single LL rotation. *)
let
val q = CONS (k, d, bal_zero, right1, right)
val q1 = CONS (k1, d1, bal_zero, left1, q)
in
(q1, T)
end
| bal_plus1 () =>
(* A double LR rotation. *)
let
val p2 = right1
val- CONS (k2, d2, bal2, left2, right2) = p2
val q = CONS (k, d, minus_neg_bal bal2, right2, right)
val q1 = CONS (k1, d1, minus_pos_bal bal2, left1, left2)
val q2 = CONS (k2, d2, bal_zero, q1, q)
in
(q2, T)
end
end
end
implement {key_t} {data_t}
avl_t_delete (avl, key) =
(avl_t_delete_if_found (avl, key)).0
implement {key_t} {data_t}
avl_t_delete_if_found (avl, key) =
let
fn
balance_L__ {size : pos}
(p : avl_t (key_t, data_t, size)) :<>
[sz : pos]
(avl_t (key_t, data_t, sz), fixbal_t) =
balance_for_shrunken_left<key_t><data_t> p
fn
balance_R__ {size : pos}
(p : avl_t (key_t, data_t, size)) :<>
[sz : pos]
(avl_t (key_t, data_t, sz), fixbal_t) =
balance_for_shrunken_right<key_t><data_t> p
fn {}
balance_L {size : pos}
(p : avl_t (key_t, data_t, size),
fixbal : fixbal_t) :<>
[sz : pos]
(avl_t (key_t, data_t, sz), fixbal_t) =
if fixbal then
balance_L__ p
else
(p, F)
fn {}
balance_R {size : pos}
(p : avl_t (key_t, data_t, size),
fixbal : fixbal_t) :<>
[sz : pos]
(avl_t (key_t, data_t, sz), fixbal_t) =
if fixbal then
balance_R__ p
else
(p, F)
fun
del {size : pos}
(r : avl_t (key_t, data_t, size),
fixbal : fixbal_t) :<!ntm>
(* Returns a new avl_t, a new fixbal, and key and data to be
‘moved up the tree’. *)
[sz : nat]
(avl_t (key_t, data_t, sz), fixbal_t, key_t, data_t) =
case+ r of
| CONS (k, d, bal, left, right) =>
begin
case+ right of
| CONS _ =>
let
val (q, fixbalq, kq, dq) = del (right, fixbal)
val q1 = CONS (k, d, bal, left, q)
val (q1bal, fixbal) = balance_R (q1, fixbalq)
in
(q1bal, fixbal, kq, dq)
end
| NIL => (left, T, k, d)
end
fun
search {size : nat}
(p : avl_t (key_t, data_t, size),
fixbal : fixbal_t) :<!ntm>
(* Return three values: a new avl_t, a new fixbal, and
whether the key was found. *)
[sz : nat]
(avl_t (key_t, data_t, sz), fixbal_t, bool) =
case+ p of
| NIL => (p, F, F)
| CONS (k, d, bal, left, right) =>
case+ avl_t$compare<key_t> (key, k) of
| cmp when cmp < 0 =>
(* Recursive search down the left branch. *)
let
val (q, fixbal, found) = search (left, fixbal)
val (q1, fixbal) =
balance_L (CONS (k, d, bal, q, right), fixbal)
in
(q1, fixbal, found)
end
| cmp when cmp > 0 =>
(* Recursive search down the right branch. *)
let
val (q, fixbal, found) = search (right, fixbal)
val (q1, fixbal) =
balance_R (CONS (k, d, bal, left, q), fixbal)
in
(q1, fixbal, found)
end
| _ =>
if avl_t_is_empty right then
(* Delete p, replace it with its left branch, then
rebalance. *)
(left, T, T)
else if avl_t_is_empty left then
(* Delete p, replace it with its right branch, then
rebalance. *)
(right, T, T)
else
(* Delete p, but it has both left and right branches, and
therefore may have complicated branch structure. *)
let
val (q, fixbal, k1, d1) = del (left, fixbal)
val (q1, fixbal) =
balance_L (CONS (k1, d1, bal, q, right), fixbal)
in
(q1, fixbal, T)
end
in
if avl_t_is_empty avl then
(avl, F)
else
let
prval _ = lemma_avl_t_param avl
val (avl1, _, found) = $effmask_ntm search (avl, F)
in
(avl1, found)
end
end
implement {key_t} {data_t}
avl_t_pairs (avl) =
let
fun
traverse {size : pos}
{n : nat}
(p : avl_t (key_t, data_t, size),
lst : list ((key_t, data_t), n)) :<!ntm>
[sz : pos] list ((key_t, data_t), sz) =
(* Reverse in-order traversal, to make an in-order list by
consing. *)
case+ p of
| CONS (k, d, _, left, right) =>
if avl_t_is_empty left then
begin
if avl_t_is_empty right then
(k, d) :: lst
else
(k, d) :: traverse (right, lst)
end
else
begin
if avl_t_is_empty right then
traverse (left, (k, d) :: lst)
else
traverse (left, (k, d) :: traverse (right, lst))
end
in
case+ avl of
| NIL => LNIL
| CONS _ => $effmask_ntm traverse (avl, LNIL)
end
implement {key_t} {data_t}
avl_t_keys (avl) =
let
fun
traverse {size : pos}
{n : nat}
(p : avl_t (key_t, data_t, size),
lst : list (key_t, n)) :<!ntm>
[sz : pos] list (key_t, sz) =
(* Reverse in-order traversal, to make an in-order list by
consing. *)
case+ p of
| CONS (k, _, _, left, right) =>
if avl_t_is_empty left then
begin
if avl_t_is_empty right then
k :: lst
else
k :: traverse (right, lst)
end
else
begin
if avl_t_is_empty right then
traverse (left, k :: lst)
else
traverse (left, k :: traverse (right, lst))
end
in
case+ avl of
| NIL => LNIL
| CONS _ => $effmask_ntm traverse (avl, LNIL)
end
implement {key_t} {data_t}
avl_t_data (avl) =
let
fun
traverse {size : pos}
{n : nat}
(p : avl_t (key_t, data_t, size),
lst : list (data_t, n)) :<!ntm>
[sz : pos] list (data_t, sz) =
(* Reverse in-order traversal, to make an in-order list by
consing. *)
case+ p of
| CONS (_, d, _, left, right) =>
if avl_t_is_empty left then
begin
if avl_t_is_empty right then
d :: lst
else
d :: traverse (right, lst)
end
else
begin
if avl_t_is_empty right then
traverse (left, d :: lst)
else
traverse (left, d :: traverse (right, lst))
end
in
case+ avl of
| NIL => LNIL
| CONS _ => $effmask_ntm traverse (avl, LNIL)
end
implement {key_t} {data_t}
list2avl_t lst =
let
fun
traverse {n : pos}
{size : nat} .<n>.
(lst : list ((key_t, data_t), n),
p : avl_t (key_t, data_t, size)) :<>
[sz : pos] avl_t (key_t, data_t, sz) =
case+ lst of
| (k, d) :: LNIL => avl_t_insert<key_t><data_t> (p, k, d)
| (k, d) :: (_ :: _) =>
let
val+ _ :: tail = lst
in
traverse (tail, avl_t_insert<key_t><data_t> (p, k, d))
end
in
case+ lst of
| LNIL => NIL
| (_ :: _) => traverse (lst, NIL)
end
fun {key_t : t@ype}
{data_t : t@ype}
push_all_the_way_left (stack : List (avl_t (key_t, data_t)),
p : avl_t (key_t, data_t)) :
List0 (avl_t (key_t, data_t)) =
let
prval _ = lemma_list_param stack
in
case+ p of
| NIL => stack
| CONS (_, _, _, left, _) =>
push_all_the_way_left (p :: stack, left)
end
fun {key_t : t@ype}
{data_t : t@ype}
push_all_the_way_right (stack : List (avl_t (key_t, data_t)),
p : avl_t (key_t, data_t)) :
List0 (avl_t (key_t, data_t)) =
let
prval _ = lemma_list_param stack
in
case+ p of
| NIL => stack
| CONS (_, _, _, _, right) =>
push_all_the_way_right (p :: stack, right)
end
fun {key_t : t@ype}
{data_t : t@ype}
push_all_the_way (stack : List (avl_t (key_t, data_t)),
p : avl_t (key_t, data_t),
direction : int) :
List0 (avl_t (key_t, data_t)) =
if direction < 0 then
push_all_the_way_right<key_t><data_t> (stack, p)
else
push_all_the_way_left<key_t><data_t> (stack, p)
fun {key_t : t@ype}
{data_t : t@ype}
update_generator_stack (stack : List (avl_t (key_t, data_t)),
left : avl_t (key_t, data_t),
right : avl_t (key_t, data_t),
direction : int) :
List0 (avl_t (key_t, data_t)) =
let
prval _ = lemma_list_param stack
in
if direction < 0 then
begin
if avl_t_is_empty left then
stack
else
push_all_the_way_right<key_t><data_t> (stack, left)
end
else
begin
if avl_t_is_empty right then
stack
else
push_all_the_way_left<key_t><data_t> (stack, right)
end
end
implement {key_t} {data_t}
avl_t_make_pairs_generator (avl, direction) =
let
typedef avl_t = avl_t (key_t, data_t)
val stack = push_all_the_way (LNIL, avl, direction)
val stack_ref = ref stack
(* Cast stack_ref to its (otherwise untyped) pointer, so it can be
enclosed within ‘generate’. *)
val p_stack_ref = $UNSAFE.castvwtp0{ptr} stack_ref
fun
generate () :<cloref1> Option @(key_t, data_t) =
let
(* Restore the type information for stack_ref. *)
val stack_ref =
$UNSAFE.castvwtp0{ref (List avl_t)} p_stack_ref
var stack : List0 avl_t = !stack_ref
var retval : Option @(key_t, data_t)
in
begin
case+ stack of
| LNIL => retval := None ()
| p :: tail =>
let
val- CONS (k, d, _, left, right) = p
in
retval := Some @(k, d);
stack :=
update_generator_stack<key_t><data_t>
(tail, left, right, direction)
end
end;
!stack_ref := stack;
retval
end
in
generate
end
implement {key_t} {data_t}
avl_t_make_keys_generator (avl, direction) =
let
typedef avl_t = avl_t (key_t, data_t)
val stack = push_all_the_way (LNIL, avl, direction)
val stack_ref = ref stack
(* Cast stack_ref to its (otherwise untyped) pointer, so it can be
enclosed within ‘generate’. *)
val p_stack_ref = $UNSAFE.castvwtp0{ptr} stack_ref
fun
generate () :<cloref1> Option key_t =
let
(* Restore the type information for stack_ref. *)
val stack_ref =
$UNSAFE.castvwtp0{ref (List avl_t)} p_stack_ref
var stack : List0 avl_t = !stack_ref
var retval : Option key_t
in
begin
case+ stack of
| LNIL => retval := None ()
| p :: tail =>
let
val- CONS (k, _, _, left, right) = p
in
retval := Some k;
stack :=
update_generator_stack<key_t><data_t>
(tail, left, right, direction)
end
end;
!stack_ref := stack;
retval
end
in
generate
end
implement {key_t} {data_t}
avl_t_make_data_generator (avl, direction) =
let
typedef avl_t = avl_t (key_t, data_t)
val stack = push_all_the_way (LNIL, avl, direction)
val stack_ref = ref stack
(* Cast stack_ref to its (otherwise untyped) pointer, so it can be
enclosed within ‘generate’. *)
val p_stack_ref = $UNSAFE.castvwtp0{ptr} stack_ref
fun
generate () :<cloref1> Option data_t =
let
(* Restore the type information for stack_ref. *)
val stack_ref =
$UNSAFE.castvwtp0{ref (List avl_t)} p_stack_ref
var stack : List0 avl_t = !stack_ref
var retval : Option data_t
in
begin
case+ stack of
| LNIL => retval := None ()
| p :: tail =>
let
val- CONS (_, d, _, left, right) = p
in
retval := Some d;
stack :=
update_generator_stack<key_t><data_t>
(tail, left, right, direction)
end
end;
!stack_ref := stack;
retval
end
in
generate
end
implement {key_t} {data_t}
avl_t_check_avl_condition (avl) =
(* If any of the assertions here is triggered, there is a bug. *)
let
fun
get_heights (p : avl_t (key_t, data_t)) : (int, int) =
case+ p of
| NIL => (0, 0)
| CONS (k, d, bal, left, right) =>
let
val (height_LL, height_LR) = get_heights left
val (height_RL, height_RR) = get_heights right
in
assertloc (abs (height_LL - height_LR) <= 1);
assertloc (abs (height_RL - height_RR) <= 1);
(height_LL + height_LR, height_RL + height_RR)
end
in
if avl_t_isnot_empty avl then
let
val (height_L, height_R) = get_heights avl
in
assertloc (abs (height_L - height_R) <= 1)
end
end
implement {key_t} {data_t}
avl_t_pretty_print (avl) =
let
fun
pad {depth : nat} .<depth>.
(depth : int depth) : void =
if depth <> 0 then
begin
print! (" ");
pad (pred depth)
end
fun
traverse {size : nat}
{depth : nat}
(p : avl_t (key_t, data_t, size),
depth : int depth) : void =
if avl_t_isnot_empty p then
let
val+ CONS (k, d, bal, left, right) = p
in
traverse (left, succ depth);
pad depth;
avl_t_pretty_print$key_and_data<key_t><data_t> (k, d);
println! ("\t\tdepth = ", depth, " bal = ", bal2int bal);
traverse (right, succ depth)
end
in
if avl_t_isnot_empty avl then
let
val+ CONS (k, d, bal, left, right) = avl
in
traverse (left, 1);
avl_t_pretty_print$key_and_data<key_t><data_t> (k, d);
println! ("\t\tdepth = 0 bal = ", bal2int bal);
traverse (right, 1)
end
end
(*------------------------------------------------------------------*)
(*
Here is a little demonstration program.
Assuming you are using Boehm GC, compile this source file with
patscc -O2 -DATS_MEMALLOC_GCBDW avl_trees-postiats.dats -lgc
and run it with
./a.out
*)
%{^
#include <time.h>
ATSinline() atstype_uint64
get_the_time (void)
{
return (atstype_uint64) time (NULL);
}
%}
(* An implementation of avl_t$compare for keys of type ‘int’. *)
implement
avl_t$compare<int> (u, v) =
if u < v then
~1
else if u > v then
1
else
0
(* An implementation of avl_t_pretty_print$key_and_data for keys of
type ‘int’ and values of type ‘double’. *)
implement
avl_t_pretty_print$key_and_data<int><double> (key, data) =
print! ("(", key, ", ", data, ")")
implement
main0 () =
let
(* A linear congruential random number generator attributed
to Donald Knuth. *)
fn
next_random (seed : &uint64) : uint64 =
let
val a : uint64 = $UNSAFE.cast 6364136223846793005ULL
val c : uint64 = $UNSAFE.cast 1442695040888963407ULL
val retval = seed
in
seed := (a * seed) + c;
retval
end
fn {t : t@ype}
fisher_yates_shuffle
{n : nat}
(a : &(@[t][n]),
n : size_t n,
seed : &uint64) : void =
let
var i : [i : nat | i <= n] size_t i
in
for (i := i2sz 0; i < n; i := succ i)
let
val randnum = $UNSAFE.cast{Size_t} (next_random seed)
val j = randnum mod n (* This is good enough for us. *)
val xi = a[i]
val xj = a[j]
in
a[i] := xj;
a[j] := xi
end
end
var seed : uint64 = $extfcall (uint64, "get_the_time")
#define N 20
var keys : @[int][N] = @[int][N] (0)
var a : avl_t (int, double)
var a_saved : avl_t (int, double)
var a1 : (avl_t (int, double), bool)
var i : [i : nat] int i
val dflt = ~99999999.0
val not_dflt = 123456789.0
in
println! ("----------------------------------------------------");
print! ("\n");
(* Initialize a shuffled array of keys. *)
for (i := 0; i < N; i := succ i)
keys[i] := succ i;
fisher_yates_shuffle<int> {N} (keys, i2sz N, seed);
print! ("The keys\n ");
for (i := 0; i < N; i := succ i)
print! (" ", keys[i]);
print! ("\n");
print! ("\nRunning some tests... ");
(* Insert key-data pairs in the shuffled order, checking aspects
of the implementation while doing so. *)
a := avl_t_nil ();
for (i := 0; i < N; i := succ i)
let
var j : [j : nat] int j
in
a := avl_t_insert<int> (a, keys[i], g0i2f keys[i]);
avl_t_check_avl_condition (a);
assertloc (avl_t_size a = succ i);
assertloc (avl_t_is_empty a = iseqz (avl_t_size a));
assertloc (avl_t_isnot_empty a = isneqz (avl_t_size a));
a := avl_t_insert<int> (a, keys[i], not_dflt);
avl_t_check_avl_condition (a);
assertloc (avl_t_search<int><double> (a, keys[i], dflt)
= not_dflt);
assertloc (avl_t_size a = succ i);
assertloc (avl_t_is_empty a = iseqz (avl_t_size a));
assertloc (avl_t_isnot_empty a = isneqz (avl_t_size a));
a := avl_t_insert<int> (a, keys[i], g0i2f keys[i]);
avl_t_check_avl_condition (a);
assertloc (avl_t_size a = succ i);
assertloc (avl_t_is_empty a = iseqz (avl_t_size a));
assertloc (avl_t_isnot_empty a = isneqz (avl_t_size a));
for (j := 0; j < N; j := succ j)
let
val k = keys[j]
val has_key = avl_t_has_key<int> (a, k)
val data_opt = avl_t_search<int><double> (a, k)
val data_dflt = avl_t_search<int><double> (a, k, dflt)
in
assertloc (has_key = (j <= i));
assertloc (option_is_some data_opt = (j <= i));
if (j <= i) then
let
val- Some data = data_opt
in
assertloc (data = g0i2f k);
assertloc (data_dflt = g0i2f k);
end
else
let
val- None () = data_opt
in
assertloc (data_dflt = dflt);
end
end
end;
(* Do it again, but using avl_t_insert_or_replace and checking its
second return value. *)
a1 := (avl_t_nil (), false);
for (i := 0; i < N; i := succ i)
let
var j : [j : nat] int j
in
a1 :=
avl_t_insert_or_replace<int> (a1.0, keys[i], g0i2f keys[i]);
avl_t_check_avl_condition (a1.0);
assertloc (~(a1.1));
assertloc (avl_t_size (a1.0) = succ i);
assertloc (avl_t_is_empty a1.0 = iseqz (avl_t_size a1.0));
assertloc (avl_t_isnot_empty a1.0 = isneqz (avl_t_size a1.0));
a1 := avl_t_insert_or_replace<int> (a1.0, keys[i], not_dflt);
avl_t_check_avl_condition (a1.0);
assertloc (avl_t_search<int><double> (a1.0, keys[i], dflt)
= not_dflt);
assertloc (avl_t_size (a1.0) = succ i);
assertloc (avl_t_is_empty a1.0 = iseqz (avl_t_size a1.0));
assertloc (avl_t_isnot_empty a1.0 = isneqz (avl_t_size a1.0));
a1 :=
avl_t_insert_or_replace<int> (a1.0, keys[i], g0i2f keys[i]);
avl_t_check_avl_condition (a1.0);
assertloc (a1.1);
assertloc (avl_t_size (a1.0) = succ i);
assertloc (avl_t_is_empty a1.0 = iseqz (avl_t_size a1.0));
assertloc (avl_t_isnot_empty a1.0 = isneqz (avl_t_size a1.0));
for (j := 0; j < N; j := succ j)
let
val k = keys[j]
val has_key = avl_t_has_key<int> (a1.0, k)
val data_opt = avl_t_search<int><double> (a1.0, k)
val data_dflt = avl_t_search<int><double> (a1.0, k, dflt)
in
assertloc (has_key = (j <= i));
assertloc (option_is_some data_opt = (j <= i));
if (j <= i) then
let
val- Some data = data_opt
in
assertloc (data = g0i2f k);
assertloc (data_dflt = g0i2f k);
end
else
let
val- None () = data_opt
in
assertloc (data_dflt = dflt);
end
end
end;
a := a1.0;
(* The trees are PERSISTENT, so SAVE THE CURRENT VALUE! *)
a_saved := a;
(* Reshuffle the keys, and test deletion, using the reshuffled
keys. *)
fisher_yates_shuffle<int> {N} (keys, i2sz N, seed);
for (i := 0; i < N; i := succ i)
let
val ix = keys[i]
var j : [j : nat] int j
in
a := avl_t_delete<int> (a, ix);
avl_t_check_avl_condition (a);
assertloc (avl_t_size a = N - succ i);
assertloc (avl_t_is_empty a = iseqz (avl_t_size a));
assertloc (avl_t_isnot_empty a = isneqz (avl_t_size a));
a := avl_t_delete<int> (a, ix);
avl_t_check_avl_condition (a);
assertloc (avl_t_size a = N - succ i);
assertloc (avl_t_is_empty a = iseqz (avl_t_size a));
assertloc (avl_t_isnot_empty a = isneqz (avl_t_size a));
for (j := 0; j < N; j := succ j)
let
val k = keys[j]
val has_key = avl_t_has_key<int> (a, k)
val data_opt = avl_t_search<int><double> (a, k)
val data_dflt = avl_t_search<int><double> (a, k, dflt)
in
assertloc (has_key = (i < j));
assertloc (option_is_some data_opt = (i < j));
if (i < j) then
let
val- Some data = data_opt
in
assertloc (data = g0i2f k);
assertloc (data_dflt = g0i2f k);
end
else
let
val- None () = data_opt
in
assertloc (data_dflt = dflt);
end
end
end;
(* Get back the PERSISTENT VALUE from before the deletions. *)
a := a_saved;
(* Reshuffle the keys, and test deletion again, this time using
avl_t_delete_if_found. *)
fisher_yates_shuffle<int> {N} (keys, i2sz N, seed);
for (i := 0; i < N; i := succ i)
let
val ix = keys[i]
var j : [j : nat] int j
in
a1 := avl_t_delete_if_found<int> (a, ix);
a := a1.0;
avl_t_check_avl_condition (a);
assertloc (a1.1);
assertloc (avl_t_size a = N - succ i);
assertloc (avl_t_is_empty a = iseqz (avl_t_size a));
assertloc (avl_t_isnot_empty a = isneqz (avl_t_size a));
a1 := avl_t_delete_if_found<int> (a, ix);
a := a1.0;
avl_t_check_avl_condition (a);
assertloc (~(a1.1));
assertloc (avl_t_size a = N - succ i);
assertloc (avl_t_is_empty a = iseqz (avl_t_size a));
assertloc (avl_t_isnot_empty a = isneqz (avl_t_size a));
for (j := 0; j < N; j := succ j)
let
val k = keys[j]
val has_key = avl_t_has_key<int> (a, k)
val data_opt = avl_t_search<int><double> (a, k)
val data_dflt = avl_t_search<int><double> (a, k, dflt)
in
assertloc (has_key = (i < j));
assertloc (option_is_some data_opt = (i < j));
if (i < j) then
let
val- Some data = data_opt
in
assertloc (data = g0i2f k);
assertloc (data_dflt = g0i2f k);
end
else
let
val- None () = data_opt
in
assertloc (data_dflt = dflt);
end
end
end;
print! ("passed\n");
(* Get back the PERSISTENT VALUE from before the deletions. *)
a := a_saved;
print! ("\n");
println! ("----------------------------------------------------");
print! ("\n");
print! ("*** PRETTY-PRINTING OF THE TREE ***\n\n");
avl_t_pretty_print<int><double> a;
print! ("\n");
println! ("----------------------------------------------------");
print! ("\n");
print! ("*** GENERATORS ***\n\n");
let
val gen = avl_t_make_pairs_generator (a, 1)
var x : Option @(int, double)
in
print! ("Association pairs in order\n ");
for (x := gen (); option_is_some (x); x := gen ())
let
val @(k, d) = option_unsome x
in
print! (" (", k : int, ", ", d : double, ")")
end
end;
print! ("\n\n");
let
val gen = avl_t_make_pairs_generator (a, ~1)
var x : Option @(int, double)
in
print! ("Association pairs in reverse order\n ");
for (x := gen (); option_is_some (x); x := gen ())
let
val @(k, d) = option_unsome x
in
print! (" (", k : int, ", ", d : double, ")")
end
end;
print! ("\n\n");
let
val gen = avl_t_make_keys_generator (a, 1)
var x : Option int
in
print! ("Keys in order\n ");
for (x := gen (); option_is_some (x); x := gen ())
print! (" ", (option_unsome x) : int)
end;
print! ("\n\n");
let
val gen = avl_t_make_keys_generator (a, ~1)
var x : Option int
in
print! ("Keys in reverse order\n ");
for (x := gen (); option_is_some (x); x := gen ())
print! (" ", (option_unsome x) : int)
end;
print! ("\n\n");
let
val gen = avl_t_make_data_generator (a, 1)
var x : Option double
in
print! ("Data values in order of their keys\n ");
for (x := gen (); option_is_some (x); x := gen ())
print! (" ", (option_unsome x) : double)
end;
print! ("\n\n");
let
val gen = avl_t_make_data_generator (a, ~1)
var x : Option double
in
print! ("Data values in reverse order of their keys\n ");
for (x := gen (); option_is_some (x); x := gen ())
print! (" ", (option_unsome x) : double)
end;
print! ("\n");
print! ("\n");
println! ("----------------------------------------------------");
print! ("\n");
print! ("*** AVL TREES TO LISTS ***\n\n");
print! ("Association pairs in order\n ");
print! (avl_t_pairs<int><double> a);
print! ("\n\n");
print! ("Keys in order\n ");
print! (avl_t_keys<int> a);
print! ("\n\n");
print! ("Data values in order of their keys\n ");
print! (avl_t_data<int><double> a);
print! ("\n");
print! ("\n");
println! ("----------------------------------------------------");
print! ("\n");
print! ("*** LISTS TO AVL TREES ***\n\n");
let
val lst = (3, 3.0) :: (1, 1.0) :: (4, 4.0) :: (2, 2.0) :: LNIL
val avl = list2avl_t<int><double> lst
in
print! (lst : List @(int, double));
print! ("\n\n =>\n\n");
avl_t_pretty_print<int><double> avl
end;
print! ("\n");
println! ("----------------------------------------------------")
end
(*------------------------------------------------------------------*)</syntaxhighlight>
{{out}}
The demonstration is randomized, so the following is just a sample output.
(You could compile with ‘-DATS_MEMALLOC_LIBC’ and leave out the ‘-lgc’. Then the heap memory used will simply be recovered only when the program ends.)
<pre>$ patscc -O2 -DATS_MEMALLOC_GCBDW avl_trees-postiats.dats -lgc
----------------------------------------------------
The keys
13 16 3 4 5 12 7 18 17 6 11 10 1 20 15 2 9 14 19 8
Running some tests... passed
----------------------------------------------------
*** PRETTY-PRINTING OF THE TREE ***
(1, 1.000000) depth = 2 bal = 1
(2, 2.000000) depth = 3 bal = 0
(3, 3.000000) depth = 1 bal = 0
(4, 4.000000) depth = 3 bal = 0
(5, 5.000000) depth = 2 bal = 0
(6, 6.000000) depth = 3 bal = 0
(7, 7.000000) depth = 0 bal = 1
(8, 8.000000) depth = 4 bal = 0
(9, 9.000000) depth = 3 bal = 0
(10, 10.000000) depth = 4 bal = 0
(11, 11.000000) depth = 2 bal = -1
(12, 12.000000) depth = 3 bal = 0
(13, 13.000000) depth = 1 bal = 0
(14, 14.000000) depth = 4 bal = 0
(15, 15.000000) depth = 3 bal = 0
(16, 16.000000) depth = 4 bal = 0
(17, 17.000000) depth = 2 bal = 0
(18, 18.000000) depth = 4 bal = 0
(19, 19.000000) depth = 3 bal = 0
(20, 20.000000) depth = 4 bal = 0
----------------------------------------------------
*** GENERATORS ***
Association pairs in order
(1, 1.000000) (2, 2.000000) (3, 3.000000) (4, 4.000000) (5, 5.000000) (6, 6.000000) (7, 7.000000) (8, 8.000000) (9, 9.000000) (10, 10.000000) (11, 11.000000) (12, 12.000000) (13, 13.000000) (14, 14.000000) (15, 15.000000) (16, 16.000000) (17, 17.000000) (18, 18.000000) (19, 19.000000) (20, 20.000000)
Association pairs in reverse order
(20, 20.000000) (19, 19.000000) (18, 18.000000) (17, 17.000000) (16, 16.000000) (15, 15.000000) (14, 14.000000) (13, 13.000000) (12, 12.000000) (11, 11.000000) (10, 10.000000) (9, 9.000000) (8, 8.000000) (7, 7.000000) (6, 6.000000) (5, 5.000000) (4, 4.000000) (3, 3.000000) (2, 2.000000) (1, 1.000000)
Keys in order
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Keys in reverse order
20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
Data values in order of their keys
1.000000 2.000000 3.000000 4.000000 5.000000 6.000000 7.000000 8.000000 9.000000 10.000000 11.000000 12.000000 13.000000 14.000000 15.000000 16.000000 17.000000 18.000000 19.000000 20.000000
Data values in reverse order of their keys
20.000000 19.000000 18.000000 17.000000 16.000000 15.000000 14.000000 13.000000 12.000000 11.000000 10.000000 9.000000 8.000000 7.000000 6.000000 5.000000 4.000000 3.000000 2.000000 1.000000
----------------------------------------------------
*** AVL TREES TO LISTS ***
Association pairs in order
(1, 1.000000), (2, 2.000000), (3, 3.000000), (4, 4.000000), (5, 5.000000), (6, 6.000000), (7, 7.000000), (8, 8.000000), (9, 9.000000), (10, 10.000000), (11, 11.000000), (12, 12.000000), (13, 13.000000), (14, 14.000000), (15, 15.000000), (16, 16.000000), (17, 17.000000), (18, 18.000000), (19, 19.000000), (20, 20.000000)
Keys in order
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Data values in order of their keys
1.000000, 2.000000, 3.000000, 4.000000, 5.000000, 6.000000, 7.000000, 8.000000, 9.000000, 10.000000, 11.000000, 12.000000, 13.000000, 14.000000, 15.000000, 16.000000, 17.000000, 18.000000, 19.000000, 20.000000
----------------------------------------------------
*** LISTS TO AVL TREES ***
(3, 3.000000), (1, 1.000000), (4, 4.000000), (2, 2.000000)
=>
(1, 1.000000) depth = 1 bal = 1
(2, 2.000000) depth = 2 bal = 0
(3, 3.000000) depth = 0 bal = -1
(4, 4.000000) depth = 1 bal = 0
----------------------------------------------------</pre>
=={{header|C}}==
Line 2,058 ⟶ 3,820:
=={{header|C++}}==
{{trans|D}}
<
#include <algorithm>
#include <iostream>
Line 2,314 ⟶ 4,076:
t.printBalance();
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,330 ⟶ 4,092:
=={{header|Common Lisp}}==
Provided is an imperative implementation of an AVL tree with a similar interface and documentation to HASH-TABLE.
<
(:use :cl)
(:export
Line 2,616 ⟶ 4,378:
(let ((tree (make-avl-tree #'<=))
(randoms (loop repeat 1000000 collect (random 100.0))))
(loop for key in randoms do (setf (gettree key tree) key))))</
=={{header|Component Pascal}}==
{{works with|BlackBox Component Builder}}
Two modules are provided - one for implementing and one for using AVL trees
<syntaxhighlight lang="oberon2">
MODULE RosettaAVLTrees;
(* An implementation of persistent AVL Trees *)
TYPE
Order = ABSTRACT RECORD END;
Tree* = POINTER TO Node;
Node* = ABSTRACT RECORD (Order)
left, right: Tree;
height: INTEGER
END; (* Contains the left and right child nodes and the height of the node *)
Out* = ABSTRACT RECORD END; (* Used for output by the `Draw` procedure *)
Void = RECORD (Order) END; (* Used by the `Ordered` procedure *)
(* The following abstract procedures must be implemented by a user of `Node` *)
(* They must be implemented correctly for the AVL tree to work *)
(* Compares one node with another and returns a boolean value based on which is less *)
PROCEDURE (IN n: Order) Less- (IN m: Node): BOOLEAN, NEW, ABSTRACT;
(* Compares one node with another and returns a boolean value based on which is more *)
PROCEDURE (IN n: Order) More- (IN m: Node): BOOLEAN, NEW, ABSTRACT;
(* Creates a new root node *)
PROCEDURE (IN n: Node) Alloc- (): Tree, NEW, ABSTRACT;
(* Returns TRUE if n is in the tree t, FALSE otherwise *)
PROCEDURE (IN n: Node) Lookup* (t: Tree): BOOLEAN, NEW;
BEGIN
IF t = NIL THEN RETURN FALSE END;
IF n.Less(t) THEN RETURN n.Lookup(t.left) END;
IF n.More(t) THEN RETURN n.Lookup(t.right) END;
RETURN TRUE
END Lookup;
(* Returns the height of the AVL tree t *)
PROCEDURE Height (t: Tree): INTEGER;
BEGIN
IF t = NIL THEN RETURN 0 END;
RETURN t.height
END Height;
(* Creates and returns a new Node with the given children *)
PROCEDURE (IN n: Node) New (left, right: Tree): Tree, NEW;
VAR t: Tree;
BEGIN
t := n.Alloc(); (* Create a new root node *)
t.left := left; t.right := right; (* set the children *)
(* set the height of the node based on its children *)
t.height := MAX(Height(left), Height(right)) + 1;
RETURN t
END New;
(* Returns the difference in height between the left and right children of a node *)
PROCEDURE Slope (l, r: Tree): INTEGER;
BEGIN RETURN Height(l) - Height(r) END Slope;
(* Returns an AVL tree if it is right-heavy *)
PROCEDURE (IN n: Node) BalL (l, r: Tree): Tree, NEW;
BEGIN
IF Slope(l, r) = - 2 THEN
IF Slope(r.left, r.right) = 1 THEN
RETURN r.left.New(n.New(l, r.left.left),
r.New(r.left.right, r.right))
END;
RETURN r.New(n.New(l, r.left), r.right)
END;
RETURN n.New(l, r)
END BalL;
(* Returns an AVL tree if it is left-heavy *)
PROCEDURE (IN n: Node) BalR (l, r: Tree): Tree, NEW;
BEGIN
IF Slope(l, r) = 2 THEN
IF Slope(l.left, l.right) = - 1 THEN
RETURN l.right.New(l.New(l.left, l.right.left),
n.New(l.right.right, r))
END;
RETURN l.New(l.left, n.New(l.right, r))
END;
RETURN n.New(l, r)
END BalR;
(* Returns the AVL tree t with the node n *)
PROCEDURE (IN n: Node) Insert* (t: Tree): Tree, NEW;
BEGIN
IF t = NIL THEN RETURN n.New(NIL, NIL) END;
IF n.Less(t) THEN RETURN t.BalR(n.Insert(t.left), t.right) END;
IF n.More(t) THEN RETURN t.BalL(t.left, n.Insert(t.right)) END;
RETURN t
END Insert;
(* Returns the leftmost node of the non-empty tree t *)
PROCEDURE (t: Tree) Head (): Tree, NEW;
BEGIN
IF t.left = NIL THEN RETURN t END;
RETURN t.left.Head()
END Head;
(* Returns the rightmost node of the non-empty tree t *)
PROCEDURE (t: Tree) Last (): Tree, NEW;
BEGIN
IF t.right = NIL THEN RETURN t END;
RETURN t.right.Last()
END Last;
(* Returns the AVL tree t without the leftmost node *)
PROCEDURE (IN t: Node) Tail* (): Tree, NEW;
BEGIN
IF t.left = NIL THEN RETURN t.right END;
RETURN t.BalL(t.left.Tail(), t.right)
END Tail;
(* Returns the AVL tree t without the rightmost node *)
PROCEDURE (IN t: Node) Init* (): Tree, NEW;
BEGIN
IF t.right = NIL THEN RETURN t.left END;
RETURN t.BalR(t.left, t.right.Init())
END Init;
(* Returns the AVL tree t without node n *)
PROCEDURE (IN n: Node) Delete* (t: Tree): Tree, NEW;
BEGIN
IF t = NIL THEN RETURN NIL END;
IF n.Less(t) THEN RETURN t.BalL(n.Delete(t.left), t.right) END;
IF n.More(t) THEN RETURN t.BalR(t.left, n.Delete(t.right)) END;
IF Slope(t.left, t.right) = 1 THEN
RETURN t.left.Last().BalL(t.left.Init(), t.right)
END;
IF t.right = NIL THEN RETURN t.left END;
RETURN t.right.Head().BalR(t.left, t.right.Tail())
END Delete;
(* The following procedures are used for debugging *)
PROCEDURE (IN n: Void) Less- (IN m: Node): BOOLEAN;
BEGIN RETURN TRUE END Less;
PROCEDURE (IN n: Void) More- (IN m: Node): BOOLEAN;
BEGIN RETURN TRUE END More;
(* Returns TRUE if the AVL tree t is ordered, FALSE otherwise *)
PROCEDURE Ordered* (t: Tree): BOOLEAN;
VAR void: Void;
PROCEDURE Bounded (IN lo, hi: Order; t: Tree): BOOLEAN;
BEGIN
IF t = NIL THEN RETURN TRUE END;
RETURN lo.Less(t) & hi.More(t) &
Bounded(lo, t, t.left) & Bounded(t, hi, t.right)
END Bounded;
BEGIN RETURN Bounded(void, void, t) END Ordered;
(* The following abstract procedures must be implemented by a user of `Out` *)
(* Writes a string *)
PROCEDURE (IN o: Out) Str- (s: ARRAY OF CHAR), NEW, ABSTRACT;
(* Writes an integer *)
PROCEDURE (IN o: Out) Int- (i: INTEGER), NEW, ABSTRACT;
(* Writes a new-line *)
PROCEDURE (IN o: Out) Ln-, NEW, ABSTRACT;
(* Writes a node *)
PROCEDURE (IN o: Out) Node- (IN n: Node), NEW, ABSTRACT;
(* Writes a tree (rotated) *)
PROCEDURE (IN o: Out) Draw* (t: Tree), NEW;
PROCEDURE Bars (bars, bar: ARRAY OF CHAR);
BEGIN
IF LEN(bars + bar) # 0 THEN o.Str(bars + "+--") END
END Bars;
PROCEDURE Do (lBar, rBar, bars: ARRAY OF CHAR; t: Tree);
BEGIN
IF t = NIL THEN Bars(bars, lBar); o.Str("|"); o.Ln
ELSIF (t.left = NIL) & (t.right = NIL) THEN
Bars(bars, lBar); o.Node(t); o.Ln
ELSE
Do("| ", " ", bars + rBar, t.right);
o.Str(bars + rBar + "|"); o.Ln;
Bars(bars, lBar); o.Node(t);
IF Slope(t.left, t.right) # 0 THEN
o.Str(" ["); o.Int(Slope(t.left, t.right)); o.Str("]")
END;
o.Ln;
o.Str(bars + lBar + "|"); o.Ln;
Do(" ", "| ", bars + lBar, t.left)
END
END Do;
BEGIN
Do("", "", "", t)
END Draw;
END RosettaAVLTrees.
</syntaxhighlight>
Interface extracted from implementation:
<syntaxhighlight lang="oberon2">
DEFINITION RosettaAVLTrees;
TYPE
Tree = POINTER TO Node;
Node = ABSTRACT RECORD (Order)
(IN n: Node) Alloc- (): Tree, NEW, ABSTRACT;
(IN n: Node) Delete (t: Tree): Tree, NEW;
(IN t: Node) Init (): Tree, NEW;
(IN n: Node) Insert (t: Tree): Tree, NEW;
(IN n: Node) Lookup (t: Tree): BOOLEAN, NEW;
(IN t: Node) Tail (): Tree, NEW
END;
Out = ABSTRACT RECORD
(IN o: Out) Draw (t: Tree), NEW;
(IN o: Out) Int- (i: INTEGER), NEW, ABSTRACT;
(IN o: Out) Ln-, NEW, ABSTRACT;
(IN o: Out) Node- (IN n: Node), NEW, ABSTRACT;
(IN o: Out) Str- (s: ARRAY OF CHAR), NEW, ABSTRACT
END;
PROCEDURE Ordered (t: Tree): BOOLEAN;
END RosettaAVLTrees.
</syntaxhighlight>
Module that uses previous module:
<syntaxhighlight lang="oberon2">
MODULE RosettaAVLTreesUse;
IMPORT Set := RosettaAVLTrees, Log := StdLog;
TYPE
Height = RECORD (Set.Node) height: INTEGER END;
(* Note that Set.Node already contains an integer field `height`. *)
(* It does not cause a duplicate field error as it is hidden from this module *)
Out = RECORD (Set.Out) END; (* Used for output by the `Draw` procedure *)
(* The following three procedures are implemented here for use by Set.Node *)
(* Compares one node with another and returns a boolean value based on which is less *)
PROCEDURE (IN h: Height) Less- (IN n: Set.Node): BOOLEAN;
BEGIN RETURN h.height < n(Height).height END Less;
(* Compares one node with another and returns a boolean value based on which is more *)
PROCEDURE (IN h: Height) More- (IN n: Set.Node): BOOLEAN;
BEGIN RETURN h.height > n(Height).height END More;
(* Creates a new root node *)
PROCEDURE (IN h: Height) Alloc- (): Set.Tree;
VAR r: POINTER TO Height;
BEGIN NEW(r); r.height := h.height; RETURN r END Alloc;
(* The following four procedures are implemented here for use by Set.Out *)
(* Writes a string *)
PROCEDURE (IN o: Out) Str- (s: ARRAY OF CHAR);
BEGIN Log.String(s) END Str;
(* Writes an integer *)
PROCEDURE (IN o: Out) Int- (i: INTEGER);
BEGIN Log.IntForm(i, Log.decimal, 0, ' ', Log.hideBase) END Int;
(* Writes a new-line *)
PROCEDURE (IN o: Out) Ln-; BEGIN Log.Ln END Ln;
(* Writes a node *)
PROCEDURE (IN o: Out) Node- (IN n: Set.Node);
BEGIN
Log.IntForm(n(Height).height, Log.decimal, 0, ' ', Log.hideBase)
END Node;
PROCEDURE Use*;
TYPE BAD = POINTER TO Height;
VAR h: Height; hs, save: Set.Tree; i: INTEGER; o: Out;
BEGIN
h.height := 10; hs := h.Insert(hs);
FOR i := 0 TO 9 DO h.height := i; hs := h.Insert(hs) END;
o.Draw(hs); Log.Ln; Log.Ln;
save := hs;
FOR i := 0 TO 9 DO h.height := i; hs := h.Delete(hs) END;
o.Draw(hs); Log.Ln; Log.Ln;
o.Draw(save); Log.Ln; Log.Ln; (* Tree demonstrates persistence *)
ASSERT(Set.Ordered(save)); (* This ASSERT succeeds *)
save(BAD).height := 11; (* UNSAFE STATEMENT *)
o.Draw(save);
ASSERT(Set.Ordered(save)) (* This ASSERT fails *)
END Use;
END RosettaAVLTreesUse.
</syntaxhighlight>
Execute: ^Q RosettaAVLTreesUse.Use
{{out}}
<pre>
+--10
|
+--9
| |
| +--8
|
+--7
| |
| | +--6
| | |
| +--5
| |
| +--4
|
3 [-1]
|
| +--2
| |
+--1
|
+--0
10
+--10
|
+--9
| |
| +--8
|
+--7
| |
| | +--6
| | |
| +--5
| |
| +--4
|
3 [-1]
|
| +--2
| |
+--1
|
+--0
+--10
|
+--9
| |
| +--8
|
+--7
| |
| | +--6
| | |
| +--5
| |
| +--4
|
11 [-1]
|
| +--2
| |
+--1
|
+--0
</pre>
=={{header|D}}==
{{trans|Java}}
<
class AVLtree {
Line 2,814 ⟶ 4,946:
write("Printing balance: ");
tree.printBalance;
}</
{{out}}
<pre>Inserting values 1 to 10
Printing balance: 0 0 0 1 0 0 0 0 1 0 </pre>
=={{header|Emacs Lisp}}==
{{trans|Java}}
<syntaxhighlight lang="lisp">
(defvar avl-all-nodes (make-vector 100 nil))
(defvar avl-root-node nil "root node")
(defun avl-create-node (key parent)
(copy-tree `((:key . ,key) (:balance . nil) (:height . nil)
(:left . nil) (:right . nil) (:parent . ,parent))))
(defun avl-node (pos)
(if (or (null pos) (> pos (1- (length avl-all-nodes))))
nil
(aref avl-all-nodes pos)))
(defun avl-node-prop (noderef &rest props)
(if (null noderef)
nil
(progn
;;(when (integerp noderef) (setq node (avl-node node)))
(let ((val noderef))
(dolist (prop props)
(if (null (avl-node val))
(setq val nil)
(progn
(setq val (alist-get prop (avl-node val))))))
val)
)
)
)
(defun avl-set-prop (node &rest props-and-value)
(when (integerp node) (setq node (avl-node node)))
(when (< (length props-and-value) 2)
(error "Both property name and value must be given."))
(let (noderef (props (seq-take props-and-value (1- (length props-and-value))))
(value (seq-elt props-and-value (1- (length props-and-value)))))
(when (> (length props) 0)
(dolist (prop (seq-take props (1- (length props))))
(if (null node)
(progn (setq noderef nil) (setq node nil))
(progn
(setq noderef (alist-get prop node))
(setq node (avl-node noderef))))))
(if (or (null (last props)) (null node))
nil
(setcdr (assoc (car (last props)) node) value))))
(defun avl-height (noderef)
(or (avl-node-prop noderef :height) -1))
(defun avl-reheight (noderef)
(if (null noderef)
nil
(avl-set-prop noderef :height
(1+ (max (avl-height (avl-node-prop noderef :left))
(avl-height (avl-node-prop noderef :right)))))))
(defun avl-setbalance (noderef)
;;(when (integerp node) (setq node (avl-node node)))
(avl-reheight noderef)
(avl-set-prop noderef :balance
(- (avl-height (avl-node-prop noderef :right))
(avl-height (avl-node-prop noderef :left)))))
(defun avl-add-node (key parent)
(let (result (idx 0))
(cl-loop for idx from 0 to (1- (seq-length avl-all-nodes))
while (null result) do
(when (null (aref avl-all-nodes idx))
(aset avl-all-nodes idx (avl-create-node key parent))
(setq result idx)))
result))
(defun avl-insert (key)
(if (null avl-root-node)
(progn (setq avl-root-node (avl-add-node key nil)) avl-root-node)
(progn
(let ((n avl-root-node) (end-loop nil) parent go-left result)
(while (not end-loop)
(if (equal key (avl-node-prop n :key))
(setq end-loop 't)
(progn
(setq parent n)
(setq go-left (> (avl-node-prop n :key) key))
(setq n (if go-left
(avl-node-prop n :left)
(avl-node-prop n :right)))
(when (null n)
(setq result (avl-add-node key parent))
(if go-left
(progn
(avl-set-prop parent :left result))
(progn
(avl-set-prop parent :right result)))
(avl-rebalance parent) ;;rebalance
(setq end-loop 't)))))
result))))
(defun avl-rotate-left (noderef)
(when (not (integerp noderef)) (error "parameter must be an integer"))
(let ((a noderef) b)
(setq b (avl-node-prop a :right))
(avl-set-prop b :parent (avl-node-prop a :parent))
(avl-set-prop a :right (avl-node-prop b :left))
(when (avl-node-prop a :right) (avl-set-prop a :right :parent a))
(avl-set-prop b :left a)
(avl-set-prop a :parent b)
(when (not (null (avl-node-prop b :parent)))
(if (equal (avl-node-prop b :parent :right) a)
(avl-set-prop b :parent :right b)
(avl-set-prop b :parent :left b)))
(avl-setbalance a)
(avl-setbalance b)
b))
(defun avl-rotate-right (node-idx)
(when (not (integerp node-idx)) (error "parameter must be an integer"))
(let ((a node-idx) b)
(setq b (avl-node-prop a :left))
(avl-set-prop b :parent (avl-node-prop a :parent))
(avl-set-prop a :left (avl-node-prop b :right))
(when (avl-node-prop a :right) (avl-set-prop a :right :parent a))
(avl-set-prop b :left a)
(avl-set-prop a :parent b)
(when (not (null (avl-node-prop b :parent)))
(if (equal (avl-node-prop b :parent :right) a)
(avl-set-prop b :parent :right b)
(avl-set-prop b :parent :left b)))
(avl-setbalance a)
(avl-setbalance b)
b))
(defun avl-rotate-left-then-right (noderef)
(avl-set-prop noderef :left (avl-rotate-left (avl-node-prop noderef :left)))
(avl-rotate-right noderef))
(defun avl-rotate-right-then-left (noderef)
(avl-set-prop noderef :right (avl-rotate-left (avl-node-prop noderef :right)))
(avl-rotate-left noderef))
(defun avl-rebalance (noderef)
(avl-setbalance noderef)
(cond
((equal -2 (avl-node-prop noderef :balance))
(if (>= (avl-height (avl-node-prop noderef :left :left))
(avl-height (avl-node-prop noderef :left :right)))
(setq noderef (avl-rotate-right noderef))
(setq noderef (avl-rotate-left-then-right noderef)))
)
((equal 2 (avl-node-prop noderef :balance))
(if (>= (avl-height (avl-node-prop noderef :right :right))
(avl-height (avl-node-prop noderef :right :left)))
(setq noderef (avl-rotate-left noderef))
(setq noderef (avl-rotate-right-then-left noderef)))))
(if (not (null (avl-node-prop noderef :parent)))
(avl-rebalance (avl-node-prop noderef :parent))
(setq avl-root-node noderef)))
(defun avl-delete (noderef)
(when noderef
(when (and (null (avl-node-prop noderef :left))
(null (avl-node-prop noderef :right)))
(if (null (avl-node-prop noderef :parent))
(setq avl-root-node nil)
(let ((parent (avl-node-prop noderef :parent)))
(if (equal noderef (avl-node-prop parent :left))
(avl-set-prop parent :left nil)
(avl-set-prop parent :right nil))
(avl-rebalance parent))))
(if (not (null (avl-node-prop noderef :left)))
(let ((child (avl-node-prop noderef :left)))
(while (not (null (avl-node-prop child :right)))
(setq child (avl-node-prop child :right)))
(avl-set-prop noderef :key (avl-node-prop child :key))
(avl-delete child))
(let ((child (avl-node-prop noderef :right)))
(while (not (null (avl-node-prop child :left)))
(setq child (avl-node-prop child :left)))
(avl-set-prop noderef :key (avl-node-prop child :key))
(avl-delete child)))))
;; Main procedure
(let ((cnt 10) balances)
(fillarray avl-all-nodes nil)
(setq avl-root-node nil)
(dotimes (val cnt)
(avl-insert (1+ val)))
(setq balances (seq-map (lambda (x) (or (avl-node-prop x :balance) 0))
(number-sequence 0 (1- cnt))))
(message "Inserting values 1 to %d" cnt)
(message "Printing balance: %s" (string-join (seq-map (lambda (x) (format "%S" x)) balances) " ")))
</syntaxhighlight>
{{out}}
<pre>
Inserting values 1 to 10
Printing balance: 0 0 0 1 0 1 0 0 0 0
</pre>
=={{header|Fortran}}==
{{works with|Fortran|2008}}
{{works with|Fortran|2018}}
See also [[#ATS|ATS]] and [[#Scheme|Scheme]], where ''persistent'' (‘immutable’) versions of this algorithm are implemented.
The following AVL tree implementation is for keys and data of any type, mixed freely. This is made possible by Fortran 2008’s unlimited polymorphism. The demonstration is for '''INTEGER''' keys and mixtures of '''REAL''' and '''CHARACTER''' data.
Supported operations include insertion of a key-data pair, deletion, tree size computed by traversal, output of the full contents as an ordered linked list, printing a representation of the tree, checking that the AVL condition is satisfied. There are actually some slightly more general mechanisms available, in terms of which the foregoing operations are written.
<syntaxhighlight lang="fortran">module avl_trees
!
! References:
Line 3,217 ⟶ 5,577:
end subroutine deletion_search
recursive subroutine del (
type(avl_node_t), pointer, intent(inout) ::
logical, intent(inout) :: fix_balance
if (associated (
call del (
if (fix_balance) call balance_for_shrunken_right (
else
q%key =
q%data =
q =>
fix_balance = .true.
end if
Line 3,253 ⟶ 5,613:
p1 => p%right
select case (p1%bal)
case (0
! A single RR rotation.
p%right => p1%left
p1%left => p
p => p1
fix_balance = .false.
case (1)
! A single RR rotation.
p%right => p1%left
p1%left => p
p%bal = 0
p1%bal = 0
p => p1
fix_balance = .true.
case (-1)
! A double RL rotation.
Line 3,300 ⟶ 5,668:
p1 => p%left
select case (p1%bal)
case (
! A single LL rotation.
p%left => p1%right
p1%right => p
p => p1
fix_balance = .false.
case (-1)
! A single LL rotation.
p%left => p1%right
p1%right => p
p1%bal = 0
p%bal = 0
p => p1
fix_balance = .true.
case (1)
! A double LR rotation.
Line 3,571 ⟶ 5,947:
do i = 1, n - 1
call random_number (randnum)
j = i + floor (randnum * (n - i + 1))
tmp = keys(i)
keys(i) = keys(j)
Line 3,661 ⟶ 6,037:
end subroutine print_contents
end program avl_trees_demo</
{{out}}
Line 3,715 ⟶ 6,091:
<
space system
{
enum state
{
Line 3,786 ⟶ 6,165:
n = y
y = y.parent
if y.is_header
}
return y
Line 3,816 ⟶ 6,195:
n = y
y = y.parent
if y.is_header
}
return y
Line 4,170 ⟶ 6,549:
}
class
{
compare_to(a b)
{
if
}
}
class set
{
header
Line 4,799 ⟶ 6,567:
comparer
{
header =
iterator =
comparer =
}
{
header =
iterator =
comparer =
}
Line 4,816 ⟶ 6,584:
left_most
{
{
}
{
header.left = value
Line 4,828 ⟶ 6,596:
right_most
{
{
}
{
header.right = value
Line 4,840 ⟶ 6,608:
root
{
{
}
{
header.parent = value
Line 4,852 ⟶ 6,620:
empty
{
{
}
}
{
{
root =
left_most = root
right_most = root
}
{
node = root
{
result = comparer.compare_to(data node.data)
{
node = node.left
{
node.left =
node.balance_tree(direction.from_left)
}
}
{
node = node.right
{
node.right =
node.balance_tree(direction.from_right)
}
}
}
}
}
update(data)
{
{
root =
left_most = root
right_most = root
}
{
node = root
{
result = comparer.compare_to(data node.data)
{
node = node.left
{
node.left =
node.balance_tree(direction.from_left)
}
}
{
node = node.right
{
node.right =
node.balance_tree(direction.from_right)
}
}
{
node.data = data
}
}
Line 4,956 ⟶ 6,724:
}
{
node = root
{
{
}
result = comparer.compare_to(data node.data)
node = node.left
node = node.right
{
{
replace = node.left
temp = node.data
node.data = replace.data
Line 4,986 ⟶ 6,754:
from = direction.from_left
{
next = node
next = next.next
{
left_most = header
right_most = header
}
left_most = next
}
{
previous = node
previous = previous.previous
{
left_most = header
right_most = header
}
right_most = previous
}
{
root = node.right
{
node.parent.left = node.right
node.parent.right = node.right
}
node.right.parent = node.parent
}
{
root = node.left
{
node.parent.left = node.left
node.parent.right = node.left
}
node.left.parent = node.parent
}
node.parent.balance_tree_remove(from)
}
}
}
{
node = root
repeat
{
if node.null()
{
throw "entry " + (string)data + " not found"
}
result = comparer.compare_to(data node.data)
if result < 0
node = node.left
else if result > 0
node = node.right
else // item found
{
if !node.left.null() && !node.right.null()
{
replace = node.left
while !replace.right.null() replace = replace.right
temp = node.data
node.data = replace.data
replace.data = temp
node = replace
}
from = direction.from_left
if node != node.parent.left from = direction.from_right
if left_most == node
{
next = node
next = next.next
if header == next
{
left_most = header
right_most = header
}
else
left_most = next
}
if right_most == node
{
previous = node
previous = previous.previous
if header == previous
{
left_most = header
right_most = header
}
else
right_most = previous
}
if node.left.null()
{
if node.parent == header
root = node.right
else
{
if node.parent.left == node
node.parent.left = node.right
else
node.parent.right = node.right
}
if !node.right.null()
node.right.parent = node.parent
}
else
{
if node.parent == header
root = node.left
else
{
if node.parent.left == node
node.parent.left = node.left
else
node.parent.right = node.left
}
if !node.left.null()
node.left.parent = node.parent
}
node.parent.balance_tree_remove(from)
break
}
}
return this
}
remove2(data)
{
node = root
repeat
{
if node.null()
{
return null
}
result = comparer.compare_to(data node.data)
if result < 0
node = node.left
else if result > 0
node = node.right
else // item found
{
if !node.left.null() && !node.right.null()
{
replace = node.left
while !replace.right.null() replace = replace.right
temp = node.data
node.data = replace.data
replace.data = temp
node = replace
}
from = direction.from_left
if node != node.parent.left from = direction.from_right
if left_most == node
{
next = node
next = next.next
if header == next
{
left_most = header
right_most = header
}
else
left_most = next
}
if right_most == node
{
previous = node
previous = previous.previous
if header == previous
{
left_most = header
right_most = header
}
else
right_most = previous
}
if node.left.null()
{
if node.parent == header
root = node.right
else
{
if node.parent.left == node
node.parent.left = node.right
else
node.parent.right = node.right
}
if !node.right.null()
node.right.parent = node.parent
}
else
{
if node.parent == header
root = node.left
else
{
if node.parent.left == node
node.parent.left = node.left
else
node.parent.right = node.left
}
if !node.left.null()
node.left.parent = node.parent
}
node.parent.balance_tree_remove(from)
break
}
}
}
operator[data]
{
{
{
}
{
node = root
{
result = comparer.compare_to(data node.data)
{
node = node.left
}
{
node = node.right
}
}
}
Line 5,091 ⟶ 7,055:
}
{
node = root
{
result = comparer.compare_to(data node.data)
{
node = node.left
}
{
node = node.right
}
}
}
last
{
get
{
if empty
throw "empty set"
else
return header.right.data
}
}
iterate()
{
{
iterator = left_most
}
{
iterator = iterator.next
}
}
{
{
}
}
depth
{
{
}
}
{
}
{
}
{
first1 = begin
Line 5,188 ⟶ 7,153:
last2 = c.end
{
result = comparer.compare_to(first1.data first2.data)
{
first1 = first1.next
first2 = first2.next
}
}
a = count
b = c.count
}
begin {
end {
{
out = "{"
first1 = begin
last1 = end
{
out = out + (string)first1.data
first1 = first1.next
}
out = out + "}"
}
{
r =
first1 = begin
Line 5,231 ⟶ 7,196:
last2 = b.end
{
result = comparer.compare_to(first1.data first2.data)
{
r << first1.data
Line 5,241 ⟶ 7,206:
}
{
r << first2.data
Line 5,247 ⟶ 7,212:
}
{
r << first1.data
Line 5,255 ⟶ 7,220:
}
{
r << first1.data
first1 = first1.next
}
{
r << first2.data
first2 = first2.next
}
}
{
r =
first1 = begin
Line 5,277 ⟶ 7,242:
last2 = b.end
{
result = comparer.compare_to(first1.data first2.data)
{
first1 = first1.next
}
{
first2 = first2.next
}
{
r << first1.data
Line 5,299 ⟶ 7,264:
}
}
{
r =
first1 = begin
Line 5,311 ⟶ 7,276:
last2 = b.end
{
result = comparer.compare_to(first1.data first2.data)
{
r << first1.data
Line 5,321 ⟶ 7,286:
}
{
r << first2.data
Line 5,327 ⟶ 7,292:
}
{
first1 = first1.next
Line 5,334 ⟶ 7,299:
}
{
r << first1.data
first1 = first1.next
}
{
r << first2.data
first2 = first2.next
}
}
{
r =
first1 = begin
Line 5,356 ⟶ 7,321:
last2 = b.end
{
result = comparer.compare_to(first1.data first2.data)
{
r << first1.data
Line 5,366 ⟶ 7,331:
}
{
r << first2.data
Line 5,373 ⟶ 7,338:
}
{
first1 = first1.next
Line 5,380 ⟶ 7,345:
}
{
r << first1.data
first1 = first1.next
}
}
}
class tree
{
s
tree()
{
s = set()
}
operator<<(e)
{
s << e
return this
}
{
get
{
{
if key < node.data
{
node = node.left
else
throw "entry not found exception"
}
else
{
if key == node.data
return node.data
else
{
node = node.
}
}
}
}
}
}
operator>>(e)
{
entry = this[e]
s >> entry
}
s >>
}
iterate()
{
return s.iterate()
}
count
{
get
{
return s.count
}
}
empty
{
get
{
return s.empty
}
}
last
{
get
{
if empty
throw "empty tree"
else
return s.last
}
}
operator string()
{
return (string)s
}
}
class dictionary
{
s
dictionary()
{
s = set()
}
operator<<(key_value)
{
s << key_value
return this
}
add(key value)
{
s << key_value(key value)
}
operator[key]
{
set
{
try { s >> key_value(key) } catch {}
s << key_value(key value)
}
get
{
r = s.get(key_value(key))
return r.value
}
}
operator>>(key)
{
s >> key_value(key)
return this
}
iterate()
{
return s.iterate()
}
count
{
get
{
return s.count
}
}
operator string()
{
return (string)s
}
}
class key_value
{
key
value
key_value(key_set)
{
key = key_set
value = nul
}
key_value(key_set value_set)
{
key = key_set
value = value_set
}
operator<(kv)
{
return key < kv.key
}
operator string()
{
if value.nul()
return "(" + (string)key + " null)"
else
return "(" + (string)key + " " + (string)value + ")"
}
}
class array
{
s // this is a set of key/value pairs.
iterator // this field holds an iterator for the array.
array() // no parameters required phor array construction.
{
s = set() // create a set of key/value pairs.
iterator = null // the iterator is initially set to null.
}
begin { get { return s.header.left } } // property: used to commence manual iteration.
end { get { return s.header } } // property: used to define the end item of iteration.
operator<(a) // less than operator is called by the avl tree algorithms
{ // this operator implies phor instance that you could potentially have sets of arrays.
if keys < a.keys // compare the key sets first.
return true
else if a.keys < keys
return false
else // the key sets are equal therephore compare array elements.
{
first1 = begin
last1 = end
first2 = a.begin
last2 = a.end
while first1 != last1 && first2 != last2
{
if first1.data.value
return true
else
{
if first2.data.value < first1.data.value
return false
else
{
}
}
return false
}
}
operator==(compare) // equals and not equals derive from operator<
{
if this < compare return false
if compare < this return false
return true
}
operator!=(compare)
{
if this < compare return true
if compare < this return true
return false
}
operator<<(e) // this operator adds an element to the end of the array.
{
this[s.last.key + +b] = e
}
catch
{
this[+a] = e
}
return this
}
operator[key] // this is the array indexer.
{
set
{
try { s >> key_value(key) } catch {}
s << key_value(integer(key) value)
}
get
{
result = s.get(key_value(key))
return result.value
}
}
operator>>(key) // this operator removes an element from the array.
{
s >> key_value(key)
return this
}
iterate() // and this is how to iterate on the array.
{
{
iterator = s.left_most
if iterator == s.header
return iterator(false none())
else
return iterator(true iterator.data.value)
}
else
{
iterator = iterator.next
if iterator == s.header
{
iterator = null
return iterator(false none())
}
else
return iterator(true iterator.data.value)
}
}
count // this property returns a count of elements in the array.
{
get
{
return s.count
}
}
empty // is the array empty? (Property of course).
{
get
{
return s.empty
}
}
last // returns the value of the last element in the array.
{
get
{
if empty
throw "empty array"
else
return s.last.value
}
}
📟 string() // converts the array to a string
{
out = "{"
iterator = s.left_most
while iterator != s.header
{
_value = iterator.data.value
out = out + (string)_value
if iterator != s.right_most
out = out + ","
iterator = iterator.next
}
out = out + "}"
return out
}
keys // return the set of keys of the array (a set of integers).
{
get
{
k = set()
for e s k << e.key
return k
}
}
sort // unloads the set into a value and reloads in sorted order.
{
get
{
sort_bag = bag()
for e s sort_bag << e.value
a = new array()
for g sort_bag a << g
return a
}
}
}
// and here is a test program
using system
space sampleB
{
sampleB()
{
{
🎛️ << "Found: " << 🌳["B"] << "\n"
for inst 🌳 🎛️ << inst << "\n"
🎛️ << 🌳 << "\n"
💰 = bag() { 1 1 2 3 } // create a bag
🎛️ << 💰 << "\n"
🪣 = ["D" "C" "B" "A"] // create an array
🎛️ << 🪣 << "\n"
🎛️ << 🪣.sort << "\n"
🪣[4] = "E"
🎛️ << 🪣 << "\n"
📘 = <[0 "hello"] [1 "world"]> // create a dictionary
🎛️ << 📘 << "\n"
📘[2] = "goodbye"
🎛️ << 📘 << "\n"
}
{
🎛️ <<
}
}
}
// The output of the program is shown below.
Found: B
A
B
C
D
E
{A,B,C,D,E}
{1,1,2,3}
{D,C,B,A}
{A,B,C,D}
{D,C,B,A,E}
{(0 hello),(1 world)}
{(0 hello),(1 world),(2 goodbye)}</syntaxhighlight>
=={{header|Go}}==
A package:
<
// AVL tree adapted from Julienne Walker's presentation at
Line 5,691 ⟶ 7,970:
func Remove(tree **Node, data Key) {
*tree, _ = removeR(*tree, data)
}</
A demonstration program:
<
import (
Line 5,735 ⟶ 8,014:
avl.Remove(&tree, intKey(1))
dump(tree)
}</
{{out}}
<pre>
Line 5,806 ⟶ 8,085:
=={{header|Haskell}}==
Based on solution of homework #4 from course http://www.seas.upenn.edu/~cis194/spring13/lectures.html.
<
= Leaf
| Node
Line 5,880 ⟶ 8,159:
main :: IO ()
main = putStr $ draw $ foldTree [1 .. 31]</
{{Out}}
<pre> (31,0)
Line 5,915 ⟶ 8,194:
=={{header|J}}==
Caution: AVL trees are not cache friendly. Linear search is significantly faster (roughly six times faster for a list of 1e8 numbers on current machines and arbitrary data), and using small cached copies of recent updates allows time for updates to be inserted into a fresh copy of the larger list (on a different thread, or failover machine -- search the current "hot copy" before searching the larger "cold copy"). Use [[wp:AoS_and_SoA#Structure_of_arrays|structure of arrays]] for best performance with that approach. (Typical avl implementation also uses memory equivalent to several copies of a flat list.)
Implementation:
<
X=.1 {::2{.x,x NB. middle element of x (don't fail on empty x)
Y=.1 {::2{.y,y NB. middle element of y (don't fail on empty y)
select.#y
case.0 do.x NB. y is an empty node
case.1 do. NB. y is a leaf node
select.*Y-X
case._1 do.a:,y;<x
Line 5,928 ⟶ 8,209:
case. 1 do.x;y;a:
end.
case.3 do. NB. y is a parent node
select.*Y-X
case._1 do.balance (}:y),<x insert 2{::y
Line 6,006 ⟶ 8,287:
't0 t1 t2'=. y
rotRight (rotLeft t0);t1;<t2
}}</
Tree is right argument, leaf value is left argument. An empty tree has no elements, leaves have 1 element, non-empty non-leaf nodes have three elements.
Line 6,043 ⟶ 8,324:
=={{header|Java}}==
This code has been cobbled together from various online examples. It's not easy to find a clear and complete explanation of AVL trees. Textbooks tend to concentrate on red-black trees because of their better efficiency. (AVL trees need to make 2 passes through the tree when inserting and deleting: one down to find the node to operate upon and one up to rebalance the tree.)
<
private Node root;
Line 6,260 ⟶ 8,541:
tree.printBalance();
}
}</
<pre>Inserting values 1 to 10
Line 6,267 ⟶ 8,548:
=== More elaborate version ===
See [[AVL_tree/Java]]
=={{header|Javascript}}==
<syntaxhighlight lang="javascript">function tree(less, val, more) {
return {
depth: 1+Math.max(less.depth, more.depth),
less: less,
val: val,
more: more,
};
}
function node(val) {
return tree({depth: 0}, val, {depth: 0});
}
function insert(x,y) {
if (0 == y.depth) return x;
if (0 == x.depth) return y;
if (1 == x.depth && 1 == y.depth) {
switch (Math.sign(y.val)-x.val) {
case -1: return tree(y, x.val, {depth: 0});
case 0: return y;
case 1: return tree(x, y.val, {depth: 0});
}
}
switch (Math.sign(y.val-x.val)) {
case -1: return balance(insert(x.less, y), x.val, x.more);
case 0: return balance(insert(x.less, y.less), x.val, insert(x.more, y.more));
case 1: return balance(x.less. x.val, insert(x.more, y));
}
}
function balance(less,val,more) {
if (2 > Math.abs(less.depth-more.depth))
return tree(less,val,more);
if (more.depth > less.depth) {
if (more.more.depth >= more.less.depth) {
// 'more' was heavy
return moreHeavy(less, val, more);
} else {
return moreHeavy(less,val,lessHeavy(more.less, more.val, more.more));
}
} else {
if(less.less.depth >= less.more.depth) {
return lessHeavy(less, val, more);
} else {
return lessHeavy(moreHeavy(less.less, less.val, less.more), val, more);
}
}
}
function moreHeavy(less,val,more) {
return tree(tree(less,val,more.less), more.val, more.more)
}
function lessHeavy(less,val,more) {
return tree(less.less, less.val, tree(less.more, val, more));
}
function remove(val, y) {
switch (y.depth) {
case 0: return y;
case 1:
if (val == y.val) {
return y.less;
} else {
return y;
}
default:
switch (Math.sign(y.val - val)) {
case -1: return balance(y.less, y.val, remove(val, y.more));
case 0: return insert(y.less, y.more);
case 1: return balance(remove(val, y.less), y.val, y.more)
}
}
}
function lookup(val, y) {
switch (y.depth) {
case 0: return y;
case 1: if (val == y.val) {
return y;
} else {
return {depth: 0};
}
default:
switch (Math.sign(y.val-val)) {
case -1: return lookup(val, y.more);
case 0: return y;
case 1: return lookup(val, y.less);
}
}
}</syntaxhighlight>
Some examples:
<syntaxhighlight lang="javascript">
function dumptree(t) {
switch (t.depth) {
case 0: return '';
case 1: return t.val;
default: return '('+dumptree(t.less)+','+t.val+','+dumptree(t.more)+')';
}
}
function example() {
let t= node(0);
for (let j= 1; j<20; j++) {
t= insert(node(j), t);
}
console.log(dumptree(t));
t= remove(2, t);
console.log(dumptree(t));
console.log(dumptree(lookup(5, t)));
console.log(dumptree(remove(5, t)));
}
example();</syntaxhighlight>
{{out}}
<pre>(((((0,1,2),3,(4,5,)),6,((7,8,),9,)),10,(((11,12,),13,),14,)),15,(((16,17,),18,),19,))
(((((0,1,),3,(4,5,)),6,((7,8,),9,)),10,(((11,12,),13,),14,)),15,(((16,17,),18,),19,))
(4,5,)
(((((0,1,),3,4),6,((7,8,),9,)),10,(((11,12,),13,),14,)),15,(((16,17,),18,),19,))</pre>
=={{header|Julia}}==
{{trans|Sidef}}
<
import Base.print
Line 6,450 ⟶ 8,855:
println("Printing tree after insertion: ")
println(tree)
</
<pre>
Inserting 10 values.
Line 6,459 ⟶ 8,864:
=={{header|Kotlin}}==
{{trans|Java}}
<
private var root: Node? = null
Line 6,633 ⟶ 9,038:
print("Printing balance : ")
tree.printBalance()
}</
{{out}}
Line 6,640 ⟶ 9,045:
Printing key : 1 2 3 4 5 6 7 8 9 10
Printing balance : 0 0 0 1 0 0 0 0 1 0
</pre>
=={{header|Logtalk}}==
The Logtalk library comes with an AVL implementation of its <code>dictionaryp</code> protocol, whose definition begins thusly:
<syntaxhighlight lang="logtalk">
:- object(avltree,
implements(dictionaryp),
extends(term)).
% ... lots of elision ...
:- end_object.
</syntaxhighlight>
{{Out}}
This makes the use of an AVL tree in Logtalk dirt simple. First we load the <code>dictionaries</code> library.
<pre>
?- logtalk_load(dictionaries(loader)).
% ... messages elided ...
true.
</pre>
We can make a new, empty AVL tree.
<pre>
?- avltree::new(Dictionary).
Dictionary = t.
</pre>
Using Logtalk's broadcast notation to avoid having to repeatedly type <code>avltree::</code> in front of every operation we can insert some keys, update one, and look up values. Note that since variables in Logtalk, as in most declarative languages, cannot be altered, we actually have several dictionaries (<code>D0</code> through <code>D4</code>) representing the initial empty state, various intermediate states, as well as the final state.
<pre>
4 ?- avltree::(
new(D0),
insert(D0, a, 1, D1),
insert(D1, b, 2, D2),
insert(D2, c, 3, D3),
update(D3, a, 7, D4),
lookup(a, Va, D4),
lookup(c, Vc, D4)).
D0 = t,
D1 = t(a, 1, -, t, t),
D2 = t(a, 1, >, t, t(b, 2, -, t, t)),
D3 = t(b, 2, -, t(a, 1, -, t, t), t(c, 3, -, t, t)),
D4 = t(b, 2, -, t(a, 7, -, t, t), t(c, 3, -, t, t)),
Va = 7,
Vc = 3.
</pre>
To save some rote typing, the <code>as_dictionary/2</code> method lets a list of <code>Key-Value</code> pairs be used to initialize a dictionary instead:
<pre>
?- avltree::(
as_dictionary([a-1, b-2, c-3, a-7], D),
lookup(a, Va, D),
lookup(c, Vc, D)).
D = t(b, 2, <, t(a, 7, <, t(a, 1, -, t, t), t), t(c, 3, -, t, t)),
Va = 7,
Vc = 3.
</pre>
=={{header|Lua}}==
<
AVL.__mt={__index = AVL}
Line 6,775 ⟶ 9,242:
print("\nlist:")
print(unpack(test:toList()))
</syntaxhighlight>
{{out}}
<pre> 20 (0)
Line 6,830 ⟶ 9,297:
We use generics for tree and node definitions. Data stored in the tree must be comparable i.e. their type must allow comparison for equality and for inequality (less than comparison). In order to ensure that, we use the notion of concept proposed by Nim.
<
http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx.
Line 7,027 ⟶ 9,494:
tree.remove(3)
tree.remove(1)
echo pretty(%tree)</
{{out}}
Line 7,098 ⟶ 9,565:
=={{header|Objeck}}==
{{trans|Java}}
<
@key : Int;
@balance : Int;
Line 7,381 ⟶ 9,848:
}
}
</syntaxhighlight>
{{out}}
Line 7,392 ⟶ 9,859:
{{trans|Java}}
{{incomplete|Objective-C|It is missing an <code>@interface</code> for AVLTree and also missing any <code>@interface</code> or <code>@implementation</code> for AVLTreeNode.}}
<syntaxhighlight lang="objective-c">
@implementation AVLTree
Line 7,588 ⟶ 10,055:
}
</syntaxhighlight>
{{out}}
Line 7,615 ⟶ 10,082:
with a command line equivalent of https://www.cs.usfca.edu/~galles/visualization/AVLtree.html as well as a simple tree structure
display routine and additional verification code (both modelled on the C version found on this page)
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">enum</span> <span style="color: #000000;">KEY</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span>
Line 7,750 ⟶ 10,217:
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">inOrder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">root</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>50001 50002 50003</pre>
=={{header|Picat}}==
{{trans|Haskell}}
The function delete is missing.
<syntaxhighlight lang="picat">main =>
T = nil,
foreach (X in 1..10)
T := insert(X,T)
end,
output(T,0).
insert(X, nil) = {1,nil,X,nil}.
insert(X, T@{H,L,V,R}) = Res =>
if X < V then
Res = rotate({H, insert(X,L) ,V,R})
elseif X > V then
Res = rotate({H,L,V, insert(X,R)})
else
Res = T
end.
rotate(nil) = nil.
rotate({H, {LH,LL,LV,LR}, V, R}) = Res,
LH - height(R) > 1,
height(LL) - height(LR) > 0
=> % Left Left.
Res = {LH,LL,LV, {depth(R,LR), LR,V,R}}.
rotate({H,L,V, {RH,RL,RV,RR}}) = Res,
RH - height(L) > 1,
height(RR) - height(RL) > 0
=> % Right Right.
Res = {RH, {depth(L,RL),L,V,RL}, RV,RR}.
rotate({H, {LH,LL,LV, {RH,RL,RV,RR}, V,R}}) = Res,
LH - height(R) > 1
=> % Left Right.
Res = {H, {RH + 1, {LH - 1, LL, LV, RL}, RV, RR}, V, R}.
rotate({H,L,V, {RH, {LH,LL,LV,LR},RV,RR}}) = Res,
RH - height(L) > 1
=> % Right Left.
Res = {H,L,V, {LH+1, LL, LV, {RH-1, LR, RV, RR}}}.
rotate({H,L,V,R}) = Res => % Re-weighting.
L1 = rotate(L),
R1 = rotate(R),
Res = {depth(L1,R1), L1,V,R1}.
height(nil) = -1.
height({H,_,_,_}) = H.
depth(A,B) = max(height(A), height(B)) + 1.
output(nil,Indent) => printf("%*w\n",Indent,nil).
output({_,L,V,R},Indent) =>
output(L,Indent+6),
printf("%*w\n",Indent,V),
output(R,Indent+6).
</syntaxhighlight>
{{out}}
<pre>
nil
1
nil
2
nil
3
nil
4
nil
5
nil
6
nil
7
nil
8
nil
9
nil
10
nil
</pre>
=={{header|Python}}==
Line 7,767 ⟶ 10,315:
<p>The dictionary and array classes includes an AVL bag sort method - which is novel.</p>
<
# Module: calculus.py
Line 9,549 ⟶ 12,097:
def __delitem__(self, key):
self.remove(key)
</syntaxhighlight>
=={{header|Raku}}==
Line 9,574 ⟶ 12,122:
like the apostrophe (') and hyphen (-) in identifiers.
<br>
<syntaxhighlight lang="raku" line>
class AVL-Tree {
has $.root is rw = 0;
Line 9,856 ⟶ 12,404:
}
}
</syntaxhighlight>
=={{header|Rust}}==
Line 9,862 ⟶ 12,410:
=={{header|Scala}}==
<
class AVLTree[A](implicit val ordering: Ordering[A]) extends mutable.SortedSet[A] {
Line 10,188 ⟶ 12,736:
}
}</
=={{header|Scheme}}==
{{trans|Fortran}}
See also [[#ATS|ATS]].
{{works with|CHICKEN|5.3.0}}
{{libheader|r7rs}}
In the following, an argument key '''a''' is consider to match a stored key '''b''' if neither '''(pred<? a b)''' nor '''(pred<? b a)'''. So '''pred<?''' should be analogous to '''<'''. No equality predicate is needed.
<syntaxhighlight lang="scheme">(cond-expand
(r7rs)
(chicken (import r7rs)))
(define-library (avl-trees)
;;
;; This library implements ‘persistent’ (that is, ‘immutable’) AVL
;; trees for R7RS Scheme.
;;
;; Included are generators of the key-data pairs in a tree. Because
;; the trees are persistent (‘immutable’), these generators are safe
;; from alterations of the tree.
;;
;; References:
;;
;; * Niklaus Wirth, 1976. Algorithms + Data Structures =
;; Programs. Prentice-Hall, Englewood Cliffs, New Jersey.
;;
;; * Niklaus Wirth, 2004. Algorithms and Data Structures. Updated
;; by Fyodor Tkachov, 2014.
;;
;; Note that the references do not discuss persistent
;; implementations. It seems worthwhile to compare the methods of
;; implementation.
;;
(export avl)
(export alist->avl)
(export avl->alist)
(export avl?)
(export avl-empty?)
(export avl-size)
(export avl-insert)
(export avl-delete)
(export avl-delete-values)
(export avl-has-key?)
(export avl-search)
(export avl-search-values)
(export avl-make-generator)
(export avl-pretty-print)
(export avl-check-avl-condition)
(export avl-check-usage)
(import (scheme base))
(import (scheme case-lambda))
(import (scheme process-context))
(import (scheme write))
(cond-expand
(chicken
(import (only (chicken base) define-record-printer))
(import (only (chicken format) format))) ; For debugging.
(else))
(begin
;; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
;;
;; Tools for making generators. These use call/cc and so might be
;; inefficient in your Scheme. I am using CHICKEN, in which
;; call/cc is not so inefficient.
;;
;; Often I have made &fail a unique object rather than #f, but in
;; this case #f will suffice.
;;
(define &fail #f)
(define *suspend*
(make-parameter (lambda (x) x)))
(define (suspend v)
((*suspend*) v))
(define (fail-forever)
(let loop ()
(suspend &fail)
(loop)))
(define (make-generator-procedure thunk)
;; Make a suspendable procedure that takes no arguments. The
;; result is a simple generator of values. (This can be
;; elaborated upon for generators to take values on resumption,
;; in the manner of Icon co-expressions.)
(define (next-run return)
(define (my-suspend v)
(set! return (call/cc (lambda (resumption-point)
(set! next-run resumption-point)
(return v)))))
(parameterize ((*suspend* my-suspend))
(suspend (thunk))
(fail-forever)))
(lambda () (call/cc next-run)))
;; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
(define-syntax avl-check-usage
(syntax-rules ()
((_ pred msg)
(or pred (usage-error msg)))))
;; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
(define-record-type <avl>
(%avl key data bal left right)
avl?
(key %key)
(data %data)
(bal %bal)
(left %left)
(right %right))
(cond-expand
(chicken (define-record-printer (<avl> rt out)
(display "#<avl " out)
(display (%key rt) out)
(display " " out)
(display (%data rt) out)
(display " " out)
(display (%bal rt) out)
(display " " out)
(display (%left rt) out)
(display " " out)
(display (%right rt) out)
(display ">" out)))
(else))
;; - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
(define avl
(case-lambda
(() (%avl #f #f #f #f #f))
((pred<? . args) (alist->avl pred<? args))))
(define (avl-empty? tree)
(avl-check-usage
(avl? tree)
"avl-empty? expects an AVL tree as argument")
(not (%bal tree)))
(define (avl-size tree)
(define (traverse p sz)
(if (not p)
sz
(traverse (%left p) (traverse (%right p) (+ sz 1)))))
(if (avl-empty? tree)
0
(traverse tree 0)))
(define (avl-has-key? pred<? tree key)
(define (search p)
(and p
(let ((k (%key p)))
(cond ((pred<? key k) (search (%left p)))
((pred<? k key) (search (%right p)))
(else #t)))))
(avl-check-usage
(procedure? pred<?)
"avl-has-key? expects a procedure as first argument")
(and (not (avl-empty? tree))
(search tree)))
(define (avl-search pred<? tree key)
;; Return the data matching a key, or #f if the key is not
;; found. (Note that the data matching the key might be #f.)
(define (search p)
(and p
(let ((k (%key p)))
(cond ((pred<? key k) (search (%left p)))
((pred<? k key) (search (%right p)))
(else (%data p))))))
(avl-check-usage
(procedure? pred<?)
"avl-search expects a procedure as first argument")
(and (not (avl-empty? tree))
(search tree)))
(define (avl-search-values pred<? tree key)
;; Return two values: the data matching the key, or #f is the
;; key is not found; and a second value that is either #f or #t,
;; depending on whether the key is found.
(define (search p)
(if (not p)
(values #f #f)
(let ((k (%key p)))
(cond ((pred<? key k) (search (%left p)))
((pred<? k key) (search (%right p)))
(else (values (%data p) #t))))))
(avl-check-usage
(procedure? pred<?)
"avl-search-values expects a procedure as first argument")
(if (avl-empty? tree)
(values #f #f)
(search tree)))
(define (alist->avl pred<? alst)
;; Go from association list to AVL tree.
(avl-check-usage
(procedure? pred<?)
"alist->avl expects a procedure as first argument")
(let loop ((tree (avl))
(lst alst))
(if (null? lst)
tree
(let ((head (car lst)))
(loop (avl-insert pred<? tree (car head) (cdr head))
(cdr lst))))))
(define (avl->alist tree)
;; Go from AVL tree to association list. The output will be in
;; order.
(define (traverse p lst)
;; Reverse in-order traversal of the tree, to produce an
;; in-order cons-list.
(if (not p)
lst
(traverse (%left p) (cons (cons (%key p) (%data p))
(traverse (%right p) lst)))))
(if (avl-empty? tree)
'()
(traverse tree '())))
(define (avl-insert pred<? tree key data)
(define (search p fix-balance?)
(cond
((not p)
;; The key was not found. Make a new node and set
;; fix-balance?
(values (%avl key data 0 #f #f) #t))
((pred<? key (%key p))
;; Continue searching.
(let-values (((p1 fix-balance?)
(search (%left p) fix-balance?)))
(cond
((not fix-balance?)
(let ((p^ (%avl (%key p) (%data p) (%bal p)
p1 (%right p))))
(values p^ #f)))
(else
;; A new node has been inserted on the left side.
(case (%bal p)
((1)
(let ((p^ (%avl (%key p) (%data p) 0
p1 (%right p))))
(values p^ #f)))
((0)
(let ((p^ (%avl (%key p) (%data p) -1
p1 (%right p))))
(values p^ fix-balance?)))
((-1)
;; Rebalance.
(case (%bal p1)
((-1)
;; A single LL rotation.
(let* ((p^ (%avl (%key p) (%data p) 0
(%right p1) (%right p)))
(p1^ (%avl (%key p1) (%data p1) 0
(%left p1) p^)))
(values p1^ #f)))
((0 1)
;; A double LR rotation.
(let* ((p2 (%right p1))
(bal2 (%bal p2))
(p^ (%avl (%key p) (%data p)
(- (min bal2 0))
(%right p2) (%right p)))
(p1^ (%avl (%key p1) (%data p1)
(- (max bal2 0))
(%left p1) (%left p2)))
(p2^ (%avl (%key p2) (%data p2) 0
p1^ p^)))
(values p2^ #f)))
(else (internal-error))))
(else (internal-error)))))))
((pred<? (%key p) key)
;; Continue searching.
(let-values (((p1 fix-balance?)
(search (%right p) fix-balance?)))
(cond
((not fix-balance?)
(let ((p^ (%avl (%key p) (%data p) (%bal p)
(%left p) p1)))
(values p^ #f)))
(else
;; A new node has been inserted on the right side.
(case (%bal p)
((-1)
(let ((p^ (%avl (%key p) (%data p) 0
(%left p) p1)))
(values p^ #f)))
((0)
(let ((p^ (%avl (%key p) (%data p) 1
(%left p) p1)))
(values p^ fix-balance?)))
((1)
;; Rebalance.
(case (%bal p1)
((1)
;; A single RR rotation.
(let* ((p^ (%avl (%key p) (%data p) 0
(%left p) (%left p1)))
(p1^ (%avl (%key p1) (%data p1) 0
p^ (%right p1))))
(values p1^ #f)))
((-1 0)
;; A double RL rotation.
(let* ((p2 (%left p1))
(bal2 (%bal p2))
(p^ (%avl (%key p) (%data p)
(- (max bal2 0))
(%left p) (%left p2)))
(p1^ (%avl (%key p1) (%data p1)
(- (min bal2 0))
(%right p2) (%right p1)))
(p2^ (%avl (%key p2) (%data p2) 0
p^ p1^)))
(values p2^ #f)))
(else (internal-error))))
(else (internal-error)))))))
(else
;; The key was found; p is an existing node.
(values (%avl key data (%bal p) (%left p) (%right p))
#f))))
(avl-check-usage
(procedure? pred<?)
"avl-insert expects a procedure as first argument")
(if (avl-empty? tree)
(%avl key data 0 #f #f)
(let-values (((p fix-balance?) (search tree #f)))
p)))
(define (avl-delete pred<? tree key)
;; If one is not interested in whether the key was in the tree,
;; then throw away that information.
(let-values (((tree had-key?)
(avl-delete-values pred<? tree key)))
tree))
(define (balance-for-shrunken-left p)
;; Returns two values: a new p and a new fix-balance?
(case (%bal p)
((-1) (values (%avl (%key p) (%data p) 0
(%left p) (%right p))
#t))
((0) (values (%avl (%key p) (%data p) 1
(%left p) (%right p))
#f))
((1)
;; Rebalance.
(let* ((p1 (%right p))
(bal1 (%bal p1)))
(case bal1
((0)
;; A single RR rotation.
(let* ((p^ (%avl (%key p) (%data p) 1
(%left p) (%left p1)))
(p1^ (%avl (%key p1) (%data p1) -1
p^ (%right p1))))
(values p1^ #f)))
((1)
;; A single RR rotation.
(let* ((p^ (%avl (%key p) (%data p) 0
(%left p) (%left p1)))
(p1^ (%avl (%key p1) (%data p1) 0
p^ (%right p1))))
(values p1^ #t)))
((-1)
;; A double RL rotation.
(let* ((p2 (%left p1))
(bal2 (%bal p2))
(p^ (%avl (%key p) (%data p) (- (max bal2 0))
(%left p) (%left p2)))
(p1^ (%avl (%key p1) (%data p1) (- (min bal2 0))
(%right p2) (%right p1)))
(p2^ (%avl (%key p2) (%data p2) 0 p^ p1^)))
(values p2^ #t)))
(else (internal-error)))))
(else (internal-error))))
(define (balance-for-shrunken-right p)
;; Returns two values: a new p and a new fix-balance?
(case (%bal p)
((1) (values (%avl (%key p) (%data p) 0
(%left p) (%right p))
#t))
((0) (values (%avl (%key p) (%data p) -1
(%left p) (%right p))
#f))
((-1)
;; Rebalance.
(let* ((p1 (%left p))
(bal1 (%bal p1)))
(case bal1
((0)
;; A single LL rotation.
(let* ((p^ (%avl (%key p) (%data p) -1
(%right p1) (%right p)))
(p1^ (%avl (%key p1) (%data p1) 1
(%left p1) p^)))
(values p1^ #f)))
((-1)
;; A single LL rotation.
(let* ((p^ (%avl (%key p) (%data p) 0
(%right p1) (%right p)))
(p1^ (%avl (%key p1) (%data p1) 0
(%left p1) p^)))
(values p1^ #t)))
((1)
;; A double LR rotation.
(let* ((p2 (%right p1))
(bal2 (%bal p2))
(p^ (%avl (%key p) (%data p) (- (min bal2 0))
(%right p2) (%right p)))
(p1^ (%avl (%key p1) (%data p1) (- (max bal2 0))
(%left p1) (%left p2)))
(p2^ (%avl (%key p2) (%data p2) 0 p1^ p^)))
(values p2^ #t)))
(else (internal-error)))))
(else (internal-error))))
(define (avl-delete-values pred<? tree key)
(define-syntax balance-L
(syntax-rules ()
((_ p fix-balance?)
(if fix-balance?
(balance-for-shrunken-left p)
(values p #f)))))
(define-syntax balance-R
(syntax-rules ()
((_ p fix-balance?)
(if fix-balance?
(balance-for-shrunken-right p)
(values p #f)))))
(define (del r fix-balance?)
;; Returns a new r, a new fix-balance?, and key and data to be
;; ‘moved up the tree’.
(if (%right r)
(let*-values
(((q fix-balance? key^ data^)
(del (%right r) fix-balance?))
((r fix-balance?)
(balance-R (%avl (%key r) (%data r) (%bal r)
(%left r) q)
fix-balance?)))
(values r fix-balance? key^ data^))
(values (%left r) #t (%key r) (%data r))))
(define (search p fix-balance?)
;; Return three values: a new p, a new fix-balance, and
;; whether the key was found.
(cond
((not p) (values #f #f #f))
((pred<? key (%key p))
;; Recursive search down the left branch.
(let*-values
(((q fix-balance? found?)
(search (%left p) fix-balance?))
((p fix-balance?)
(balance-L (%avl (%key p) (%data p) (%bal p)
q (%right p))
fix-balance?)))
(values p fix-balance? found?)))
((pred<? (%key p) key)
;; Recursive search down the right branch.
(let*-values
(((q fix-balance? found?)
(search (%right p) fix-balance?))
((p fix-balance?)
(balance-R (%avl (%key p) (%data p) (%bal p)
(%left p) q)
fix-balance?)))
(values p fix-balance? found?)))
((not (%right p))
;; Delete p, replace it with its left branch, then
;; rebalance.
(values (%left p) #t #t))
((not (%left p))
;; Delete p, replace it with its right branch, then
;; rebalance.
(values (%right p) #t #t))
(else
;; Delete p, but it has both left and right branches,
;; and therefore may have complicated branch structure.
(let*-values
(((q fix-balance? key^ data^)
(del (%left p) fix-balance?))
((p fix-balance?)
(balance-L (%avl key^ data^ (%bal p) q (%right p))
fix-balance?)))
(values p fix-balance? #t)))))
(avl-check-usage
(procedure? pred<?)
"avl-delete-values expects a procedure as first argument")
(if (avl-empty? tree)
(values tree #f)
(let-values (((tree fix-balance? found?)
(search tree #f)))
(if found?
(values (or tree (avl)) #t)
(values tree #f)))))
(define avl-make-generator
(case-lambda
((tree) (avl-make-generator tree 1))
((tree direction)
(if (negative? direction)
(make-generator-procedure
(lambda ()
(define (traverse p)
(unless (or (not p) (avl-empty? p))
(traverse (%right p))
(suspend (cons (%key p) (%data p)))
(traverse (%left p)))
&fail)
(traverse tree)))
(make-generator-procedure
(lambda ()
(define (traverse p)
(unless (or (not p) (avl-empty? p))
(traverse (%left p))
(suspend (cons (%key p) (%data p)))
(traverse (%right p)))
&fail)
(traverse tree)))))))
(define avl-pretty-print
(case-lambda
((tree)
(avl-pretty-print tree (current-output-port)))
((tree port)
(avl-pretty-print tree port
(lambda (port key data)
(display "(" port)
(write key port)
(display ", " port)
(write data port)
(display ")" port))))
((tree port key-data-printer)
;; In-order traversal, so the printing is done in
;; order. Reflect the display diagonally to get the more
;; usual orientation of left-to-right, top-to-bottom.
(define (pad depth)
(unless (zero? depth)
(display " " port)
(pad (- depth 1))))
(define (traverse p depth)
(when p
(traverse (%left p) (+ depth 1))
(pad depth)
(key-data-printer port (%key p) (%data p))
(display "\t\tdepth = " port)
(display depth port)
(display " bal = " port)
(display (%bal p) port)
(display "\n" port)
(traverse (%right p) (+ depth 1))))
(unless (avl-empty? tree)
(traverse (%left tree) 1)
(key-data-printer port (%key tree) (%data tree))
(display "\t\tdepth = 0 bal = " port)
(display (%bal tree) port)
(display "\n" port)
(traverse (%right tree) 1)))))
(define (avl-check-avl-condition tree)
;; Check that the AVL condition is satisfied.
(define (check-heights height-L height-R)
(when (<= 2 (abs (- height-L height-R)))
(display "*** AVL condition violated ***"
(current-error-port))
(internal-error)))
(define (get-heights p)
(if (not p)
(values 0 0)
(let-values (((height-LL height-LR)
(get-heights (%left p)))
((height-RL height-RR)
(get-heights (%right p))))
(check-heights height-LL height-LR)
(check-heights height-RL height-RR)
(values (+ height-LL height-LR)
(+ height-RL height-RR)))))
(unless (avl-empty? tree)
(let-values (((height-L height-R) (get-heights tree)))
(check-heights height-L height-R))))
(define (internal-error)
(display "internal error\n" (current-error-port))
(emergency-exit 123))
(define (usage-error msg)
(display "Procedure usage error:\n" (current-error-port))
(display " " (current-error-port))
(display msg (current-error-port))
(newline (current-error-port))
(exit 1))
)) ;; end library (avl-trees)
(cond-expand
(DEMONSTRATION
(begin
(import (avl-trees))
(import (scheme base))
(import (scheme time))
(import (scheme process-context))
(import (scheme write))
(cond-expand
(chicken
(import (only (chicken format) format))) ; For debugging.
(else))
(define 2**64 (expt 2 64))
(define seed (truncate-remainder (exact (current-second)) 2**64))
(define random
;; A really slow (but presumably highly portable)
;; implementation of Donald Knuth’s linear congruential random
;; number generator, returning a rational number in [0,1). See
;; https://en.wikipedia.org/w/index.php?title=Linear_congruential_generator&oldid=1076681286
(let ((a 6364136223846793005)
(c 1442695040888963407))
(lambda ()
(let ((result (/ seed 2**64)))
(set! seed (truncate-remainder (+ (* a seed) c) 2**64))
result))))
(do ((i 0 (+ i 1)))
((= i 10))
(random))
(define (fisher-yates-shuffle keys)
(let ((n (vector-length keys)))
(do ((i 1 (+ i 1)))
((= i n))
(let* ((randnum (random))
(j (+ i (floor (* randnum (- n i)))))
(xi (vector-ref keys i))
(xj (vector-ref keys j)))
(vector-set! keys i xj)
(vector-set! keys j xi)))))
(define (display-key-data key data)
(display "(")
(write key)
(display ", ")
(write data)
(display ")"))
(define (display-tree-contents tree)
(do ((p (avl->alist tree) (cdr p)))
((null? p))
(display-key-data (caar p) (cdar p))
(newline)))
(define (error-stop)
(display "*** ERROR STOP ***\n" (current-error-port))
(emergency-exit 1))
(define n 20)
(define keys (make-vector (+ n 1)))
(do ((i 0 (+ i 1)))
((= i n))
;; To keep things more like Fortran, do not use index zero.
(vector-set! keys (+ i 1) (+ i 1)))
(fisher-yates-shuffle keys)
;; Insert key-data pairs in the shuffled order.
(define tree (avl))
(avl-check-avl-condition tree)
(do ((i 1 (+ i 1)))
((= i (+ n 1)))
(let ((ix (vector-ref keys i)))
(set! tree (avl-insert < tree ix (inexact ix)))
(avl-check-avl-condition tree)
(do ((j 1 (+ j 1)))
((= j (+ n 1)))
(let*-values (((k) (vector-ref keys j))
((has-key?) (avl-has-key? < tree k))
((data) (avl-search < tree k))
((data^ has-key?^)
(avl-search-values < tree k)))
(unless (exact? k) (error-stop))
(if (<= j i)
(unless (and has-key? data data^ has-key?^
(inexact? data) (= data k)
(inexact? data^) (= data^ k))
(error-stop))
(when (or has-key? data data^ has-key?^)
(error-stop)))))))
(display "----------------------------------------------------------------------\n")
(display "keys = ")
(write (cdr (vector->list keys)))
(newline)
(display "----------------------------------------------------------------------\n")
(avl-pretty-print tree)
(display "----------------------------------------------------------------------\n")
(display "tree size = ")
(display (avl-size tree))
(newline)
(display-tree-contents tree)
(display "----------------------------------------------------------------------\n")
;;
;; Reshuffle the keys, and change the data from inexact numbers
;; to strings.
;;
(fisher-yates-shuffle keys)
(do ((i 1 (+ i 1)))
((= i (+ n 1)))
(let ((ix (vector-ref keys i)))
(set! tree (avl-insert < tree ix (number->string ix)))
(avl-check-avl-condition tree)))
(avl-pretty-print tree)
(display "----------------------------------------------------------------------\n")
(display "tree size = ")
(display (avl-size tree))
(newline)
(display-tree-contents tree)
(display "----------------------------------------------------------------------\n")
;;
;; Reshuffle the keys, and delete the contents of the tree, but
;; also keep the original tree by saving it in a variable. Check
;; persistence of the tree.
;;
(fisher-yates-shuffle keys)
(define saved-tree tree)
(do ((i 1 (+ i 1)))
((= i (+ n 1)))
(let ((ix (vector-ref keys i)))
(set! tree (avl-delete < tree ix))
(avl-check-avl-condition tree)
(unless (= (avl-size tree) (- n i)) (error-stop))
;; Try deleting a second time.
(set! tree (avl-delete < tree ix))
(avl-check-avl-condition tree)
(unless (= (avl-size tree) (- n i)) (error-stop))
(do ((j 1 (+ j 1)))
((= j (+ n 1)))
(let ((jx (vector-ref keys j)))
(unless (eq? (avl-has-key? < tree jx) (< i j))
(error-stop))
(let ((data (avl-search < tree jx)))
(unless (eq? (not (not data)) (< i j))
(error-stop))
(unless (or (not data)
(= (string->number data) jx))
(error-stop)))
(let-values (((data found?)
(avl-search-values < tree jx)))
(unless (eq? found? (< i j)) (error-stop))
(unless (or (and (not data) (<= j i))
(and data (= (string->number data) jx)))
(error-stop)))))))
(do ((i 1 (+ i 1)))
((= i (+ n 1)))
;; Is save-tree the persistent value of the tree we just
;; deleted?
(let ((ix (vector-ref keys i)))
(unless (equal? (avl-search < saved-tree ix)
(number->string ix))
(error-stop))))
(display "forwards generator:\n")
(let ((gen (avl-make-generator saved-tree)))
(do ((pair (gen) (gen)))
((not pair))
(display-key-data (car pair) (cdr pair))
(newline)))
(display "----------------------------------------------------------------------\n")
(display "backwards generator:\n")
(let ((gen (avl-make-generator saved-tree -1)))
(do ((pair (gen) (gen)))
((not pair))
(display-key-data (car pair) (cdr pair))
(newline)))
(display "----------------------------------------------------------------------\n")
))
(else))</syntaxhighlight>
{{out}}
The demonstration is randomized. The following is an example of one run.
The ‘pretty printed’ tree is a diagonal reflection of the usual from-the-root-downwards, left-to-right representation. It goes from-the-root-rightwards, top-to-bottom.
<pre>$ csc -DDEMONSTRATION -R r7rs -X r7rs avl_trees-scheme.scm && ./avl_trees-scheme
----------------------------------------------------------------------
keys = (12 16 20 6 9 18 15 10 13 4 2 7 11 5 8 3 19 14 17 1)
----------------------------------------------------------------------
(1, 1.0) depth = 4 bal = 0
(2, 2.0) depth = 3 bal = 0
(3, 3.0) depth = 4 bal = 0
(4, 4.0) depth = 2 bal = -1
(5, 5.0) depth = 3 bal = 0
(6, 6.0) depth = 1 bal = 0
(7, 7.0) depth = 3 bal = 1
(8, 8.0) depth = 4 bal = 0
(9, 9.0) depth = 2 bal = 0
(10, 10.0) depth = 3 bal = 1
(11, 11.0) depth = 4 bal = 0
(12, 12.0) depth = 0 bal = 0
(13, 13.0) depth = 3 bal = 0
(14, 14.0) depth = 2 bal = 0
(15, 15.0) depth = 3 bal = 0
(16, 16.0) depth = 1 bal = 1
(17, 17.0) depth = 4 bal = 0
(18, 18.0) depth = 3 bal = -1
(19, 19.0) depth = 2 bal = -1
(20, 20.0) depth = 3 bal = 0
----------------------------------------------------------------------
tree size = 20
(1, 1.0)
(2, 2.0)
(3, 3.0)
(4, 4.0)
(5, 5.0)
(6, 6.0)
(7, 7.0)
(8, 8.0)
(9, 9.0)
(10, 10.0)
(11, 11.0)
(12, 12.0)
(13, 13.0)
(14, 14.0)
(15, 15.0)
(16, 16.0)
(17, 17.0)
(18, 18.0)
(19, 19.0)
(20, 20.0)
----------------------------------------------------------------------
(1, "1") depth = 4 bal = 0
(2, "2") depth = 3 bal = 0
(3, "3") depth = 4 bal = 0
(4, "4") depth = 2 bal = -1
(5, "5") depth = 3 bal = 0
(6, "6") depth = 1 bal = 0
(7, "7") depth = 3 bal = 1
(8, "8") depth = 4 bal = 0
(9, "9") depth = 2 bal = 0
(10, "10") depth = 3 bal = 1
(11, "11") depth = 4 bal = 0
(12, "12") depth = 0 bal = 0
(13, "13") depth = 3 bal = 0
(14, "14") depth = 2 bal = 0
(15, "15") depth = 3 bal = 0
(16, "16") depth = 1 bal = 1
(17, "17") depth = 4 bal = 0
(18, "18") depth = 3 bal = -1
(19, "19") depth = 2 bal = -1
(20, "20") depth = 3 bal = 0
----------------------------------------------------------------------
tree size = 20
(1, "1")
(2, "2")
(3, "3")
(4, "4")
(5, "5")
(6, "6")
(7, "7")
(8, "8")
(9, "9")
(10, "10")
(11, "11")
(12, "12")
(13, "13")
(14, "14")
(15, "15")
(16, "16")
(17, "17")
(18, "18")
(19, "19")
(20, "20")
----------------------------------------------------------------------
forwards generator:
(1, "1")
(2, "2")
(3, "3")
(4, "4")
(5, "5")
(6, "6")
(7, "7")
(8, "8")
(9, "9")
(10, "10")
(11, "11")
(12, "12")
(13, "13")
(14, "14")
(15, "15")
(16, "16")
(17, "17")
(18, "18")
(19, "19")
(20, "20")
----------------------------------------------------------------------
backwards generator:
(20, "20")
(19, "19")
(18, "18")
(17, "17")
(16, "16")
(15, "15")
(14, "14")
(13, "13")
(12, "12")
(11, "11")
(10, "10")
(9, "9")
(8, "8")
(7, "7")
(6, "6")
(5, "5")
(4, "4")
(3, "3")
(2, "2")
(1, "1")
----------------------------------------------------------------------</pre>
=={{header|Sidef}}==
{{trans|D}}
<
has root = nil
Line 10,365 ⟶ 13,866:
{|i| tree.insert(i) } << 1..10
print "Printing balance: "
tree.printBalance</
{{out}}
<pre>
Line 10,373 ⟶ 13,874:
=={{header|Simula}}==
<
BEGIN
Line 10,572 ⟶ 14,073:
END REMOVEM;
END.</
A demonstration program:
<
AVL
Line 10,609 ⟶ 14,110:
END;
END.</
{{out}}
<pre>
Line 10,625 ⟶ 14,126:
Note that in general, you would not normally write a tree directly in Tcl when writing code that required an <math>\alpha</math><sup>=</sup><math>\rightarrow\beta</math> map, but would rather use either an array variable or a dictionary value (which are internally implemented using a high-performance hash table engine).
{{works with|Tcl|8.6}}
<
namespace eval AVL {
Line 10,805 ⟶ 14,306:
}
}
}</
Demonstrating:
<
AVL::Tree create tree
Line 10,826 ⟶ 14,327:
# Destroy the tree and all its nodes
tree destroy</
{{out}}
<pre style="overflow:auto;height:400px">
Line 10,938 ⟶ 14,439:
{{trans|Java}}
For use within a project, consider adding "export default" to AVLtree class declaration.
<
class AVLnode <T> {
balance: number
Line 11,151 ⟶ 14,652:
}
}
</syntaxhighlight>
=={{header|Wren}}==
{{trans|Kotlin}}
<
construct new(key, parent) {
_key = key
Line 11,343 ⟶ 14,844:
tree.printKey()
System.write("Printing balance : ")
tree.printBalance()</
{{out}}
Line 11,351 ⟶ 14,852:
Printing balance : 0 0 0 1 0 0 0 0 1 0
</pre>
=={{header|Yabasic}}==
<syntaxhighlight lang="yabasic">// AVL-Tree C code, https://www.programiz.com/dsa/avl-tree
// Ported to Yabasic by Galileo 2022/07
KEY = 1 : LRIGHT = 2 : LLEFT = 3 : HEIGHT = 4
root = 0 : ramas = 5 : indice = 0
dim arbol(ramas, 4)
sub rotateRight(y)
local x, T2
x = arbol(y, LLEFT)
T2 = arbol(x, LRIGHT)
arbol(x, LRIGHT) = y
arbol(y, LLEFT) = T2
arbol(y, HEIGHT) = max(height(arbol(y, LLEFT)), height(arbol(y, LRIGHT))) + 1
arbol(x, HEIGHT) = max(height(arbol(x, LLEFT)), height(arbol(x, LRIGHT))) + 1
return x
end sub
sub rotateLeft(x)
local y, T2
y = arbol(x, LRIGHT)
T2 = arbol(y, LLEFT)
arbol(y, LLEFT) = x
arbol(x, LRIGHT) = T2
arbol(x, HEIGHT) = max(height(arbol(x, LLEFT)), height(arbol(x, LRIGHT))) + 1
arbol(y, HEIGHT) = max(height(arbol(y, LLEFT)), height(arbol(y, LRIGHT))) + 1
return y
end sub
sub Balance(current)
return height(arbol(current, LLEFT)) - height(arbol(current, LRIGHT))
end sub
sub height(current)
return arbol(current, HEIGHT)
end sub
sub insert(current, key)
local balance
if current = 0 indice = indice + 1 : if indice > ramas then ramas = ramas + 5 : redim arbol(ramas, 4) endif : arbol(indice, KEY) = key : arbol(indice, HEIGHT) = 1 : return indice
if key < arbol(current, KEY) then
arbol(current, LLEFT) = insert(arbol(current, LLEFT), key)
elsif key > arbol(current, KEY) then
arbol(current, LRIGHT) = insert(arbol(current, LRIGHT), key)
else
return current
endif
arbol(current, HEIGHT) = max(height(arbol(current, LLEFT)), height(arbol(current, LRIGHT))) + 1
balance = Balance(current)
if balance > 1 and key < arbol(arbol(current, LLEFT), KEY) return rotateRight(current)
if balance < -1 and key > arbol(arbol(current, LRIGHT), KEY) return rotateLeft(current)
if balance > 1 and key > arbol(arbol(current, LLEFT), KEY) then
arbol(current, LLEFT) = rotateLeft(arbol(current, LLEFT))
return rotateRight(current)
endif
if balance < -1 and key < arbol(arbol(current, LRIGHT), KEY) then
arbol(current, LRIGHT) = rotateRight(arbol(current, LRIGHT))
return rotateLeft(current)
endif
return current
end sub
sub minValueNode(current)
while arbol(current, LLEFT)
current = arbol(current, LLEFT)
wend
return current
end sub
// Delete a nodes
sub deleteNode(root, key)
local temp, balance
// Find the node and delete it
if root = 0 return root
if key < arbol(root, KEY) then
arbol(root, LLEFT) = deleteNode(arbol(root, LLEFT), key)
elsif key > arbol(root, KEY) then
arbol(root, LRIGHT) = deleteNode(arbol(root, LRIGHT), key)
else
if arbol(root, LLEFT) = 0 or arbol(root, LRIGHT) = 0 then
temp = max(arbol(root, LLEFT), arbol(root, LRIGHT))
if temp = 0 then
temp = root
root = 0
else
root = temp
endif
else
temp = minValueNode(arbol(root, LRIGHT))
arbol(root, KEY) = arbol(temp, KEY)
arbol(root, LRIGHT) = deleteNode(arbol(root, LRIGHT), arbol(temp, KEY))
endif
endif
if root = 0 return root
// Update the balance factor of each node and
// balance the tree
arbol(root, HEIGHT) = 1 + max(height(arbol(root, LLEFT)), height(arbol(root, LRIGHT)))
balance = Balance(root)
if balance > 1 and Balance(arbol(root, LLEFT)) >= 0 return rightRotate(root)
if balance > 1 and Balance(arbol(root, LLEFT)) < 0 arbol(root, LLEFT) = leftRotate(arbol(root, LLEFT)) : return rightRotate(root)
if balance < -1 and Balance(arbol(root, LRIGHT)) <= 0 return leftRotate(root)
if balance < -1 and Balance(arbol(root, LRIGHT)) > 0 arbol(root, LRIGHT) = rightRotate(arbol(root, LRIGHT)) : return leftRotate(root)
return root
end sub
sub preOrder(temp)
if temp then
print arbol(temp, KEY), " ", arbol(temp, HEIGHT), " ", Balance(temp)
preOrder(arbol(temp, LLEFT))
preOrder(arbol(temp, LRIGHT))
endif
end sub
root = insert(root, 2)
root = insert(root, 1)
root = insert(root, 7)
root = insert(root, 4)
root = insert(root, 5)
root = insert(root, 3)
root = insert(root, 8)
preOrder(root)
root = deleteNode(root, 3)
print "\nAfter deletion: "
preOrder(root)</syntaxhighlight>
{{out}}
<pre>4 3 0
2 2 0
1 1 0
3 1 0
7 2 0
5 1 0
8 1 0
After deletion:
4 3 0
2 2 1
1 1 0
7 2 0
5 1 0
8 1 0
---Program done, press RETURN---</pre>
{{omit from|MiniZinc|type system is too inexpressive}}
| |||