AVL tree: Difference between revisions
Add Emacs Lisp
m (→{{header|Javascript}}: eliminate spurious newlines) |
(Add Emacs Lisp) |
||
| (12 intermediate revisions by 9 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,059 ⟶ 2,061:
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.)
<
#define ATS_DYNLOADFLAG 0
Line 3,719 ⟶ 3,721:
end
(*------------------------------------------------------------------*)</
{{out}}
Line 3,818 ⟶ 3,820:
=={{header|C++}}==
{{trans|D}}
<
#include <algorithm>
#include <iostream>
Line 4,074 ⟶ 4,076:
t.printBalance();
}
</syntaxhighlight>
{{out}}
<pre>
Line 4,090 ⟶ 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 4,376 ⟶ 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 4,574 ⟶ 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}}==
Line 4,588 ⟶ 5,184:
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.
<
!
! References:
Line 5,441 ⟶ 6,037:
end subroutine print_contents
end program avl_trees_demo</
{{out}}
Line 5,495 ⟶ 6,091:
<
space system
{
Line 7,205 ⟶ 7,801:
{D,C,B,A,E}
{(0 hello),(1 world)}
{(0 hello),(1 world),(2 goodbye)}</
=={{header|Go}}==
A package:
<
// AVL tree adapted from Julienne Walker's presentation at
Line 7,374 ⟶ 7,970:
func Remove(tree **Node, data Key) {
*tree, _ = removeR(*tree, data)
}</
A demonstration program:
<
import (
Line 7,418 ⟶ 8,014:
avl.Remove(&tree, intKey(1))
dump(tree)
}</
{{out}}
<pre>
Line 7,489 ⟶ 8,085:
=={{header|Haskell}}==
Based on solution of homework #4 from course http://www.seas.upenn.edu/~cis194/spring13/lectures.html.
<
= Leaf
| Node
Line 7,563 ⟶ 8,159:
main :: IO ()
main = putStr $ draw $ foldTree [1 .. 31]</
{{Out}}
<pre> (31,0)
Line 7,599 ⟶ 8,195:
=={{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 [[
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)
Line 7,691 ⟶ 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 7,728 ⟶ 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 7,945 ⟶ 8,541:
tree.printBalance();
}
}</
<pre>Inserting values 1 to 10
Line 7,955 ⟶ 8,551:
=={{header|Javascript}}==
<
return {
depth: 1+Math.max(less.depth, more.depth),
Line 8,045 ⟶ 8,641:
}
}
}</
Some examples:
<syntaxhighlight lang="javascript">
function dumptree(t) {
switch (t.depth) {
Line 8,069 ⟶ 8,665:
}
example();</
{{out}}
Line 8,079 ⟶ 8,675:
=={{header|Julia}}==
{{trans|Sidef}}
<
import Base.print
Line 8,259 ⟶ 8,855:
println("Printing tree after insertion: ")
println(tree)
</
<pre>
Inserting 10 values.
Line 8,268 ⟶ 8,864:
=={{header|Kotlin}}==
{{trans|Java}}
<
private var root: Node? = null
Line 8,442 ⟶ 9,038:
print("Printing balance : ")
tree.printBalance()
}</
{{out}}
Line 8,449 ⟶ 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 8,584 ⟶ 9,242:
print("\nlist:")
print(unpack(test:toList()))
</syntaxhighlight>
{{out}}
<pre> 20 (0)
Line 8,639 ⟶ 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 8,836 ⟶ 9,494:
tree.remove(3)
tree.remove(1)
echo pretty(%tree)</
{{out}}
Line 8,907 ⟶ 9,565:
=={{header|Objeck}}==
{{trans|Java}}
<
@key : Int;
@balance : Int;
Line 9,190 ⟶ 9,848:
}
}
</syntaxhighlight>
{{out}}
Line 9,201 ⟶ 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 9,397 ⟶ 10,055:
}
</syntaxhighlight>
{{out}}
Line 9,424 ⟶ 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 9,559 ⟶ 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 9,576 ⟶ 10,315:
<p>The dictionary and array classes includes an AVL bag sort method - which is novel.</p>
<
# Module: calculus.py
Line 11,358 ⟶ 12,097:
def __delitem__(self, key):
self.remove(key)
</syntaxhighlight>
=={{header|Raku}}==
Line 11,383 ⟶ 12,122:
like the apostrophe (') and hyphen (-) in identifiers.
<br>
<syntaxhighlight lang="raku" line>
class AVL-Tree {
has $.root is rw = 0;
Line 11,665 ⟶ 12,404:
}
}
</syntaxhighlight>
=={{header|Rust}}==
Line 11,671 ⟶ 12,410:
=={{header|Scala}}==
<
class AVLTree[A](implicit val ordering: Ordering[A]) extends mutable.SortedSet[A] {
Line 11,997 ⟶ 12,736:
}
}</
=={{header|Scheme}}==
Line 12,007 ⟶ 12,746:
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.
<
(r7rs)
(chicken (import r7rs)))
Line 12,809 ⟶ 13,548:
))
(else))</
{{out}}
Line 12,954 ⟶ 13,693:
=={{header|Sidef}}==
{{trans|D}}
<
has root = nil
Line 13,127 ⟶ 13,866:
{|i| tree.insert(i) } << 1..10
print "Printing balance: "
tree.printBalance</
{{out}}
<pre>
Line 13,135 ⟶ 13,874:
=={{header|Simula}}==
<
BEGIN
Line 13,334 ⟶ 14,073:
END REMOVEM;
END.</
A demonstration program:
<
AVL
Line 13,371 ⟶ 14,110:
END;
END.</
{{out}}
<pre>
Line 13,387 ⟶ 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 13,567 ⟶ 14,306:
}
}
}</
Demonstrating:
<
AVL::Tree create tree
Line 13,588 ⟶ 14,327:
# Destroy the tree and all its nodes
tree destroy</
{{out}}
<pre style="overflow:auto;height:400px">
Line 13,700 ⟶ 14,439:
{{trans|Java}}
For use within a project, consider adding "export default" to AVLtree class declaration.
<
class AVLnode <T> {
balance: number
Line 13,913 ⟶ 14,652:
}
}
</syntaxhighlight>
=={{header|Wren}}==
{{trans|Kotlin}}
<
construct new(key, parent) {
_key = key
Line 14,105 ⟶ 14,844:
tree.printKey()
System.write("Printing balance : ")
tree.printBalance()</
{{out}}
Line 14,113 ⟶ 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}}
| |||