Binary Search and AVL Trees

home1 home2
 Bib
 Algorithms
 Bioinfo
 FP
 Logic
 MML
 Prog.Lang
and the
 Book

Algorithms
 glossary
 Binary Trees
  Search T'
  23trees
  234trees
  Btrees
  Tries
  PATRICIA
  Suffix Trees

 Tables

Insert and delete data (strings) into a binary search tree (BST) and an AVL tree using the input area and the `insert' and `delete' buttons in the HTML FORM below (change the names to protect the innocent). Note that space, ` ', is a valid character.

input=[  ]
©
L
.
A
l
l
i
s
o
n

NB. You can insert numerals into the tree but they will be sorted lexicographically (e.g. `10 < 9'), not numerically, under the current (string) coding. This is easy to change.

NB. The roots of the trees are at the left-hand-side of the large TEXTAREA. The trees are shown with links, and also in infix order, after each insertion or deletion. Balance of AVL (sub-)tree(s) is indicated by `|' (balanced), `^' (right taller) and `v' (left taller).

AVL Tree

An AVL (height balanced) tree is shown beneath the ordinary binary search tree in the HTML FORM above. It undergoes exactly the same sequence of insertions and deletions as the simple BST. Note that the AVL tree remains much shorter than the BST when, for example, alphabetically ordered names {a, b, c, d, ...} are inserted.



© L.A. (HTML, JavaScript) 1999, School of Computer Science and S.W.E., Monash University, Australia.
Coding Ockham's Razor, L. Allison, Springer

A Practical Introduction to Denotational Semantics, L. Allison, CUP

Linux
 Ubuntu
free op. sys.
OpenOffice
free office suite
The GIMP
~ free photoshop
Firefox
web browser

© L. Allison   http://www.allisons.org/ll/   (or as otherwise indicated),
Faculty of Information Technology (Clayton), Monash University, Australia 3800 (6/'05 was School of Computer Science and Software Engineering, Fac. Info. Tech., Monash University,
was Department of Computer Science, Fac. Comp. & Info. Tech., '89 was Department of Computer Science, Fac. Sci., '68-'71 was Department of Information Science, Fac. Sci.)
Created with "vi (Linux + Solaris)",  charset=iso-8859-1,  fetched Saturday, 30-Mar-2024 02:05:01 AEDT.