AVL tree: Difference between revisions
m
Automated syntax highlighting fixup (second round - minor fixes)
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
Thundergnat (talk | contribs) m (Automated syntax highlighting fixup (second round - minor fixes)) |
||
Line 2:
{{wikipedia|AVL tree}}
[[Category:Data Structures]]
{{omit from|MiniZinc|type system is too inexpressive}}▼
<br>
Line 18 ⟶ 17:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang=
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program avltree64.s */
Line 883 ⟶ 882:
=={{header|Ada}}==
{{trans|C++}}
<syntaxhighlight lang="ada">
with Ada.Text_IO, Ada.Finalization, Ada.Unchecked_Deallocation;
Line 1,132 ⟶ 1,131:
=={{header|Agda}}==
This implementation uses the type system to enforce the height invariants, though not the BST invariants
<syntaxhighlight lang="agda">
module Avl where
Line 1,239 ⟶ 1,238:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang=
/* ARM assembly Raspberry PI */
/* program avltree2.s */
Line 2,062 ⟶ 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.)
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
#define ATS_DYNLOADFLAG 0
Line 3,821 ⟶ 3,820:
=={{header|C++}}==
{{trans|D}}
<syntaxhighlight lang="cpp">
#include <algorithm>
#include <iostream>
Line 4,093 ⟶ 4,092:
=={{header|Common Lisp}}==
Provided is an imperative implementation of an AVL tree with a similar interface and documentation to HASH-TABLE.
<syntaxhighlight lang="lisp">(defpackage :avl-tree
(:use :cl)
(:export
Line 4,383 ⟶ 4,382:
=={{header|D}}==
{{trans|Java}}
<syntaxhighlight lang="d">import std.stdio, std.algorithm;
class AVLtree {
Line 4,591 ⟶ 4,590:
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 5,498 ⟶ 5,497:
<syntaxhighlight lang="cpp">
space system
{
Line 7,212 ⟶ 7,211:
=={{header|Go}}==
A package:
<syntaxhighlight lang="go">package avl
// AVL tree adapted from Julienne Walker's presentation at
Line 7,379 ⟶ 7,378:
}</syntaxhighlight>
A demonstration program:
<syntaxhighlight lang="go">package main
import (
Line 7,492 ⟶ 7,491:
=={{header|Haskell}}==
Based on solution of homework #4 from course http://www.seas.upenn.edu/~cis194/spring13/lectures.html.
<syntaxhighlight lang="haskell">data Tree a
= Leaf
| Node
Line 7,605 ⟶ 7,604:
Implementation:
<syntaxhighlight lang=
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,731 ⟶ 7,730:
=={{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.)
<syntaxhighlight lang="java">public class AVLtree {
private Node root;
Line 7,958 ⟶ 7,957:
=={{header|Javascript}}==
<syntaxhighlight lang=
return {
depth: 1+Math.max(less.depth, more.depth),
Line 8,052 ⟶ 8,051:
Some examples:
<syntaxhighlight lang=
function dumptree(t) {
switch (t.depth) {
Line 8,082 ⟶ 8,081:
=={{header|Julia}}==
{{trans|Sidef}}
<syntaxhighlight lang="julia">module AVLTrees
import Base.print
Line 8,271 ⟶ 8,270:
=={{header|Kotlin}}==
{{trans|Java}}
<syntaxhighlight lang="kotlin">class AvlTree {
private var root: Node? = null
Line 8,455 ⟶ 8,454:
=={{header|Lua}}==
<syntaxhighlight lang=
AVL.__mt={__index = AVL}
Line 8,642 ⟶ 8,641:
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.
<syntaxhighlight lang=
http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx.
Line 8,910 ⟶ 8,909:
=={{header|Objeck}}==
{{trans|Java}}
<syntaxhighlight lang="objeck">class AVLNode {
@key : Int;
@balance : Int;
Line 9,204 ⟶ 9,203:
{{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=
@implementation AVLTree
Line 9,427 ⟶ 9,426:
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)
<!--<syntaxhighlight lang=
<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,570 ⟶ 9,569:
The function delete is missing.
<syntaxhighlight lang=
T = nil,
foreach (X in 1..10)
Line 9,660 ⟶ 9,659:
<p>The dictionary and array classes includes an AVL bag sort method - which is novel.</p>
<syntaxhighlight lang="python">
# Module: calculus.py
Line 11,467 ⟶ 11,466:
like the apostrophe (') and hyphen (-) in identifiers.
<br>
<syntaxhighlight lang=
class AVL-Tree {
has $.root is rw = 0;
Line 11,755 ⟶ 11,754:
=={{header|Scala}}==
<syntaxhighlight lang="scala">import scala.collection.mutable
class AVLTree[A](implicit val ordering: Ordering[A]) extends mutable.SortedSet[A] {
Line 12,091 ⟶ 12,090:
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)))
Line 13,038 ⟶ 13,037:
=={{header|Sidef}}==
{{trans|D}}
<syntaxhighlight lang="ruby">class AVLtree {
has root = nil
Line 13,219 ⟶ 13,218:
=={{header|Simula}}==
<syntaxhighlight lang="simula">CLASS AVL;
BEGIN
Line 13,420 ⟶ 13,419:
END.</syntaxhighlight>
A demonstration program:
<syntaxhighlight lang="simula">EXTERNAL CLASS AVL;
AVL
Line 13,471 ⟶ 13,470:
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}}
<syntaxhighlight lang="tcl">package require TclOO
namespace eval AVL {
Line 13,653 ⟶ 13,652:
}</syntaxhighlight>
Demonstrating:
<syntaxhighlight lang="tcl"># Create an AVL tree
AVL::Tree create tree
Line 13,784 ⟶ 13,783:
{{trans|Java}}
For use within a project, consider adding "export default" to AVLtree class declaration.
<syntaxhighlight lang=
class AVLnode <T> {
balance: number
Line 14,001 ⟶ 14,000:
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="ecmascript">class Node {
construct new(key, parent) {
_key = key
Line 14,199 ⟶ 14,198:
=={{header|Yabasic}}==
<syntaxhighlight lang=
// Ported to Yabasic by Galileo 2022/07
Line 14,363 ⟶ 14,362:
8 1 0
---Program done, press RETURN---</pre>
▲{{omit from|MiniZinc|type system is too inexpressive}}
| |||