Manipulate binary trees
Date/Time of Processing: Tuesday 24 May 1994 01:34:26Pm Overall Assessment of System: OK Classification of System: A Basis of Classification -- Syntax Errors PASS Completeness PASS Independence from External Libraries PASS Independence from a Specific Ada Compiler PASS Number of ... Files 2 Library Units 2 Lines 906 Statements 254 Comments 315
languages/ada/asr/new-abstractions/bintree: File Name Size --------- ---- bintree.zip 6,643 Totals ============== ============== 1 Files 6,643
This generic package is an efficient implementation of unbalanced binary trees. These trees have the following properties: 1) inserting a value is cheap (log n differences per insert) 2) finding a value is chap (log n differences per query) 3) can iterate over values in sorted order in linear time 4) moderate space overhead (2 pointers per value) Unbalanced binary trees are useful both for sorting sequences of indeterminate size and for lookup tables. The supplied operations are: Constructors: Insert Insert a node into a tree Insert_If_Not_Found Insert a node into a tree if not already there Replace_If_Found Replace a node if duplicate exists, else insert Destroy Destroy a tree Destroy_Deep Destroy a tree and its contents Balanced_Tree Create a balanced tree Copy Copy a tree Queries: Is_Empty Return TRUE if a tree is empty Find Search a tree for a node Is_Found Return TRUE if tree contains a specified value Size Return number of nodes in a tree Iterators: Visit Apply a procedure to every node Make_Iter Create an iterator More, Next Iteration functions NEW_ABSTRACTIONS is used by NOSC/WIS tools 4.1.1 and 4.1.2.
DATE VERSION AUTHOR HISTORY 03/85 1.0 Bill Toscano Initial Release
This prologue must be included in all copies of this software. This software is copyright by the author. This software is released to the Ada community. This software is released to the Public Domain (note: software released to the Public Domain is not subject to copyright protection). Restrictions on use or distribution: NONE
This software and its documentation are provided "AS IS" and without any expressed or implied warranties whatsoever. No warranties as to performance, merchantability, or fitness for a particular purpose exist. The user is advised to test the software thoroughly before relying on it. The user must assume the entire risk and liability of using this software. In no event shall any person or organization of people be held responsible for any direct, indirect, consequential or inconsequential damages or lost profits.